Sampling-based selectivity estimation for joins using augmented frequent value statistics
Peter J. Haas, A. Swami · Proceedings - International Conference on Data Engineering · 2002
We compare empirically the cost of estimating the selectivity of a star join using the sampling-based t-cross procedure to the cost of computing the join and obtaining the exact answer. The relative cost of sampling can be excessive when a join attribute value exhibits "heterogeneous skew." To alleviate this problem, we propose Algorithm TCM, a modified version of t-cross that incorporates "augmented frequent value" (AFV) statistics. We provide a sampling-based method for estimating AFV statistics that does not require indexes on attribute values, requires only one pass though each relation, and uses an amount of memory much smaller than the size of a relation. Our experiments show that the use of estimated AFV statistics can reduce the relative cost of sampling by orders of magnitude. We also show that use of estimated AFV statistics can reduce the relative error of the classical System R selectivity formula.>
Cited by 44 works. doi:10.1109/icde.1995.380361
Authors
References
- An introduction to probability theory and its applications
- Access path selection in a relational database management system
- The Art of Computer Programming, Vol. 3: Sorting and Searching
- An Introduction to Probability Theory and its Applications
- Selectivity and Cost Estimation for Joins Based on Random Sampling
- Optimal histograms for limiting worst-case error propagation in the size of join results
- Why decision support fails and how to fix it
- Error-constrained COUNT query evaluation in relational databases
- Efficient sampling strategies for relational database operations
- On the relative cost of sampling for join selectivity estimation