TR-78: Improving Semijoin Evaluation in Distributed Query Processing

Abstract

The semi-join operation constitutes the fundamental operation for reducing
the volume of data transferred between sites in a distributed query processing. We present a method called “augmented semi-join” evaluation technique that mini­
mizes the volume of data exchanged between sites in query processing algorithms
that relying on semi-join computations. The technique performs some initial pre­processing of the common join-attribute values of relations stored at different sites
in such a way that each site can determine the tuples of the various relations that participate in the join computation for all subsequent queries that compute joins.
Let jCTql denote the total volume of intersite data transferred to achieve complete reduction of the relations referenced in a query Q by using a semi-join expression
CTq. Let lo-Q i denote the volume of data exchanged in achieving the same reduc­
tion with an augmented semi-join evaluation. Then we have that iaol S 0.5ICTqj always. For some special queries e.g., simple queries, the query can be completely evaluated without semi-join computations, i.e., lol = 0.