As parallel database computers have been more popular, the design of efficient parallel join algorithms has been one of major issues of the database system area. Basically, the conventional parallel join algorithms have two phases: partitioning the joined relations and locally joining the partitioned relations in parallel. In real databases, it is often found that certain values for a given attribute occur more frequently than other values. This phenomenon is referred to as data skew. With skewed data distribution, the join algorithms have encountered many difficulties to achieve good load balancing among processors in the joining phase. This thesis discusses a data distribution problem for load balance on parallel join algorithms to minimize total execution time.
We first propose a data distribution framework to resolve load imbalance and bucket overflow in parallel join. Using the histogram transformation technique, the framework transforms a histogram of skewed data to a desired distribution that corresponds to the relative computing power of node processors in the system.
Next we propose an efficient parallel join algorithm for handling skewed data based on the proposed data distribution method. The main idea is to use the data distribution framework for allocating relations evenly across all the nodes. The proposed join algorithm works in three phases: the histogram evaluation phase, the partitioning phase, and the joining phase. The histogram evaluation phase first obtains a cumulative histogram of the hashed values of the join attribute for the smaller relation. Then, it determines a histogram equalization transfer function and boundary values for partitioning. In the subsequent partitioning phase, the relations are distributed among the nodes using the boundary values. Finally, the partitioned relations are locally joined on each node processor in parallel.
We also present a parallel join algorithm for a heterogeneous system where computing power of each node may be different. In the system, data distribution algorithm for efficient local join needs to allocate unequal size of data into nodes to acquire load balancing. We also employ the data distribution framework based on the histogram transformation technique to achieve good load balancing in the heterogeneous computing environment.
For validation and performance comparison of our algorithm with other hashbased algorithms, we present an analytical cost model and a simulation model. We also implement our algorithm in the COREDB database computer with 8-node hypercube architecture. We also perform simulation experiments and actual execution in COREDB computer under several different environments. In these experiments, skewed data distribution of the join attribute is modeled using a Zipf-like distribution. The performance studies indicate that 1) our algorithm exhibits better performance compared with the conventional hash-based algorithm in the skewed distribution and has a negligible overhead in the uniform distribution, and 2) our algorithm outperforms other skew handling algorithms in all the cases.
데이타베이스 관리 시스템의 성능을 향상시키고자 하는 연구가 활발히 이루어 지고 있다. 이러한 연구의 큰 흐름은 다중 프로세서 컴퓨터에서의 병렬 처리에 의한 성능 향상이다. 본 논문은 관계형 데이타베이스 관리 시스템에서 가장 많이 사용되고 그 비용이 큰 결합 연산의 병렬화에 관한 연구이다.
과거에 많은 병렬 결합 알고리즘들이 제안되었으며 그것들 중에서 해쉬 결합 알고리즘이 병렬 처리가 용이하고 그 성능이 우수하다고 알려져 있다. 그러나 지금까지 제안된 대부분의 해쉬 결합 알고리즘은 데이타의 결합 애트리뷰트가 불균일한 분포를 갖는 경우에, 노드 프로세서 사이에 데이타의 불균형 분산과 국부적 결합시에 버켓 오버플로우가 발생한다. 병렬 결합 연산의 성능은 최대 수행시간을 요하는 프로세서에 의하여 결정되므로 버켓 오버플로우나 불균형 분산은 성능에 상당한 저하를 가져온다. 따라서 본 논문에서는 불균일한 데이타 분포에서 병렬 해쉬 결합 연산의 성능 향상을 위하여 노드 프로세서 사이에 부하 균등을 주는 튜플의 재분산 문제를 다루고자 하였다.
우선 본 논문에서는 병렬 결합 연산에서 부하 불균형과 버켓 오버플로우를 해결하는 새로운 데이타 분산 틀을 제안하였다. 제안된 데이타 분산 틀은 히스토그램 변환기법을 이용하여 불균일한 데이타의 히스토그램을 시스템 안에 있는 노드 프러세서의 상대적인 계산 능력에 상응하는 히스토그램으로 변환되도록 데이타를 분산한다.
그리고 본 논문에서는 제안된 데이타 분산 틀을 이용하여 불균일 데이타 분포 문제를 해결할 수 있는 효율적인 병렬 결합 알고리즘을 제안하였다. 이 알고리즘은 분할 단계에 앞서서 결합할 릴레이션 중에서 작은 릴레이션의 결합 애트리뷰트에 해쉬 함수를 적용하여, 해쉬 결과값의 히스토그램을 구하는 히스토그램 계산 단계와 이를 이용한 릴레이션의 균형 분산 및 결합의 단계로 구성된다. 또한 본 논문에서는 서로 다른 계산 능력을 갖는 노드 프로세서로 구성된 병렬 환경에서 효율적인 병렬 결합 알고리즘을 제안하였다. 이 알고리즘은 제안된 데이타 분산 틀을 이용하여 노드 프로세서 사이에 부하 균등을 얻기위하여 노드 프로세서에 서로 다른 양의 데이타를 분산한다.
본 논문에서는 제안된 알고리즘들의 정당성을 입증하기 위하여 실제적인 상황을 가정한 다양한 모의 실험을 하였다. 실제적인 데이타베이스에서 데이타 분포가 Zipf 분포를 갖는다는 것이 여러 연구의 결과로 입증되었기 때문에, 모의실험을 위한 실험 데이타베이스를 Zipf 분포를 갖도록 생성하였다. 모의실험 결과 제안된 알고리즘은 기존의 병렬 해쉬 결합 방법 뿐만 아니라 데이타의 불균일 분포 문제를 다루는 기존의 다른 제안된 방법들 보다 데이타를 균일하게 분산 시킴을 알 수 있었다. 또한 제안된 알고리즘은 서로 다른 계산 능력을 갖는 노드 프로세서로 구성된 병렬 환경에서도 부하 균등을 주도록 데이타를 분산 시킴을 알 수 있었다. 그리고 본 논문에서는 제안된 알고리즘과 기존의 여러 병렬 해쉬 결합 알고리즘들과의 성능을 비교하기 위하여 모의실험 모델을 설계하였고 모의실험을 통하여 여러 알고리즘의 성능을 계산하였다. 실험 결과 제안된 알고리즘은 기존의 데이타 불균형을 고려하지 않은 병렬 해쉬 결합 방법보다 데이타의 불균일한 상황에서 항상 좋은 성능을 나타내었으며, 데이타가 균일한 경우에도 무시할 수 있을 정도로 미비한 부가적인 비용이 단지 필요로 함을 알 수 있었다. 또한 모의 실험 결과 본 논문에서 제안된 알고리즘은 기존의 데이타 불균일을 고려하여 제안된 알고리즘 보다 항상 좋은 성능을 갖는 것을 알 수 있었다.
본 논문에서는 성능 비교를 위하여 설계한 모의실험 모델의 타당성을 입증하고, 실제 컴퓨터에서의 수행시의 성능을 측정하기 위하여, 한국과학기술원 전기 및 전자공학과 컴퓨터공학 연구실에서 개발한 하이퍼큐브형 구조인 COREDB 병렬 데이타베이스 컴퓨터에 제안된 알고리즘을 구현하고, 기존의 병렬 결합 알고리즘과의 성능 비교를 위한 실험을 하였다. 실험 결과는 모의 실험 결과와 같음을 알 수 있었다.
