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: ha95fa85692806241
Venue: SIGMOD
Year: 1996
Pagerank: 0.00013931773
Overall Rank: 796 | 94.66%
DOI: 10.1145/233269.233317

Incoming Non-self Citations Over Time

Authors

1. Bennet Vance (Oregon Graduate Institute)
2. David Maier (Oregon Graduate Institute)

BibTeX Citation

@inproceedings{vance_sigmod96,
        title = {{Rapid Bushy Join-order Optimization with Cartesian Products}},
        author = {Vance, Bennet and Maier, David},
        series = {{SIGMOD} '96},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/233269.233317},
        url = {https://dl.acm.org/doi/10.1145/233269.233317},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 29 of 29 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
883	Dynamic Programming Strikes Back	2008	SIGMOD	0.00013263866
1,301	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB	0.00011107788
1,594	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00010129129
1,727	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.7849752e-05
2,252	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.7480805e-05
2,660	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.1574087e-05
2,746	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	8.0587951e-05
3,140	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.6012971e-05
3,800	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	7.0130412e-05
4,002	Partial Join Order Optimization in the ParAccel Analytic Database	2009	SIGMOD	6.8577586e-05
4,052	Of Snowstorms and Bushy Trees	2014	VLDB	6.8257821e-05
4,371	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	6.6284915e-05
4,623	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	6.4957114e-05
5,200	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	6.2303304e-05
5,227	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	6.2183387e-05
5,429	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	6.1320252e-05
5,911	Quantum-Inspired Digital Annealing for Join Ordering	2024	VLDB	5.9478816e-05
6,111	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS	5.8815204e-05
6,138	Parallelizing Extensible Query Optimizers	2009	SIGMOD	5.8732713e-05
6,636	Join Order Selection with Deep Reinforcement Learning: Fundamentals, Techniques, and Challenges	2023	VLDB	5.7243042e-05
7,727	Extending XQuery with Window Functions	2007	VLDB	5.4652337e-05
8,046	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	5.3992239e-05
8,659	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	5.292093e-05
8,980	A Fast Randomized Algorithm for Multi-Objective Query Optimization	2016	SIGMOD	5.2439101e-05
9,221	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	5.2036474e-05
9,628	Parallelizing Query Optimization on Shared-Nothing Architectures	2016	VLDB	5.1473253e-05
10,144	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB	5.0718686e-05
10,519	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD	4.9769913e-05
12,589	A Performance Study of Three Disk-based Structures for Indexing and Querying Frequent Itemsets	2013	VLDB	4.9769913e-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.0023943337
125	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030462671
321	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00021082176
726	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00014459508
3,043	Fast, Randomized Join-Order Selection—Why Use Transformations?	1994	VLDB	7.7178769e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,024	Faster Plan Generation through Consideration of Functional Dependencies and Keys	2016	VLDB
2	10,519	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
3	2,516	Optimization of Queries with User-defined Predicates	1996	VLDB
4	8,046	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD
5	1,185	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
6	13,380	Avoiding Cartesian Products in Programs for Multiple Joins (Extended Abstract)	1992	PODS
7	321	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB
8	8,471	On the Optimality of Strategies for Multiple Joins	1990	PODS
9	6,111	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS
10	15	How Good Are Query Optimizers, Really?	2016	VLDB