Join Synopses for Approximate Query Answering

Summary: Join synopses enable accurate approximate answers for join queries using only statistics. A single synopsis per relation boosts FK-join accuracy; the work provides optimal and heuristic space allocation under known workloads, plus incremental maintenance and extensive TPC-D experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3168
Venue: SIGMOD
Year: 1999
Pagerank: 0.00030123303
Overall Rank: 136 | 99.07%
DOI: 10.1145/304182.304207

Incoming Non-self Citations Over Time

Authors

1. Swarup Acharya (AT&T)
2. Phillip B. Gibbons (AT&T)
3. Viswanath Poosala (AT&T)
4. Sridhar Ramaswamy (Epiphany Inc.)

BibTeX Citation

@inproceedings{acharya_sigmod99,
        title = {{Join Synopses for Approximate Query Answering}},
        author = {Acharya, Swarup and Gibbons, Phillip B. and Poosala, Viswanath and Ramaswamy, Sridhar},
        series = {{SIGMOD} '99},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/304182.304207},
        url = {https://dl.acm.org/doi/10.1145/304182.304207},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 37 of 87 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,537	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	6.1820087e-05
5,551	PGMJoins: Random Join Sampling with Graphical Models	2021	SIGMOD	6.1782856e-05
5,743	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	6.1025457e-05
5,755	Compression Aware Physical Database Design	2011	VLDB	6.0974171e-05
5,785	BlinkML: Efficient Maximum Likelihood Estimation with Probabilistic Guarantees	2019	SIGMOD	6.0892672e-05
5,863	Supporting Time-Constrained SQL Queries in Oracle	2007	VLDB	6.0626421e-05
5,906	Approximate Query Engines: Commercial Challenges and Research Opportunities	2017	SIGMOD	6.0457047e-05
5,911	RPJ: Producing Fast Join Results on Streams through Rate-based Optimization	2005	SIGMOD	6.0443263e-05
6,038	Efficient Construction of Approximate Ad-Hoc ML models Through Materialization and Reuse	2018	VLDB	5.9990929e-05
6,323	Modeling Shifting Workloads for Learned Database Systems	2024	SIGMOD	5.9141228e-05
6,332	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	5.9107433e-05
6,562	Query Sampling in DB2 Universal Database	2004	SIGMOD	5.838575e-05
6,585	JoinBoost: Grow Trees Over Normalized Data Using Only SQL	2023	VLDB	5.8350362e-05
6,654	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB	5.8131331e-05
7,123	Depth Estimation for Ranking Query Optimization	2007	VLDB	5.6966694e-05
7,256	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.6625146e-05
7,335	Reservoir Sampling over Joins	2024	SIGMOD	5.64193e-05
7,388	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	5.6268292e-05
7,866	Dscaler: Synthetically Scaling A Given Relational Database	2016	VLDB	5.5281143e-05
8,181	Foreign Keys Open the Door for Faster Incremental View Maintenance	2023	SIGMOD	5.4721346e-05
8,183	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	5.4714466e-05
8,204	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	5.4667903e-05
8,492	ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation	2023	VLDB	5.4145838e-05
9,209	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	5.3058708e-05
9,512	Poisson Sampling over Acyclic Joins	2026	SIGMOD	5.2571354e-05
9,951	Cquirrel: Continuous Query Processing over Acyclic Relational Schemas	2021	VLDB	5.1915905e-05
10,093	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	5.1530576e-05
10,094	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	5.1530576e-05
10,169	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS	5.093636e-05
10,186	Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees	2026	SIGMOD	5.093636e-05
10,486	Qualitative Join Discovery in Data Lakes using Examples	2026	SIGMOD	5.093636e-05
10,542	Secure Multi-Party Sampling over Joins	2026	VLDB	5.093636e-05
11,194	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	5.093636e-05
11,651	XLJoins	2021	SIGMOD	5.093636e-05
11,916	Demonstration of VerdictDB, the Platform-Independent AQP System	2018	SIGMOD	5.093636e-05
12,096	Capturing the Laws of (Data) Nature	2015	CIDR	5.093636e-05
12,216	When Data Management Systems Meet Approximate Hardware: Challenges and Opportunities	2014	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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.0024089429
9	Online Aggregation	1997	SIGMOD	0.00077458002
35	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00048481081
55	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040746149
75	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00037277061
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
222	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00024193708
235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023783792
327	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00021091539
730	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014539362
1,440	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00010778889
2,127	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.127762e-05
2,943	The Ins and Outs (and Everything in Between) of Data Warehousing	1996	SIGMOD	7.9348214e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
2	2,608	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD
3	7,335	Reservoir Sampling over Joins	2024	SIGMOD
4	5,383	Compressed Representations of Conjunctive Query Results	2018	PODS
5	3,941	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS
6	1,397	Approximate Join Processing Over Data Streams	2003	SIGMOD
7	149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD
8	10,169	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS
9	4,630	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD
10	7,388	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS