Practical selectivity estimation through adaptive sampling
Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider · Proceedings - ACM-SIGMOD International Conference on Management of Data · 1990
Recently we have proposed an adaptive, random sampling algorithm for general query size estimation. In earlier work we analyzed the asymptotic efficiency and accuracy of the algorithm, 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 of sampling necessary for a given level of accuracy. Next, we provide “sanity bounds” to deal with queries for which the underlying data is extremely skewed or the query result is very small. Finally, we report on the performance of the estimation algorithm as implemented in a host language on a commercial relational system. The results are encouraging, even with this loose coupling between the estimation algorithm and the DBMS.
Cited by 272 works. doi:10.1145/93597.93611 Open-access PDF
Authors
References
- Access path selection in a relational database management system
- Benchmarking Database Systems A Systematic Approach
- Accurate estimation of the number of tuples satisfying a condition
- Practical selectivity estimation through adaptive sampling
- Statistical estimators for relational algebra expressions
- Equi-depth multidimensional histograms
- Statistical profile estimation in database systems
- Simple Random Sampling from Relational Databases
- Processing aggregate relational queries with hard time constraints
- Random sampling from B + trees