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: 3962
Venue: SIGMOD
Year: 2007
Pagerank: 9.91063e-05
Overall Rank: 1,727 | 88.16%
DOI: 10.1145/1247480.1247567

Incoming Non-self Citations Over Time

Authors

1. David DeHaan (University of Waterloo)
2. Frank Wm. Tompa (University of Waterloo)

BibTeX Citation

@inproceedings{dehaan_sigmod07,
        title = {{Optimal Top-Down Join Enumeration}},
        author = {DeHaan, David and Tompa, Frank Wm.},
        series = {{SIGMOD} '07},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1247480.1247567},
        url = {https://dl.acm.org/doi/10.1145/1247480.1247567},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
944	RDF-3X: a RISC-style Engine for RDF	2008	VLDB	0.00013067088
1,013	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012652549
1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011320736
1,979	Scalable Join Processing on Very Large RDF Graphs	2009	SIGMOD	9.3621296e-05
2,275	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.8196821e-05
3,726	Parallelizing Query Optimization	2008	VLDB	7.1697834e-05
3,813	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	7.1051056e-05
5,947	Revisiting Reuse in Main Memory Database Systems	2017	SIGMOD	6.0323707e-05
6,340	Optimizing Join Enumeration in Transformation-based Query Optimizers	2014	VLDB	5.9071133e-05
6,434	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.8799421e-05
7,495	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD	5.6041473e-05
7,882	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	5.5237338e-05
9,042	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	5.3256042e-05
10,106	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB	5.1435736e-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

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.0024089429
110	Extensible/Rule Based Query Rewrite Optimization in Starburst	1992	SIGMOD	0.0003309592
316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.0002141607
774	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014123979
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
2,627	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.3284491e-05
3,779	EROC: A Toolkit for Building NEATO Query Optimizers	1996	VLDB	7.1326925e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
2	7,550	Processing Top-k Join Queries	2010	VLDB
3	10,394	Query Optimization for Database-Returning Queries	2026	SIGMOD
4	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
5	316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB
6	5,601	Optimal Join Algorithms Meet Top-k	2020	SIGMOD
7	2,627	The Complexity of Transformation-Based Join Enumeration	1997	VLDB
8	2,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
9	6,340	Optimizing Join Enumeration in Transformation-based Query Optimizers	2014	VLDB
10	2,275	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB