A parallel distributive join algorithm for cube-connected multiprocessors

Author

Chung, Soon M. ; Yang, Jaerheen

Author_Institution

Dept. of Comput. Sci. & Eng., Wright State Univ., Dayton, OH, USA

Volume

7

Issue

2

fYear

1996

fDate

2/1/1996 12:00:00 AM

Firstpage

127

Lastpage

137

Abstract

This paper presents a parallel distributive join algorithm for cube-connected multiprocessors. The performance analysis shows that the proposed algorithm has an almost linear speedup over the sequential distributive join algorithm as the number of processors increases, and its performance is comparable to that of the parallel hybrid-hash join algorithm. A big advantage of the proposed algorithm over hash-based join algorithms is that it does not have the bucket overflow problem caused by nonuniform hashing of the smaller operand relation. Moreover, the proposed algorithm can easily support the nonequijoin operation, which is very hard to implement by using hash-based join algorithms

Keywords

database theory; multiprocessing systems; parallel algorithms; relational databases; cube-connected multiprocessors; distributive; distributive join algorithm; join algorithms; parallel; performance analysis; Computer science; Costs; Hardware; Merging; Parallel processing; Partitioning algorithms; Performance analysis; Relational databases; Sorting; Water resources;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.485502

Filename

485502