DBScholar

Back to papers

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.00014459508
Overall Rank
726 | 95.13%
DOI
10.1145/115790.115813

Incoming Non-self Citations Over Time

Authors

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.00023349603
792 Parametric Query Optimization 1992 VLDB 0.00013938197
796 Rapid Bushy Join-order Optimization with Cartesian Products 1996 SIGMOD 0.00013931773
1,738 Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins 1992 VLDB 9.7467088e-05
1,892 CS2: A New Database Synopsis for Query Estimation 2013 SIGMOD 9.4150583e-05
2,022 Scalable Distributed Subgraph Enumeration 2017 VLDB 9.1686153e-05
2,627 On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces 1993 VLDB 8.2030431e-05
2,660 The Complexity of Transformation-Based Join Enumeration 1997 VLDB 8.1574087e-05
3,000 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.7657164e-05
3,043 Fast, Randomized Join-Order Selection—Why Use Transformations? 1994 VLDB 7.7178769e-05
3,574 Multi-Join Optimization for Symmetric Multiprocessors 1993 VLDB 7.1932731e-05
3,661 Scalable Computation of Acyclic Joins (Extended Abstract) 2006 PODS 7.1184935e-05
3,680 openGauss: An Autonomous Database System 2021 VLDB 7.1016555e-05
3,881 Distributed Subgraph Matching on Timely Dataflow 2019 VLDB 6.9477894e-05
4,040 Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer 2000 SIGMOD 6.8357679e-05
4,052 Of Snowstorms and Bushy Trees 2014 VLDB 6.8257821e-05
4,124 HUGE: An Efficient and Scalable Subgraph Enumeration System 2021 SIGMOD 6.7895411e-05
4,417 Estimating Compilation Time of a Query Optimizer 2003 SIGMOD 6.6064397e-05
4,623 Join Query Optimization Techniques for Complex Event Processing Applications 2018 VLDB 6.4957114e-05
4,712 On Parallel Execution Of Multiple Pipelined Hash Joins 1994 SIGMOD 6.4543768e-05
4,790 Applying Hash Filters to Improving the Execution of Bushy Trees 1993 VLDB 6.4114271e-05
5,097 A Decomposition-Based Simulated Annealing Technique for Data Clustering 1994 PODS 6.2746044e-05
5,500 Density-optimized Intersection-free Mapping and Matrix Multiplication for Join-Project Operations 2022 VLDB 6.1020763e-05
5,673 Subgraph Matching over Graph Federation 2022 VLDB 6.0404425e-05
6,111 On the Complexity of Generating Optimal Plans with Cross Products (extended abstract) 1997 PODS 5.8815204e-05
7,908 Processing and Optimization of Multiway Spatial Joins Using R-trees 1999 PODS 5.4270211e-05
8,576 The Fittest Survives: An Adaptive Approach to Query Optimization 1995 VLDB 5.3109021e-05
8,980 A Fast Randomized Algorithm for Multi-Objective Query Optimization 2016 SIGMOD 5.2439101e-05
Previous Page 1 / 1 Next

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.00029168671
469 Optimization of Large Join Queries 1988 SIGMOD 0.00017749337
487 Randomized Algorithms For Optimizing Large Join Queries 1990 SIGMOD 0.00017455404
592 Global Query Optimization 1986 SIGMOD 0.00015835128
859 Query Optimization by Simulated Annealing 1987 SIGMOD 0.0001341356
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 1,449 Design and Analysis of Parametric Query Optimization Algorithms 1998 VLDB
2 3,215 Efficient and Provable Multi-Query Optimization 2017 PODS
3 6,219 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,290 A Formal Model of Trade-off between Optimization and Execution Costs in Semantic Query Optimization 1988 VLDB
6 3,574 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,627 On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces 1993 VLDB