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: 2931
Venue: SIGMOD
Year: 1996
Pagerank: 0.00014123979
Overall Rank: 774 | 94.70%
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
1,013	Dynamic Programming Strikes Back	2008	SIGMOD	0.00012652549
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
1,568	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.0001034191
1,727	Optimal Top-Down Join Enumeration	2007	SIGMOD	9.91063e-05
2,275	Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs	2013	VLDB	8.8196821e-05
2,627	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.3284491e-05
2,694	Holistic Twig Joins on Indexed XML Documents	2003	VLDB	8.2469414e-05
3,158	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.6888079e-05
3,813	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	7.1051056e-05
4,044	Partial Join Order Optimization in the ParAccel Analytic Database	2009	SIGMOD	6.9400535e-05
4,091	Of Snowstorms and Bushy Trees	2014	VLDB	6.9090244e-05
4,553	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	6.6346951e-05
4,588	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	6.6167545e-05
5,124	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	6.3567981e-05
5,137	Exact Cardinality Query Optimization with Bounded Execution Cost	2019	SIGMOD	6.3507372e-05
5,399	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	6.2319315e-05
6,026	Parallelizing Extensible Query Optimizers	2009	SIGMOD	6.0024042e-05
6,164	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS	5.9532278e-05
6,735	Join Order Selection with Deep Reinforcement Learning: Fundamentals, Techniques, and Challenges	2023	VLDB	5.7878855e-05
7,577	Extending XQuery with Window Functions	2007	VLDB	5.5927837e-05
7,882	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	5.5237338e-05
7,910	Quantum-Inspired Digital Annealing for Join Ordering	2024	VLDB	5.5181056e-05
8,831	A Fast Randomized Algorithm for Multi-Objective Query Optimization	2016	SIGMOD	5.3607984e-05
9,042	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	5.3256042e-05
9,446	Parallelizing Query Optimization on Shared-Nothing Architectures	2016	VLDB	5.2667452e-05
9,969	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	5.1845938e-05
10,106	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB	5.1435736e-05
10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD	5.093636e-05
12,292	A Performance Study of Three Disk-based Structures for Indexing and Querying Frequent Itemsets	2013	VLDB	5.093636e-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.0024089429
132	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030378624
316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.0002141607
708	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00014727576
2,996	Fast, Randomized Join-Order Selection—Why Use Transformations?	1994	VLDB	7.8745175e-05

Semantically Similar Papers

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