Virtual-join: A query execution technique

Abstract

Although communication cost is still a major cost for distributed databases, local cost in distributed query processing cannot be neglected. Observing the fact that almost all commercial database products employ Plan Enumeration with Dynamic Programming (PEDP) techniques, we find reducing the cost of both communication and local processing in 2-way join has potential benefits. Although many methods for reducing communication cost have been proposed, most of them employ a cost model that neglects local processing cost. This paper proposes a join execution method (called virtual join) that considers both of them. Virtual join has two desirable features: 1) Being adaptive to different values of selectivity. 2) Giving accurate cardinality of join result before it is materialized. Experiment results showed virtual join was both adaptive and efficient.