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: hebc30e6f39bd4e04
Venue: SIGMOD
Year: 2023
Pagerank: 5.4017809e-05
Overall Rank: 8,039 | 45.96%
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
7,410	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	5.5342768e-05
9,211	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	5.206112e-05
9,360	Extending SQL to Return a Subdatabase	2025	SIGMOD	5.1868213e-05
10,140	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB	5.0742707e-05
10,336	An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL	2025	SIGMOD	5.0200193e-05
10,590	Query Optimization for Database-Returning Queries	2026	SIGMOD	4.9793485e-05
11,507	Sub-optimal Join Order Identification with L1-error	2024	SIGMOD	4.9793485e-05
11,546	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.9793485e-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
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00029179719
145	Neo: A Learned Query Optimizer	2019	VLDB	0.0002908188
149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00028981723
321	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00021088704
362	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00019989474
569	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00016245271
796	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00013938011
1,186	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.0001160797
1,257	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00011310561
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.00011112842
1,726	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.788916e-05
3,797	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	7.0163619e-05
5,110	Steering Query Optimizers: A Practical Take on Big Data Workloads	2021	SIGMOD	6.269351e-05

Semantically Similar Papers

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