Combining semijoins and hash-semijoins in a distributed query processing strategy

Tseng and Chen (1992) presented a new relational operator called a hash-semijoin. They proposed a method which will transform a sequence of semijoins, produced by any existing semijoin-based algorithm, into a more cost effective sequence by replacing some of the semijoins by hash-semijoins. The hash-semijoin can be very effective but some of the benefits may be negated by the occurrence of collisions in the reduction filter. Such collisions mean that the hash-semijoin cannot achieve the same amount of reduction as a semijoin can. However, under certain circumstances, the benefits may greatly outweigh the costs and thus collisions are not a serious problem. But their approach has not been experimentally evaluated. In this paper we explore their hypothesis that traditional algorithms, which use semijoins, can always be improved by replacing some or all of the semijoins by hash-semijoins. Four different algorithms are investigated. Each aims to minimize the amount of data transmitted around the network during distributed query processing.