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.00022143946
Overall Rank
285 | 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.00047654188
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033847446
149 Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans 1998 SIGMOD 0.00028910892
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.0002855087
254 The History of Histograms (abridged) 2003 VLDB 0.00022999992
277 Optimal Histograms with Quality Guarantees 1998 VLDB 0.0002235043
372 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00019768921
374 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.00019698889
432 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00018400309
518 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016918797
745 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00014267268
860 What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically 2003 PODS 0.00013382689
971 Recovering Information from Summary Data 1997 VLDB 0.00012748313
972 The Data Civilizer System 2017 CIDR 0.00012742827
1,080 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012114187
1,164 Estimating Alphanumeric Selectivity in the Presence of Wildcards 1996 SIGMOD 0.0001170903
1,466 Substring Selectivity Estimation 1999 PODS 0.00010546176
1,587 Estimating Progress of Execution for SQL Queries 2004 SIGMOD 0.00010119368
1,693 Global Optimization of Histograms 2001 SIGMOD 9.8377504e-05
1,754 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 9.7111856e-05
2,310 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.6493038e-05
2,329 When Can We Trust Progress Estimators for SQL Queries? 2005 SIGMOD 8.6188984e-05
2,852 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.9201312e-05
3,168 REHIST: Relative Error Histogram Construction Algorithms 2004 VLDB 7.5583423e-05
3,611 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 7.1443694e-05
3,653 Optimal Histograms for Hierarchical Range Queries (Extended Abstract) 2000 PODS 7.1149642e-05
3,977 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.8707656e-05
4,962 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.3244317e-05
5,049 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 6.287033e-05
5,056 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.282339e-05
5,223 Exact Cardinality Query Optimization with Bounded Execution Cost 2019 SIGMOD 6.210331e-05
5,552 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS 6.0707348e-05
6,183 Modeling skewed distributions using multifractals and the '80-20 law' 1996 VLDB 5.8417594e-05
6,202 VergeDB: A Database for IoT Analytics on Edge Devices 2021 CIDR 5.8347611e-05
6,712 MOST: Model-Based Compression with Outlier Storage for Time Series Data 2023 SIGMOD 5.6852386e-05
7,365 PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression 2024 VLDB 5.5273291e-05
7,512 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 5.490671e-05
7,536 Compact Histograms for Hierarchical Identifiers 2006 VLDB 5.4844135e-05
7,584 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS 5.4749539e-05
7,654 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 5.4588598e-05
8,060 JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023 SIGMOD 5.382134e-05
8,473 Efficient Top-K Processing Over Query-Dependent Functions 2008 VLDB 5.3148581e-05
8,883 Adaptive Index Structures 2002 VLDB 5.2436823e-05
9,173 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 5.2011875e-05
9,422 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 5.1672232e-05
9,879 Hubble: An Advanced Dynamic Folder Technology for XML 2005 VLDB 5.1044181e-05
10,466 Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond 2026 PODS 4.9605343e-05
11,353 Cardinality Estimation for Having-Clauses 2025 VLDB 4.9605343e-05
13,178 Searching on the Secondary Structure of Protein Sequences 2002 VLDB 4.9605343e-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.0023948467
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00047770864
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036394222
91 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00034691614
119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00031291457
234 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00023726296
346 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020265363
425 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.00018437618
806 Universality of Serial Histograms 1993 VLDB 0.00013752086
1,086 On B-tree Indices for Skewed Distributions 1992 VLDB 0.00012069306
1,648 A Model of Data Distribution Based on Texture Analysis 1985 SIGMOD 9.9739132e-05
6,060 Experience from a Real Life Query Optimizer 1992 SIGMOD 5.8831987e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,654 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB
2 1,693 Global Optimization of Histograms 2001 SIGMOD
3 119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD
4 7,584 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS
5 277 Optimal Histograms with Quality Guarantees 1998 VLDB
6 1,754 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,977 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