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
1768
Venue
PODS
Year
2018
Pagerank
0.00021283186
Overall Rank
321 | 97.80%
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 31 of 81 citing papers.

Rank Citing Paper Year Venue Pagerank
10,135 I Can't Believe It's Not Yannakakis: Pragmatic Bitmap Filters in Microsoft SQL Server 2026 CIDR 5.093636e-05
10,146 Acyclic Conjunctive Regular Path Queries are no Harder than Corresponding Conjunctive Queries 2026 PODS 5.093636e-05
10,153 Faster Relational Algorithms Using Geometric Data Structures 2026 PODS 5.093636e-05
10,155 FPT Parameterisations of Fractional and Generalised Hypertree Width 2026 PODS 5.093636e-05
10,160 Maintaining Queries under Updates Using Heavy-Light Partitioning of the Input Relations 2026 PODS 5.093636e-05
10,165 PANDAExpress: A Simpler and Faster PANDA Algorithm 2026 PODS 5.093636e-05
10,169 Towards Output-Optimal Uniform Sampling and Approximate Counting for Join-Project Queries 2026 PODS 5.093636e-05
10,182 The Space-Time Complexity of Sum-Product Queries 2026 PODS 5.093636e-05
10,188 Acyclic Graph Pattern Counting under Local Differential Privacy 2026 SIGMOD 5.093636e-05
10,221 Differentially Oblivious Multi-way Join 2026 SIGMOD 5.093636e-05
10,229 Efficient Meta-subgraph Instance Search over Large Heterogeneous Information Networks 2026 SIGMOD 5.093636e-05
10,312 BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching 2026 SIGMOD 5.093636e-05
10,375 GraphMatch: Subgraph Query Processing on Steroids 2026 SIGMOD 5.093636e-05
10,524 A Semantics-aware Approach for Graph Edit Distance Estimation over Knowledge Graphs 2026 VLDB 5.093636e-05
10,542 Secure Multi-Party Sampling over Joins 2026 VLDB 5.093636e-05
10,622 Towards Efficient Random-Order Enumeration for Join Queries 2026 VLDB 5.093636e-05
10,643 Fast Matrix Multiplication meets the Submodular Width 2025 PODS 5.093636e-05
10,754 Community Detection in Heterogeneous Information Networks Without Materialization 2025 SIGMOD 5.093636e-05
10,762 Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized 2025 SIGMOD 5.093636e-05
10,787 cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns 2025 SIGMOD 5.093636e-05
10,885 Efficient and Accurate Subgraph Counting: A Bottom-up Flow-learning Based Approach 2025 VLDB 5.093636e-05
11,144 Improved Approximation Algorithms for Relational Clustering 2024 PODS 5.093636e-05
11,183 Relational Algorithms for Top-k Query Evaluation 2024 SIGMOD 5.093636e-05
11,192 Atom: An Efficient Query Serving System for Embedding-based Knowledge Graph Reasoning with Operator-level Batching 2024 SIGMOD 5.093636e-05
11,205 Towards a Converged Relational-Graph Optimization Framework 2024 SIGMOD 5.093636e-05
11,338 A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition 2024 VLDB 5.093636e-05
11,421 Lightweight Materialization for Fast Dashboards Over Joins 2023 SIGMOD 5.093636e-05
11,520 Approximately Counting Subgraphs in Data Streams 2022 PODS 5.093636e-05
11,635 Two-Attribute Skew Free, Isolated CP Theorem, and Massively Parallel Joins 2021 PODS 5.093636e-05
11,677 Vertex-centric Parallel Computation of SQL Queries 2021 SIGMOD 5.093636e-05
11,819 Towards Multi-way Join Aware Optimizer in SAP HANA 2020 VLDB 5.093636e-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.0024089429
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010828372
89 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00035031529
106 The MADlib Analytics Library or MAD Skills, the SQL 2012 VLDB 0.00033539462
211 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024797217
358 FAQ: Questions Asked Frequently 2016 PODS 0.00020243592
382 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.00019546431
414 On the Complexity of Database Queries (Extended Abstract) 1997 PODS 0.00018893507
490 Design and Implementation of the LogicBlox System 2015 SIGMOD 0.000175757
518 Towards a Unified Architecture for in-RDBMS Analytics 2012 SIGMOD 0.00017167492
536 Learning Linear Regression Models over Factorized Joins 2016 SIGMOD 0.0001693369
715 Learning Generalized Linear Models Over Normalized Data 2015 SIGMOD 0.00014655327
814 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00013841737
1,058 Graphflow: An Active Graph Database 2017 SIGMOD 0.00012378784
1,109 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012142685
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,448 Skew in Parallel Query Processing 2014 PODS 0.00010758872
1,699 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 9.975915e-05
1,857 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.6047945e-05
1,998 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 9.3363505e-05
2,804 Demonstration of the Myria Big Data Management Service 2014 SIGMOD 8.1075524e-05
2,927 In-Database Learning with Sparse Tensors 2018 PODS 7.9531195e-05
3,284 SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning 2017 CIDR 7.5663058e-05
3,334 F: Regression Models over Factorized Views 2016 VLDB 7.5110164e-05
4,401 Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins 2016 PODS 6.7233577e-05
6,672 Computing Join Queries with Functional Dependencies 2016 PODS 5.8070233e-05
Previous Page 1 / 1 Next

Semantically Similar Papers