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.00021236408
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.00011622165
1,596 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010122962
2,017 RapidMatch: A Holistic Approach to Subgraph Query Processing 2021 VLDB 9.1788573e-05
2,162 DIFF: A Relational Interface for Large-Scale Data Explanation 2019 VLDB 8.9344773e-05
2,302 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.6687541e-05
2,593 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2429717e-05
2,635 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1954989e-05
2,844 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.9446987e-05
3,161 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.5771609e-05
3,188 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 7.5510881e-05
3,494 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 7.2548566e-05
3,881 Distributed Subgraph Matching on Timely Dataflow 2019 VLDB 6.9477894e-05
3,974 TCUDB: Accelerating Database with Tensor Processors 2022 SIGMOD 6.8848857e-05
4,077 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.8156109e-05
4,371 Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries 2024 CIDR 6.6284915e-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
4,877 Rel: A Programming Language for Relational Data 2025 SIGMOD 6.3697574e-05
4,945 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.3418058e-05
5,013 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 6.3119508e-05
5,454 High-Performance Row Pattern Recognition Using Joins 2023 VLDB 6.1225019e-05
5,487 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.1085184e-05
5,895 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9534254e-05
5,910 Join Size Bounds using l_p-Norms on Degree Sequences 2024 PODS 5.9478947e-05
5,984 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 5.9234316e-05
6,432 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.7857524e-05
6,533 Query Evaluation by Circuits 2022 PODS 5.7519838e-05
6,569 Fast Matrix Multiplication for Query Processing 2024 PODS 5.7442578e-05
6,576 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 5.7428578e-05
6,811 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6754603e-05
6,881 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 5.6559492e-05
6,958 The Complexity of Boolean Conjunctive Queries with Intersection Joins 2022 PODS 5.6316072e-05
7,294 Computing the Difference of Conjunctive Queries Efficiently 2023 SIGMOD 5.5616228e-05
7,372 ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning 2023 VLDB 5.5385404e-05
7,616 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 5.4822011e-05
7,768 Adaptive Factorization Using Linear-Chained Hash Tables 2025 CIDR 5.4548741e-05
7,943 GraphINC: Graph Pattern Mining at Network Speed 2023 SIGMOD 5.4197795e-05
8,172 Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints 2020 SIGMOD 5.3824434e-05
8,219 Tight Fine-Grained Bounds for Direct Access on Join Queries 2022 PODS 5.3745518e-05
8,285 Subset Sampling over Joins 2026 PODS 5.3612232e-05
8,539 GRainDB: A Relational-core Graph-Relational DBMS 2022 CIDR 5.3193454e-05
8,841 On Reporting Durable Patterns in Temporal Proximity Graphs 2024 PODS 5.2655908e-05
9,234 An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication 2025 PODS 5.2032182e-05
9,420 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 5.1802184e-05
9,940 Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction 2021 PODS 5.1076476e-05
10,107 Still Asking: How Good Are Query Optimizers, Really? 2025 VLDB 5.0765311e-05
10,131 A Modular Graph-Native Query Optimization Framework 2025 SIGMOD 5.0727027e-05
10,186 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 5.0628015e-05
10,258 TenGraph: A Tensor-Based Graph Query Engine 2024 VLDB 5.0489964e-05
10,259 BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching 2026 SIGMOD 5.0480912e-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.0023943337
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010679903
91 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00034748721
105 The MADlib Analytics Library or MAD Skills, the SQL 2012 VLDB 0.00033633007
208 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024899872
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020013731
391 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.00019245666
421 On the Complexity of Database Queries (Extended Abstract) 1997 PODS 0.00018507815
466 Design and Implementation of the LogicBlox System 2015 SIGMOD 0.00017765702
503 Towards a Unified Architecture for in-RDBMS Analytics 2012 SIGMOD 0.00017195428
521 Learning Linear Regression Models over Factorized Joins 2016 SIGMOD 0.00016923519
731 Learning Generalized Linear Models Over Normalized Data 2015 SIGMOD 0.00014400356
819 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00013660715
1,046 Graphflow: An Active Graph Database 2017 SIGMOD 0.00012316579
1,091 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012068611
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,482 Skew in Parallel Query Processing 2014 PODS 0.00010534147
1,726 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 9.7857214e-05
1,813 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.5759542e-05
2,045 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 9.1363731e-05
2,796 Demonstration of the Myria Big Data Management Service 2014 SIGMOD 7.9934519e-05
2,978 In-Database Learning with Sparse Tensors 2018 PODS 7.7872011e-05
3,331 SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning 2017 CIDR 7.4138851e-05
3,373 F: Regression Models over Factorized Views 2016 VLDB 7.3627128e-05
4,477 Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins 2016 PODS 6.580699e-05
6,745 Computing Join Queries with Functional Dependencies 2016 PODS 5.6890943e-05
Previous Page 1 / 1 Next

Semantically Similar Papers