Rapid Bushy Join-order Optimization with Cartesian Products

Summary: Full bushy join-order search, including subplan Cartesian products, is feasible in seconds for up to 15 relations, challenging standard optimizer exclusions. Join-order enumeration is decoupled from predicate analysis, with novel techniques and a benchmarking framework. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2870
Venue: SIGMOD
Year: 1996
Pagerank: 0.00014871114
Overall Rank: 979 | 93.20%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Bennet Vance
2. David Maier

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,344	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012477274
1,559	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00011368746
1,825	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00010392367
2,053	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.682841e-05
2,778	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.1345892e-05
2,878	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	7.9694937e-05
3,125	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	7.5228453e-05
3,476	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.0560383e-05
4,001	Partial Join Order Optimization in the ParAccel Analytic Database	2009	SIGMOD	6.540692e-05
4,503	Of Snowstorms and Bushy Trees	2014	VLDB	6.131076e-05
4,734	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9553181e-05
4,876	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	5.8544467e-05
5,091	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	5.7010894e-05
5,696	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	5.367449e-05
5,772	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	5.3313794e-05
6,060	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	5.2271244e-05
6,333	Parallelizing Extensible Query Optimizers	2009	SIGMOD	5.1013149e-05
6,541	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS	5.0160682e-05
6,862	Join Order Selection with Deep Reinforcement Learning: Fundamentals, Techniques, and Challenges	2023	VLDB	4.9004921e-05
7,486	Quantum-Inspired Digital Annealing for Join Ordering	2024	VLDB	4.7135369e-05
7,669	Extending XQuery with Window Functions	2007	VLDB	4.6784108e-05
8,149	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5715614e-05
8,720	A Fast Randomized Algorithm for Multi-Objective Query Optimization	2016	SIGMOD	4.4563359e-05
9,312	Parallelizing Query Optimization on Shared-Nothing Architectures	2016	VLDB	4.353536e-05
9,956	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB	4.2332427e-05
10,295	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	4.1905499e-05
10,990	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	4.1905499e-05
12,103	A Performance Study of Three Disk-based Structures for Indexing and Querying Frequent Itemsets	2013	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 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.0040465394
140	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00042289025
422	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023654556
811	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00016385568
3,053	Fast, Randomized Join-Order Selection — Why Use Transformations?	1994	VLDB	7.6482987e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,526	Simplicity Done Right for Join Ordering	2021	CIDR	6.1079584e-05
8,844	Faster Plan Generation through Consideration of Functional Dependencies and Keys	2016	VLDB	4.4334103e-05
2,867	Optimization of Queries with User-defined Predicates	1996	VLDB	7.9931252e-05
8,149	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5715614e-05
1,621	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011105663
12,900	Avoiding Cartesian Products in Programs for Multiple Joins (Extended Abstract)	1992	PODS	4.1905499e-05
422	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023654556
7,979	On the Optimality of Strategies for Multiple Joins	1990	PODS	4.6089395e-05
6,541	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS	5.0160682e-05
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059446482