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: h51f52fff9f5825bc
Venue: SIGMOD
Year: 1999
Pagerank: 0.00029627449
Overall Rank: 138 | 99.08%
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,656	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	6.0488629e-05
5,657	PGMJoins: Random Join Sampling with Graphical Models	2021	SIGMOD	6.0488437e-05
5,831	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.9782109e-05
5,853	Compression Aware Physical Database Design	2011	VLDB	5.9710387e-05
5,865	Modeling Shifting Workloads for Learned Database Systems	2024	SIGMOD	5.9659203e-05
5,877	BlinkML: Efficient Maximum Likelihood Estimation with Probabilistic Guarantees	2019	SIGMOD	5.9627218e-05
5,983	Supporting Time-Constrained SQL Queries in Oracle	2007	VLDB	5.926918e-05
6,004	Approximate Query Engines: Commercial Challenges and Research Opportunities	2017	SIGMOD	5.9166815e-05
6,030	RPJ: Producing Fast Join Results on Streams through Rate-based Optimization	2005	SIGMOD	5.9105381e-05
6,143	Efficient Construction of Approximate Ad-Hoc ML models Through Materialization and Reuse	2018	VLDB	5.8721471e-05
6,386	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	5.8040725e-05
6,550	JoinBoost: Grow Trees Over Normalized Data Using Only SQL	2023	VLDB	5.7503043e-05
6,685	Query Sampling in DB2 Universal Database	2004	SIGMOD	5.7086005e-05
6,781	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB	5.6836871e-05
7,247	Depth Estimation for Ranking Query Optimization	2007	VLDB	5.5748328e-05
7,364	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.5418075e-05
7,467	Reservoir Sampling over Joins	2024	SIGMOD	5.5198675e-05
7,493	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	5.5103311e-05
7,542	Foreign Keys Open the Door for Faster Incremental View Maintenance	2023	SIGMOD	5.4986181e-05
8,028	Dscaler: Synthetically Scaling A Given Relational Database	2016	VLDB	5.4041252e-05
8,223	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	5.3751366e-05
8,347	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	5.350539e-05
8,659	ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation	2023	VLDB	5.2930951e-05
9,387	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	5.1868213e-05
9,634	Poisson Sampling over Acyclic Joins	2026	SIGMOD	5.146966e-05
10,134	Cquirrel: Continuous Query Processing over Acyclic Relational Schemas	2021	VLDB	5.0751052e-05
10,315	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	5.0377739e-05
10,316	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	5.0377739e-05
10,386	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS	4.9793485e-05
10,402	Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees	2026	SIGMOD	4.9793485e-05
10,673	Qualitative Join Discovery in Data Lakes using Examples	2026	SIGMOD	4.9793485e-05
10,724	Secure Multi-Party Sampling over Joins	2026	VLDB	4.9793485e-05
11,536	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9793485e-05
11,958	XLJoins	2021	SIGMOD	4.9793485e-05
12,215	Demonstration of VerdictDB, the Platform-Independent AQP System	2018	SIGMOD	4.9793485e-05
12,389	Capturing the Laws of (Data) Nature	2015	CIDR	4.9793485e-05
12,507	When Data Management Systems Meet Approximate Hardware: Challenges and Opportunities	2014	VLDB	4.9793485e-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.0023947656
9	Online Aggregation	1997	SIGMOD	0.00076195956
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00040035279
77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036828234
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036487763
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028633995
232	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00023792809
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023363722
336	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00020657819
745	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014288286
1,467	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00010567959
2,162	Selectivity Estimation in Spatial Databases	1999	SIGMOD	8.935022e-05
3,002	The Ins and Outs (and Everything in Between) of Data Warehousing	1996	SIGMOD	7.7661188e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,655	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD
2	5,831	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB
3	7,467	Reservoir Sampling over Joins	2024	SIGMOD
4	5,489	Compressed Representations of Conjunctive Query Results	2018	PODS
5	3,992	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS
6	1,431	Approximate Join Processing Over Data Streams	2003	SIGMOD
7	153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD
8	10,386	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS
9	4,642	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD
10	7,493	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS