Efficiently Computing Join Orders with Heuristic Search

Summary: The paper reduces join-order optimization to a shortest-path problem within a formal framework, enabling principled heuristic search for query plans. In a real DBMS, it achieves order-of-magnitude speedups on star- and clique-shaped queries, with suboptimal variants expanding the cost–time Pareto frontier. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6638
Venue: SIGMOD
Year: 2023
Pagerank: 5.5237338e-05
Overall Rank: 7,882 | 45.93%
DOI: 10.1145/3588927

Incoming Non-self Citations Over Time

Authors

1. Immanuel Haffner (Saarland University)
2. Jens Dittrich (Saarland University)

BibTeX Citation

@inproceedings{haffner_sigmod23,
        title = {{Efficiently Computing Join Orders with Heuristic Search}},
        author = {Haffner, Immanuel and Dittrich, Jens},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3588927},
        url = {https://dl.acm.org/doi/10.1145/3588927},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,494	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	5.4142129e-05
9,042	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	5.3256042e-05
9,183	Extending SQL to Return a Subdatabase	2025	SIGMOD	5.3058708e-05
10,106	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB	5.1435736e-05
10,108	An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL	2025	SIGMOD	5.1347137e-05
10,394	Query Optimization for Database-Returning Queries	2026	SIGMOD	5.093636e-05
11,160	Sub-optimal Join Order Identification with L1-error	2024	SIGMOD	5.093636e-05
11,205	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
143	Optimization of Nonrecursive Queries	1986	VLDB	0.0002959213
151	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00029161879
154	Neo: A Learned Query Optimizer	2019	VLDB	0.00028726181
316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.0002141607
378	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00019638121
566	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016436005
774	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014123979
1,256	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00011457194
1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011320736
1,298	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00011259156
1,727	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.91063e-05
3,813	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	7.1051056e-05
5,059	Steering Query Optimizers: A Practical Take on Big Data Workloads	2021	SIGMOD	6.3807509e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	698	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD
2	6,412	Ranked Enumeration of Join Queries with Projections	2022	VLDB
3	3,959	Simplicity Done Right for Join Ordering	2021	CIDR
4	3,553	On the Complexity of Approximate Query Optimization	2002	PODS
5	143	Optimization of Nonrecursive Queries	1986	VLDB
6	9,969	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB
7	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
8	18	How Good Are Query Optimizers, Really?	2016	VLDB
9	1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
10	3,813	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD