Selectivity estimation of range queries based on data density approximation via cosine series

摘要

Selectivity estimation is an integral part of query optimization. In this paper, we propose to approximate data density functions of relations by cosine series and use the approximations to estimate selectivities of range queries. We lay down the foundation for applying cosine series to range query size estimation and compare it with some notable approaches, such as the wavelets, DCT, kernel-spline, sketch, and Legendre polynomials. Experimental results have shown that our approach is simple to construct, easy to update, and fast to estimate. It also yields accurate estimates, especially in multi-dimensional cases.