Sequential sampling procedures for query size estimation
Peter J. Haas, A. Swami · Proceedings - ACM-SIGMOD International Conference on Management of Data · 1992
We provide a procedure, based on random sampling, for estimation of the size of a query result. The procedure is sequential in that sampling terminates after a random number of steps according to a stopping rule that depends upon the observations obtained so far. Enough observations are obtained so that, with a pre-specified probability, the estimate differs from the true size of the query result by no more than a prespecified amount. Unlike previous sequential estimation procedures for queries, our procedure is asymptotically efficient and requires no ad hoc pilot sample or a a priori assumptions about data characteristics. In addition to establishing the asymptotic properties of the estimation procedure, we provide techniques for reducing undercoverage at small sample sizes and show that the sampling cost of the procedure can be reduced through stratified sampling techniques.
Cited by 173 works. doi:10.1145/130283.130335
Authors
References
- The Art of Computer Programming: Volume 3: Sorting and Searching
- The Art of Computer Programming, Volume 3, Sorting and Searching
- Query Optimization in Database Systems
- Practical selectivity estimation through adaptive sampling
- Sequential Analysis, Tests and Confidence Intervals
- On the Asymptotic Theory of Fixed-Width Sequential Confidence Intervals for the Mean
- Statistical estimators for relational algebra expressions
- Statistical profile estimation in database systems
- Sequential Analysis
- Processing aggregate relational queries with hard time constraints