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: 2893
Venue: SIGMOD
Year: 1996
Pagerank: 0.00063595699
Overall Rank: 63 | 99.57%
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.00044753012
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041819767
181	LEO - DB2's LEarning Optimizer	2001	VLDB	0.00036970794
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
212	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033997204
221	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00033182072
270	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029648047
274	Approximate Medians and other Quantiles in One Pass and with Limited Memory	1998	SIGMOD	0.00029383266
275	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00029381206
316	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00027981848
325	The History of Histograms (abridged)	2003	VLDB	0.00027398081
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
360	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00025768448
380	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00024943236
416	Approximate Query Processing Using Wavelets	2000	VLDB	0.00023773968
430	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00023406426
431	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00023397171
446	Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets	1999	SIGMOD	0.00023002059
454	An Overview of Query Optimization in Relational Systems	1998	PODS	0.00022796106
503	Worst-case Optimal Join Algorithms	2012	PODS	0.00021517145
512	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00021385343
526	A One-Pass Algorithm for Accurately Estimating Quantiles for Disk-Resident Data	1997	VLDB	0.00021046587
527	Self-tuning Histograms: Building Histograms Without Looking at Data	1999	SIGMOD	0.00020862475
531	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.0002079072
627	Preventing Bad Plans by Bounding the Impact of Cardinality Estimation Errors	2009	VLDB	0.00018959896
650	Robust Query Processing through Progressive Optimization	2004	SIGMOD	0.0001865144
680	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018193263
736	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00017414831
752	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00017138049
786	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00016624743
802	Evaluating Top-k Selection Queries	1999	VLDB	0.00016440813
838	Independence is Good: Dependency-Based Histogram Synopses for High-Dimensional Data	2001	SIGMOD	0.00016024923
849	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015919478
905	NeuroCard: One Cardinality Estimator for All Tables	2021	VLDB	0.00015423174
1,100	Generic Database Cost Models for Hierarchical Memory Systems	2002	VLDB	0.00014062265
1,116	Global Optimization of Histograms	2001	SIGMOD	0.00013863484
1,126	Dynamic Maintenance of Wavelet-Based Histograms	2000	VLDB	0.0001381102
1,234	Least Expected Cost Query Optimization: An Exercise in Utility	1999	PODS	0.00013115865
1,240	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00013090678
1,268	Proactive Re-Optimization	2005	SIGMOD	0.00012914584
1,379	Substring Selectivity Estimation	1999	PODS	0.00012280308
1,691	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	0.00010890775
1,699	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010848882
1,780	Reducing the Braking Distance of an SQL Query Engine	1998	VLDB	0.00010558417
1,790	Effective Use of Block-Level Sampling in Statistics Estimation	2004	SIGMOD	0.00010529479
2,016	StatiX: Making XML Count	2002	SIGMOD	9.7892568e-05
2,056	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.6692561e-05
2,101	Automatic Categorization of Query Results	2004	SIGMOD	9.5406958e-05
2,120	Using Probabilistic Models for Data Management in Acquisitional Environments	2005	CIDR	9.5017579e-05
2,136	SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads	2003	VLDB	9.4668797e-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.0040465394
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080571183
60	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064450997
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
100	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050033475
114	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046317654
250	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00030640525
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
388	Optimization of Large Join Queries	1988	SIGMOD	0.00024654816
400	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00024308369
801	Universality of Serial Histograms	1993	VLDB	0.00016440976
1,019	An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment	1993	SIGMOD	0.00014623543

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
223	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00032829841
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
1,978	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	9.8764627e-05
801	Universality of Serial Histograms	1993	VLDB	0.00016440976
270	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029648047
3,292	Optimal and Approximate Computation of Summary Statistics for Range Aggregates	2001	PODS	7.2598265e-05
5,066	A Comparison of Selectivity Estimators for Range Queries on Metric Attributes	1999	SIGMOD	5.7157182e-05
896	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB	0.00015486851
114	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046317654
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497