Worst-case Optimal Join Algorithms

Summary: Algorithm for natural joins that attains the AGM fractional-cover bound, i.e., worst-case optimal runtime and provably superior to some project-join plans. Provides a constructive, entropy-free proof linking the bound to Bollobás–Thomason/Loomis–Whitney and extends to relaxed joins. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1563
Venue: PODS
Year: 2012
Pagerank: 0.00021526612
Overall Rank: 502 | 96.51%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 55 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
342	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026795977
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
613	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.00019181325
772	Answering Conjunctive Queries under Updates	2017	PODS	0.00016876498
834	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016135159
1,333	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00012523806
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.0001212565
1,442	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011956109
1,557	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	0.00011392493
1,939	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025655
1,953	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	9.9665955e-05
2,156	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2018	VLDB	9.4170209e-05
2,169	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	9.3845975e-05
2,219	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	9.2623533e-05
2,296	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0776226e-05
2,962	Kuzu* Graph Database Management System	2023	CIDR	7.8101752e-05
2,997	Subgraph Matching: on Compression and Computation	2018	VLDB	7.7559339e-05
3,006	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	7.7299363e-05
4,432	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1938383e-05
4,465	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	6.1604282e-05
4,708	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	5.980172e-05
4,779	Join Dependency Testing, Loomis-Whitney Join, and Triangle Enumeration	2015	PODS	5.9271735e-05
4,787	The Relational Data Borg is Learning	2020	VLDB	5.9224501e-05
5,053	DunceCap: Query Plans Using Generalized Hypertree Decompositions	2015	SIGMOD	5.7323846e-05
5,104	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	5.6946113e-05
5,493	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	5.4771449e-05
5,639	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	5.393897e-05
5,705	Datalog Unchained	2021	PODS	5.3621239e-05
5,718	Conjunctive Queries with Comparisons	2022	SIGMOD	5.3552123e-05
5,855	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3006096e-05
5,880	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	5.2898074e-05
6,281	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	5.128862e-05
6,305	Free Join: Unifying Worst-Case Optimal and Traditional Joins	2023	SIGMOD	5.1209718e-05
6,647	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	4.9772122e-05
6,690	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	4.9621556e-05
6,704	Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation	2021	SIGMOD	4.9554912e-05
6,824	Computing Join Queries with Functional Dependencies	2016	PODS	4.9144789e-05
7,166	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.8124491e-05
7,723	Mind the Gap: Bridging Multi-Domain Query Workloads with EmptyHeaded	2017	VLDB	4.6676712e-05
7,934	Fast Local Subgraph Counting	2024	VLDB	4.613363e-05
8,028	Tight Fine-Grained Bounds for Direct Access on Join Queries	2022	PODS	4.6028646e-05
8,195	DunceCap: Compiling Worst-Case Optimal Query Plans	2015	SIGMOD	4.561696e-05
8,432	SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries	2020	SIGMOD	4.5153924e-05
8,589	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4897014e-05
9,031	Extending SQL to Return a Subdatabase	2025	SIGMOD	4.4039656e-05
9,843	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS	4.2721228e-05
9,957	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB	4.2373024e-05
10,009	The Space-Time Complexity of Sum-Product Queries	2026	PODS	4.1945683e-05
10,104	Query Optimization for Database-Returning Queries	2026	SIGMOD	4.1945683e-05
10,236	A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs	2026	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
64	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063612837
99	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050022914
115	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00046221215
325	The History of Histograms (abridged)	2003	VLDB	0.00027378328
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.00027358981
549	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020376603
626	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00018973823
1,272	Proactive Re-Optimization	2005	SIGMOD	0.00012920076
1,547	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00011442359
1,695	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	0.00010882793
1,915	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD	0.00010104123
2,356	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	8.9620762e-05
3,515	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.0220813e-05
5,744	Size and Treewidth Bounds for Conjunctive Queries	2009	PODS	5.3441438e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
99	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050022914
4,432	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1938383e-05
3,515	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.0220813e-05
5,962	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2536266e-05
8,164	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5718104e-05
6,647	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	4.9772122e-05
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
2,296	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0776226e-05
4,953	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8085795e-05
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05