DBScholar

Back to papers

Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems

Summary: Tutorial survey of worst-case optimal join algorithms, connecting AGM-style output bounds and information-theoretic inequalities to executable algorithms. Reviews cross-disciplinary techniques, practical adoption, and foundational open problems. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID
hb713ddaebf75e4c5
Venue
PODS
Year
2018
Pagerank
0.00021246
Overall Rank
315 | 97.89%
DOI
10.1145/3196959.3196990

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{ngo_pods18,
        address = {New York, NY, USA},
        series = {{PODS} '18},
        title = {{Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems}},
        url = {https://dl.acm.org/doi/10.1145/3196959.3196990},
        doi = {10.1145/3196959.3196990},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ngo, Hung Q.},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 33 of 83 citing papers.

Rank Citing Paper Year Venue Pagerank
10,270 GraphMatch: Subgraph Query Processing on Steroids 2026 SIGMOD 5.0485061e-05
10,301 Worst-Case-Optimal Similarity Joins on Graph Databases 2024 SIGMOD 5.040157e-05
10,356 I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server 2026 CIDR 4.9793485e-05
10,363 Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries 2026 PODS 4.9793485e-05
10,370 Faster Relational Algorithms Using Geometric Data Structures 2026 PODS 4.9793485e-05
10,372 FPT Parameterisations of Fractional and Generalised Hypertree Width 2026 PODS 4.9793485e-05
10,377 Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations 2026 PODS 4.9793485e-05
10,382 PANDAExpress: A Simpler and Faster PANDA Algorithm 2026 PODS 4.9793485e-05
10,386 Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries 2026 PODS 4.9793485e-05
10,398 The Space-Time Complexity of Sum-Product Queries 2026 PODS 4.9793485e-05
10,404 Acyclic Graph Pattern Counting under Local Differential Privacy 2026 SIGMOD 4.9793485e-05
10,437 Differentially Oblivious Multi-way Join 2026 SIGMOD 4.9793485e-05
10,445 Efficient Meta-subgraph Instance Search over Large Heterogeneous Information Networks 2026 SIGMOD 4.9793485e-05
10,708 A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs 2026 VLDB 4.9793485e-05
10,724 Secure Multi-Party Sampling over Joins 2026 VLDB 4.9793485e-05
10,768 One Join Order Does Not Fit All: Reducing Intermediate Results with Per-Split Query Plans 2026 VLDB 4.9793485e-05
10,854 Worst-Case Optimal BGPs on Temporal Graphs 2026 VLDB 4.9793485e-05
11,068 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB 4.9793485e-05
11,086 Fast Matrix Multiplication meets the Submodular Width 2025 PODS 4.9793485e-05
11,180 Community Detection in Heterogeneous Information Networks Without Materialization 2025 SIGMOD 4.9793485e-05
11,185 Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized 2025 SIGMOD 4.9793485e-05
11,203 cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns 2025 SIGMOD 4.9793485e-05
11,286 Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach 2025 VLDB 4.9793485e-05
11,492 Improved Approximation Algorithms for Relational Clustering 2024 PODS 4.9793485e-05
11,526 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 4.9793485e-05
11,535 Atom: An Efficient Query Serving System for Embedding-based Knowledge Graph Reasoning with Operator-level Batching 2024 SIGMOD 4.9793485e-05
11,546 Towards a Converged Relational-Graph Optimization Framework 2024 SIGMOD 4.9793485e-05
11,656 A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition 2024 VLDB 4.9793485e-05
11,735 Lightweight Materialization for Fast Dashboards Over Joins 2023 SIGMOD 4.9793485e-05
11,829 Approximately Counting Subgraphs in Data Streams 2022 PODS 4.9793485e-05
11,942 Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins 2021 PODS 4.9793485e-05
11,984 Vertex-centric Parallel Computation of SQL Queries 2021 SIGMOD 4.9793485e-05
12,121 Towards Multi-way Join Aware Optimizer in SAP HANA 2020 VLDB 4.9793485e-05
Previous Page 2 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 27 of 27 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
1 Access Path Selection in a Relational Database Management System 1979 SIGMOD 0.0023947656
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010679641
91 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.0003475226
105 The MADlib Analytics Library or MAD Skills, the SQL 2012 VLDB 0.00033638251
208 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024884544
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020020639
390 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.00019248147
421 On the Complexity of Database Queries (Extended Abstract) 1997 PODS 0.00018516535
466 Design and Implementation of the LogicBlox System 2015 SIGMOD 0.00017773029
503 Towards a Unified Architecture for in-RDBMS Analytics 2012 SIGMOD 0.00017202276
521 Learning Linear Regression Models over Factorized Joins 2016 SIGMOD 0.00016929744
730 Learning Generalized Linear Models Over Normalized Data 2015 SIGMOD 0.00014406936
818 Hypertree Decompositions: Questions and Answers 2016 PODS 0.0001366708
1,045 Graphflow: An Active Graph Database 2017 SIGMOD 0.00012322402
1,091 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012074152
1,249 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 0.00011340141
1,292 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00011152286
1,481 Skew in Parallel Query Processing 2014 PODS 0.00010539119
1,725 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 9.7902443e-05
1,812 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.5803973e-05
2,043 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 9.1406885e-05
2,796 Demonstration of the Myria Big Data Management Service 2014 SIGMOD 7.9971623e-05
2,975 In-Database Learning with Sparse Tensors 2018 PODS 7.7907759e-05
3,330 SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning 2017 CIDR 7.4173693e-05
3,373 F: Regression Models over Factorized Views 2016 VLDB 7.3661025e-05
4,475 Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins 2016 PODS 6.5838041e-05
6,739 Computing Join Queries with Functional Dependencies 2016 PODS 5.6917027e-05
Previous Page 1 / 1 Next

Semantically Similar Papers