Self-tuning Histograms: Building Histograms Without Looking at Data

Summary: Self-tuning histograms infer distributions from query-execution feedback, not data samples, and refine via range-selectivity observations. Data-size independent, cheaper than multi-dimensional histograms; effective for low–moderate skew, with initialization/refinement techniques and experimental validation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: hdcfd44ae6c3d1545
Venue: SIGMOD
Year: 1999
Pagerank: 0.00017915659
Overall Rank: 457 | 96.94%
DOI: 10.1145/304182.304198

Incoming Non-self Citations Over Time

Authors

1. Ashraf Aboulnaga (University of Wisconsin)
2. Surajit Chaudhuri (Microsoft)

BibTeX Citation

@inproceedings{aboulnaga_sigmod99,
        title = {{Self-tuning Histograms: Building Histograms Without Looking at Data}},
        author = {Aboulnaga, Ashraf and Chaudhuri, Surajit},
        series = {{SIGMOD} '99},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/304182.304198},
        url = {https://dl.acm.org/doi/10.1145/304182.304198},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 57 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
98	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00034050614
160	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00027775994
254	The History of Histograms (abridged)	2003	VLDB	0.00022999992
316	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021238056
372	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00019768921
374	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00019698889
545	Plan-Structured Deep Neural Network Models for Query Performance Prediction	2019	VLDB	0.0001657599
646	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00015166402
676	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB	0.00014838681
690	Selectivity Estimation for Range Predicates using Lightweight Models	2019	VLDB	0.00014703258
745	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014267268
868	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00013336675
958	Flexible Database Generators	2005	VLDB	0.00012834376
1,006	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB	0.00012551491
1,064	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012181459
1,156	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011759683
1,159	Toward a Progress Indicator for Database Queries	2004	SIGMOD	0.00011739527
1,246	Compressing SQL Workloads	2002	SIGMOD	0.00011355447
1,513	DSB: A Decision Support Benchmark for Workload-Driven and Traditional Database Systems	2021	VLDB	0.00010394557
1,587	Estimating Progress of Execution for SQL Queries	2004	SIGMOD	0.00010119368
1,614	SciBORQ: Scientific data management with Bounds On Runtime and Quality	2011	CIDR	0.00010054823
1,935	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	9.3407959e-05
1,987	Plan Bouquets: Query Processing without Selectivity Estimation	2014	SIGMOD	9.2323722e-05
2,154	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	8.9382906e-05
2,174	A Black-Box Approach to Query Cardinality Estimation	2007	CIDR	8.9067128e-05
2,419	Towards Elastic Transactional Cloud Storage with Range Query Support	2010	VLDB	8.4818595e-05
2,768	Query Performance Prediction for Concurrent Queries using Graph Embedding	2020	VLDB	8.0199086e-05
2,888	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	7.8895201e-05
2,987	Accurate Summary-based Cardinality Estimation Through the Lens of Cardinality Estimation Graphs	2022	VLDB	7.767043e-05
3,060	A Unified Deep Model of Learning from both Data and Queries for Cardinality Estimation	2021	SIGMOD	7.6828463e-05
3,062	Towards a Hands-Free Query Optimizer through Deep Learning	2019	CIDR	7.6809918e-05
3,081	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	7.6515625e-05
3,212	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB	7.5145409e-05
3,371	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD	7.3493132e-05
3,531	Identifying Robust Plans through Plan Diagram Reduction	2008	VLDB	7.2065332e-05
3,653	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	7.1149642e-05
3,858	Graph-Based Synopses for Relational Selectivity Estimation	2006	SIGMOD	6.9543709e-05
4,268	Primitives for Workload Summarization and Implications for SQL	2003	VLDB	6.6784565e-05
4,480	DigitHist: a Histogram-Based Data Summary with Tight Error Bounds	2017	VLDB	6.566036e-05
4,545	XPathLearner: An On-Line Self-Tuning Markov Histogram for XML Path Selectivity Estimation	2002	VLDB	6.5366364e-05
4,672	Automated Statistics Collection in DB2 UDB	2004	VLDB	6.4593469e-05
5,056	Lightweight Cardinality Estimation in LSM-based Systems	2018	SIGMOD	6.282339e-05
5,490	A Pay-As-You-Go Framework for Query Execution Feedback	2008	VLDB	6.0970166e-05
5,854	Modeling Shifting Workloads for Learned Database Systems	2024	SIGMOD	5.9520525e-05
6,224	Efficient Detection of Empty-Result Queries	2006	VLDB	5.828372e-05
6,672	Speeding Up End-to-end Query Execution via Learning-based Progressive Cardinality Estimation	2023	SIGMOD	5.6975871e-05
6,725	Simple Adaptive Query Processing vs. Learned Query Optimizers: Observations and Analysis	2023	VLDB	5.6826988e-05
7,094	Plan Stitch: Harnessing the Best of Many Plans	2018	VLDB	5.5863735e-05
7,542	Comparing Synopsis Techniques for Approximate Spatial Data Analysis	2019	VLDB	5.4821664e-05
7,654	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	5.4588598e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047654188
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036394222
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033847446
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00031291457
149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00028910892
171	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027063233
234	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00023726296
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023327437
252	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023058622

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,173	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD
2	9,859	Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects	2010	SIGMOD
3	11,989	Data-Independent Space Partitionings for Summaries	2021	PODS
4	1,693	Global Optimization of Histograms	2001	SIGMOD
5	745	Dynamic Multidimensional Histograms	2002	SIGMOD
6	119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD
7	37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD
8	2,154	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB
9	285	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD
10	7,654	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB