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
2865
Venue
SIGMOD
Year
1995
Pagerank
0.00022645621
Overall Rank
274 | 98.13%
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
35 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00048481081
101 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00034376651
149 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00029226907
151 Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans 1998 SIGMOD 0.00029161879
257 The History of Histograms (abridged) 2003 VLDB 0.00023154793
267 Optimal Histograms with Quality Guarantees 1998 VLDB 0.00022798161
363 Approximate Query Processing: Taming the TeraBytes! A Tutorial 2001 VLDB 0.0002005475
365 STHoles: A Multidimensional Workload-Aware Histogram 2001 SIGMOD 0.00020041735
418 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00018812821
508 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00017275873
723 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00014620977
838 What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically 2003 PODS 0.0001370404
952 Recovering Information from Summary Data 1997 VLDB 0.00013010681
963 The Data Civilizer System 2017 CIDR 0.00012935145
1,053 Multi-dimensional Selectivity Estimation Using Compressed Histogram Information 1999 SIGMOD 0.00012401532
1,140 Estimating Alphanumeric Selectivity in the Presence of Wildcards 1996 SIGMOD 0.0001200574
1,427 Substring Selectivity Estimation 1999 PODS 0.00010812749
1,562 Estimating Progress of Execution for SQL Queries 2004 SIGMOD 0.00010354429
1,668 Global Optimization of Histograms 2001 SIGMOD 0.00010057026
1,729 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 9.908788e-05
2,270 When Can We Trust Progress Estimators for SQL Queries? 2005 SIGMOD 8.8310714e-05
2,281 Selectivity Estimation in Extensible Databases - A Neural Network Approach 1998 VLDB 8.8129279e-05
2,991 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.8880723e-05
3,111 REHIST: Relative Error Histogram Construction Algorithms 2004 VLDB 7.7470414e-05
3,575 Optimal Histograms for Hierarchical Range Queries (Extended Abstract) 2000 PODS 7.2946291e-05
3,595 Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees 2020 VLDB 7.2736195e-05
3,893 Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing 1996 VLDB 7.04191e-05
4,819 Space efficiency in Synopsis construction algorithms 2005 VLDB 6.4940349e-05
4,926 Adaptive Sampling for Rapidly Matching Histograms 2018 VLDB 6.4428362e-05
4,945 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 6.4321265e-05
5,137 Exact Cardinality Query Optimization with Bounded Execution Cost 2019 SIGMOD 6.3507372e-05
5,421 Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms 2015 PODS 6.2245831e-05
6,053 Modeling skewed distributions using multifractals and the '80-20 law' 1996 VLDB 5.9939282e-05
6,061 VergeDB: A Database for IoT Analytics on Edge Devices 2021 CIDR 5.9910733e-05
6,590 MOST: Model-Based Compression with Outlier Storage for Time Series Data 2023 SIGMOD 5.8316635e-05
7,351 PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression 2024 VLDB 5.6354898e-05
7,375 Compact Histograms for Hierarchical Identifiers 2006 VLDB 5.6299286e-05
7,388 Synopses for Query Optimization: A Space-Complexity Perspective 2004 PODS 5.6268292e-05
7,443 Histograms Revisited: When are histograms the best approximation method for aggregates over joins? 2005 PODS 5.6166792e-05
7,554 Consistent Histograms In The Presence of Distinct Value Counts 2009 VLDB 5.6001388e-05
8,281 Efficient Top-K Processing Over Query-Dependent Functions 2008 VLDB 5.4574671e-05
8,689 Adaptive Index Structures 2002 VLDB 5.3843737e-05
8,998 Histograms Reloaded: The Merits of Bucket Diversity 2010 SIGMOD 5.3355988e-05
9,027 JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023 SIGMOD 5.3293224e-05
9,209 Optimality and Scalability in Lattice Histogram Construction 2009 VLDB 5.3058708e-05
9,658 Hubble: An Advanced Dynamic Folder Technology for XML 2005 VLDB 5.2413041e-05
10,171 Unbiased Insights: Optimal Streaming Algorithms for l_p Sampling, the Forget Model, and Beyond 2026 PODS 5.093636e-05
10,891 Cardinality Estimation for Having-Clauses 2025 VLDB 5.093636e-05
12,841 Searching on the Secondary Structure of Protein Sequences 2002 VLDB 5.093636e-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.0024089429
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00048351457
76 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00037054261
89 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00035031529
118 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00031922279
222 Adaptive Selectivity Estimation Using Query Feedback 1994 SIGMOD 0.00024193708
339 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020723773
417 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.00018819871
786 Universality of Serial Histograms 1993 VLDB 0.00014053885
1,059 On B-tree Indices for Skewed Distributions 1992 VLDB 0.00012377809
1,614 A Model of Data Distribution Based on Texture Analysis 1985 SIGMOD 0.00010215186
5,930 Experience from a Real Life Query Optimizer 1992 SIGMOD 6.0372035e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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