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: 6576
Venue: SIGMOD
Year: 2023
Pagerank: 4.5718104e-05
Overall Rank: 8,164 | 43.21%
DOI: 10.1145/3588927

Incoming Non-self Citations Over Time

Authors

1. Immanuel Haffner
2. Jens Dittrich

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,031	Extending SQL to Return a Subdatabase	2025	SIGMOD	4.4039656e-05
9,187	POLAR: Adaptive and Non-invasive Join Order Selection via Plans of Least Resistance	2024	VLDB	4.3780059e-05
9,957	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB	4.2373024e-05
9,960	An Elephant Under The Microscope: Analyzing The Interaction Of Optimizer Components In PostgreSQL	2025	SIGMOD	4.2294678e-05
10,104	Query Optimization for Database-Returning Queries	2026	SIGMOD	4.1945683e-05
10,942	Sub-optimal Join Order Identification with L1-error	2024	SIGMOD	4.1945683e-05
10,987	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	4.1945683e-05
10,994	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.1945683e-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
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00041510555
220	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD	0.00033194808
333	Neo: A Learned Query Optimizer	2019	VLDB	0.00027206884
423	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023669348
640	Bao: Making Learned Query Optimization Practical	2021	SIGMOD	0.00018759152
684	Towards a Robust Query Optimizer: A Principled and Practical Approach	2005	SIGMOD	0.00018179769
978	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014881073
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
1,758	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00010655546
1,826	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00010400425
2,050	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.6886663e-05
4,738	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9600502e-05
6,040	Steering Query Optimizers: A Practical Take on Big Data Workloads	2021	SIGMOD	5.2412035e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
784	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00016675823
7,166	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.8124491e-05
4,523	Simplicity Done Right for Join Ordering	2021	CIDR	6.1135504e-05
4,194	On the Complexity of Approximate Query Optimization	2002	PODS	6.3697822e-05
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00041510555
10,283	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	4.1945683e-05
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
4,738	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9600502e-05