DBScholar

Back to papers

Balancing Histogram Optimality and Practicality for Query Result Size Estimation

Summary: Trade-off between histogram optimality and practicality for estimating query result sizes. Proposes a practical histogram class: preserve exact frequencies for a few values, assume uniformity for the rest, and pick per relation the self-join-optimal histogram; theory and experiments show strong accuracy and tractable construction. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
hb1fc2f8247c3dbc5
Venue
SIGMOD
Year
1995
Pagerank
0.00022214789
Overall Rank
283 | 98.10%
DOI
10.1145/223784.223841

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{ioannidis_sigmod95,
        title = {{Balancing Histogram Optimality and Practicality for Query Result Size Estimation}},
        author = {Ioannidis, Yannis E. and Poosala, Viswanath},
        series = {{SIGMOD} '95},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/223784.223841},
        url = {https://dl.acm.org/doi/10.1145/223784.223841},
        year = {1995}
}

Incoming Citations (Sorted by Pagerank)

Showing 49 of 49 citing papers.

Rank Citing Paper Year Venue Pagerank
37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00047731453
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033894985
149 Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans 1998 SIGMOD 0.00028981723
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00028633995
255 The History of Histograms (abridged) 2003 VLDB 0.00022981861
275 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00022413521
371 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00019829769
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019720059
428 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.0001845349
519 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016942879
742 Dynamic Multidimensional Histograms 2002 SIGMOD 0.0001431602
858 What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically 2003 PODS 0.000134266
967 Recovering Information from Summary Data 1997 VLDB 0.00012794553
972 The Data Civilizer System 2017 CIDR 0.00012763234
1,077 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012154948
1,163 Estimating Alphanumeric Selectivity in the Presence of Wildcards 1996 SIGMOD 0.00011750813
1,461 Substring Selectivity Estimation 1999 PODS 0.00010583833
1,587 Estimating Progress of Execution for SQL Queries 2004 SIGMOD 0.0001014156
1,687 Global Optimization of Histograms 2001 SIGMOD 9.8655879e-05
1,741 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 9.7382372e-05
2,303 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.6708797e-05
2,318 When Can We Trust Progress Estimators for SQL Queries? 2005 SIGMOD 8.6464837e-05
2,846 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.9453616e-05
3,163 REHIST: Relative Error Histogram Construction Algorithms 2004 VLDB 7.5789852e-05
3,613 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 7.162283e-05
3,644 Optimal Histograms for Hierarchical Range Queries (Extended Abstract) 2000 PODS 7.1399991e-05
3,967 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.8905715e-05
4,932 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.3483816e-05
5,021 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 6.3106761e-05
5,044 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.30014e-05
5,199 Exact Cardinality Query Optimization with Bounded Execution Cost 2019 SIGMOD 6.2327836e-05
5,534 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS 6.0923159e-05
6,168 Modeling skewed distributions using multifractals and the '80-20 law' 1996 VLDB 5.8627239e-05
6,189 VergeDB: A Database for IoT Analytics on Edge Devices 2021 CIDR 5.8568233e-05
6,694 MOST: Model-Based Compression with Outlier Storage for Time Series Data 2023 SIGMOD 5.7068014e-05
7,375 PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression 2024 VLDB 5.5400509e-05
7,493 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 5.5103311e-05
7,512 Compact Histograms for Hierarchical Identifiers 2006 VLDB 5.504973e-05
7,568 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS 5.49478e-05
7,633 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 5.4792473e-05
8,035 JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023 SIGMOD 5.4025473e-05
8,449 Efficient Top-K Processing Over Query-Dependent Functions 2008 VLDB 5.3350162e-05
8,856 Adaptive Index Structures 2002 VLDB 5.2635701e-05
9,142 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 5.220581e-05
9,387 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 5.1868213e-05
9,836 Hubble: An Advanced Dynamic Folder Technology for XML 2005 VLDB 5.123765e-05
10,388 Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond 2026 PODS 4.9793485e-05
11,290 Cardinality Estimation for Having-Clauses 2025 VLDB 4.9793485e-05
13,131 Searching on the Secondary Structure of Protein Sequences 2002 VLDB 4.9793485e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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.0023947656
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00047863192
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036487763
91 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.0003475226
119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.0003137356
232 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00023792809
346 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020329113
422 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.00018492336
806 Universality of Serial Histograms 1993 VLDB 0.00013792174
1,085 On B-tree Indices for Skewed Distributions 1992 VLDB 0.00012112632
1,641 A Model of Data Distribution Based on Texture Analysis 1985 SIGMOD 0.00010007832
6,047 Experience from a Real Life Query Optimizer 1992 SIGMOD 5.9049647e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,633 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB
2 119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD
3 1,687 Global Optimization of Histograms 2001 SIGMOD
4 7,568 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS
5 275 Optimal Histograms with Quality Guarantees 1998 VLDB
6 1,741 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB
7 242 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB
8 3,967 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB
9 37 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD
10 806 Universality of Serial Histograms 1993 VLDB