DBScholar

Back to papers

Sequential Sampling Procedures For Query Size Estimation

Summary: Sequential sampling for estimating query result cardinality with a data-dependent stopping rule. Asymptotically efficient, it needs no pilot sample or prior data, offers finite-sample undercoverage control, and lowers cost via stratified sampling. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h9cfddfe9aeed7f64
Venue
SIGMOD
Year
1992
Pagerank
0.00020265363
Overall Rank
346 | 97.69%
DOI
10.1145/130283.130335

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{haas_sigmod92,
        title = {{SEQUENTIAL SAMPLING PROCEDURES FOR QUERY SIZE ESTIMATION}},
        author = {Haas, Peter J. and Swami, Arun N.},
        series = {{SIGMOD} '92},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/130283.130335},
        url = {https://dl.acm.org/doi/10.1145/130283.130335},
        year = {1992}
}

Incoming Citations (Sorted by Pagerank)

Showing 39 of 39 citing papers.

Rank Citing Paper Year Venue Pagerank
234 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00023726296
277 Optimal Histograms with Quality Guarantees 1998 VLDB 0.0002235043
285 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00022143946
477 Sampling Large Databases for Association Rules 1996 VLDB 0.00017624579
518 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016918797
568 Towards a Robust Query Optimizer: A Principled and Practical Approach 2005 SIGMOD 0.00016221103
745 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00014267268
750 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014246313
1,164 Estimating Alphanumeric Selectivity in the Presence of Wildcards 1996 SIGMOD 0.0001170903
1,174 Wavelet Synopses with Error Guarantees 2002 SIGMOD 0.0001165008
1,187 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD 0.00011580993
1,206 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00011510881
1,469 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00010533259
1,569 Reducing the Braking Distance of an SQL Query Engine 1998 VLDB 0.00010177494
1,609 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2019 SIGMOD 0.0001007196
1,647 Combinatorial Pattern Discovery for Scientific Data: Some Preliminary Results 1994 SIGMOD 9.9747449e-05
1,803 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2018 VLDB 9.5987229e-05
1,828 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 9.5396315e-05
1,896 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4010932e-05
1,901 Generating Targeted Queries for Database Testing 2008 SIGMOD 9.3902763e-05
2,224 Managing Memory to Meet Multiclass Workload Response Time Goals 1993 VLDB 8.8023428e-05
2,310 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.6493038e-05
2,438 Cardinality Estimation Using Sample Views with Quality Assurance 2007 SIGMOD 8.4532693e-05
3,291 Kernel-Based Skyline Cardinality Estimation 2009 SIGMOD 7.4370263e-05
4,290 One-Pass Wavelet Synopses for Maximum-Error Metrics 2005 VLDB 6.6675308e-05
4,438 Deterministic Wavelet Thresholding for Maximum-Error Metrics 2004 PODS 6.5840202e-05
4,692 The Power of Sampling in Knowledge Discovery 1994 PODS 6.4492362e-05
5,056 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.282339e-05
5,153 Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach 2020 SIGMOD 6.2375324e-05
5,712 Approximate Quantiles and the Order of the Stream 2006 PODS 6.0096683e-05
7,175 Learning to Sample: Counting with Complex Queries 2020 VLDB 5.5779755e-05
7,512 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 5.490671e-05
7,542 Comparing Synopsis Techniques for Approximate Spatial Data Analysis 2019 VLDB 5.4821664e-05
8,363 alpha to omega: The Greek Alphabet of Sampling 2020 CIDR 5.3305234e-05
8,883 Adaptive Index Structures 2002 VLDB 5.2436823e-05
9,859 Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects 2010 SIGMOD 5.1064323e-05
9,892 Analysis and Application of Adaptive Sampling 2000 PODS 5.1009009e-05
11,159 Perfect Sampling in Turnstile Streams Beyond Small Moments 2025 PODS 4.9605343e-05
11,878 Truly Perfect Samplers for Data Streams and Sliding Windows 2022 PODS 4.9605343e-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.00039922419
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036394222
183 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026316699
480 Random Sampling from B+ trees 1989 VLDB 0.00017573936
492 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017359343
1,012 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00012489386
1,423 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010696781
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 58 Statistical Estimators for Relational Algebra Expressions 1988 PODS
2 2,544 Applying the Golden Rule of Sampling for Query Estimation 2001 SIGMOD
3 1,896 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD
4 153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD
5 1,681 Two-Level Sampling for Join Size Estimation 2017 SIGMOD
6 9,892 Analysis and Application of Adaptive Sampling 2000 PODS
7 175 Simple Random Sampling from Relational Databases 1986 VLDB
8 1,187 An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment 1993 SIGMOD
9 1,012 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS
10 79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD