DBScholar

Back to papers

Solving the Join Ordering Problem via Mixed Integer Linear Programming

Summary: Join ordering as MILP with binary operands/intermediates and linear constraints enforcing plans and costs. Integrated into Postgres, it uses MILP solvers' anytime search to optimize up to 40 tables in under a min, beats traditional optimizers. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h8b7088cf1373fab8
Venue
SIGMOD
Year
2017
Pagerank
7.6012971e-05
Overall Rank
3,140 | 78.90%
DOI
10.1145/3035918.3064039

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{trummer_sigmod17,
        title = {{Solving the Join Ordering Problem via Mixed Integer Linear Programming}},
        author = {Trummer, Immanuel and Koch, Christoph},
        series = {{SIGMOD} '17},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3035918.3064039},
        url = {https://dl.acm.org/doi/10.1145/3035918.3064039},
        year = {2017}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank Citing Paper Year Venue Pagerank
1,185 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.00011607329
3,228 Opportunities for Quantum Acceleration of Databases: Optimization of Queries and Transaction Schedules 2023 VLDB 7.5059992e-05
4,406 Ready to Leap (by Co-Design)? Join Order Optimisation on Quantum Hardware 2023 SIGMOD 6.6103825e-05
4,975 SPORES: Sum-Product Optimization via Relational Equality Saturation for Large Scale Linear Algebra 2020 VLDB 6.3289021e-05
5,429 Efficient Massively Parallel Join Optimization for Large Queries* 2022 SIGMOD 6.1320252e-05
5,911 Quantum-Inspired Digital Annealing for Join Ordering 2024 VLDB 5.9478816e-05
8,019 AJoin: Ad-hoc Stream Joins at Scale 2020 VLDB 5.4045347e-05
8,659 Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation 2026 VLDB 5.292093e-05
8,673 Applicability of Quantum Computing on Database Query Optimization 2022 SIGMOD 5.2897413e-05
8,769 Is Integer Linear Programming All You Need for Deletion Propagation? A Unified and Practical Approach for Generalized Deletion Propagation 2025 VLDB 5.2811408e-05
9,221 DPconv: Super-Polynomially Faster Join Ordering 2024 SIGMOD 5.2036474e-05
10,380 Coresets for Robust Query Optimization 2026 PODS 4.9769913e-05
11,251 Quantum Data Management in the NISQ Era 2025 VLDB 4.9769913e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 25 of 25 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
125 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00030462671
321 Measuring the Complexity of Join Enumeration in Query Optimization 1990 VLDB 0.00021082176
469 Optimization of Large Join Queries 1988 SIGMOD 0.00017749337
487 Randomized Algorithms For Optimizing Large Join Queries 1990 SIGMOD 0.00017455404
708 Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques 1989 SIGMOD 0.00014623779
796 Rapid Bushy Join-order Optimization with Cartesian Products 1996 SIGMOD 0.00013931773
883 Dynamic Programming Strikes Back 2008 SIGMOD 0.00013263866
1,015 Improved Unnesting Algorithms for Join Aggregate SQL Queries 1992 VLDB 0.00012495751
1,277 Orca: A Modular Query Optimizer Architecture for Big Data 2014 SIGMOD 0.00011234276
1,298 Parametric Query Optimization for Linear and Piecewise Linear Cost Functions 2002 VLDB 0.00011122244
1,301 Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products 2006 VLDB 0.00011107788
1,449 Design and Analysis of Parametric Query Optimization Algorithms 1998 VLDB 0.00010616486
1,482 Skew in Parallel Query Processing 2014 PODS 0.00010534147
1,612 AniPQO: Almost Non-intrusive Parametric Query Optimization for Nonlinear Cost Functions 2003 VLDB 0.00010068388
1,706 Algorithms for Materialized View Design in Data Warehousing Environment 1997 VLDB 9.8256789e-05
1,860 Optimizing Disjunctive Queries with Expensive Predicates 1994 SIGMOD 9.4862912e-05
2,524 Multi-Objective Parametric Query Optimization 2015 VLDB 8.3400278e-05
2,890 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.9010819e-05
3,568 On the Complexity of Approximate Query Optimization 2002 PODS 7.1978817e-05
3,777 Parallelizing Query Optimization 2008 VLDB 7.0240115e-05
4,982 An Incremental Anytime Algorithm for Multi-Objective Query Optimization 2015 SIGMOD 6.3264052e-05
6,051 Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs 2009 SIGMOD 5.9019888e-05
6,138 Parallelizing Extensible Query Optimizers 2009 SIGMOD 5.8732713e-05
9,628 Parallelizing Query Optimization on Shared-Nothing Architectures 2016 VLDB 5.1473253e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 3,983 Simplicity Done Right for Join Ordering 2021 CIDR
2 10,519 Succinct Structure Representations for Efficient Query Optimization 2026 SIGMOD
3 2,138 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB
4 8,046 Efficiently Computing Join Orders with Heuristic Search 2023 SIGMOD
5 12,215 Improving Join Reorderability with Compensation Operators 2018 SIGMOD
6 3,777 Parallelizing Query Optimization 2008 VLDB
7 3,800 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD
8 5,429 Efficient Massively Parallel Join Optimization for Large Queries* 2022 SIGMOD
9 1,185 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD
10 8,659 Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation 2026 VLDB