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: 2804
Venue: SIGMOD
Year: 1995
Pagerank: 0.00027301497
Overall Rank: 328 | 97.73%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Yannis E. Ioannidis
2. Viswanath Poosala

Incoming Citations (Sorted by Pagerank)

Showing 48 of 48 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041819767
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
221	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00033182072
325	The History of Histograms (abridged)	2003	VLDB	0.00027398081
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
430	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00023406426
512	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00021385343
523	Recovering Information from Summary Data	1997	VLDB	0.00021101376
531	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.0002079072
550	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020346247
849	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015919478
874	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.0001568356
1,116	Global Optimization of Histograms	2001	SIGMOD	0.00013863484
1,145	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.00013672625
1,240	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00013090678
1,274	The Data Civilizer System	2017	CIDR	0.00012869297
1,379	Substring Selectivity Estimation	1999	PODS	0.00012280308
1,509	Estimating Progress of Execution for SQL Queries	2004	SIGMOD	0.0001158945
1,691	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	0.00010890775
2,113	When Can We Trust Progress Estimators for SQL Queries?	2005	SIGMOD	9.5207583e-05
2,752	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	8.1723418e-05
2,844	Selectivity Estimation in Extensible Databases - A Neural Network Approach	1998	VLDB	8.0308994e-05
3,720	Space efficiency in Synopsis construction algorithms	2005	VLDB	6.8139746e-05
3,801	Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees	2020	VLDB	6.7528979e-05
3,896	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	6.6526869e-05
3,992	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	6.5519369e-05
4,018	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	6.5250686e-05
4,679	Adaptive Sampling for Rapidly Matching Histograms	2018	VLDB	5.9978792e-05
5,543	Lightweight Cardinality Estimation in LSM-based Systems	2018	SIGMOD	5.4486922e-05
5,696	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	5.367449e-05
5,832	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS	5.3085972e-05
5,967	Modeling skewed distributions using multifractals and the '80-20 law'	1996	VLDB	5.247088e-05
6,311	VergeDB: A Database for IoT Analytics on Edge Devices	2021	CIDR	5.1112212e-05
7,150	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	4.8128138e-05
7,392	MOST: Model-Based Compression with Outlier Storage for Time Series Data	2023	SIGMOD	4.737456e-05
7,460	Compact Histograms for Hierarchical Identifiers	2006	VLDB	4.7198214e-05
7,573	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7034681e-05
7,725	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	4.6621296e-05
7,966	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB	4.6089395e-05
8,414	PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression	2024	VLDB	4.5135713e-05
8,471	Adaptive Index Structures	2002	VLDB	4.4986491e-05
8,893	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	4.4232868e-05
9,059	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	4.3997447e-05
9,079	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD	4.3956812e-05
9,464	Hubble: An Advanced Dynamic Folder Technology for XML	2005	VLDB	4.3314489e-05
10,647	Cardinality Estimation for Having-Clauses	2025	VLDB	4.1905499e-05
12,657	Searching on the Secondary Structure of Protein Sequences	2002	VLDB	4.1905499e-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
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
226	Estimating Block Transfers and Join Sizes	1983	SIGMOD	0.0003243274
250	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00030640525
369	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025502381
639	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00018782897
801	Universality of Serial Histograms	1993	VLDB	0.00016440976
1,399	A Model of Data Distribution Based on Texture Analysis	1985	SIGMOD	0.00012197728
5,312	Experience from a Real Life Query Optimizer	1992	SIGMOD	5.5712237e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,725	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	4.6621296e-05
114	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046317654
1,116	Global Optimization of Histograms	2001	SIGMOD	0.00013863484
7,150	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	4.8128138e-05
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
1,691	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	0.00010890775
270	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029648047
3,896	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	6.6526869e-05
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
801	Universality of Serial Histograms	1993	VLDB	0.00016440976