Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and its Implications for Query Optimization.

@inproceedings{DBLP:conf/sigmod/IoannidisK91,
  author    = {Yannis E. Ioannidis and
               Younkyung Cha Kang},
  editor    = {James Clifford and
               Roger King},
  title     = {Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and
               its Implications for Query Optimization},
  booktitle = {Proceedings of the 1991 ACM SIGMOD International Conference on
               Management of Data, Denver, Colorado, May 29-31, 1991},
  publisher = {ACM Press},
  year      = {1991},
  pages     = {168-177},
  ee        = {http://doi.acm.org/10.1145/115790.115813, db/conf/sigmod/IoannidisK91.html},
  crossref  = {DBLP:conf/sigmod/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1991 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod7592 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[Gran81]

...

[Ibar84]

Toshihide Ibaraki, Tiko Kameda: On the Optimal Nesting Order for Computing N-Relational Joins. ACM Trans. Database Syst. 9(3): 482-502(1984) BibTeX

[Ioan87]

Yannis E. Ioannidis, Eugene Wong: Query Optimization by Simulated Annealing. SIGMOD Conference 1987: 9-22 BibTeX

[Ioan90]

Yannis E. Ioannidis, Younkyung Cha Kang: Randomized Algorithms for Optimizing Large Join Queries. SIGMOD Conference 1990: 312-321 BibTeX

[Jark84]

Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984) BibTeX

[Kang91]

...

[Kim86]

Won Kim, David S. Reiner, Don S. Batory (Eds.): Query Processing in Database Systems. Springer 1985, ISBN 3-540-13831-5
Contents BibTeX

[Kirk83]

...

[Kris86]

Ravi Krishnamurthy, Haran Boral, Carlo Zaniolo: Optimization of Nonrecursive Queries. VLDB 1986: 128-137 BibTeX

[Monm79]

...

[Naha86]

...

[Roth86]

...

[Seli79]

Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX

[Sell86]

Timos K. Sellis: Global Query Optimization. SIGMOD Conference 1986: 191-205 BibTeX

[Swam88]

Arun N. Swami, Anoop Gupta: Optimization of Large Join Queries. SIGMOD Conference 1988: 8-17 BibTeX

[Ullm82]

Jeffrey D. Ullman: Principles of Database Systems, 2nd Edition. Computer Science Press 1982, ISBN 0-914894-36-6
BibTeX

Referenced by

1. Florian Waas, César A. Galindo-Legaria: Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer. SIGMOD Conference 2000: 499-509
2. Dimitris Papadias, Nikos Mamoulis, Yannis Theodoridis: Processing and Optimization of Multiway Spatial Joins Using R-Trees. PODS 1999: 44-55
3. Michael Steinbrunn, Guido Moerkotte, Alfons Kemper: Heuristic and Randomized Optimization for the Join Ordering Problem. VLDB J. 6(3): 191-208(1997)
4. Yannis E. Ioannidis, Raymond T. Ng, Kyuseok Shim, Timos K. Sellis: Parametric Query Optimization. VLDB J. 6(2): 132-151(1997)
5. Ming-Syan Chen, Hui-I Hsiao, Philip S. Yu: On Applying Hash Filters to Improving the Execution of Multi-Join Queries. VLDB J. 6(2): 121-131(1997)
6. Arjan Pellenkoft, César A. Galindo-Legaria, Martin L. Kersten: The Complexity of Transformation-Based Join Enumeration. VLDB 1997: 306-315
7. Wolfgang Scheufele, Guido Moerkotte: On the Complexity of Generating Optimal Plans with Cross Products. PODS 1997: 238-248
8. Arjan Pellenkoft, César A. Galindo-Legaria, Martin L. Kersten: Duplicate-Free Generation of Alternatives in Transformation-Based Optimizers. DASFAA 1997: 117-124
9. John Mylopoulos, Vinay K. Chaudhri, Dimitris Plexousakis, Adel Shrufi, Thodoros Topaloglou: Building Knowledge Base Management Systems. VLDB J. 5(4): 238-263(1996)
10. Myra Spiliopoulou, Michael Hatzopoulos, Yannis Cotronis: Parallel Optimization of Large Join Queries with Set Operators and Aggregates in a Parallel Environment Supporting Pipeline. IEEE Trans. Knowl. Data Eng. 8(3): 429-445(1996)
11. Bennet Vance, David Maier: Rapid Bushy Join-order Optimization with Cartesian Products. SIGMOD Conference 1996: 35-46
12. Bojan Groselj, Qutaibah M. Malluhi: Combinatorial Optimization of Distributed Queries. IEEE Trans. Knowl. Data Eng. 7(6): 915-927(1995)
13. Ming-Syan Chen, Ming-Ling Lo, Philip S. Yu, Honesty C. Young: Applying Segmented Right-Deep Trees to Pipelining Multiple Hash Joins. IEEE Trans. Knowl. Data Eng. 7(4): 656-668(1995)
14. Hongjun Lu, Kian-Lee Tan, Son Dao: The Fittest Survives: An Adaptive Approach to Query Optimization. VLDB 1995: 251-262
15. Silvio Salza, Giovanni Barone, Tadeusz Morzy: Distributed Query Optimization in Loosly Coupled Multidatabase Systems. ICDT 1995: 40-53
16. César A. Galindo-Legaria, Arjan Pellenkoft, Martin L. Kersten: Uniformly-Distributed Random Generation of Join Orders. ICDT 1995: 280-293
17. Adel Shrufi, Thodoros Topaloglou: Query Processing for Knowledge Bases Using Join Indices. CIKM 1995: 158-166
18. César A. Galindo-Legaria, Arjan Pellenkoft, Martin L. Kersten: Fast, Randomized Join-Order Selection - Why Use Transformations? VLDB 1994: 85-95
19. Hui-I Hsiao, Ming-Syan Chen, Philip S. Yu: On Parallel Execution of Multiple Pipelined Hash Joins. SIGMOD Conference 1994: 185-196
20. Kien A. Hua, Sheau-Dong Lang, Wen K. Lee: A Decomposition-Based Simulated Annealing Technique for Data Clustering. PODS 1994: 117-128
21. Michael Stonebraker, Paul M. Aoki, Robert Devine, Witold Litwin, Michael A. Olson: Mariposa: A New Architecture for Distributed Data. ICDE 1994: 54-65
22. Tadeusz Morzy, Maciej Matysiak, Silvio Salza: Tabu Search Optimization of Large Join Queries. EDBT 1994: 309-322
23. Mikal Ziane, Mohamed Zaït, Pascale Borla-Salamet: Parallel Query Processing with Zigzag Trees. VLDB J. 2(3): 277-301(1993)
24. Philip S. Yu, Douglas W. Cornell: Buffer Management Based on Return on Consumption in a Multi-Query Environment. VLDB J. 2(1): 1-37(1993)
25. Ming-Syan Chen, Hui-I Hsiao, Philip S. Yu: Applying Hash Filters to Improving the Execution of Bushy Trees. VLDB 1993: 505-516
26. Eugene J. Shekita, Honesty C. Young, Kian-Lee Tan: Multi-Join Optimization for Symmetric Multiprocessors. VLDB 1993: 479-492
27. Rosana S. G. Lanzelotte, Patrick Valduriez, Mohamed Zaït: On the Effectiveness of Optimization Search Strategies for Parallel Execution Spaces. VLDB 1993: 493-504
28. Allen Van Gelder: Multiple Join Size Estimation by Virtual Domains. PODS 1993: 180-189
29. Yannis E. Ioannidis, Raymond T. Ng, Kyuseok Shim, Timos K. Sellis: Parametric Query Optimization. VLDB 1992: 103-114
30. Ming-Syan Chen, Ming-Ling Lo, Philip S. Yu, Honesty C. Young: Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins. VLDB 1992: 15-26