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

Rank Citing Paper Year Venue Pagerank
1,237 In-Memory Subgraph Matching: An In-depth Study 2020 SIGMOD 0.00011545768
1,740 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 9.875587e-05
2,035 RapidMatch: A Holistic Approach to Subgraph Query Processing 2021 VLDB 9.2787188e-05
2,161 DIFF: A Relational Interface for Large-Scale Data Explanation 2019 VLDB 9.0606664e-05
2,266 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.8391372e-05
2,731 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1959181e-05
2,745 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.1747954e-05
2,991 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.8880723e-05
3,136 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 7.7210541e-05
3,283 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.56675e-05
3,453 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 7.4004131e-05
3,821 Distributed Subgraph Matching on Timely Dataflow 2019 VLDB 7.0933895e-05
4,089 TCUDB: Accelerating Database with Tensor Processors 2022 SIGMOD 6.9096857e-05
4,553 Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries 2024 CIDR 6.6346951e-05
4,753 Worst-Case Optimal Graph Joins in Almost No Space 2021 SIGMOD 6.5231863e-05
4,983 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.4127092e-05
5,321 High-Performance Row Pattern Recognition Using Joins 2023 VLDB 6.2659937e-05
5,529 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.18591e-05
5,593 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1552328e-05
5,601 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.1540123e-05
5,761 Rel: A Programming Language for Relational Data 2025 SIGMOD 6.0957569e-05
5,781 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 6.0910397e-05
5,870 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 6.061038e-05
6,257 Join Size Bounds using l_p-Norms on Degree Sequences 2024 PODS 5.9397944e-05
6,301 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.9213518e-05
6,398 Query Evaluation by Circuits 2022 PODS 5.8867918e-05
6,434 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.8799421e-05
6,444 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 5.8774519e-05
6,732 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 5.7885064e-05
6,885 Fast Matrix Multiplication for Query Processing 2024 PODS 5.7464502e-05
7,161 Computing the Difference of Conjunctive Queries Efficiently 2023 SIGMOD 5.6852987e-05
7,386 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6273882e-05
7,451 The Complexity of Boolean Conjunctive Queries with Intersection Joins 2022 PODS 5.6135032e-05
7,978 ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning 2023 VLDB 5.514996e-05
8,002 Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints 2020 SIGMOD 5.5085906e-05
8,047 Tight Fine-Grained Bounds for Direct Access on Join Queries 2022 PODS 5.500514e-05
8,179 GraphINC: Graph Pattern Mining at Network Speed 2023 SIGMOD 5.472762e-05
8,232 Adaptive Factorization Using Linear-Chained Hash Tables 2025 CIDR 5.4612012e-05
8,235 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 5.4608734e-05
8,376 GRainDB: A Relational-core Graph-Relational DBMS 2022 CIDR 5.4389021e-05
8,691 On Reporting Durable Patterns in Temporal Proximity Graphs 2024 PODS 5.3839057e-05
9,048 An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication 2025 PODS 5.3251649e-05
9,235 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 5.3016261e-05
9,719 Subset Sampling over Joins 2026 PODS 5.2319816e-05
9,755 Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction 2021 PODS 5.2273544e-05
9,920 Still Asking: How Good Are Query Optimizers, Really? 2025 VLDB 5.1955087e-05
9,942 A Modular Graph-Native Query Optimization Framework 2025 SIGMOD 5.1915905e-05
9,994 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 5.1814573e-05
10,060 TenGraph: A Tensor-Based Graph Query Engine 2024 VLDB 5.166346e-05
10,087 Worst-Case-Optimal Similarity Joins on Graph Databases 2024 SIGMOD 5.1558402e-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.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