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: 3106
Venue: SIGMOD
Year: 1999
Pagerank: 0.00033981214
Overall Rank: 211 | 98.54%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 84 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
43	Models and Issues in Data Stream Systems	2002	PODS	0.00072723062
308	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00028142852
325	The History of Histograms (abridged)	2003	VLDB	0.00027378328
372	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00025354779
405	Approximate Query Processing Using Wavelets	2000	VLDB	0.00024057494
429	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00023476494
449	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00022846068
467	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00022443768
549	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020376603
684	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018179769
739	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00017401518
790	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.0001663283
967	Aqua: A Fast Decision Support System Using Approximate Query Answers	1999	VLDB	0.00014959939
996	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014741524
1,064	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00014356481
1,204	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00013319541
1,260	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00012993347
1,272	Proactive Re-Optimization	2005	SIGMOD	0.00012920076
1,335	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00012502131
1,369	Random Sampling over Joins Revisited	2018	SIGMOD	0.00012339777
1,400	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.00012191684
1,547	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00011442359
1,909	SciBORQ: Scientific data management with Bounds On Runtime and Quality	2011	CIDR	0.00010121304
2,111	When Can We Trust Progress Estimators for SQL Queries?	2005	SIGMOD	9.5286436e-05
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1897043e-05
2,365	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	8.9551432e-05
2,368	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.9501526e-05
2,377	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	8.9402115e-05
2,501	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	8.6453446e-05
2,588	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	8.4909562e-05
2,808	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD	8.0870741e-05
2,995	A Sampling Algebra for Aggregate Estimation	2013	VLDB	7.7587199e-05
3,013	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	7.7137441e-05
3,051	Partial Results in Database Systems	2014	SIGMOD	7.6512591e-05
3,387	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	7.1573735e-05
3,408	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	7.1288167e-05
3,593	Graph-Based Synopses for Relational Selectivity Estimation	2006	SIGMOD	6.9385476e-05
3,651	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD	6.8768678e-05
3,656	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB	6.8714509e-05
3,824	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	6.7260705e-05
3,954	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB	6.5926838e-05
4,093	Distributed Online Aggregations	2009	VLDB	6.4558147e-05
4,100	A Bi-Level Bernoulli Scheme for Database Sampling	2004	SIGMOD	6.4531387e-05
4,358	Buffer Pool Aware Query Optimization	2005	CIDR	6.2571485e-05
4,546	Bounded Conjunctive Queries	2014	VLDB	6.0987778e-05
4,698	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	5.9887317e-05
4,953	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8085795e-05
5,150	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	5.6626586e-05
5,539	Supporting Time-Constrained SQL Queries in Oracle	2007	VLDB	5.4503121e-05
5,806	BlinkML: Efficient Maximum Likelihood Estimation with Probabilistic Guarantees	2019	SIGMOD	5.3200643e-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.0040449103
14	Online Aggregation	1997	SIGMOD	0.0010801504
39	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00074745564
59	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064501896
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051315959
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036625711
252	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00030632263
269	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029656549
429	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00023476494
553	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00020272061
811	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00016425612
2,053	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.6728745e-05
2,739	The Ins and Outs (and Everything in Between) of Data Warehousing	1996	SIGMOD	8.1985423e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,159	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	4.5729025e-05
8,061	Efficient Computation of Quantiles over Joins	2023	PODS	4.5943269e-05
6,493	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.0424713e-05
2,808	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD	8.0870741e-05
8,959	Reservoir Sampling over Joins	2024	SIGMOD	4.4206222e-05
5,104	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	5.6946113e-05
1,717	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010793312
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036625711
5,150	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	5.6626586e-05
7,581	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7057641e-05