Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor.

Edward Omiecinski: Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor. VLDB 1991: 375-385

@inproceedings{DBLP:conf/vldb/Omiecinski91,
  author    = {Edward Omiecinski},
  editor    = {Guy M. Lohman and
               Am\'{\i}lcar Sernadas and
               Rafael Camps},
  title     = {Performance Analysis of a Load Balancing Hash-Join Algorithm
               for a Shared Memory Multiprocessor},
  booktitle = {17th International Conference on Very Large Data Bases, September
               3-6, 1991, Barcelona, Catalonia, Spain, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1991},
  isbn      = {1-55860-150-3},
  pages     = {375-385},
  ee        = {db/conf/vldb/Omiecinski91.html},
  crossref  = {DBLP:conf/vldb/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Within the last several years, there has been a growing interest in applying general multiprocessor systems to relational database query processing. Efficient parallel algorithms have been designed for the join operation but usually have a failing in that their performance deteriorates greatly when the data is nonuniform. In this paper, we propose a new version of the hash- based join algorithm that balances the load between the processors, for any given bucket, in a shared everything environment. We develop an analytical model of the cost of the algorithm and implement the algorithm on a shared memory multiprocessor machine. We also perform a number of experiments comparing our model with our empirical results.

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

Guy M. Lohman, Amílcar Sernadas, Rafael Camps (Eds.): 17th International Conference on Very Large Data Bases, September 3-6, 1991, Barcelona, Catalonia, Spain, Proceedings. Morgan Kaufmann 1991, ISBN 1-55860-150-3

References

[BF87]: Chaitanya K. Baru, Ophir Frieder: Implementing Relational Database Operations in a Cube-Connected Multicomputer System. ICDE 1987: 36-43
[DKT90]: S. Misbah Deen, D. N. P. Kannangara, Malcolm C. Taylor: Multi-Join on Parallel Processors. DPDS 1990: 92-102
[DG85]: David J. DeWitt, Robert H. Gerber: Multiprocessor Hash-Based Join Algorithms. VLDB 1985: 151-164
[DGGHKM86]: 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
[HS78]: Ellis Horowitz, Sartaj Sahni: Fundamentals of Computer Algorithms. Computer Science Press 1978
[KNHT90]: Masaru Kitsuregawa, Miyuki Nakano, Lilian Harada, Mikio Takagi: Performance Evaluation of Functional Disk System with Nonuniform Data Distribution. DPDS 1990: 80-89
[KO90]: Masaru Kitsuregawa, Yasushi Ogawa: Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC). VLDB 1990: 210-221
[KTM83]: 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)
[LY88]: M. Seetha Lakshmi, Philip S. Yu: Effect of Skew on Join Performance in Parallel Architectures. DPDS 1988: 107-120
[LTS90]: Hongjun Lu, Kian-Lee Tan, Ming-Chien Shan: Hash-Based Join Algorithms for Multiprocessor Computers. VLDB 1990: 198-209
[MR89]: Marguerite C. Murphy, Doron Rotem: Effective Resource Utilization for Multiprocessor Join Execution. VLDB 1989: 67-75
[OL89]: 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)
[OS90]: ...
[QI88]: 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)
[SD89]: 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
[Sha86]: Leonard D. Shapiro: Join Processing in Database Systems with Large Main Memories. ACM Trans. Database Syst. 11(3): 239-264(1986)
[SKPO88]: Michael Stonebraker, Randy H. Katz, David A. Patterson, John K. Ousterhout: The Design of XPRS. VLDB 1988: 318-330
[WDY90]: Joel L. Wolf, Daniel M. Dias, Philip S. Yu: An Effective Algorithm for Parallelizing Sort Merge in the Presence of Data Skew. DPDS 1990: 103-115