Park Ung Kyu

The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 6, No. 6, pp. 1468-1480, Jun. 1999
10.3745/KIPSTE.1999.6.6.1468,   PDF Download:

Abstract

In database systems, join operations are the most complex and time consuming ones which limit performance of such system. Many parallel join algorithms have been proposed for the systems. However, they did not consider data skew, such as attribute value skew(AVS) and join product skew(JPS). In the skewness environments, performance of their algorithms can degrade due to load imbalance during join operation processing. In this paper, we propose a framework for a uniform load distribution and an efficient parallel join algorithm using the framework to handle AVS and JPS. In our algorithm, we estimate data distributions of input and output relations of join operations using the sampling methodology and evaluate join cost for the estimated data distributions. Finally, using the histogram equalization method we distributed data among nodes to achieve good load balancing among nodes in the local joining phase. For performance comparison, we present simulation model of our algorithm and other join algorithms and present the result of some simulation experiments. The results indicate that our algorithm outperforms other algorithms in the skewed case.

Statistics
Cite this article