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.00017962189
Overall Rank: 454 | 96.95%
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 7 of 57 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,167	CXHist: An On-line Classification-Based Histogram for XML String Selectivity Estimation	2005	VLDB	5.3848674e-05
9,387	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	5.1868213e-05
9,718	A Practical Theory of Generalization in Selectivity Learning	2025	VLDB	5.1353964e-05
9,976	Selectivity Estimation for Queries Containing Predicates over Set-Valued Attributes	2023	SIGMOD	5.1031384e-05
10,294	Data-Agnostic Cardinality Learning from Imperfect Workloads	2025	VLDB	5.0431863e-05
12,967	Peer-to-Peer Similarity Search in Metric Spaces	2007	VLDB	4.9793485e-05
12,992	Adaptive Density Estimation	2006	VLDB	4.9793485e-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.00047731453
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036487763
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033894985
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.0003137356
149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00028981723
169	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027134723
232	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00023792809
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023363722
252	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00023050233

Semantically Similar Papers

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