As performance becomes a crutical issue in large database applications, parallel database machines are receiving more attention in both theory and practice. In a ralational database management system running on such a machine, database operations are divided into a set of relational operations which are executed on a collection of processors in parallel. Among such operations join operations are the most complex and time consuming. These operations will limit the performance of such a database system. The effectiveness of parallel execution under join operations will largely depend on data distributions among processors in such a database machine.
Several parallel join algorithms are proposed for parallel relational databases systems, and the hash-partitioned parallel join algorithm (HPJA) is the most commonly used. It should be clear that for good parallelism the number of tuples mapped to each processor should be approximately equal. Most of the conventional parallel join algorithms have assumed uniform distribution of data. Therefore all algorithms including HPJA may limit the degree of parallelism in execution as degrees of replication in the join attribute values become large. For efficient parallel joins a hash function must map tuples with equal join attribute values to the same processor. However, there is no such a hash function that can avoid the skewness of data distribution resulted from these replicated values. The problem is that such skewness is inevitable even if an ideal hash function is used. Therefore if the data distribution is heavily skewed, load imbalances are caused by a skewed node. This will lose any of the advantages due to parallelism, and performance will be degraded.
This thesis proposes a new partitioning method to resolve the problem of data skewness for parallel join operations in a hypercube database system. Based on quantile selection, the algorithm makes data distribution to be approximately even among node processors in the hypercube. Proposed quantile-selection based partitioning method guarantees the approximately even distribution for heavily skewed environment. Therefore the quantile-select partitioned join algorithm(QSJA) can exploit the high degree of parallelism. For performance evaluation, we developed a simulation model of a hypercube database system on which various partitioning algorithms along with parallel join operations based on the algorithms are implemented. We analyzed on their performance with analyzed on their performance with respect to the execution time including CPU, I/O, and communication times. Performance of the proposed algorithm is compared with that of HPJAs. From performance evaluation, we show that the proposed join algorithm outperforms the existing HPJA and the skew resolution methods of HPJA. We implement our algorithm into COREDB, a hypercube multiprocessor databases computer, and experiment for performance comparison with the existing HPJA. also our proposed join algorithm outperforms the existing HPJA fof experimental of COREDB.
최근에 컴퓨터의 사용이 급격히 늘어나면서 점점 더 커지고 복잡해지는 정보를 효율적으로 처리하고 관리하기 위하여 데이타베이스시스템의 사용이 늘고있다. 실제로 데이타베이스시스템은 컴퓨터 응용에서 중요한 분야를 차지하고 있으며, 많은 새로운 응용분야에서 급속히 적용되고 있는 실정이다. 대용량의 자료를 처리하기 위한 데이타베이스 시스템에서는 성능이 중요한 연구과제가 되고 있으며, 성능 향상을 위하여 하드웨어 및 소프트웨어적으로 많은 연구가 진행되고 있다. 병렬처리형 데이타베이스 처리기에서, 데이타베이스 연산들은 각 처리기에서 수행되는 관계형 연산들의 집합으로 나누어진다. 이들 연산중에서 특히 결합 연산은 가장 자주 사용되는 연산중의 하나로서, 가장 복잡하고 처리시간이 긴 연산이다. 따라서 결합 연산은 데이타 베이스시스템의 성능에 매우 커다란 영향을 미치며, 많은 사람들이 이 연산의 성능 향상을 위하여 많은 병렬 결합 알고리즘들을 제안하였다. 또한 결합 연산의 병렬 수행의 효율성은 데이타베이스 컴퓨터에서 처리기들 사이의 자료 분포에도 크게 영향을 받음을 알 수 있다.
제안된 많은 병렬 결합 알고리즘 중에 해쉬 분할 병렬 결합 연산이 가장 많이 사용되고 있다. 그것은 각 처리기에 분포된 튜플들의 수가 거의 균등할때에 훌륭한 병렬화가 이루어 지며 최적의 성능을 얻을 수가 있다. 그러나, 보통의 병렬 알고리즘들은 대부분 자료의 균등 분포를 가정하였다. 따라서, 해쉬 분할 병렬 결합 연산을 포함한 모든 알고리즘들은 결합 속성 값의 중복도가 커질때 어느 한 처리기로의 치우침 현상이 발생하며, 병렬화의 효율이 크게 제한 받음을 알 수 있다. 이것은 해쉬 함수가 같은 결합 속성값을 가지는 튜플들에 대해 같은 처리기를 배정하기 때문이며, 이들 중복된 값들로 부터 초래되는 자료 분포의 치우침 현상을 피할 수 있는 해쉬 함수는 없다. 그러므로, 만약에 자료 분포가 매우 심하게 치우쳐져 있다면, 병렬 결합 연산을 수행함에 있어 부하 불균형 현상이 발생하며, 이로 인해 병렬화의 장점이 줄어 들게 되고 전체 성능 감소도 초래하게 될 것이다. 실제로 많은 데이타베이스시스템에서 자료들은 중복 현상이 발생하며, Zipf의 분포를 따른다고 알려져 있다.
본 논문에서는 하이퍼큐브형 데이타베이스 컴퓨터에서 병렬 결합 연산시의 자료 치우침 현상의 문제점들을 해결하기 위한 새로운 분할 기법을 제안한다. 이를 위해서 먼저 변량 표본값 추출을 이용한 외부 선택 알고리즘을 제안하며, 이 알고리즘이 2N 디스크 I/O만에 처리됨을 보인다. 그리고 이 변량 표본값 선택의 원리를 이용하여 하이퍼큐브 구조에서 각 처리기에 거의 균등하게 자료를 분할할 수 있음을 보인다. 제안된 변량 표본값 추출에 근거한 분할 기법은 매우 심하게 치우침이 생긴 환경에서도 거의 균등하게 분포됨을 보장한다. 그러므로, 본 분할기법에 근거한 병렬 결합 알고리즘은 매우 높은 병렬화를 이룰 수가 있다. 성능 분석을 위해 하이퍼큐브 구조의 모의 실험모델을 구축하였으며, 본 알고리즘과 해쉬 분할 병렬 결합 알고리즘 및 치우침 현상문제를 해결하기 위하여 제안된 알고리즘들과 비교하였다. 사용된 자료는 Zipf의 분포 규칙에 의해 다양한 형태의 치우침에 대해 실험하였다. 모의 실험 결과, 본 논문에서 제안된 알고리즘이 해쉬 분할 병렬 결합 알고리즘 및 다른 알고리즘에 비해, 치우침 현상이 존재하는 경우에 보다 더 좋은 성능이 나타남을 보았다.
마지막으로 모의 실험 결과의 정확성을 검증하기 위해, 실제로 하이퍼큐브 구조의 데이타베이스 컴퓨터인 COREDB에 구현하였다. COREDB는 한국과학기술원 전기 및 전자공학과의 컴퓨터 공학 연구실에서 개발한 8노드로 구성된 하이퍼큐브 구조형의 데이타베이스 컴퓨터이다. 또한 제안된 알고리즘의 모의 실험 결과와 실제 실험과의 차이를 극소화하기 위한 매개변수 조정을 통해 정당성도 확인하였다. 실제 실험 결과에서도 본 논문의 알고리즘이 해쉬 분할 병렬 결합 알고리즘의 성능 보다 좋음을 알 수 있었다.