During the past decade, there have been constant efforts toward creating more powerful database systems, especially focusing on the relational database system and as a result, several relational database system have appeared. However, most of these systems exhibit poor performance in supporting a large class of database operations, since they are too large and complex to run on a conventional general purpose von Neumann computer which is particularly not suitable for database management. In order to overcome the drawbacks of the conventional database systems, the database computer approach has been inspired by parallel processing to support some or all of the functions of the relational database system, in particular to efficiently support the relational join operation because the join operation is the most important limiting factor on the performance of the relational database system.
In this thesis, we extensively investigate the join processing algorithms under multiprocessor database computer environments. first, the problems of the existing join algorithms are addressed, and then we propose a new join algorithm, referred to as hybrid join, which improves both the sort-merge and the hash-partitioned join algorithms by completely sorting only the smaller relation and partitioning the other one into ranged buckets according to the order statistics of the sorted relation. The key idea in the hybrid join is to determine the bound on the bucket sizes during the sort of the smaller relation. This guarantees a nice bound on the number of buffers necessary for any smaller relation bucket. Accordingly, the hybrid join requires relatively less sorting cost than that of the sort-merge join and also can prevent the bucket overflows which appear in the hash-partitioned join. Second, we extend this result to develop efficient parallel join algorithms on two types of multiprocessor database computers: a shared-memory multiprocessor and a distributed-memory multiprocessor. All the parallel join algorithms developed are the extensions of the hybrid join algorithm. Therefore, the parallel join algorithms inherit the advantages of the hybrid join. Moreover, the parallel hybrid join algorithms have another important feature which ensures better load balancing by partitioning relations evenly across all the processors. Therefore, the parallel hybrid join algorithms can exploit the high degree of parallelism and thus exhibit better performance compared with the existing parallel join algorithms, such as the parallel hash-partitioned join.
All the proposed join algorithms in this thesis are analyzed on their performance with respect to the execution time including CPU, I/O, and communication costs. The performances of the proposed algorithms are compared with those of the existing join algorithms. In addition, simulation studies are conducted to validate the performances of the proposed join algorithms in practical situation. From the performance evaluation, we show that the proposed join algorithms outperform the existing join algorithms.
데이타베이스 시스템은 컴퓨터 응용 분야의 중요한 한 영역으로서, 보다 성능이 우수한 데이타베이스 시스템을 실현하기 위한 많은 연구가 계속되어 오고있다. 그 결과로 지금까지 여러 데이타베이스 시스템들이 출현하였으며 이들은 주로 관계 데이타 모델을 기본으로하여 구현 되었다. 그러나, 이들 대부분의 시스템들은 데이타베이스 처리에 근본적으로 부적합한 범용 컴퓨터 상에 크고 복잡한 소프트웨어로 구현되었기 때문에 대용량의 데이타베이스에 대하여는 그 성능을 크게 개선하지 못하였다. 이러한 결점을 보완하기 위해 출현한 데이타베이스 컴퓨터는 데이타베이스 시스템에 필요한 여러가지 기능들을 주로 병렬 처리를 통하여 실현 함으로써 보다 높은 성능 향상을 꾀하였다. 특히 관계 데이타베이스 시스템의 경우 관계 결합 연산은 관계 데이타베이스 시스템의 성능에 가장 큰 영향을 미치는 동작으로, 데이타베이스 컴퓨터를 기본으로한 병렬 결합 연산에 대한 연구가 매우 활발히 진행돼 오고 있다.
본 논문에서는 이러한 관계 결합 연산을 위한 병렬 처리 알고리듬들이 다중프로세서 데이타베이스 컴퓨터 환경 하에서 광범위하게 연구되었다. 이를 위해 먼저 기존의 결합 연산 알고리듬들의 문제점을 분석하고, 새로운 하이브리드(hybrid) 결합 알고리듬을 제안하였다. 제안된 하이브리드 결합 알고리듬은 기존의 정렬-병합(sort-merge) 결합 알고리듬과 해쉬-분할(hash-partitioned) 결합 알고리듬의 특성을 조합하여 이들의 성능을 개선한 새로운 결합 알고리듬으로, 그 기본 동작은 두 릴레이션 중 크기가 작은 릴레이션을 정렬을 통하여 정확한 크기의 버킷(bucket)들로 분할하고 이로부터 얻은 순서 정보(order statistics)를 이용하여 다른 릴레이션을 분할하는 것으로 이루어진다. 따라서, 하이브리드 결합 알고리듬은 정렬-병합 결합에 비해 적은 정렬 시간을 요하며 해쉬-분할 결합에서와 같은 버킷 오버플로우(bucket overflow)의 발생을 방지 할 수 있다. 다음으로, 이들 결과는 두 형태의 다중프로세서 데이타베이스 컴퓨터, 즉 공유-메모리 다중프로세서(shared-memory multiprocessor) 데이타베이스 컴퓨터와 분산-메모리 다중프로세서(distributed-memory multiprocessor) 데이타베이스 컴퓨터 상에서 효율적으로 적용 될수 있는 병렬 결합 알고리듬들을 구현하기 위해 확장 되었다. 제안된 병렬 결합 알고리듬들은 모두 하이브리드 결합 알고리듬의 병렬화 알고리듬들로서 하이브리드 결합 알고리듬에서와 같은 특성을 가진다. 특히, 병렬 하이브리드 결합 알고리듬에서는 크기가 작은 릴레이션의 정렬에 의하여 릴레이션들이 모든 프로세서들에 대하여 균등하게 분배 될 수 있으므로 높은 부하 평형(load balancing) 능력을 가진다. 이는 다중프로세서 환경 하에서 매우 중요한 요건으로, 병렬 하이브리드 결합 알고리듬들은 이로 인하여 높은 병렬 처리 능력을 가지며 결과적으로 해쉬-분할 결합 알고리듬과 같은 기존의 알고리듬에 비해 좋은 성능을 나타낸다.
본 논문에서 제안된 모든 결합 알고리듬들의 성능은 CPU, 입/출력, 통신 시간 등을 포함하는 전체적인 수행 시간의 측면에서 분석 되었으며 이들 성능 분석의 결과는 다른 기존의 결합 알고리듬들의 성능과 비교 분석 되었다. 또한, 보다 실제적인 상황 하에서 제안된 결합 알고리듬들의 성능을 비교 분석하기 위하여 모의실험이 수행되었다. 이들 성능 분석의 결과로 제안된 결합 알고리듬들은 기존의 결합 알고리듬들 보다 성능이 우수함을 보인다.
