A PARALLEL SORT-BALANCE MUTUAL RANGE-JOIN ALGORITHM ON HYPERCUBE COMPUTERS

This paper presents an efficient parallel algorithm for computing the mutual range-join of N sets of numbers on shared-nothing hypercube com puters. The algorithm iteratively joins each set to the mutual range-j oin of the preceding sets. Each join is performed on all processors of the hypercube in parallel. The algorithm uses a global sorting method to distribute the elements of the first set evenly across all process ors in increasing order, a new data balancing technique to distribute the elements of subsequent sets to match the intermediate set at each processor and to compensate for join skew, and a new efficient local r ange-join procedure. We analyse the performance of this algorithm and demonstrate that it improves on the previous result for this problem w hen the join selectivity factor is small and the restriction of SIMD o peration is lifted. The method can also be applied to similar problems such as band-join and equi-join. (C) 1998 Elsevier Science B.V.