Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization

Summary: Analyzes cost landscapes of left-deep vs. bushy query-tree spaces, showing both form a well with distinct quality. Evaluates Iterative Improvement, Simulated Annealing, and Two-Phase Optimization on these spaces, concluding the combined space is easier to optimize. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: he48a978964c665ab
Venue: SIGMOD
Year: 1991
Pagerank: 0.00014465736
Overall Rank: 725 | 95.13%
DOI: 10.1145/115790.115813

Incoming Non-self Citations Over Time

Authors

1. Yannis E. Ioannidis (University of Wisconsin)
2. Younkyung Cha Kang (University of Wisconsin)

BibTeX Citation

@inproceedings{ioannidis_sigmod91,
        title = {{LEFT-DEEP VS. BUSHY TREES: AN ANALYSIS OF STRATEGY SPACES AND ITS IMPLICATIONS FOR QUERY OPTIMIZATION}},
        author = {Ioannidis, Yannis E. and Kang, Younkyung Cha},
        series = {{SIGMOD} '91},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/115790.115813},
        url = {https://dl.acm.org/doi/10.1145/115790.115813},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
243	Automating Physical Database Design in a Parallel Database	2002	SIGMOD	0.00023358891
792	Parametric Query Optimization	1992	VLDB	0.00013942753
796	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00013938011
1,736	Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins	1992	VLDB	9.7507905e-05
1,891	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.4184294e-05
2,020	Scalable Distributed Subgraph Enumeration	2017	VLDB	9.1729558e-05
2,626	On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces	1993	VLDB	8.2068909e-05
2,660	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.1611913e-05
3,005	Multiple Join Size Estimation by Virtual Domains (extended abstract)	1993	PODS	7.7621043e-05
3,042	Fast, Randomized Join-Order Selection—Why Use Transformations?	1994	VLDB	7.7213044e-05
3,572	Multi-Join Optimization for Symmetric Multiprocessors	1993	VLDB	7.1966777e-05
3,660	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.1218018e-05
3,682	openGauss: An Autonomous Database System	2021	VLDB	7.1013922e-05
3,880	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	6.9510799e-05
4,038	Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer	2000	SIGMOD	6.8389401e-05
4,052	Of Snowstorms and Bushy Trees	2014	VLDB	6.8283077e-05
4,123	HUGE: An Efficient and Scalable Subgraph Enumeration System	2021	SIGMOD	6.7927568e-05
4,415	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD	6.6094699e-05
4,621	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	6.4987856e-05
4,710	On Parallel Execution Of Multiple Pipelined Hash Joins	1994	SIGMOD	6.4574114e-05
4,786	Applying Hash Filters to Improving the Execution of Bushy Trees	1993	VLDB	6.4143659e-05
5,094	A Decomposition-Based Simulated Annealing Technique for Data Clustering	1994	PODS	6.2775013e-05
5,496	Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations	2022	VLDB	6.1049663e-05
5,672	Subgraph Matching over Graph Federation	2022	VLDB	6.0433033e-05
6,110	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS	5.8843027e-05
7,904	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	5.4295914e-05
8,575	The Fittest Survives: An Adaptive Approach to Query Optimization	1995	VLDB	5.3115836e-05
8,971	A Fast Randomized Algorithm for Multi-Objective Query Optimization	2016	SIGMOD	5.2462912e-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
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00029179719
470	Optimization of Large Join Queries	1988	SIGMOD	0.00017755852
487	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017462723
592	Global Query Optimization	1986	SIGMOD	0.00015841026
859	Query Optimization by Simulated Annealing	1987	SIGMOD	0.00013418999

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,449	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB
2	3,214	Efficient and Provable Multi-Query Optimization	2017	PODS
3	6,216	Window Query-Optimal Clustering of Spatial Objects	1995	PODS
4	708	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD
5	8,284	A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization	1988	VLDB
6	3,572	Multi-Join Optimization for Symmetric Multiprocessors	1993	VLDB
7	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
8	859	Query Optimization by Simulated Annealing	1987	SIGMOD
9	487	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD
10	2,626	On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces	1993	VLDB