Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins.

@inproceedings{DBLP:conf/vldb/ChenLYY92,
  author    = {Ming-Syan Chen and
               Ming-Ling Lo and
               Philip S. Yu and
               Honesty C. Young},
  editor    = {Li-Yan Yuan},
  title     = {Using Segmented Right-Deep Trees for the Execution of Pipelined
               Hash Joins},
  booktitle = {18th International Conference on Very Large Data Bases, August
               23-27, 1992, Vancouver, Canada, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1992},
  isbn      = {1-55860-151-1},
  pages     = {15-26},
  ee        = {db/conf/vldb/ChenLYY92.html},
  crossref  = {DBLP:conf/vldb/92},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1992 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• 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/vldb8997 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

References

[1]

Chaitanya K. Baru, Ophir Frieder: Database Operations in a Cube-Connected Multicomputer System. IEEE Trans. Computers 38(6): 920-927(1989) BibTeX

[2]

Haran Boral, William Alexander, Larry Clay, George P. Copeland, Scott Danforth, Michael J. Franklin, Brian E. Hart, Marc G. Smith, Patrick Valduriez: Prototyping Bubba, A Highly Parallel Database System. IEEE Trans. Knowl. Data Eng. 2(1): 4-24(1990) BibTeX

[3]

Ming-Syan Chen, Philip S. Yu: Determining Beneficial Semijoins for a Join Sequence in Distributed Query Processing. ICDE 1991: 50-58 BibTeX

[4]

Ming-Syan Chen, Philip S. Yu, Kun-Lung Wu: Scheduling and Processor Allocation for Parallel Execution of Multi-Join Queries. ICDE 1992: 58-67 BibTeX

[5]

David J. DeWitt, Robert H. Gerber: Multiprocessor Hash-Based Join Algorithms. VLDB 1985: 151-164 BibTeX

[6]

David J. DeWitt, Shahram Ghandeharizadeh, Donovan A. Schneider, Allan Bricker, Hui-I Hsiao, Rick Rasmussen: The Gamma Database Machine Project. IEEE Trans. Knowl. Data Eng. 2(1): 44-62(1990) BibTeX

[7]

David J. DeWitt, Jim Gray: Parallel Database Systems: The Future of High Performance Database Systems. Commun. ACM 35(6): 85-98(1992) BibTeX

[8]

Danièle Gardy, Claude Puech: On the Effects of Join Operations on Relation Sizes. ACM Trans. Database Syst. 14(4): 574-603(1989) BibTeX

[9]

Goetz Graefe: Rule-Based Query Optimization in Extensible Database Systems. Ph.D. thesis, Univ. of Wisconsin-Madison 1987
BibTeX

[10]

Wei Hong, Michael Stonebraker: Optimization of Parallel Query Execution Plans in XPRS. PDIS 1991: 218-225 BibTeX

[11]

Yannis E. Ioannidis, Younkyung Cha Kang: Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and its Implications for Query Optimization. SIGMOD Conference 1991: 168-177 BibTeX

[12]

Ming-Ling Lo, Ming-Syan Chen, Chinya V. Ravishankar, Philip S. Yu: On Optimal Processor Allocation to Support Pipelined Hash Joins. SIGMOD Conference 1993: 69-78 BibTeX

[13]

...

[14]

Hongjun Lu, Kian-Lee Tan, Ming-Chien Shan: Hash-Based Join Algorithms for Multiprocessor Computers. VLDB 1990: 198-209 BibTeX

[15]

Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992) BibTeX

[16]

Edward Omiecinski, Eileen Tien Lin: Hash-Based and Index-Based Join Algorithms for Cube and Ring Connected Multicomputers. IEEE Trans. Knowl. Data Eng. 1(3): 329-343(1989) BibTeX

[17]

Hamid Pirahesh, C. Mohan, Josephine M. Cheng, T. S. Liu, Patricia G. Selinger: Parallelism in Relational Data Base Systems: Architectural Issues and Design Approaches. DPDS 1990: 4-29 BibTeX

[18]

James P. Richardson, Hongjun Lu, Krishna P. Mikkilineni: Design and Evaluation of Parallel Pipelined Join Algorithms. SIGMOD Conference 1987: 399-409 BibTeX

[19]

...

[20]

Donovan A. Schneider, David J. DeWitt: A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment. SIGMOD Conference 1989: 110-121 BibTeX

[21]

Donovan A. Schneider, David J. DeWitt: Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines. VLDB 1990: 469-480 BibTeX

[22]

Michael Stonebraker, Randy H. Katz, David A. Patterson, John K. Ousterhout: The Design of XPRS. VLDB 1988: 318-330 BibTeX

[23]

Arun N. Swami: Optimization of Large Join Queries: Combining Heuristic and Combinatorial Techniques. SIGMOD Conference 1989: 367-376 BibTeX

[24]

Annita N. Wilschut, Peter M. G. Apers: Dataflow Query Execution in a Parallel Main-Memory Environment. PDIS 1991: 68-77 BibTeX

[25]

Joel L. Wolf, Daniel M. Dias, Philip S. Yu, John Turek: An Effective Algorithm for Parallelizing Hash Joins in the Presence of Data Skew. ICDE 1991: 200-209 BibTeX

[26]

Philip S. Yu, Ming-Syan Chen, Hans-Ulrich Heiss, Sukho Lee: On Workload Characterization of Relational Database Environments. IEEE Trans. Software Eng. 18(4): 347-355(1992) BibTeX

Referenced by

1. Navin Kabra, David J. DeWitt: Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans. SIGMOD Conference 1998: 106-117
2. Manish Mehta, David J. DeWitt: Data Placement in Shared-Nothing Parallel Database Systems. VLDB J. 6(1): 53-72(1997)
3. Minos N. Garofalakis, Yannis E. Ioannidis: Multi-dimensional Resource Scheduling for Parallel Queries. SIGMOD Conference 1996: 365-376
4. Manish Mehta, David J. DeWitt: Managing Intra-operator Parallelism in Parallel Database Systems. VLDB 1995: 382-394
5. Waqar Hasan, Rajeev Motwani: Coloring Away Communication in Parallel Query Optimization. VLDB 1995: 239-250
6. Annita N. Wilschut, Jan Flokstra, Peter M. G. Apers: Parallel Evaluation of Multi-Join Queries. SIGMOD Conference 1995: 115-126
7. Hongjun Lu, Kian-Lee Tan: Batch Query Processing in Shared-Nothing Multiprocessors. DASFAA 1995: 238-245
8. Abdelkader Hameurlain, Franck Morvan: Scheduling and Mapping for Parallel Execution of Extended SQL Queries. CIKM 1995: 197-204
9. Hui-I Hsiao, Ming-Syan Chen, Philip S. Yu: On Parallel Execution of Multiple Pipelined Hash Joins. SIGMOD Conference 1994: 185-196
10. Goetz Graefe: Sort-Merge-Join: An Idea Whose Time Has(h) Passed? ICDE 1994: 406-417
11. Mikal Ziane, Mohamed Zaït, Pascale Borla-Salamet: Parallel Query Processing with Zigzag Trees. VLDB J. 2(3): 277-301(1993)
12. Kien A. Hua, Yu-lung Lo, Honesty C. Young: Considering Data Skew Factor in Multi-Way Join Query Optimization for Parallel Execution. VLDB J. 2(3): 303-330(1993)
13. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
14. Ming-Syan Chen, Hui-I Hsiao, Philip S. Yu: Applying Hash Filters to Improving the Execution of Bushy Trees. VLDB 1993: 505-516
15. Eugene J. Shekita, Honesty C. Young, Kian-Lee Tan: Multi-Join Optimization for Symmetric Multiprocessors. VLDB 1993: 479-492
16. Manish Mehta, David J. DeWitt: Dynamic Memory Allocation for Multiple-Query Workloads. VLDB 1993: 354-367
17. Ming-Ling Lo, Ming-Syan Chen, Chinya V. Ravishankar, Philip S. Yu: On Optimal Processor Allocation to Support Pipelined Hash Joins. SIGMOD Conference 1993: 69-78
18. Manish Mehta, Valery Soloviev, David J. DeWitt: Batch Scheduling in Parallel Database Systems. ICDE 1993: 400-410
19. Ming-Syan Chen, Philip S. Yu, Kun-Lung Wu: Scheduling and Processor Allocation for Parallel Execution of Multi-Join Queries. ICDE 1992: 58-67