DBScholar

Back to papers

Fixed-Precision Estimation of Join Selectivity

Summary: Establishes a partial ordering of variability among sampling-based equijoin-selectivity estimators for any fixed sample budget. Presents a general method to convert fixed-step estimators into asymptotically efficient fixed-precision procedures, derives cost orderings, and gives a top index-free algorithm. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
998
Venue
PODS
Year
1993
Pagerank
0.00011764128
Overall Rank
1,186 | 91.87%
DOI
10.1145/153850.153875

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{haas_pods93,
        address = {New York, NY, USA},
        series = {{PODS} '93},
        title = {{Fixed-Precision Estimation of Join Selectivity}},
        url = {https://dl.acm.org/doi/10.1145/153850.153875},
        doi = {10.1145/153850.153875},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Haas, Peter J. and Naughton, Jeffrey F. and Seshadri, S. and Swami, Arun N.},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank Citing Paper Year Venue Pagerank
418 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00018812821
723 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00014620977
730 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014539362
737 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00014490983
862 Spectral Bloom Filters 2003 SIGMOD 0.00013532857
1,440 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00010778889
1,536 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 0.00010460864
1,893 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.5269935e-05
2,069 Generating Targeted Queries for Database Testing 2008 SIGMOD 9.2293717e-05
2,633 Relational Confidence Bounds Are Easy With The Bootstrap* 2005 SIGMOD 8.3224527e-05
4,857 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 6.4752373e-05
8,155 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 5.4766319e-05
8,183 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR 5.4714466e-05
9,027 JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023 SIGMOD 5.3293224e-05
9,333 Efficiently Joining Large Relations on Multi-GPU Systems 2025 VLDB 5.2887551e-05
12,563 Stretch 'n' Shrink: Resizing Queries to User Preferences 2008 SIGMOD 5.093636e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
55 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00040746149
76 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00037054261
178 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026881845
339 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020723773
484 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017746696
992 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00012790174
1,382 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010965236
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 54 On Random Sampling over Joins 1999 SIGMOD
2 694 Cardinality Estimation Done Right: Index-Based Join Sampling 2017 CIDR
3 737 Join Size Estimation Subject to Filter Conditions 2015 VLDB
4 1,536 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB
5 280 Selectivity Estimation using Probabilistic Models 2001 SIGMOD
6 11,644 Index-Based Join Size Estimation Using Adaptive Sampling 2021 SIGMOD
7 1,172 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD
8 1,664 Two-Level Sampling for Join Size Estimation 2017 SIGMOD
9 1,440 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS
10 76 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD