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.00019095982
Overall Rank
402 | 97.30%
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 63 citing papers.

Rank Citing Paper Year Venue Pagerank
208 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024899872
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020013731
466 Design and Implementation of the LogicBlox System 2015 SIGMOD 0.00017765702
521 Learning Linear Regression Models over Factorized Joins 2016 SIGMOD 0.00016923519
637 Answering Conjunctive Queries under Updates 2017 PODS 0.00015334386
713 Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins 2019 VLDB 0.00014571507
1,091 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012068611
1,233 Communication Steps for Parallel Query Processing 2013 PODS 0.00011404978
1,252 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 0.00011334813
1,292 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00011147959
1,570 AJAR: Aggregations and Joins over Annotated Relations 2016 PODS 0.0001020376
1,605 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2019 SIGMOD 0.00010095581
1,726 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 9.7857214e-05
1,753 Kuzu* Graph Database Management System 2023 CIDR 9.7244117e-05
1,800 SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning 2018 VLDB 9.6082185e-05
1,813 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.5759542e-05
2,168 Subgraph Matching: on Compression and Computation 2018 VLDB 8.9292584e-05
2,302 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.6687541e-05
2,978 In-Database Learning with Sparse Tensors 2018 PODS 7.7872011e-05
3,154 Robust Join Processing with Diamond Hardened Joins 2024 VLDB 7.5849549e-05
3,909 DunceCap: Query Plans Using Generalized Hypertree Decompositions 2015 SIGMOD 6.9287689e-05
3,994 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 6.8652819e-05
4,077 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.8156109e-05
4,161 The Relational Data Borg is Learning 2020 VLDB 6.7669004e-05
4,466 Instance and Output Optimal Parallel Algorithms for Acyclic Joins 2019 PODS 6.584648e-05
4,477 Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins 2016 PODS 6.580699e-05
4,510 Conjunctive Queries with Comparisons 2022 SIGMOD 6.5673056e-05
4,607 Worst-Case Optimal Graph Joins in Almost No Space 2021 SIGMOD 6.501689e-05
4,745 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.4369578e-05
5,006 COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021 SIGMOD 6.3159614e-05
5,013 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 6.3119508e-05
5,070 Datalog Unchained 2021 PODS 6.2869206e-05
5,072 Join Dependency Testing, Loomis-Whitney Join, and Triangle Enumeration 2015 PODS 6.2860922e-05
5,491 Fast Join Project Query Evaluation using Matrix Multiplication 2020 SIGMOD 6.1067499e-05
5,492 Compressed Representations of Conjunctive Query Results 2018 PODS 6.1066968e-05
5,596 Cover or Pack: New Upper and Lower Bounds for Massively Parallel Joins 2021 PODS 6.0698953e-05
5,904 Combining Sampling and Synopses with Worst-Case Optimal Runtime and Quality Guarantees for Graph Pattern Cardinality Estimation 2021 SIGMOD 5.9511271e-05
6,528 Parallel Discrepancy Detection and Incremental Detection 2021 VLDB 5.7540798e-05
6,547 Ranked Enumeration of Join Queries with Projections 2022 VLDB 5.7488764e-05
6,576 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 5.7428578e-05
6,745 Computing Join Queries with Functional Dependencies 2016 PODS 5.6890943e-05
7,535 Fast Local Subgraph Counting 2024 VLDB 5.4983904e-05
7,872 Mind the Gap: Bridging Multi-Domain Query Workloads with EmptyHeaded 2017 VLDB 5.4339723e-05
8,219 Tight Fine-Grained Bounds for Direct Access on Join Queries 2022 PODS 5.3745518e-05
8,314 DunceCap: Compiling Worst-Case Optimal Query Plans 2015 SIGMOD 5.3557545e-05
8,501 SPRINTER: A Fast n-ary Join Query Processing Method for Complex OLAP Queries 2020 SIGMOD 5.3285575e-05
9,221 DPconv: Super-Polynomially Faster Join Ordering 2024 SIGMOD 5.2036474e-05
9,370 Extending SQL to Return a Subdatabase 2025 SIGMOD 5.1843659e-05
9,735 PAR2QO: Parametric Penalty-Aware Robust Query Optimization 2025 VLDB 5.1325223e-05
10,144 How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches 2025 VLDB 5.0718686e-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