DBScholar

Back to papers

An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment

Summary: Regression-based size estimation for equi-joins and selections using an approximating series derived from data distribution and dependencies. Instant evaluation with negligible CPU and no runtime space or page-fault overhead; accuracy is on par with sampling-based estimators, making it ideal for retrieval-intensive workloads and periodic updates. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
he68fe70788ce271c
Venue
SIGMOD
Year
1993
Pagerank
0.00011611937
Overall Rank
1,184 | 92.05%
DOI
10.1145/170035.170055

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{sun_sigmod93,
        title = {{An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment}},
        author = {Sun, Wei and Ling, Yibei and Rishe, Naphtali and Deng, Yi},
        series = {{SIGMOD} '93},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/170035.170055},
        url = {https://dl.acm.org/doi/10.1145/170035.170055},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank Citing Paper Year Venue Pagerank
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047731453
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033894985
232 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00023792809
255 The History of Histograms (abridged) 2003 VLDB 0.00022981861
1,077 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012154948
1,741 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 9.7382372e-05
2,303 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.6708797e-05
2,974 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.7938744e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank Cited Paper Year Venue Pagerank
1 Access Path Selection in a Relational Database Management System 1979 SIGMOD 0.0023947656
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
422 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.00018492336
492 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017408001
956 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00012865801
1,185 An Analytic Approach to Statistical Databases 1983 VLDB 0.0001161182
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 428 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS
2 3,005 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS
3 1,203 Fixed-Precision Estimation of Join Selectivity 1993 PODS
4 346 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD
5 750 Join Size Estimation Subject to Filter Conditions 2015 VLDB
6 11,951 Index-Based Join Size Estimation Using Adaptive Sampling 2021 SIGMOD
7 3,992 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS
8 1,011 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS
9 1,678 Two-Level Sampling for Join Size Estimation 2017 SIGMOD
10 79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD