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
2253
Venue
SIGMOD
Year
1984
Pagerank
0.00080435857
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.00092385438
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051315959
116 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00046148737
118 Executing SQL over Encrypted Data in the Database-Service-Provider Model 2002 SIGMOD 0.00045685662
134 Processing Aggregate Relational Queries with Hard Time Constraints 1989 SIGMOD 0.00042452811
141 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00041786333
252 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00030632263
275 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00029364901
325 The History of Histograms (abridged) 2003 VLDB 0.00027378328
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00027358981
327 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00027308479
361 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB 0.00025775749
449 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00022846068
454 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022734812
501 Query Optimization for XML 1999 VLDB 0.00021530411
512 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00021380733
526 A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data 1997 VLDB 0.00021044221
530 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00020803682
688 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00018134733
696 BlazeIt: Optimizing Declarative Aggregation and Limit Queries for Neural Network-Based Video Analytics 2020 VLDB 0.00018048935
736 AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data 2020 VLDB 0.00017447617
762 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00017036868
790 Exploiting Statistics on Query Expressions for Optimization 2002 SIGMOD 0.0001663283
808 Universality of Serial Histograms 1993 VLDB 0.00016432772
897 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00015528028
1,120 Global Optimization of Histograms 2001 SIGMOD 0.00013856211
1,127 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00013819179
1,574 Approximate Query Processing: No Silver Bullet 2017 SIGMOD 0.00011287495
1,703 Are We Ready For Learned Cardinality Estimation? 2021 VLDB 0.00010836769
1,789 Reducing the Braking Distance of an SQL Query Engine 1998 VLDB 0.00010555087
1,797 Effective Use of Block-Level Sampling in Statistics Estimation 2004 SIGMOD 0.00010523169
2,010 StatiX: Making XML Count 2002 SIGMOD 9.7970026e-05
2,053 Selectivity Estimation in Spatial Databases 1999 SIGMOD 9.6728745e-05
2,356 Consistently Estimating the Selectivity of Conjuncts of Predicates 2005 VLDB 8.9620762e-05
2,455 Optimizing Boolean Expressions in Object Bases 1992 VLDB 8.7770449e-05
2,995 A Sampling Algebra for Aggregate Estimation 2013 VLDB 7.7587199e-05
3,053 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.64969e-05
3,310 Optimal and Approximate Computation of Summary Statistics for Range Aggregates 2001 PODS 7.2408955e-05
3,561 Estimating Block Accesses When Attributes Are Correlated 1986 VLDB 6.971123e-05
3,651 Conditional Selectivity for Statistics on Query Expressions 2004 SIGMOD 6.8768678e-05
3,665 Ad-hoc Top-k Query Answering for Data Streams 2007 VLDB 6.8633354e-05
3,798 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 6.7592302e-05
3,893 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.6584217e-05
3,966 Random Sampling from Pseudo-Ranked B+ Trees 1992 VLDB 6.580483e-05
4,277 A Blackboard Architecture for Query Optimization in Object Bases 1993 VLDB 6.2959161e-05
4,711 Answering Top-k Queries with Multi-Dimensional Selections: The Ranking Cube Approach 2006 VLDB 5.9790683e-05
4,712 Accelerating Approximate Aggregation Queries with Expensive Predicates 2021 VLDB 5.9787986e-05
4,933 A Cost Model for Clustered Object-Oriented Databases 1995 VLDB 5.8205625e-05
5,082 A Comparison of Selectivity Estimators for Range Queries on Metric Attributes 1999 SIGMOD 5.711623e-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.0040449103
228 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.00032269684
615 Top-down statistical estimation on a database 1983 SIGMOD 0.00019128024
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
326 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00027358981
7,150 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS 4.8163484e-05
3,702 Every Row Counts: Combining Sketches and Sampling for Accurate Group-By Result Estimates 2019 CIDR 6.8295759e-05
808 Universality of Serial Histograms 1993 VLDB 0.00016432772
269 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029656549
327 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00027308479
361 Histogram-Based Approximation of Set-Valued Query Answers 1999 VLDB 0.00025775749
996 Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes 2000 SIGMOD 0.00014741524
315 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.0002802103
39 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00074745564