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.0001441771
Overall Rank: 728 | 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.00023296011
792	Parametric Query Optimization	1992	VLDB	0.00013903954
794	Rapid Bushy Join-order Optimization with Cartesian Products	1996	SIGMOD	0.0001389694
1,746	Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins	1992	VLDB	9.718559e-05
1,896	CS2: A New Database Synopsis for Query Estimation	2013	SIGMOD	9.4010932e-05
2,023	Scalable Distributed Subgraph Enumeration	2017	VLDB	9.1568397e-05
2,630	On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces	1993	VLDB	8.1828876e-05
2,671	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.1310287e-05
3,009	Multiple Join Size Estimation by Virtual Domains (extended abstract)	1993	PODS	7.7439468e-05
3,051	Fast, Randomized Join-Order Selection—Why Use Transformations?	1994	VLDB	7.6933177e-05
3,583	Multi-Join Optimization for Symmetric Multiprocessors	1993	VLDB	7.1705907e-05
3,662	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS	7.1009211e-05
3,687	openGauss: An Autonomous Database System	2021	VLDB	7.0797286e-05
3,885	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	6.9282318e-05
4,048	Of Snowstorms and Bushy Trees	2014	VLDB	6.817438e-05
4,055	Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer	2000	SIGMOD	6.814254e-05
4,133	HUGE: An Efficient and Scalable Subgraph Enumeration System	2021	SIGMOD	6.7738028e-05
4,435	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD	6.5858211e-05
4,640	Join Query Optimization Techniques for Complex Event Processing Applications	2018	VLDB	6.4742349e-05
4,713	On Parallel Execution Of Multiple Pipelined Hash Joins	1994	SIGMOD	6.4397959e-05
4,809	Applying Hash Filters to Improving the Execution of Bushy Trees	1993	VLDB	6.3910269e-05
5,118	A Decomposition-Based Simulated Annealing Technique for Data Clustering	1994	PODS	6.2548449e-05
5,522	Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations	2022	VLDB	6.0818991e-05
5,676	Subgraph Matching over Graph Federation	2022	VLDB	6.0246247e-05
6,125	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS	5.862077e-05
7,924	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS	5.4090777e-05
8,594	The Fittest Survives: An Adaptive Approach to Query Optimization	1995	VLDB	5.2933942e-05
8,999	A Fast Randomized Algorithm for Multi-Objective Query Optimization	2016	SIGMOD	5.2270052e-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
144	Optimization of Nonrecursive Queries	1986	VLDB	0.00029092688
470	Optimization of Large Join Queries	1988	SIGMOD	0.00017699145
489	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017402488
595	Global Query Optimization	1986	SIGMOD	0.00015791231
862	Query Optimization by Simulated Annealing	1987	SIGMOD	0.00013372073

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,226	Efficient and Provable Multi-Query Optimization	2017	PODS
2	1,453	Design and Analysis of Parametric Query Optimization Algorithms	1998	VLDB
3	6,231	Window Query-Optimal Clustering of Spatial Objects	1995	PODS
4	714	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD
5	8,307	A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization	1988	VLDB
6	3,583	Multi-Join Optimization for Symmetric Multiprocessors	1993	VLDB
7	1,293	Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products	2006	VLDB
8	862	Query Optimization by Simulated Annealing	1987	SIGMOD
9	489	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD
10	2,630	On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces	1993	VLDB