Synopses for Query Optimization: A Space-Complexity Perspective

Summary: Information-theoretic analysis of synopsis space: histograms suffice for single-table selections but are fundamentally limited for joins. For key–foreign-key joins, small precomputed samples yield nearly space-optimal probabilistic guarantees; experiments confirm samples outperform histograms as joins increase. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1322
Venue: PODS
Year: 2004
Pagerank: 4.7034681e-05
Overall Rank: 7,573 | 47.37%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
752	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00017138049
5,405	ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads	2024	VLDB	5.5243727e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
18	On Random Sampling over Joins	1999	SIGMOD	0.00092569117
28	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00080571183
46	Simple Random Sampling from Relational Databases	1986	VLDB	0.00071588702
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
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
212	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033997204
270	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029648047
275	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00029381206
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
369	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00025502381
550	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020346247
801	Universality of Serial Histograms	1993	VLDB	0.00016440976
995	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014745185
1,065	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00014344675
4,018	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	6.5250686e-05
4,189	On the Complexity of Approximate Query Optimization	2002	PODS	6.3681294e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
782	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00016665859
9,580	Constructing Join Histograms from Histograms with q-error Guarantees	2016	SIGMOD	4.318902e-05
4,926	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8184457e-05
550	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020346247
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1871115e-05
801	Universality of Serial Histograms	1993	VLDB	0.00016440976
328	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00027301497
100	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050033475
1,978	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB	9.8764627e-05
212	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00033997204