Hash-Based Join Algorithms for Multiprocessor Computers.

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

@inproceedings{DBLP:conf/vldb/LuTS90,
  author    = {Hongjun Lu and
               Kian-Lee Tan and
               Ming-Chien Shan},
  editor    = {Dennis McLeod and
               Ron Sacks-Davis and
               Hans-J{\"o}rg Schek},
  title     = {Hash-Based Join Algorithms for Multiprocessor Computers},
  booktitle = {16th International Conference on Very Large Data Bases, August
               13-16, 1990, Brisbane, Queensland, Australia, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1990},
  isbn      = {1-55860-149-X},
  pages     = {198-209},
  ee        = {db/conf/vldb/LuTS90.html},
  crossref  = {DBLP:conf/vldb/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

This paper studies a number of hash-based join algorithms for general purpose multiprocessor computers with shared memory where the amount of memory allocated to the join operation is proportional to the number of processors assigned to the operation and a global hash table is built in this shared memory. The concurrent update and access to this global hash table is studied. The elapsed time and total processing time for these algorithms are analyzed. The results indicate that, hybrid hash join that outperforms other hash-based algorithms in uniprocessor systems does not always performs the best. A simpler algorithm, hash-based nested loops join, performs better in terms ofelapsed time when both the relations are of similar sizes.

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

CDROM Version: Load the CDROM "Volume 1 Issue 5, VLDB '89-'97" 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/vldb8997 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" 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 DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Dennis McLeod, Ron Sacks-Davis, Hans-Jörg Schek (Eds.): 16th International Conference on Very Large Data Bases, August 13-16, 1990, Brisbane, Queensland, Australia, Proceedings. Morgan Kaufmann 1990, ISBN 1-55860-149-X

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)
[Brat84]: Kjell Bratbergsengen: Hashing Methods and Relational Algebra Operations. VLDB 1984: 323-333
[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
[DeWi85]: David J. DeWitt, Robert H. Gerber: Multiprocessor Hash-Based Join Algorithms. VLDB 1985: 151-164
[Ensl77]: Philip H. Enslow Jr.: Multiprocessor Organization - A Survey. ACM Comput. Surv. 9(1): 103-129(1977)
[Good81]: ...
[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)
[Laks88]: M. Seetha Lakshmi, Philip S. Yu: Effect of Skew on Join Performance in Parallel Architectures. DPDS 1988: 107-120
[Lang82]: A. M. Langer, Annie W. Shum: The Distribution of Granule Accesses Made by Database Transactions. Commun. ACM 25(11): 831-832(1982)
[Low90]: ...
[Lu85]: Hongjun Lu, Michael J. Carey: Some Experimental Results on Distributed Join Algorithms in a Local Network. VLDB 1985: 292-304
[Lu90]: ...
[Meno86]: ...
[Qada88]: Ghassan Z. Qadah, Keki B. Irani: The Join Alogorithms on a Shared-Memory Multiprocessor Database Machine. IEEE Trans. Software Eng. 14(11): 1668-1683(1988)
[Rich87]: James P. Richardson, Hongjun Lu, Krishna P. Mikkilineni: Design and Evaluation of Parallel Pipelined Join Algorithms. SIGMOD Conference 1987: 399-409
[Schn89]: 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
[Shap86]: Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986)
[Tera83]: ...
[Vald84]: Patrick Valduriez, Georges Gardarin: Join and Semijoin Algorithms for a Multiprocessor Database Machine. ACM Trans. Database Syst. 9(1): 133-161(1984)
[Yao77]: S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977)