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: 1321
Venue: PODS
Year: 2004
Pagerank: 5.6268292e-05
Overall Rank: 7,388 | 49.32%
DOI: 10.1145/1055558.1055586

Incoming Non-self Citations Over Time

Authors

1. Raghav Kaushik (Microsoft)
2. Raghu Ramakrishnan (University of Wisconsin)
3. Venkatesan T. Chakaravarthy (University of Wisconsin)

BibTeX Citation

@inproceedings{kaushik_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{Synopses for Query Optimization: A Space-Complexity Perspective}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055586},
        doi = {10.1145/1055558.1055586},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kaushik, Raghav and Ramakrishnan, Raghu and Chakaravarthy, Venkatesan T.},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
401	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00019092557
4,349	ALECE: An Attention-based Learned Cardinality Estimator for SPJ Queries on Dynamic Workloads	2024	VLDB	6.7504619e-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
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00048351457
54	On Random Sampling over Joins	1999	SIGMOD	0.00040810225
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
89	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00035031529
118	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00031922279
136	Join Synopses for Approximate Query Answering	1999	SIGMOD	0.00030123303
173	Simple Random Sampling from Relational Databases	1986	VLDB	0.00027273858
213	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD	0.00024723025
235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023783792
267	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00022798161
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
339	Sequential Sampling Procedures For Query Size Estimation	1992	SIGMOD	0.00020723773
418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018812821
786	Universality of Serial Histograms	1993	VLDB	0.00014053885
817	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00013823702
850	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00013619394
3,553	On the Complexity of Approximate Query Optimization	2002	PODS	7.3175599e-05
3,575	Optimal Histograms for Hierarchical Range Queries (Extended Abstract)	2000	PODS	7.2946291e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,666	Constructing Join Histograms from Histograms with q-error Guarantees	2016	SIGMOD
2	3,453	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS
3	418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS
4	1,664	Two-Level Sampling for Join Size Estimation	2017	SIGMOD
5	786	Universality of Serial Histograms	1993	VLDB
6	274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD
7	89	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD
8	10,169	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS
9	1,536	Improved Selectivity Estimation by Combining Knowledge from Sampling and Synopses	2018	VLDB
10	136	Join Synopses for Approximate Query Answering	1999	SIGMOD