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)
Incoming Non-self Citations Over Time
Authors
- 1. Hung Q. Ngo (State University of New York at Buffalo)
- 2. Ely Porat (Bar-Ilan University)
- 3. Christopher Ré (University of Wisconsin)
- 4. Atri Rudra (State University of New York at Buffalo)
BibTeX Citation
@inproceedings{ngo_pods12,
address = {New York, NY, USA},
series = {{PODS} '12},
title = {{Worst-case Optimal Join Algorithms}},
url = {https://dl.acm.org/doi/10.1145/2213556.2213565},
doi = {10.1145/2213556.2213565},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Ngo, Hung Q. and Porat, Ely and Ré, Christopher and Rudra, Atri},
year = {2012}
}Incoming Citations (Sorted by Pagerank)
Showing 11 of 61 citing papers.
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.
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 3,617 | Scalable Computation of Acyclic Joins (Extended Abstract) | 2006 | PODS |
| 2 | 5,593 | Beyond Equi-joins: Ranking, Enumeration and Factorization | 2021 | VLDB |
| 3 | 7,882 | Efficiently Computing Join Orders with Heuristic Search | 2023 | SIGMOD |
| 4 | 10,169 | Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries | 2026 | PODS |
| 5 | 5,364 | Fast Join Project Query Evaluation using Matrix Multiplication | 2020 | SIGMOD |
| 6 | 1,286 | Adaptive Optimization of Very Large Join Queries | 2018 | SIGMOD |
| 7 | 1,857 | Joins via Geometric Resolutions: Worst-case and Beyond | 2015 | PODS |
| 8 | 3,453 | On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms | 2023 | PODS |
| 9 | 1,740 | Adopting Worst-Case Optimal Joins in Relational Database Systems | 2020 | VLDB |
| 10 | 321 | Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems | 2018 | PODS |