Title

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

Keywords

Database machines; hypercube; load balancing; parallel join; relational database

Abstract

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. © 1993 IEEE

Publication Date

1-1-1993

Publication Title

IEEE Transactions on Computers

Volume

42

Issue

12

Number of Pages

1425-1439

Document Type

Article

Identifier

scopus

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/12.260633

Socpus ID

0027887699 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0027887699

This document is currently not available here.

Share

COinS