Using join operations as reducers in distributed query processing

Abstract

Semijoin has traditionally been relied upon for reducing the communication cost required for distributed query processing. However, judiciously applying join operations as reducers can lead to further reduction in the communication cost. In view of this fact, the approach of using join operations, in addition to semijoins, as reducers in distributed query processing is explored. It is first shown that the problem of determining a sequence of join operations for a query graph can be transformed to that of finding a set of cuts to that graph, where a cut to a graph is a partition of the nodes in that graph. In light of the mapping, an efficient heuristic algorithm to determine an effective sequence of join reducers for a query is developed. The algorithm, using the concept of divide-and-conquer, is shown to have polynomial time complexity. Examples are given to illustrate the results.