Optimal Top-Down Join Enumeration

Summary: Top-down join enumeration algorithm optimal for the join graph. Preserves DP-like architecture, uses branch-and-bound, and enables migrating from bottom-up optimizers to top-down search with substantially faster performance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3900
Venue: SIGMOD
Year: 2007
Pagerank: 9.6886663e-05
Overall Rank: 2,050 | 85.75%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. David DeHaan
2. Frank Wm. Tompa

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,213	RDF-3X: a RISC-style Engine for RDF	2008	VLDB	0.0001325231
1,341	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012486285
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
2,410	Scalable Join Processing on Very Large RDF Graphs	2009	SIGMOD	8.8773796e-05
2,785	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.1286814e-05
4,261	Parallelizing Query Optimization	2008	VLDB	6.31244e-05
4,738	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9600502e-05
6,443	Optimizing Join Enumeration in Transformation-based Query Optimizers	2014	VLDB	5.0599139e-05
6,777	Revisiting Reuse in Main Memory Database Systems	2017	SIGMOD	4.9288776e-05
7,467	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	4.7218691e-05
8,164	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5718104e-05
8,213	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	4.557937e-05
9,957	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB	4.2373024e-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

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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.0040449103
106	Extensible/Rule Based Query Rewrite Optimization in Starburst	1992	SIGMOD	0.00048400734
423	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023669348
978	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014881073
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,869	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	7.9808408e-05
3,404	EROC: A Toolkit for Building NEATO Query Optimizers	1996	VLDB	7.1321923e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00041510555
7,692	Processing Top-k Join Queries	2010	VLDB	4.6761366e-05
10,104	Query Optimization for Database-Returning Queries	2026	SIGMOD	4.1945683e-05
2,275	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.1262202e-05
423	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023669348
5,855	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3006096e-05
2,869	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	7.9808408e-05
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
6,443	Optimizing Join Enumeration in Transformation-based Query Optimizers	2014	VLDB	5.0599139e-05
2,785	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.1286814e-05