TY - GEN
T1 - GPU-Accelerated Method of Query Selectivity Estimation for Non Equi-Join Conditions Based on Discrete Fourier Transform
AU - Augustyn, Dariusz Rafal
AU - Warchal, Lukasz
PY - 2015
Y1 - 2015
N2 - Selectivity factor is obtained by database query optimizer for estimating the size of data that satisfy a query condition. This allows to choose the optimal query execution plan. In this paper we consider the problem of selectivity estimation for inequality predicates based on two attributes, therefore the proposed solution allows to estimate the size of data that satisfy theta-join conditions. The proposed method is based on Discrete Fourier Transform and convolution theorem. DFT spectrums are used as representations of distribution of attribute values. We compute selectivity either performing Inverse DFT (for an inequality condition based on two attributes) or avoiding it (for a single-attribute range one). Selectivity calculation is a time-critical operation performed during an on-line query preparing phase. We show that by applying parallel processing capabilities of Graphical Processing Unit, the implementation of the method satisfies the assumed time constraint.
AB - Selectivity factor is obtained by database query optimizer for estimating the size of data that satisfy a query condition. This allows to choose the optimal query execution plan. In this paper we consider the problem of selectivity estimation for inequality predicates based on two attributes, therefore the proposed solution allows to estimate the size of data that satisfy theta-join conditions. The proposed method is based on Discrete Fourier Transform and convolution theorem. DFT spectrums are used as representations of distribution of attribute values. We compute selectivity either performing Inverse DFT (for an inequality condition based on two attributes) or avoiding it (for a single-attribute range one). Selectivity calculation is a time-critical operation performed during an on-line query preparing phase. We show that by applying parallel processing capabilities of Graphical Processing Unit, the implementation of the method satisfies the assumed time constraint.
KW - CUDA
KW - Discrete Fourier Transform
KW - Query Selectivity Estimation
KW - Theta-Join Condition
UR - https://www.scopus.com/pages/publications/84906675436
U2 - 10.1007/978-3-319-10518-5_17
DO - 10.1007/978-3-319-10518-5_17
M3 - Conference contribution
AN - SCOPUS:84906675436
SN - 9783319105178
T3 - Advances in Intelligent Systems and Computing
SP - 215
EP - 227
BT - New Trends in Database and Inf. Systems II - Selected Papers of the 18th East European Conference on Advances in Databases and Information Systems and Associated Satellite Events, ADBIS 2014, Proc. II
PB - Springer Verlag
T2 - 18th East European Conference on Advances in Databases and Information Systems and Associated Satellite Events, ADBIS 2014
Y2 - 7 September 2014 through 10 September 2014
ER -