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
h2623ba99265381af
Venue
PODS
Year
2012
Pagerank
0.0001911958
Overall Rank
397 | 97.35%
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 64 citing papers.

Rank Citing Paper Year Venue Pagerank
208 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024929198
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020048899
467 Design and Implementation of the LogicBlox System 2015 SIGMOD 0.00017740891
522 Learning Linear Regression Models over Factorized Joins 2016 SIGMOD 0.00016893112
639 Answering Conjunctive Queries under Updates 2017 PODS 0.00015289346
706 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00014622696
1,096 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012035761
1,242 Communication Steps for Parallel Query Processing 2013 PODS 0.00011372366
1,253 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 0.00011316982
1,296 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00011119184
1,568 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 0.00010178045
1,609 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2019 SIGMOD 0.0001007196
1,734 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 9.7545941e-05
1,764 Kuzu* Graph Database Management System 2023 CIDR 9.6923285e-05
1,803 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2018 VLDB 9.5987229e-05
1,821 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.5466386e-05
2,128 Subgraph Matching: on Compression and Computation 2018 VLDB 8.9879343e-05
2,316 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.6404062e-05
2,974 In-Database Learning with Sparse Tensors 2018 PODS 7.7812156e-05
3,165 Robust Join Processing with Diamond Hardened Joins 2024 VLDB 7.5598778e-05
3,921 DunceCap: Query Plans Using Generalized Hypertree Decompositions 2015 SIGMOD 6.9059118e-05
4,011 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 6.842581e-05
4,099 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.7940875e-05
4,174 The Relational Data Borg is Learning 2020 VLDB 6.750725e-05
4,487 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.5628751e-05
4,497 Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins 2016 PODS 6.5592387e-05
4,527 Conjunctive Queries with Comparisons 2022 SIGMOD 6.5466033e-05
4,627 Worst-Case Optimal Graph Joins in Almost No Space 2021 SIGMOD 6.4801904e-05
4,730 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.4313418e-05
5,029 COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021 SIGMOD 6.2952031e-05
5,034 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 6.2921115e-05
5,089 Datalog Unchained 2021 PODS 6.2661323e-05
5,093 Join Dependency Testing, Loomis-Whitney Join, and Triangle Enumeration 2015 PODS 6.2653284e-05
5,512 Compressed Representations of Conjunctive Query Results 2018 PODS 6.0867282e-05
5,514 Fast Join Project Query Evaluation using Matrix Multiplication 2020 SIGMOD 6.0866191e-05
5,610 Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins 2021 PODS 6.0498245e-05
5,717 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 6.0067263e-05
6,539 Parallel Discrepancy Detection and Incremental Detection 2021 VLDB 5.7351897e-05
6,557 Ranked Enumeration of Join Queries with Projections 2022 VLDB 5.7298671e-05
6,585 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 5.7238683e-05
6,761 Computing Join Queries with Functional Dependencies 2016 PODS 5.6705551e-05
7,552 Fast Local Subgraph Counting 2024 VLDB 5.4802093e-05
7,888 Mind the Gap: Bridging Multi-Domain Query Workloads with EmptyHeaded 2017 VLDB 5.4161029e-05
8,238 Tight Fine-Grained Bounds for Direct Access on Join Queries 2022 PODS 5.3567801e-05
8,328 DunceCap: Compiling Worst-Case Optimal Query Plans 2015 SIGMOD 5.3380779e-05
8,517 SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries 2020 SIGMOD 5.3110227e-05
9,244 DPconv: Super-Polynomially Faster Join Ordering 2024 SIGMOD 5.1864409e-05
9,396 Extending SQL to Return a Subdatabase 2025 SIGMOD 5.1672232e-05
9,767 PAR2QO: Parametric Penalty-Aware Robust Query Optimization 2025 VLDB 5.115551e-05
10,181 How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches 2025 VLDB 5.0550978e-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