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.00029532435
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,670	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	6.0266818e-05
5,671	PGMJoins: Random Join Sampling with Graphical Models	2021	SIGMOD	6.026372e-05
5,841	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.9569427e-05
5,854	Modeling Shifting Workloads for Learned Database Systems	2024	SIGMOD	5.9520525e-05
5,866	Compression Aware Physical Database Design	2011	VLDB	5.9492579e-05
5,885	BlinkML: Efficient Maximum Likelihood Estimation with Probabilistic Guarantees	2019	SIGMOD	5.9421702e-05
5,994	Supporting Time-Constrained SQL Queries in Oracle	2007	VLDB	5.9045522e-05
6,014	Approximate Query Engines: Commercial Challenges and Research Opportunities	2017	SIGMOD	5.8956963e-05
6,045	RPJ: Producing Fast Join Results on Streams through Rate-based Optimization	2005	SIGMOD	5.8882414e-05
6,164	Efficient Construction of Approximate Ad-Hoc ML models Through Materialization and Reuse	2018	VLDB	5.8508462e-05
6,397	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	5.7822506e-05
6,562	JoinBoost: Grow Trees Over Normalized Data Using Only SQL	2023	VLDB	5.7287508e-05
6,703	Query Sampling in DB2 Universal Database	2004	SIGMOD	5.687355e-05
6,800	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB	5.662589e-05
7,266	Depth Estimation for Ranking Query Optimization	2007	VLDB	5.55407e-05
7,387	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	5.5212177e-05
7,490	Reservoir Sampling over Joins	2024	SIGMOD	5.499011e-05
7,512	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	5.490671e-05
7,550	Foreign Keys Open the Door for Faster Incremental View Maintenance	2023	SIGMOD	5.4809422e-05
7,745	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	5.4457135e-05
8,051	Dscaler: Synthetically Scaling A Given Relational Database	2016	VLDB	5.383739e-05
8,363	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	5.3305234e-05
8,685	ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation	2023	VLDB	5.2730954e-05
9,422	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	5.1672232e-05
9,669	Poisson Sampling over Acyclic Joins	2026	SIGMOD	5.1275185e-05
10,175	Cquirrel: Continuous Query Processing over Acyclic Relational Schemas	2021	VLDB	5.0559291e-05
10,345	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	5.0197268e-05
10,346	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	5.0197268e-05
10,464	Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries	2026	PODS	4.9605343e-05
10,480	Accelerating Approximate Analytical Join Queries over Unstructured Data with Statistical Guarantees	2026	SIGMOD	4.9605343e-05
10,745	Qualitative Join Discovery in Data Lakes using Examples	2026	SIGMOD	4.9605343e-05
10,795	Secure Multi-Party Sampling over Joins	2026	VLDB	4.9605343e-05
11,591	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.9605343e-05
12,008	XLJoins	2021	SIGMOD	4.9605343e-05
12,264	Demonstration of VerdictDB, the Platform-Independent AQP System	2018	SIGMOD	4.9605343e-05
12,438	Capturing the Laws of (Data) Nature	2015	CIDR	4.9605343e-05
12,556	When Data Management Systems Meet Approximate Hardware: Challenges and Opportunities	2014	VLDB	4.9605343e-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.0023948467
9	Online Aggregation	1997	SIGMOD	0.00076079812
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047654188
58	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00039922419
78	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036725074
79	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00036394222
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.0002855087
234	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00023726296
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023327437
337	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00020593498
750	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00014246313
1,469	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00010533259
2,176	Selectivity Estimation in Spatial Databases	1999	SIGMOD	8.9031141e-05
3,015	The Ins and Outs (and Everything in Between) of Data Warehousing	1996	SIGMOD	7.7376493e-05

Semantically Similar Papers

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