Selectivity estimation using orthogonal series

Selectivity estimation is an integral part of query optimization. In this paper, we propose a novel approach to approximate data density functions of relations and use them to estimate selectivities. A data density function here is approximated by a partial sum of an orthogonal series. Such approximate density functions can be derived easily, stored efficiently, and maintained dynamically. Experimental results show that our approach yields comparable or better estimation accuracy than the Wavelet and DCT methods, especially in the high dimensional spaces.