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 5 of 55 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,324	Towards Efficient Random-Order Enumeration for Join Queries	2026	VLDB	4.1945683e-05
10,514	cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns	2025	SIGMOD	4.1945683e-05
10,751	PAR2QO: Parametric Penalty-Aware Robust Query Optimization	2025	VLDB	4.1945683e-05
10,987	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	4.1945683e-05
11,703	Worst Case Optimal Joins on Relational and XML data	2018	SIGMOD	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