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.00021517145
Overall Rank: 503 | 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
341	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00026850764
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
610	Design and Implementation of the LogicBlox System	2015	SIGMOD	0.00019204048
770	Answering Conjunctive Queries under Updates	2017	PODS	0.0001686092
832	Learning Linear Regression Models over Factorized Joins	2016	SIGMOD	0.00016089705
1,334	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00012543633
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.00012118832
1,452	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011922523
1,556	Beyond Worst-case Analysis for Joins with Minesweeper	2014	PODS	0.00011383141
1,938	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025547
1,948	Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows	2018	VLDB	9.9938634e-05
2,154	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2018	VLDB	9.4176683e-05
2,173	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	9.3767985e-05
2,222	SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning	2019	SIGMOD	9.2598438e-05
2,298	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0746479e-05
2,962	Kuzu* Graph Database Management System	2023	CIDR	7.8069285e-05
2,963	Subgraph Matching: on Compression and Computation	2018	VLDB	7.8061004e-05
3,009	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	7.7230513e-05
4,430	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1879319e-05
4,466	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	6.1545841e-05
4,709	Instance and Output Optimal Parallel Algorithms for Acyclic Joins	2019	PODS	5.9744219e-05
4,783	Join Dependency Testing, Loomis-Whitney Join, and Triangle Enumeration	2015	PODS	5.9215677e-05
4,787	The Relational Data Borg is Learning	2020	VLDB	5.9168117e-05
5,050	DunceCap: Query Plans Using Generalized Hypertree Decompositions	2015	SIGMOD	5.7268774e-05
5,085	Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins	2023	PODS	5.7040225e-05
5,503	Worst-Case Optimal Graph Joins in Almost No Space	2021	SIGMOD	5.4718854e-05
5,650	Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins	2021	PODS	5.3887172e-05
5,716	Datalog Unchained	2021	PODS	5.3569788e-05
5,728	Conjunctive Queries with Comparisons	2022	SIGMOD	5.350072e-05
5,845	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3057391e-05
5,886	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	5.2847297e-05
5,968	A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction	2024	SIGMOD	5.2469955e-05
6,294	Free Join: Unifying Worst-Case Optimal and Traditional Joins	2023	SIGMOD	5.1202075e-05
6,647	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	4.9729424e-05
6,691	Parallel Discrepancy Detection and Incremental Detection	2021	VLDB	4.9573939e-05
6,705	Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation	2021	SIGMOD	4.9507418e-05
6,822	Computing Join Queries with Functional Dependencies	2016	PODS	4.9101655e-05
7,165	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.807833e-05
7,721	Mind the Gap: Bridging Multi-Domain Query Workloads with EmptyHeaded	2017	VLDB	4.6631706e-05
7,936	Fast Local Subgraph Counting	2024	VLDB	4.6089395e-05
8,029	Tight Fine-Grained Bounds for Direct Access on Join Queries	2022	PODS	4.598451e-05
8,195	DunceCap: Compiling Worst-Case Optimal Query Plans	2015	SIGMOD	4.5573236e-05
8,423	SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries	2020	SIGMOD	4.5112315e-05
8,587	Output-Optimal Algorithms for Join-Aggregate Queries	2025	PODS	4.4853975e-05
9,034	Extending SQL to Return a Subdatabase	2025	SIGMOD	4.3997447e-05
9,843	Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints	2025	PODS	4.2680295e-05
9,956	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB	4.2332427e-05
10,009	The Space-Time Complexity of Sum-Product Queries	2026	PODS	4.1905499e-05
10,104	Query Optimization for Database-Returning Queries	2026	SIGMOD	4.1905499e-05
10,236	A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs	2026	VLDB	4.1905499e-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
63	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00063595699
100	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050033475
116	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00046191288
325	The History of Histograms (abridged)	2003	VLDB	0.00027398081
326	Optimal Histograms with Quality Guarantees	1998	VLDB	0.0002737538
550	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00020346247
623	Generalized Hypertree Decompositions: NP-Hardness and Tractable Variants	2007	PODS	0.00018976192
1,268	Proactive Re-Optimization	2005	SIGMOD	0.00012914584
1,536	Lightweight Graphical Models for Selectivity Estimation Without Independence Assumptions	2011	VLDB	0.00011458359
1,691	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	0.00010890775
1,919	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD	0.00010097452
2,359	Consistently Estimating the Selectivity of Conjuncts of Predicates	2005	VLDB	8.967267e-05
3,519	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.0181381e-05
5,752	Size and Treewidth Bounds for Conjunctive Queries	2009	PODS	5.3393414e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
100	On the Propagation of Errors in the Size of Join Results	1991	SIGMOD	0.00050033475
4,430	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS	6.1879319e-05
3,519	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.0181381e-05
5,963	Beyond Equi-joins: Ranking, Enumeration and Factorization	2021	VLDB	5.2485815e-05
8,149	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5715614e-05
6,647	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD	4.9729424e-05
1,621	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011105663
2,298	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.0746479e-05
4,926	On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms	2023	PODS	5.8184457e-05
2,281	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.122455e-05