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

Rank Citing Paper Year Venue Pagerank
1,180 In-Memory Subgraph Matching: An In-depth Study 2020 SIGMOD 0.00011627669
1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010127607
2,014 RapidMatch: A Holistic Approach to Subgraph Query Processing 2021 VLDB 9.1832045e-05
2,160 DIFF: A Relational Interface for Large-Scale Data Explanation 2019 VLDB 8.9364035e-05
2,299 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.6727773e-05
2,591 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2468757e-05
2,634 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1993804e-05
2,846 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.9453616e-05
3,160 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.5807496e-05
3,187 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 7.5546613e-05
3,494 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 7.2582926e-05
3,880 Distributed Subgraph Matching on Timely Dataflow 2019 VLDB 6.9510799e-05
3,972 TCUDB: Accelerating Database with Tensor Processors 2022 SIGMOD 6.8881464e-05
4,075 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.8188389e-05
4,369 Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries 2024 CIDR 6.6315141e-05
4,605 Worst-Case Optimal Graph Joins in Almost No Space 2021 SIGMOD 6.5047683e-05
4,752 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.434561e-05
4,874 Rel: A Programming Language for Relational Data 2025 SIGMOD 6.3727742e-05
4,950 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.3421691e-05
5,010 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 6.3149028e-05
5,449 High-Performance Row Pattern Recognition Using Joins 2023 VLDB 6.1254016e-05
5,482 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.111411e-05
5,902 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9536872e-05
5,918 Join Size Bounds using l_p-Norms on Degree Sequences 2024 PODS 5.9481539e-05
5,984 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 5.926237e-05
6,429 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.7884926e-05
6,531 Query Evaluation by Circuits 2022 PODS 5.754708e-05
6,567 Fast Matrix Multiplication for Query Processing 2024 PODS 5.7469783e-05
6,573 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 5.7455776e-05
6,805 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6780394e-05
6,876 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 5.6586279e-05
6,955 The Complexity of Boolean Conjunctive Queries with Intersection Joins 2022 PODS 5.6342744e-05
7,292 Computing the Difference of Conjunctive Queries Efficiently 2023 SIGMOD 5.5642569e-05
7,367 ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning 2023 VLDB 5.5411636e-05
7,609 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 5.4847975e-05
7,774 Adaptive Factorization Using Linear-Chained Hash Tables 2025 CIDR 5.4549846e-05
7,939 GraphINC: Graph Pattern Mining at Network Speed 2023 SIGMOD 5.4223464e-05
8,166 Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints 2020 SIGMOD 5.3849926e-05
8,212 Tight Fine-Grained Bounds for Direct Access on Join Queries 2022 PODS 5.3770972e-05
8,279 Subset Sampling over Joins 2026 PODS 5.3637624e-05
8,531 GRainDB: A Relational-core Graph-Relational DBMS 2022 CIDR 5.3218647e-05
8,832 On Reporting Durable Patterns in Temporal Proximity Graphs 2024 PODS 5.2680847e-05
9,224 An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication 2025 PODS 5.2056825e-05
9,410 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 5.1826718e-05
9,933 Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction 2021 PODS 5.1100666e-05
10,103 Still Asking: How Good Are Query Optimizers, Really? 2025 VLDB 5.0789354e-05
10,127 A Modular Graph-Native Query Optimization Framework 2025 SIGMOD 5.0751052e-05
10,182 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 5.0651993e-05
10,251 TenGraph: A Tensor-Based Graph Query Engine 2024 VLDB 5.0513876e-05
10,253 BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching 2026 SIGMOD 5.050482e-05
Previous Page 1 / 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