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.00021178303
Overall Rank
318 | 97.88%
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,171 In-Memory Subgraph Matching: An In-depth Study 2020 SIGMOD 0.00011677799
1,603 Adopting Worst-Case Optimal Joins in Relational Database Systems 2020 VLDB 0.00010090639
1,988 RapidMatch: A Holistic Approach to Subgraph Query Processing 2021 VLDB 9.2301018e-05
2,167 DIFF: A Relational Interface for Large-Scale Data Explanation 2019 VLDB 8.9166414e-05
2,316 On Functional Aggregate Queries with Additive Inequalities 2019 PODS 8.6404062e-05
2,602 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB 8.2157154e-05
2,635 Neural Subgraph Counting with Wasserstein Estimator 2022 SIGMOD 8.1795762e-05
2,852 FactorJoin: A New Cardinality Estimation Framework for Join Queries 2023 SIGMOD 7.9201312e-05
3,105 A Learned Sketch for Subgraph Counting 2021 SIGMOD 7.6278115e-05
3,199 Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries 2020 PODS 7.5261206e-05
3,502 On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms 2023 PODS 7.2308675e-05
3,885 Distributed Subgraph Matching on Timely Dataflow 2019 VLDB 6.9282318e-05
3,982 TCUDB: Accelerating Database with Tensor Processors 2022 SIGMOD 6.8663329e-05
4,099 A Comprehensive Survey and Experimental Study of Subgraph Matching: Trends, Unbiasedness, and Interaction 2024 SIGMOD 6.7940875e-05
4,396 Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries 2024 CIDR 6.6072577e-05
4,627 Worst-Case Optimal Graph Joins in Almost No Space 2021 SIGMOD 6.4801904e-05
4,730 Optimal Join Algorithms Meet Top-k 2020 SIGMOD 6.4313418e-05
4,900 Rel: A Programming Language for Relational Data 2025 SIGMOD 6.348695e-05
4,971 Debunking the Myth of Join Ordering: Toward Robust SQL Analytics 2025 SIGMOD 6.3209003e-05
5,034 Free Join: Unifying Worst-Case Optimal and Traditional Joins 2023 SIGMOD 6.2921115e-05
5,469 High-Performance Row Pattern Recognition Using Joins 2023 VLDB 6.1022571e-05
5,506 Beyond Equi-joins: Ranking, Enumeration and Factorization 2021 VLDB 6.0883761e-05
5,911 Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees 2025 SIGMOD 5.9338021e-05
5,925 Join Size Bounds using l_p-Norms on Degree Sequences 2024 PODS 5.9282898e-05
5,995 An In-Depth Study of Continuous Subgraph Matching 2022 VLDB 5.903845e-05
6,443 Evaluating Datalog over Semirings: A Grounding-based Approach 2024 PODS 5.7666211e-05
6,545 Query Evaluation by Circuits 2022 PODS 5.7329641e-05
6,579 Fast Matrix Multiplication for Query Processing 2024 PODS 5.7252637e-05
6,585 Output-Optimal Algorithms for Join-Aggregate Queries 2025 PODS 5.7238683e-05
6,826 Instance-Optimal Acyclic Join Processing Without Regret: Engineering the Yannakakis Algorithm in Column Stores 2025 VLDB 5.6566963e-05
6,882 Computing Complex Temporal Join Queries Efficiently 2022 SIGMOD 5.6412354e-05
6,900 Insert-Only versus Insert-Delete in Dynamic Query Evaluation 2024 PODS 5.6372471e-05
6,979 The Complexity of Boolean Conjunctive Queries with Intersection Joins 2022 PODS 5.6129856e-05
7,311 Computing the Difference of Conjunctive Queries Efficiently 2023 SIGMOD 5.5432326e-05
7,394 ADOPT: Adaptively Optimizing Attribute Orders for Worst-Case Optimal Join Algorithms via Reinforcement Learning 2023 VLDB 5.5202266e-05
7,782 Adaptive Factorization Using Linear-Chained Hash Tables 2025 CIDR 5.4368388e-05
7,957 GraphINC: Graph Pattern Mining at Network Speed 2023 SIGMOD 5.4019044e-05
8,192 Fast and Reliable Missing Data Contingency Analysis with Predicate-Constraints 2020 SIGMOD 5.3646457e-05
8,238 Tight Fine-Grained Bounds for Direct Access on Join Queries 2022 PODS 5.3567801e-05
8,300 Subset Sampling over Joins 2026 PODS 5.3434957e-05
8,556 GRainDB: A Relational-core Graph-Relational DBMS 2022 CIDR 5.3017563e-05
8,859 On Reporting Durable Patterns in Temporal Proximity Graphs 2024 PODS 5.2481795e-05
9,258 An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication 2025 PODS 5.1860131e-05
9,445 Output-Sensitive Evaluation of Regular Path Queries 2025 PODS 5.1630894e-05
9,881 BEE: Towards Redundancy Reduction via Block-Separator Decomposition for Subgraph Matching 2026 SIGMOD 5.1043481e-05
9,973 Modern Lower Bound Techniques in Database Theory and Constraint Satisfaction 2021 PODS 5.0907585e-05
10,143 Still Asking: How Good Are Query Optimizers, Really? 2025 VLDB 5.0597449e-05
10,168 A Modular Graph-Native Query Optimization Framework 2025 SIGMOD 5.0559291e-05
10,220 Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints 2025 PODS 5.0460607e-05
10,286 TenGraph: A Tensor-Based Graph Query Engine 2024 VLDB 5.0333144e-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.0023948467
5 Optimal Aggregation Algorithms for Middleware [Extended Abstract] 2001 PODS 0.0010688884
91 On the Propagation of Errors in the Size of Join Results 1991 SIGMOD 0.00034691614
105 The MADlib Analytics Library or MAD Skills, the SQL 2012 VLDB 0.00033605348
208 EmptyHeaded: A Relational Engine for Graph Processing 2016 SIGMOD 0.00024929198
357 FAQ: Questions Asked Frequently 2016 PODS 0.00020048899
391 Conjunctive-Query Containment and Constraint Satisfaction 1998 PODS 0.0001918714
424 On the Complexity of Database Queries (Extended Abstract) 1997 PODS 0.00018448553
467 Design and Implementation of the LogicBlox System 2015 SIGMOD 0.00017740891
506 Towards a Unified Architecture for in-RDBMS Analytics 2012 SIGMOD 0.00017158546
522 Learning Linear Regression Models over Factorized Joins 2016 SIGMOD 0.00016893112
731 Learning Generalized Linear Models Over Normalized Data 2015 SIGMOD 0.00014363943
819 Hypertree Decompositions: Questions and Answers 2016 PODS 0.00013623401
1,049 Graphflow: An Active Graph Database 2017 SIGMOD 0.00012293903
1,096 What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another? 2017 PODS 0.00012035761
1,253 Distributed Evaluation of Subgraph Queries Using Worst-case Optimal Low-Memory Dataflows 2018 VLDB 0.00011316982
1,296 From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System 2015 SIGMOD 0.00011119184
1,483 Skew in Parallel Query Processing 2014 PODS 0.00010500209
1,734 Beyond Worst-case Analysis for Joins with Minesweeper 2014 PODS 9.7545941e-05
1,821 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.5466386e-05
2,052 A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries 2017 PODS 9.1064522e-05
2,804 Demonstration of the Myria Big Data Management Service 2014 SIGMOD 7.96944e-05
2,974 In-Database Learning with Sparse Tensors 2018 PODS 7.7812156e-05
3,331 SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning 2017 CIDR 7.4065701e-05
3,369 F: Regression Models over Factorized Views 2016 VLDB 7.3507965e-05
4,497 Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins 2016 PODS 6.5592387e-05
6,761 Computing Join Queries with Functional Dependencies 2016 PODS 5.6705551e-05
Previous Page 1 / 1 Next

Semantically Similar Papers