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
2690
Venue
SIGMOD
Year
1993
Pagerank
0.00011825923
Overall Rank
1,172 | 91.97%
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
35 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00048481081
101 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00034376651
222 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00024193708
257 The History of Histograms (abridged) 2003 VLDB 0.00023154793
1,053 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012401532
1,729 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 9.908788e-05
2,281 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.8129279e-05
3,070 Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs 2022 VLDB 7.7900444e-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.0024089429
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
417 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.00018819871
484 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017746696
934 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00013108714
1,183 An Analytic Approach to Statistical Databases 1983 VLDB 0.00011778053
Previous Page 1 / 1 Next

Semantically Similar Papers

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