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: 3107
Venue: SIGMOD
Year: 1999
Pagerank: 0.00033997204
Overall Rank: 212 | 98.53%
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.00072660894
316	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00027981848
325	The History of Histograms (abridged)	2003	VLDB	0.00027398081
373	Selectivity Estimation using Probabilistic Models	2001	SIGMOD	0.00025354685
416	Approximate Query Processing Using Wavelets	2000	VLDB	0.00023773968
430	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.00023406426
431	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00023397171
463	Evaluating Probabilistic Queries over Imprecise Data	2003	SIGMOD	0.00022497894
550	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020346247
680	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018193263
736	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00017414831
786	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00016624743
960	Aqua: A Fast Decision Support System Using Approximate Query Answers	1999	VLDB	0.00015031055
995	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD	0.00014745185
1,065	Processing Complex Aggregate Queries over Data Streams	2002	SIGMOD	0.00014344675
1,161	VerdictDB: Universalizing Approximate Query Processing	2018	SIGMOD	0.00013579831
1,257	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00013002384
1,268	Proactive Re-Optimization	2005	SIGMOD	0.00012914584
1,331	ICICLES: Self-tuning Samples for Approximate Query Answering	2000	VLDB	0.00012553948
1,372	Random Sampling over Joins Revisited	2018	SIGMOD	0.0001233325
1,400	Wavelet Synopses with Error Guarantees	2002	SIGMOD	0.0001219602
1,536	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00011458359
1,735	SciBORQ: Scientific data management with Bounds On Runtime and Quality	2011	CIDR	0.00010713691
2,113	When Can We Trust Progress Estimators for SQL Queries?	2005	SIGMOD	9.5207583e-05
2,254	Two-Level Sampling for Join Size Estimation	2017	SIGMOD	9.1871115e-05
2,369	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	8.9462051e-05
2,377	Online Maintenance of Very Large Random Samples	2004	SIGMOD	8.9359321e-05
2,424	The Analytical Bootstrap: a New Method for Fast Error Estimation in Approximate Query Processing	2014	SIGMOD	8.8415494e-05
2,494	DBEst: Revisiting Approximate Query Processing Engines with Machine Learning Models	2019	SIGMOD	8.6457436e-05
2,589	Database Learning: Toward a Database that Becomes Smarter Every Time	2017	SIGMOD	8.4868591e-05
2,813	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD	8.0816314e-05
2,995	A Sampling Algebra for Aggregate Estimation	2013	VLDB	7.7606324e-05
3,013	Cardinality Estimation Using Sample Views with Quality Assurance	2007	SIGMOD	7.7082045e-05
3,054	Partial Results in Database Systems	2014	SIGMOD	7.6478475e-05
3,386	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS	7.151562e-05
3,402	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	7.134261e-05
3,597	Graph-Based Synopses for Relational Selectivity Estimation	2006	SIGMOD	6.9337747e-05
3,656	Conditional Selectivity for Statistics on Query Expressions	2004	SIGMOD	6.8712579e-05
3,664	Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams	2003	VLDB	6.8645092e-05
3,827	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD	6.7195959e-05
3,955	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB	6.5895015e-05
4,083	Distributed Online Aggregations	2009	VLDB	6.4583812e-05
4,100	A Bi-Level Bernoulli Scheme for Database Sampling	2004	SIGMOD	6.4473679e-05
4,353	Buffer Pool Aware Query Optimization	2005	CIDR	6.2535805e-05
4,545	Bounded Conjunctive Queries	2014	VLDB	6.0917464e-05
4,696	Deterministic Wavelet Thresholding for Maximum-Error Metrics	2004	PODS	5.9843254e-05
4,926	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8184457e-05
5,128	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	5.6728511e-05
5,547	Supporting Time-Constrained SQL Queries in Oracle	2007	VLDB	5.4452585e-05
5,817	BlinkML: Efficient Maximum Likelihood Estimation with Probabilistic Guarantees	2019	SIGMOD	5.3154329e-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.0040465394
14	Online Aggregation	1997	SIGMOD	0.0010813443
37	Statistical Estimators for Relational Algebra Expressions	1988	PODS	0.00075597514
60	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00064450997
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
92	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00051431888
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
250	Adaptive Selectivity Estimation Using Query Feedback	1994	SIGMOD	0.00030640525
270	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00029648047
431	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00023397171
553	Bifocal Sampling for Skew-Resistant Join Size Estimation	1996	SIGMOD	0.00020272747
803	On the Relative Cost of Sampling for Join Selectivity Estimation	1994	PODS	0.00016438972
2,056	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.6692561e-05
2,743	The Ins and Outs (and Everything in Between) of Data Warehousing	1996	SIGMOD	8.1936504e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,163	Computing Complex Temporal Join Queries Efficiently	2022	SIGMOD	4.5685178e-05
8,065	Efficient Computation of Quantiles over Joins	2023	PODS	4.5899218e-05
2,813	A Robust, Optimization-Based Approach for Approximate Answering of Aggregate Queries	2001	SIGMOD	8.0816314e-05
6,481	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.039683e-05
8,964	Reservoir Sampling over Joins	2024	SIGMOD	4.4163852e-05
5,085	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	5.7040225e-05
1,712	Approximate Join Processing Over Data Streams	2003	SIGMOD	0.00010786152
184	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00036655704
5,128	Efficient Join Synopsis Maintenance for Data Warehouse	2020	SIGMOD	5.6728511e-05
7,573	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7034681e-05