Adaptive parallel distributive join algorithm for skewed data

Author

Chung, Soon M. ; Chatterjee, Arindam

Author_Institution

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

fYear

2001

fDate

2001

Firstpage

15

Lastpage

22

Abstract

We present an adaptive version of the parallel distributive join (DJ) algorithm that we proposed in (Chung and Yang, 1996). The adaptive parallel DJ algorithm can handle the data skew in operand relations efficiently. We implemented the original and adaptive parallel DJ algorithms on a network of Alpha workstations using the Parallel Virtual Machine (PVM). We analyzed the performance of the algorithms, and compared it with that of the parallel Hybrid-Hash (HH) join algorithms. Our results show that the parallel DJ algorithms perform comparably with the parallel HH join algorithms over the entire range of the number of processors used and for different join selectivities. A significant advantage of the parallel DJ algorithms is that they can easily support non-equijoin operations

Keywords

parallel algorithms; relational algebra; relational databases; software performance evaluation; workstation clusters; Alpha workstation network; PVM; Parallel Virtual Machine; adaptive parallel distributive join algorithm; algorithm performance; data skew; nonequijoin operations; operand relations; parallel Hybrid-Hash join algorithms; relational algebra; Algorithm design and analysis; Clustering algorithms; Computer science; Delay; Hardware; Parallel algorithms; Partitioning algorithms; Performance analysis; Virtual machining; Workstations;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Systems, 2001. ICPADS 2001. Proceedings. Eighth International Conference on

Conference_Location

Kyongju City

ISSN

1521-9097

Print_ISBN

0-7695-1153-8

Type

conf

DOI

10.1109/ICPADS.2001.934796

Filename

934796