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.00022205848
Overall Rank
284 | 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.0004772731
103 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00033884854
149 Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans 1998 SIGMOD 0.00028977821
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00028621958
255 The History of Histograms (abridged) 2003 VLDB 0.00022974524
275 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00022404363
371 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00019822444
372 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0001971778
429 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00018445263
518 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00016938992
743 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00014309723
858 What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically 2003 PODS 0.00013420431
969 Recovering Information from Summary Data 1997 VLDB 0.00012788914
972 The Data Civilizer System 2017 CIDR 0.00012757732
1,078 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012149796
1,163 Estimating Alphanumeric Selectivity in the Presence of Wildcards 1996 SIGMOD 0.0001174542
1,462 Substring Selectivity Estimation 1999 PODS 0.00010578962
1,588 Estimating Progress of Execution for SQL Queries 2004 SIGMOD 0.00010137374
1,687 Global Optimization of Histograms 2001 SIGMOD 9.8614576e-05
1,743 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 9.7342409e-05
2,303 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.6685874e-05
2,320 When Can We Trust Progress Estimators for SQL Queries? 2005 SIGMOD 8.6429103e-05
2,844 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.9446987e-05
3,164 REHIST: Relative Error Histogram Construction Algorithms 2004 VLDB 7.5756378e-05
3,607 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 7.1645803e-05
3,646 Optimal Histograms for Hierarchical Range Queries (Extended Abstract) 2000 PODS 7.1368554e-05
3,969 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 6.8874168e-05
4,933 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.3454089e-05
5,025 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 6.3078009e-05
5,047 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.2972183e-05
5,200 Exact Cardinality Query Optimization with Bounded Execution Cost 2019 SIGMOD 6.2303304e-05
5,535 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS 6.0905677e-05
6,169 Modeling skewed distributions using multifractals and the '80-20 law' 1996 VLDB 5.8600493e-05
6,192 VergeDB: A Database for IoT Analytics on Edge Devices 2021 CIDR 5.8540507e-05
6,698 MOST: Model-Based Compression with Outlier Storage for Time Series Data 2023 SIGMOD 5.7040999e-05
7,363 PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression 2024 VLDB 5.5404386e-05
7,496 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 5.5081355e-05
7,517 Compact Histograms for Hierarchical Identifiers 2006 VLDB 5.5025167e-05
7,574 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS 5.4922744e-05
7,639 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 5.4767414e-05
8,042 JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023 SIGMOD 5.3999898e-05
8,458 Efficient Top-K Processing Over Query-Dependent Functions 2008 VLDB 5.3324907e-05
8,865 Adaptive Index Structures 2002 VLDB 5.2610786e-05
9,151 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 5.2181099e-05
9,396 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 5.1843659e-05
9,843 Hubble: An Advanced Dynamic Folder Technology for XML 2005 VLDB 5.1213404e-05
10,400 Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond 2026 PODS 4.9769913e-05
11,298 Cardinality Estimation for Having-Clauses 2025 VLDB 4.9769913e-05
13,137 Searching on the Secondary Structure of Protein Sequences 2002 VLDB 4.9769913e-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.0023943337
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00047864281
79 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00036476265
91 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00034748721
119 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.0003136296
232 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.0002378554
346 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020320726
424 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.00018487052
806 Universality of Serial Histograms 1993 VLDB 0.00013786471
1,084 On B-tree Indices for Skewed Distributions 1992 VLDB 0.00012108365
1,641 A Model of Data Distribution Based on Texture Analysis 1985 SIGMOD 0.00010003599
6,049 Experience from a Real Life Query Optimizer 1992 SIGMOD 5.9022349e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 7,639 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,574 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,743 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,969 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