Design and Evaluation of Parallel Pipelined Join Algorithms.

@inproceedings{DBLP:conf/sigmod/RichardsonLM87,
  author    = {James P. Richardson and
               Hongjun Lu and
               Krishna P. Mikkilineni},
  editor    = {Umeshwar Dayal and
               Irving L. Traiger},
  title     = {Design and Evaluation of Parallel Pipelined Join Algorithms},
  booktitle = {Proceedings of the Association for Computing Machinery Special
               Interest Group on Management of Data 1987 Annual Conference,
               San Francisco, California, May 27-29, 1987},
  publisher = {ACM Press},
  year      = {1987},
  pages     = {399-409},
  ee        = {http://doi.acm.org/10.1145/38713.38756, db/conf/sigmod/RichardsonLM87.html},
  crossref  = {DBLP:conf/sigmod/87},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

The join operation is the most costly operation in relational database management systems. Distributed and parallel processing can effectively speed up the join operation. In this paper, we describe a number of highly parallel and pipelined multiprocessor join algorithms using sort-merge and hashing techniques. Among them, two algorithms are parallel and pipelined versions of traditional sort-merge join methods, two algorithms use both hashing and sort-merge techniques, and another two are variations of the hybrid hash join algorithms. The performance of those algorithms is evaluated analytically against a generic database machine architecture. The methodology used in the design and evaluation of these algorithms is also discussed.

The results of the analysis indicate that using a hashing technique to partition the source relations can dramatically reduce the elapsed time hash-based algorithms outperform sort-merge algorithms in almost all cases because of their high parallelism. Hash-based sort-merge and hybrid hash methods provide similar performance in most cases. With large source relations, the algorithms which replicate the smaller relation usually give better elapsed time. Sharing memory among processors also improves performance somewhat.

Copyright © 1987 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

[Bitt83]

Dina Bitton, Haran Boral, David J. DeWitt, W. Kevin Wilkinson: Parallel Algorithms for the Execution of Relational Database Operations. ACM Trans. Database Syst. 8(3): 324-353(1983) BibTeX

[Brat84]

Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333 BibTeX

[DeWi79]

...

[DeWi84]

David J. DeWitt, Randy H. Katz, Frank Olken, Leonard D. Shapiro, Michael Stonebraker, David A. Wood: Implementation Techniques for Main Memory Database Systems. SIGMOD Conference 1984: 1-8 BibTeX

[DeWi85]

Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985: 127-141 BibTeX

[DeWi86]

David J. DeWitt, Robert H. Gerber, Goetz Graefe, Michael L. Heytens, Krishna B. Kumar, M. Muralikrishna: GAMMA - A High Performance Dataflow Database Machine. VLDB 1986: 228-237 BibTeX

[Kits83]

Masaru Kitsuregawa, Hidehiko Tanaka, Tohru Moto-Oka: Application of Hash to Data Base Machine and Its Architecture. New Generation Comput. 1(1): 63-74(1983) BibTeX

[Knut73]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX

[Lu85]

Hongjun Lu, Michael J. Carey: Some Experimental Results on Distributed Join Algorithms in a Local Network. VLDB 1985: 292-304 BibTeX

[Rich87]

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

[Schu79]

...

[Shib84]

Shigeki Shibayama, Takeo Kakuta, Nobuyoshi Miyazaki, Haruo Yokota, Kunio Murakami: A Relational Database Machine with Large Semiconductor Disk and Hardware Relational Algebra Processor. New Generation Comput. 2(2): 131-155(1984) BibTeX

[Su79]

...

[Tera83]

...

[Vald84]

Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984) BibTeX

Referenced by

1. Evan P. Harris, Kotagiri Ramamohanarao: Join Algorithm Costs Revisited. VLDB J. 5(1): 64-84(1996)
2. Ming-Syan Chen, Philip S. Yu, Kun-Lung Wu: Optimization of Parallel Execution for Multi-Join Queries. IEEE Trans. Knowl. Data Eng. 8(3): 416-428(1996)
3. 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)
4. Patrick Martin, Per-Åke Larson, Vinay Deshpande: Parallel Hash-Based Join Algorithms for a Shared-Everything. IEEE Trans. Knowl. Data Eng. 6(5): 750-763(1994)
5. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
6. Priti Mishra, Margaret H. Eich: Join Processing in Relational Databases. ACM Comput. Surv. 24(1): 63-113(1992)
7. 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
8. Ming-Syan Chen, Philip S. Yu, Kun-Lung Wu: Scheduling and Processor Allocation for Parallel Execution of Multi-Join Queries. ICDE 1992: 58-67
9. Christopher B. Walton, Alfred G. Dale, Roy M. Jenevein: A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins. VLDB 1991: 537-548
10. Hongjun Lu, Kian-Lee Tan, Ming-Chien Shan: Hash-Based Join Algorithms for Multiprocessor Computers. VLDB 1990: 198-209
11. Y. C. Tay: On the Optimality of Strategies for Multiple Joins. PODS 1990: 124-131
12. Balakrishna R. Iyer, Daniel M. Dias: System Issues in Parallel Sorting for Database Systems. ICDE 1990: 246-255
13. 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)
14. Farshad Fotouhi, Sakti Pramanik: Optimal Secondary Storage Access Sequence for Performing Relational Join. IEEE Trans. Knowl. Data Eng. 1(3): 318-328(1989)
15. Michael Stonebraker, Randy H. Katz, David A. Patterson, John K. Ousterhout: The Design of XPRS. VLDB 1988: 318-330
16. James P. Richardson, Hongjun Lu, Krishna P. Mikkilineni: Design and Evaluation of Parallel Pipelined Join Algorithms. SIGMOD Conference 1987: 399-409