Practical selectivity estimation through adaptive sampling
- 1 May 1990
- proceedings article
- Published by Association for Computing Machinery (ACM)
- Vol. 19 (2), 1-11
- https://doi.org/10.1145/93597.93611
Abstract
Recently we have proposed an adaptive, random sampling algorithm for general querysize estimation. In earlier work we analyzed the asymptotic efficiency and accuracy of thealgorithm; in this paper we investigate its practicality as applied to selects and joins. First,we extend our previous analysis to provide significantly improved bounds on the amount ofsampling necessary for a given level of accuracy. Next, we provide "sanity bounds" to dealwith queries for which the underlying data is...Keywords
This publication has 12 references indexed in Scilit:
- Query size estimation by adaptive sampling (extended abstract)Published by Association for Computing Machinery (ACM) ,1990
- Statistical profile estimation in database systemsACM Computing Surveys, 1988
- Statistical estimators for relational algebra expressionsPublished by Association for Computing Machinery (ACM) ,1988
- Equi-depth multidimensional histogramsPublished by Association for Computing Machinery (ACM) ,1988
- A model of data distribution based on texture analysisPublished by Association for Computing Machinery (ACM) ,1985
- Accurate estimation of the number of tuples satisfying a conditionPublished by Association for Computing Machinery (ACM) ,1984
- Database evaluation using multiple regression techniquesPublished by Association for Computing Machinery (ACM) ,1984
- Estimating block transfers and join sizesPublished by Association for Computing Machinery (ACM) ,1983
- Query optimization in star computer networksACM Transactions on Database Systems, 1982
- Access path selection in a relational database management systemPublished by Association for Computing Machinery (ACM) ,1979