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: 2869
Venue: SIGMOD
Year: 1996
Pagerank: 0.00014881073
Overall Rank: 978 | 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,341	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012486285
1,562	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00011356744
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
2,785	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.1286814e-05
2,869	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	7.9808408e-05
3,120	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	7.5295938e-05
3,474	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.0625972e-05
4,001	Partial Join Order Optimization in the ParAccel Analytic Database	2009	SIGMOD	6.5463503e-05
4,511	Of Snowstorms and Bushy Trees	2014	VLDB	6.1247645e-05
4,738	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9600502e-05
4,874	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	5.8594632e-05
5,097	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	5.7011496e-05
5,685	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	5.3717535e-05
5,765	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	5.336442e-05
6,056	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	5.2321475e-05
6,337	Parallelizing Extensible Query Optimizers	2009	SIGMOD	5.1053757e-05
6,543	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS	5.0208799e-05
6,862	Join Order Selection with Deep Reinforcement Learning: Fundamentals, Techniques, and Challenges	2023	VLDB	4.9051979e-05
7,486	Quantum-Inspired Digital Annealing for Join Ordering	2024	VLDB	4.7180617e-05
7,670	Extending XQuery with Window Functions	2007	VLDB	4.682982e-05
8,164	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5718104e-05
8,725	A Fast Randomized Algorithm for Multi-Objective Query Optimization	2016	SIGMOD	4.4600243e-05
9,305	Parallelizing Query Optimization on Shared-Nothing Architectures	2016	VLDB	4.3577129e-05
9,957	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB	4.2373024e-05
10,283	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	4.1945683e-05
10,987	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	4.1945683e-05
12,095	A Performance Study of Three Disk-based Structures for Indexing and Querying Frequent Itemsets	2013	VLDB	4.1945683e-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.0040449103
139	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00042299329
423	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023669348
813	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.0001639584
3,048	Fast, Randomized Join-Order Selection — Why Use Transformations?	1994	VLDB	7.6543116e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
5,685	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	5.3717535e-05
8,844	Faster Plan Generation through Consideration of Functional Dependencies and Keys	2016	VLDB	4.437664e-05
2,860	Optimization of Queries with User-defined Predicates	1996	VLDB	7.9934503e-05
8,164	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5718104e-05
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
12,890	Avoiding Cartesian Products in Programs for Multiple Joins (Extended Abstract)	1992	PODS	4.1945683e-05
423	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023669348
7,976	On the Optimality of Strategies for Multiple Joins	1990	PODS	4.613363e-05
6,543	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS	5.0208799e-05
71	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059038975