Parallel implementations of exclusion joins

This paper examines the parallel processing of exclusion join in a shared-nothing multiprocessor environment. First, a parallel hash-based exclusion join algorithm is presented. Unlike the case of equijoin, this algorithm does not work correctly in the presence of nulls in the join attributes. One solution is to restrict the hash-on attributes to non-nullable fields. However, this can lead to the well known data skew problem. If the number of tuples containing null values in their join attributes is small, an alternative is to replicate those tuples to all processors. Otherwise, we can consider a range partitioning algorithm where those tuples are only sent to a small subset of the processors. The hash-based algorithm usually outperforms the range partitioning algorithm except when the number of tuples containing null values in their join attributes is large or when the data is highly skewed