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: 2803
Venue: SIGMOD
Year: 1995
Pagerank: 0.00027308479
Overall Rank: 327 | 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
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
141	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00041786333
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036625711
220	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00033194808
325	The History of Histograms (abridged)	2003	VLDB	0.00027378328
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
449	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00022846068
512	STHoles: A Multidimensional Workload-Aware Histogram	2001	SIGMOD	0.00021380733
523	Recovering Information from Summary Data	1997	VLDB	0.00021089782
530	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00020803682
549	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020376603
852	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00015941524
865	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.00015808172
1,120	Global Optimization of Histograms	2001	SIGMOD	0.00013856211
1,146	Estimating Alphanumeric Selectivity in the Presence of Wildcards	1996	SIGMOD	0.00013679782
1,241	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00013097578
1,277	The Data Civilizer System	2017	CIDR	0.00012879695
1,379	Substring Selectivity Estimation	1999	PODS	0.00012286879
1,512	Estimating Progress of Execution for SQL Queries	2004	SIGMOD	0.00011597041
1,695	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	0.00010882793
2,111	When Can We Trust Progress Estimators for SQL Queries?	2005	SIGMOD	9.5286436e-05
2,748	REHIST: Relative Error Histogram Construction Algorithms	2004	VLDB	8.1785955e-05
2,841	Selectivity Estimation in Extensible Databases - A Neural Network Approach	1998	VLDB	8.0287389e-05
3,719	Space efficiency in Synopsis construction algorithms	2005	VLDB	6.8204683e-05
3,798	Plato: Approximate Analytics over Compressed Time Series with Tight Deterministic Error Guarantees	2020	VLDB	6.7592302e-05
3,893	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	6.6584217e-05
3,990	FactorJoin: A New Cardinality Estimation Framework for Join Queries	2023	SIGMOD	6.5581983e-05
4,017	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	6.524501e-05
4,681	Adaptive Sampling for Rapidly Matching Histograms	2018	VLDB	6.0034918e-05
5,535	Lightweight Cardinality Estimation in LSM-based Systems	2018	SIGMOD	5.4539235e-05
5,685	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	5.3717535e-05
5,879	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS	5.2908101e-05
5,982	Modeling skewed distributions using multifractals and the '80-20 law'	1996	VLDB	5.2446136e-05
6,311	VergeDB: A Database for IoT Analytics on Edge Devices	2021	CIDR	5.1161316e-05
7,150	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	4.8163484e-05
7,395	MOST: Model-Based Compression with Outlier Storage for Time Series Data	2023	SIGMOD	4.7420041e-05
7,459	Compact Histograms for Hierarchical Identifiers	2006	VLDB	4.7243492e-05
7,581	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7057641e-05
7,728	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	4.666214e-05
7,963	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB	4.613363e-05
8,474	Adaptive Index Structures	2002	VLDB	4.5029015e-05
8,893	Histograms Reloaded: The Merits of Bucket Diversity	2010	SIGMOD	4.4275272e-05
9,061	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	4.4039656e-05
9,082	JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation	2023	SIGMOD	4.3998984e-05
9,431	PairwiseHist: Fast, Accurate and Space-Efficient Approximate Query Processing with Data Compression	2024	VLDB	4.3434046e-05
9,462	Hubble: An Advanced Dynamic Folder Technology for XML	2005	VLDB	4.3356061e-05
10,639	Cardinality Estimation for Having-Clauses	2025	VLDB	4.1945683e-05
12,648	Searching on the Secondary Structure of Protein Sequences	2002	VLDB	4.1945683e-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
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
228	Estimating Block Transfers and Join Sizes	1983	SIGMOD	0.00032269684
252	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00030632263
367	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025509745
638	On B-tree Indices for Skewed Distributions	1992	VLDB	0.00018798677
808	Universality of Serial Histograms	1993	VLDB	0.00016432772
1,398	A Model of Data Distribution Based on Texture Analysis	1985	SIGMOD	0.00012197586
5,309	Experience from a Real Life Query Optimizer	1992	SIGMOD	5.5756379e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,728	Consistent Histograms In The Presence of Distinct Value Counts	2009	VLDB	4.666214e-05
1,120	Global Optimization of Histograms	2001	SIGMOD	0.00013856211
116	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00046148737
7,150	Histograms Revisited: When are histograms the best approximation method for aggregates over joins?	2005	PODS	4.8163484e-05
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
1,695	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	0.00010882793
269	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029656549
3,893	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	6.6584217e-05
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
808	Universality of Serial Histograms	1993	VLDB	0.00016432772