Skew-insensitive parallel algorithms for relational join

Author

Alsabti, Khaled ; Ranka, Sanjay

Author_Institution

Syracuse Univ., NY, USA

fYear

1998

fDate

17-20 Dec 1998

Firstpage

367

Lastpage

374

Abstract

Join is the most important and expensive operation in relational databases. The parallel join operation is very sensitive to the presence of the data skew. In this paper we present two new parallel join algorithms for coarse grained machines which work optimally in presence of arbitrary amount of data skew. The first algorithm is sort-based and the second is hash-based. Both of these algorithms employ a preprocessing phase to equally partition the work among the processors. These algorithms are shown to be theoretically as well as practically scalable

Keywords

database theory; file organisation; parallel algorithms; parallel machines; relational databases; resource allocation; coarse grained machines; data skew; hash-based algorithm; parallel join operation; preprocessing phase; relational database; relational join; scalable algorithms; skew-insensitive parallel algorithms; sort-based algorithm; work partitioning; Algorithm design and analysis; Costs; Databases; Hypercubes; Load management; Multiprocessor interconnection networks; Parallel algorithms; Partitioning algorithms; Subcontracting; User-generated content;

fLanguage

English

Publisher

ieee

Conference_Titel

High Performance Computing, 1998. HIPC '98. 5th International Conference On

Conference_Location

Madras

Print_ISBN

0-8186-9194-8

Type

conf

DOI

10.1109/HIPC.1998.738010

Filename

738010