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 34 of 84 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,815	StatAdvisor: Recommending Statistical Views	2009	VLDB	5.3165295e-05
5,951	PGMJoins: Random Join Sampling with Graphical Models	2021	SIGMOD	5.2592385e-05
5,976	Responsible Data Integration: Next-generation Challenges	2022	SIGMOD	5.245976e-05
6,157	Compression Aware Physical Database Design	2011	VLDB	5.1801143e-05
6,278	Uncertainty Aware Query Execution Time Prediction	2014	VLDB	5.1309442e-05
6,330	Efficient Construction of Approximate Ad-Hoc ML models Through Materialization and Reuse	2018	VLDB	5.1077416e-05
6,338	RPJ: Producing Fast Join Results on Streams through Rate-based Optimization	2005	SIGMOD	5.105321e-05
6,411	Approximate Query Engines: Commercial Challenges and Research Opportunities	2017	SIGMOD	5.0752468e-05
6,491	Robust Estimation With Sampling and Approximate Pre-Aggregation	2003	VLDB	5.0429323e-05
6,493	Joins on Samples: A Theoretical Guide for Practitioners	2020	VLDB	5.0424713e-05
6,548	Query Sampling in DB2 Universal Database	2004	SIGMOD	5.0181595e-05
6,695	Maintaining Acyclic Foreign-Key Joins under Updates	2020	SIGMOD	4.9582125e-05
6,829	Depth Estimation for Ranking Query Optimization	2007	VLDB	4.9136064e-05
7,358	Weighted Distinct Sampling: Cardinality Estimation for SPJ Queries	2021	SIGMOD	4.7529363e-05
7,581	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7057641e-05
7,759	Dscaler: Synthetically Scaling A Given Relational Database	2016	VLDB	4.6593145e-05
7,828	Modeling Shifting Workloads for Learned Database Systems	2024	SIGMOD	4.6407986e-05
7,920	JoinBoost: Grow Trees Over Normalized Data Using Only SQL	2023	VLDB	4.6163888e-05
8,181	Foreign Keys Open the Door for Faster Incremental View Maintenance	2023	SIGMOD	4.5660166e-05
8,350	alpha to omega: The Greek Alphabet of Sampling	2020	CIDR	4.5404832e-05
8,959	Reservoir Sampling over Joins	2024	SIGMOD	4.4206222e-05
9,061	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB	4.4039656e-05
9,621	ShadowAQP: Efficient Approximate Group-by and Join Query via Attribute-oriented Sample Size Allocation and Data Generation	2023	VLDB	4.3167167e-05
9,800	Cquirrel: Continuous Query Processing over Acyclic Relational Schemas	2021	VLDB	4.2818172e-05
9,949	AB-tree: Index for Concurrent Random Sampling and Updates	2022	VLDB	4.2421586e-05
9,950	Distributed Wavelet Thresholding for Maximum Error Metrics	2016	SIGMOD	4.2421586e-05
10,197	Qualitative Join Discovery in Data Lakes using Examples	2026	SIGMOD	4.1945683e-05
10,254	Secure Multi-Party Sampling over Joins	2026	VLDB	4.1945683e-05
10,497	PilotDB: Database-Agnostic Online Approximate Query Processing with A Priori Error Guarantees	2025	SIGMOD	4.1945683e-05
10,981	Enabling Adaptive Sampling for Intra-Window Join: Simultaneously Optimizing Quantity and Quality	2024	SIGMOD	4.1945683e-05
11,453	XLJoins	2021	SIGMOD	4.1945683e-05
11,711	Demonstration of VerdictDB, the Platform-Independent AQP System	2018	SIGMOD	4.1945683e-05
11,897	Capturing the Laws of (Data) Nature	2015	CIDR	4.1945683e-05
12,019	When Data Management Systems Meet Approximate Hardware: Challenges and Opportunities	2014	VLDB	4.1945683e-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