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
had4f60a2dc564289
Venue
PODS
Year
1993
Pagerank
0.00011548537
Overall Rank
1,203 | 91.92%
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
428 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.0001845349
742 Dynamic Multidimensional Histograms 2002 SIGMOD 0.0001431602
745 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014288286
750 Join Size Estimation Subject to Filter Conditions 2015 VLDB 0.00014265196
870 Spectral Bloom Filters 2003 SIGMOD 0.0001334417
1,467 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00010567959
1,542 Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses 2018 VLDB 0.00010308631
1,890 Generating Targeted Queries for Database Testing 2008 SIGMOD 9.4193315e-05
1,891 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4184294e-05
2,677 Relational Confidence Bounds Are Easy With The Bootstrap* 2005 SIGMOD 8.1461074e-05
4,958 Similarity Join Size Estimation using Locality Sensitive Hashing 2011 VLDB 6.3394776e-05
8,035 JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023 SIGMOD 5.4025473e-05
8,325 Containment Join Size Estimation: Models and Methods 2003 SIGMOD 5.3540828e-05
8,347 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR 5.350539e-05
9,429 Efficiently Joining Large Relations on Multi-GPU Systems 2025 VLDB 5.1786456e-05
12,853 Stretch 'n' Shrink: Resizing Queries to User Preferences 2008 SIGMOD 4.9793485e-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
58 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00040035279
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036487763
181 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026389403
346 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020329113
492 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017408001
1,011 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00012529816
1,416 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010734049
Previous Page 1 / 1 Next

Semantically Similar Papers

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