DBScholar

Back to papers

Accurate Estimation Of The Number Of Tuples Satisfying A Condition

Summary: Introduces distribution steps: histograms with equal-height buckets to bound selectivity error for predicates rel op constant. Increasing steps lowers error; derives worst-case and average-case estimation formulas, plus fast sampling-based construction; targets query optimization and statistical queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
2315
Venue
SIGMOD
Year
1984
Pagerank
0.00048351457
Overall Rank
36 | 99.76%
DOI
10.1145/602259.602294

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{piatetskyshapiro_sigmod84,
        title = {{ACCURATE ESTIMATION OF THE NUMBER OF TUPLES SATISFYING A CONDITION}},
        author = {Piatetsky-Shapiro, Gregory and Connell, Charles},
        series = {{SIGMOD} '84},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/602259.602294},
        url = {https://dl.acm.org/doi/10.1145/602259.602294},
        year = {1984}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 64 citing papers.

Rank Citing Paper Year Venue Pagerank
35 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00048481081
54 On Random Sampling over Joins 1999 SIGMOD 0.00040810225
76 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00037054261
101 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00034376651
114 Executing SQL over Encrypted Data in the Database-Service-Provider Model 2002 SIGMOD 0.00032363776
118 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00031922279
178 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00026881845
222 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00024193708
257 The History of Histograms (abridged) 2003 VLDB 0.00023154793
261 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00023097188
267 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00022798161
274 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00022645621
290 An Overview of Query Optimization in Relational Systems 1998 PODS 0.0002227038
363 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0002005475
365 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00020041735
406 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00019054532
435 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB 0.000185063
470 Query Optimization for XML 1999 VLDB 0.00017965707
508 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00017275873
569 BlazeIt: Optimizing Declarative Aggregation and Limit Queries for Neural Network-Based Video Analytics 2020 VLDB 0.00016348191
664 Exploiting Statistics on Query Expressions for Optimization 2002 SIGMOD 0.00015167825
783 A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data 1997 VLDB 0.00014076306
786 Universality of Serial Histograms 1993 VLDB 0.00014053885
934 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00013108714
977 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012864017
992 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00012790174
1,061 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00012369764
1,108 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00012145154
1,382 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00010965236
1,544 Reducing the Braking Distance of an SQL Query Engine 1998 VLDB 0.00010410466
1,668 Global Optimization of Histograms 2001 SIGMOD 0.00010057026
1,806 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 9.7112151e-05
1,900 StatiX: Making XML Count 2002 SIGMOD 9.5168326e-05
1,936 Consistently Estimating the Selectivity of Conjuncts of Predicates 2005 VLDB 9.4557372e-05
2,127 Selectivity Estimation in Spatial Databases 1999 SIGMOD 9.127762e-05
2,413 A Sampling Algebra for Aggregate Estimation 2013 VLDB 8.6116764e-05
2,923 Optimizing Boolean Expressions in Object Bases 1992 VLDB 7.9578414e-05
2,984 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.8920597e-05
3,241 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.6057671e-05
3,309 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD 7.5368417e-05
3,317 Ad-hoc Top-k Query Answering for Data Streams 2007 VLDB 7.5251856e-05
3,595 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 7.2736195e-05
3,684 ThalamusDB: Approximate Query Processing on Multi-Modal Data 2024 SIGMOD 7.2033959e-05
3,893 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 7.04191e-05
3,907 Accelerating Approximate Aggregation Queries with Expensive Predicates 2021 VLDB 7.0278233e-05
3,996 Estimating Block Accesses When Attributes Are Correlated 1986 VLDB 6.9682171e-05
4,413 A Blackboard Architecture for Query Optimization in Object Bases 1993 VLDB 6.7168289e-05
4,458 Random Sampling from Pseudo-Ranked B+ Trees 1992 VLDB 6.6905953e-05
4,587 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 6.6170389e-05
4,846 A Comparison of Selectivity Estimators for Range Queries on Metric Attributes 1999 SIGMOD 6.4807645e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 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
417 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.00018819871
1,405 Top-down statistical estimation on a database 1983 SIGMOD 0.00010875661
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 267 Optimal Histograms with Quality Guarantees 1998 VLDB
2 7,443 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS
3 3,215 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR
4 786 Universality of Serial Histograms 1993 VLDB
5 235 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB
6 274 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD
7 435 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB
8 850 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD
9 484 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD
10 55 Statistical Estimators for Relational Algebra Expressions 1988 PODS