DBScholar

Back to papers

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
1562
Venue
PODS
Year
2012
Pagerank
0.00018902089
Overall Rank
411 | 97.19%
DOI
10.1145/2213556.2213565

Incoming Non-self Citations Over Time

Authors

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 50 of 61 citing papers.

Rank Citing Paper Year Venue Pagerank
211 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024797217
358 FAQ: Questions Asked Frequently 2016 PODS 0.00020243592
490 Design and Implementation of the LogicBlox System 2015 SIGMOD 0.000175757
536 Learning Linear Regression Models over Factorized Joins 2016 SIGMOD 0.0001693369
636 Answering Conjunctive Queries under Updates 2017 PODS 0.0001551856
809 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00013874588
1,109 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012142685
1,207 Communication Steps for Parallel Query Processing 2013 PODS 0.00011663155
1,246 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 0.00011504088
1,320 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00011166426
1,549 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 0.00010390168
1,699 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 9.975915e-05
1,712 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2019 SIGMOD 9.9492299e-05
1,815 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2018 VLDB 9.6894541e-05
1,857 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.6047945e-05
2,126 Kuzu* Graph Database Management System 2023 CIDR 9.1329991e-05
2,187 Subgraph Matching: on Compression and Computation 2018 VLDB 8.9966682e-05
2,266 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.8391372e-05
2,927 In-Database Learning with Sparse Tensors 2018 PODS 7.9531195e-05
3,622 Robust Join Processing with Diamond Hardened Joins 2024 VLDB 7.2465862e-05
3,841 DunceCap: Query Plans Using Generalized Hypertree Decompositions 2015 SIGMOD 7.0808098e-05
3,941 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 7.0074268e-05
4,128 The Relational Data Borg is Learning 2020 VLDB 6.8850804e-05
4,371 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.738679e-05
4,401 Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins 2016 PODS 6.7233577e-05
4,575 Conjunctive Queries with Comparisons 2022 SIGMOD 6.6223692e-05
4,753 Worst-Case Optimal Graph Joins in Almost No Space 2021 SIGMOD 6.5231863e-05
4,900 COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021 SIGMOD 6.4534715e-05
4,943 Datalog Unchained 2021 PODS 6.4332239e-05
4,949 Join Dependency Testing, Loomis-Whitney Join, and Triangle Enumeration 2015 PODS 6.4314032e-05
4,983 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.4127092e-05
5,364 Fast Join Project Query Evaluation using Matrix Multiplication 2020 SIGMOD 6.2472125e-05
5,383 Compressed Representations of Conjunctive Query Results 2018 PODS 6.2374576e-05
5,463 Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins 2021 PODS 6.2086169e-05
5,601 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.1540123e-05
5,781 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 6.0910397e-05
6,325 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 5.9125893e-05
6,403 Parallel Discrepancy Detection and Incremental Detection 2021 VLDB 5.8859374e-05
6,412 Ranked Enumeration of Join Queries with Projections 2022 VLDB 5.8836116e-05
6,444 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 5.8774519e-05
6,672 Computing Join Queries with Functional Dependencies 2016 PODS 5.8070233e-05
7,733 Mind the Gap: Bridging Multi-Domain Query Workloads with EmptyHeaded 2017 VLDB 5.5564458e-05
8,047 Tight Fine-Grained Bounds for Direct Access on Join Queries 2022 PODS 5.500514e-05
8,168 DunceCap: Compiling Worst-Case Optimal Query Plans 2015 SIGMOD 5.4743814e-05
8,251 Fast Local Subgraph Counting 2024 VLDB 5.4574671e-05
8,374 SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries 2020 SIGMOD 5.4399097e-05
9,042 DPconv: Super-Polynomially Faster Join Ordering 2024 SIGMOD 5.3256042e-05
9,183 Extending SQL to Return a Subdatabase 2025 SIGMOD 5.3058708e-05
9,994 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 5.1814573e-05
10,106 How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches 2025 VLDB 5.1435736e-05
Previous Page 1 / 2 Next

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