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: 2587
Venue: SIGMOD
Year: 1991
Pagerank: 0.00014727576
Overall Rank: 708 | 95.15%
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
246	Automating Physical Database Design in a Parallel Database	2002	SIGMOD	0.00023457421
770	Parametric Query Optimization	1992	VLDB	0.00014166811
774	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.00014123979
1,720	Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins	1992	VLDB	9.9265634e-05
1,893	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.5269935e-05
2,065	Scalable Distributed Subgraph Enumeration	2017	VLDB	9.2352771e-05
2,582	On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces	1993	VLDB	8.3875949e-05
2,627	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.3284491e-05
2,984	Multiple Join Size Estimation by Virtual Domains (extended abstract)	1993	PODS	7.8920597e-05
2,996	Fast, Randomized Join-Order Selection—Why Use Transformations?	1994	VLDB	7.8745175e-05
3,508	Multi-Join Optimization for Symmetric Multiprocessors	1993	VLDB	7.3566888e-05
3,617	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.2557398e-05
3,662	openGauss: An Autonomous Database System	2021	VLDB	7.2166682e-05
3,821	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	7.0933895e-05
3,970	Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer	2000	SIGMOD	6.9835426e-05
4,091	Of Snowstorms and Bushy Trees	2014	VLDB	6.9090244e-05
4,158	HUGE: An Efficient and Scalable Subgraph Enumeration System	2021	SIGMOD	6.8628196e-05
4,346	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD	6.7510183e-05
4,588	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	6.6167545e-05
4,652	On Parallel Execution Of Multiple Pipelined Hash Joins	1994	SIGMOD	6.5851924e-05
5,007	A Decomposition-Based Simulated Annealing Technique for Data Clustering	1994	PODS	6.4032846e-05
5,014	Applying Hash Filters to Improving the Execution of Bushy Trees	1993	VLDB	6.4002123e-05
5,368	Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations	2022	VLDB	6.2448114e-05
5,581	Subgraph Matching over Graph Federation	2022	VLDB	6.1624715e-05
6,164	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS	5.9532278e-05
7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	5.5541724e-05
8,400	The Fittest Survives: An Adaptive Approach to Query Optimization	1995	VLDB	5.4331924e-05
8,831	A Fast Randomized Algorithm for Multi-Objective Query Optimization	2016	SIGMOD	5.3607984e-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.0002959213
463	Optimization of Large Join Queries	1988	SIGMOD	0.00018064961
479	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017789732
583	Global Query Optimization	1986	SIGMOD	0.00016145442
839	Query Optimization by Simulated Annealing	1987	SIGMOD	0.00013692785

Semantically Similar Papers

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