A PARALLEL JOIN ALGORITHM FOR SIMD ARCHITECTURES

This paper presents a parallel join algorithm for the data-parallel ex ecution model used in SIMD architectures. This algorithm is hash-based , i.e., the tuples in a relation are divided into different buckets ba sed on the hash value of the join attribute. In this algorithm the buc kets are maintained in a distributed fashion, i.e., the tuples in a bu cket are stored in an array of processors. The join operation is perfo rmed in parallel over all the buckets. The algorithm presented here ha s been implemented and evaluated on the Connection Machine (CM-2). We present here the results of the experimental evaluation of this algori thm for different values of design parameters and work-load. Using exp erimental evaluations of the CM communication primitives we develop an alytical models for the performance evaluation of this algorithm and d emonstrate the effectiveness of these models. (C) 1997 Elsevier Scienc e Inc.