Query selectivity estimation based on Hough transform and PCA method

Dariusz R Augustyn, Daniel Kostrzewa

Abstract


Query selectivity estimation is an important element of obtaining optimal query execution plan. Selectivity estimation requires a nonparametric estimator of attribute values distribution – commonly a histogram. Using a multidimensional histogram as a representation of a joint multidimensional distribution of attributes values is not space-efficient. The paper introduces a new space-efficient method called HPCA, where a 2-dimesional distribution may be represented by a set of 1-dimensional histograms. HPCA is based on Hough transform and principal component analysis method. Using HPCA commonly gives more accurate selectivity estimation than standard methods based on a 2-dimensional histogram.

Keywords


query optimization; selectivity estimation; histograms; Hough transform; dimensionality reduction; PCA

Full Text:

PDF (Polski)


DOI: http://dx.doi.org/10.21936/si2012_v33.n2A.143