Improved Histograms for Selectivity Estimation of Range Predicates

Summary: Proposes a systematic taxonomy of histograms for range-predicate selectivity estimation, unifying prior types and enabling novel design combinations. Demonstrates sampling to reduce histogram construction cost and empirically evaluates types on range queries to identify the best performers. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2892
Venue: SIGMOD
Year: 1996
Pagerank: 0.00063612837
Overall Rank: 64 | 99.56%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 111 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
126	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD	0.00044744986
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041786333
182	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00036962631
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036625711
211	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033981214
220	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00033194808
269	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029656549
273	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00029390945
275	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029364901
308	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00028142852
325	The History of Histograms (abridged)	2003	VLDB	0.00027378328
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
361	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00025775749
378	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.0002497492
405	Approximate Query Processing Using Wavelets	2000	VLDB	0.00024057494
429	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00023476494
443	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00022996573
449	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00022846068
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022734812
502	Worst-case Optimal Join Algorithms	2012	PODS	0.00021526612
512	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00021380733
526	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB	0.00021044221
529	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00020828852
530	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00020803682
629	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00018942366
650	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.00018659177
684	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018179769
739	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00017401518
758	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.0001706608
790	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.0001663283
805	Evaluating Top-k Selection Queries	1999	VLDB	0.00016437265
842	Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data	2001	SIGMOD	0.00016031973
852	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015941524
910	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00015423056
1,101	Generic Database Cost Models for Hierarchical Memory Systems	2002	VLDB	0.00014070632
1,120	Global Optimization of Histograms	2001	SIGMOD	0.00013856211
1,127	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB	0.00013819179
1,236	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS	0.00013117798
1,241	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00013097578
1,272	Proactive Re-Optimization	2005	SIGMOD	0.00012920076
1,379	Substring Selectivity Estimation	1999	PODS	0.00012286879
1,695	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	0.00010882793
1,703	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010836769
1,789	Reducing the Braking Distance of an SQL Query Engine	1998	VLDB	0.00010555087
1,797	Effective Use of Block-Level Sampling in Statistics Estimation	2004	SIGMOD	0.00010523169
2,010	StatiX: Making XML Count	2002	SIGMOD	9.7970026e-05
2,053	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.6728745e-05
2,096	Automatic Categorization of Query Results	2004	SIGMOD	9.5498009e-05
2,118	Using Probabilistic Models for Data Management in Acquisitional Environments	2005	CIDR	9.5100739e-05
2,137	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	9.4719326e-05

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.0040449103
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080435857
59	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064501896
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959
99	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050022914
116	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046148737
252	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00030632263
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479
387	Optimization of Large Join Queries	1988	SIGMOD	0.0002471967
399	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00024315433
808	Universality of Serial Histograms	1993	VLDB	0.00016432772
1,020	An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment	1993	SIGMOD	0.00014624893

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
222	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032828302
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
1,981	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	9.8687545e-05
808	Universality of Serial Histograms	1993	VLDB	0.00016432772
269	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029656549
3,310	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2408955e-05
5,082	A Comparison of Selectivity Estimators for Range Queries on Metric Attributes	1999	SIGMOD	5.711623e-05
897	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB	0.00015528028
116	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046148737
327	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027308479