On Propagation of Reduction Effects of a Semijoin in Distributed Query Processing.

Abstract

In distributed query processing, the semijoin is used as an effective operator in reducing relations referenced in the query and thus reducing the total amount of data transmission. A semijoin is associated with two quantities: cost and benefit. These two quantities of semijoins are the useful ingredients in many heuristic algorithms proposed to generate a semijoin program which is a sequence of semijoins and is executed as a query pre- processing strategy. In this paper, in addition to the cost and benefit, we associate a semijoin with the third quantity: reduction propagation. It measures the propagation of reduction effects of a semijoin to other semijoins. We define this propagation in the context of distributed query processing and by precisely quantifying it, we present a heuristic algorithm to generate a semijoin program. The simulation reaults show that the new algorithm provides a considerable improvement over those based only on the cost and benefit.