Dynamic Load Balancing In Very Large Shared-Nothing Hypercube Database-Computers

A consensus on parallel architecture for database management has emerged. This architecture is based on a shared-nothing (message passing) hardware organization. Various network topologies can be used to implement this structure. Among them, hypercube is widely used for many commercial highly parallel systems such as Intel iPSC/2 and nCUBE nCUBE/2. The availability of these machines has spurred a great interest in developing database management systems for this structure. Recently, two relational join strategies, Broadcast-Based Join and Bucket-Based Join, have been proposed specifically for the hypercube interconnection topology. The first strategy, however, incurs many unnecessary comparisons of pairs of tuples of the two relations. Although the second technique compares only tuples of the relevant buckets, it may suffer from potential load imbalance which is most critical to the performance of a shared-nothing system. This paper deals with these issues. In particular, we propose a novel join algorithm, for hypercube computers, which includes dynamic load balancing capabilities to minimize the effect of skewness in tuple distribution. Our simulation results indicate that the proposed scheme provides significant improvement over the Bucket-Based Join strategy. It is also interesting to observe that our technique is consistently superior even when the skew condition is very mild