language: en

Predictive Dynamic Load Balancing of Parallel Hash-Joins over Heterogeneous Processors in the Presence of Data Skew

Hasanat M. Dewan Mauricio Hernandez Kui W. Mok Salvatore J. Stolfo
Department of Computer Science, Columbia University,
New York, NY 10027
CUCS-026-94

(This is an extended version of the paper that appeared in the Proceedings of the 3rd International Conference on Parallel and Distributed Information Systems.)

Abstract In this paper, we present new algorithms to balance the computation of parallel hash joins over heterogeneous processors in the presence of data skew and external loads. Heterogeneity in our model consists of disparate computing elements, as well as general purpose computing ensembles that are subject to external loading (e.g., a LAN connected workstation cluster). Data skew manifests itself as significant non-uniformities in the distribution of attribute values of underlying relations that are involved in a join. We develop cost models and predictive dynamic load balancing protocols to detect imbalance during the computation of a single large join. New predictive bucket scheduling algorithms are presented that smooth out the load over the entire ensemble by reallocating buckets whenever imbalance is detected. Our algorithms can account for imbalance due to data skew as well as heterogeneity in the computing environment. Significant performance gains are reported for a wide range of test cases on a prototype implementation of the system.

1 Introduction