Database Paper Browser

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
2254
Venue
SIGMOD
Year
1984
Pagerank
0.00080571183
Overall Rank
28 | 99.81%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 64 citing papers.

Rank Citing Paper Year Venue Pagerank
18 On Random Sampling over Joins 1999 SIGMOD 0.00092569117
63 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063595699
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051431888
114 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00046317654
119 Executing SQL over Encrypted Data in the Database-Service-Provider Model 2002 SIGMOD 0.00045724707
133 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00043220055
141 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00041819767
250 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00030640525
274 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00029383266
325 The History of Histograms (abridged) 2003 VLDB 0.00027398081
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.0002737538
328 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00027301497
360 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB 0.00025768448
430 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00023406426
454 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022796106
504 Query Optimization for XML 1999 VLDB 0.00021513261
512 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00021385343
526 A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data 1997 VLDB 0.00021046587
531 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.0002079072
694 BlazeIt: Optimizing Declarative Aggregation and Limit Queries for Neural Network-Based Video Analytics 2020 VLDB 0.00018031141
730 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00017443615
751 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00017155121
786 Exploiting Statistics on Query Expressions for Optimization 2002 SIGMOD 0.00016624743
801 Universality of Serial Histograms 1993 VLDB 0.00016440976
896 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00015486851
897 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00015484372
1,116 Global Optimization of Histograms 2001 SIGMOD 0.00013863484
1,126 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.0001381102
1,574 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00011289028
1,699 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00010848882
1,780 Reducing the Braking Distance of an SQL Query Engine 1998 VLDB 0.00010558417
1,790 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 0.00010529479
2,016 StatiX: Making XML Count 2002 SIGMOD 9.7892568e-05
2,056 Selectivity Estimation in Spatial Databases 1999 SIGMOD 9.6692561e-05
2,359 Consistently Estimating the Selectivity of Conjuncts of Predicates 2005 VLDB 8.967267e-05
2,455 Optimizing Boolean Expressions in Object Bases 1992 VLDB 8.7667904e-05
2,995 A Sampling Algebra for Aggregate Estimation 2013 VLDB 7.7606324e-05
3,056 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.6459653e-05
3,292 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.2598265e-05
3,564 Estimating Block Accesses When Attributes Are Correlated 1986 VLDB 6.9655849e-05
3,656 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD 6.8712579e-05
3,665 Ad-hoc Top-k Query Answering for Data Streams 2007 VLDB 6.8631567e-05
3,801 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 6.7528979e-05
3,896 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.6526869e-05
3,965 Random Sampling from Pseudo-Ranked B+ Trees 1992 VLDB 6.5786424e-05
4,274 A Blackboard Architecture for Query Optimization in Object Bases 1993 VLDB 6.290327e-05
4,703 Accelerating Approximate Aggregation Queries with Expensive Predicates 2021 VLDB 5.9793615e-05
4,718 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 5.9664602e-05
4,944 A Cost Model for Clustered Object-Oriented Databases 1995 VLDB 5.8120276e-05
5,066 A Comparison of Selectivity Estimators for Range Queries on Metric Attributes 1999 SIGMOD 5.7157182e-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.0040465394
226 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.0003243274
613 Top-down statistical estimation on a database 1983 SIGMOD 0.00019104493
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.0002737538
7,150 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS 4.8128138e-05
3,706 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 6.8232992e-05
801 Universality of Serial Histograms 1993 VLDB 0.00016440976
270 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029648047
328 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00027301497
360 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB 0.00025768448
995 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD 0.00014745185
291 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00028778973
37 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00075597514