During the past decades, the effective and efficient management of large quantities of data has been a common problem found in most large business, scientific, engineering, and military applications. There has been a considerable amount of research and development effort in the design and development of multiprocessor database computers that are tailored for processing large databases in parallel. Also a large amount of effort in the design and performance study of parallel algorithms on the multiprocessor has been done for efficiently performing complex database management functions, such as the join operation.
In this thesis, we present the performance evaluation of parallel join algorithms running on the multiprocessor database computer. First, we design and implement the multiprocessor database computer as a type of the distributed-memory multiprocessor. The overall performance of the multiprocessor database computer is measured and evaluated using well-known benchmarking method, and then good results are shown compared with other systems. Next, a various parallel algorithms to carry out the join operation on the multiprocessor database computer is presented and developed by the structural way, and the performance of each of the algorithms with different tuple distribution and local joining policies, addition of bit vector filters, and non-uniformly distributed join attribute values are studied. The performance evaluations are also conducted by an experimental way on our multiprocessor database computer, and the results are compared with the analytic results. As a result of the performance evaluation, we show that there is not just one overall best performing join algorithm, but different algorithms score the best performance, depending on the characteristics of the data participating in the join operation.
본 논문은 다중 프로세서 데이타 베이스 베이스 컴퓨터상에서 효율적으로 수행되는 병렬 결합 알고리즘들을 설계 구현하고 그 성능을 분석하였다. 먼저 병렬 결합 알고리즘들을 수행시키기 위한 다중 프로세서 데이타 베이스 컴퓨터를 분산 메모리 다중 프로세서 형태로 설계하여 구현하였다. 구현된 데이타 베이스 컴퓨터의 성능을 일반적으로 사용되는 벤치마킹 방법을 사용하여 측정한 결과, 다른 시스템과 비교하여 좋은 성능을 보였다. 병렬 결합 알고리즘들을 구조적으로 분석하여 다중 프로세서에 적합한 몇 개의 알고리즘을 구성하였다. 각각의 알고리즘을 구현된 데이타 베이스 컴퓨터에서 여러가지 조건 아래 수행시켜 그 실험적 결과를 분석하고 비교하였다. 병렬 결합 알고리즘들의 성능 분석 결과는 모든 조건에서 항상 좋은 성능을 갖는 것은 없다는 것을 보여준다. 결론적으로 결합 연산에 사용되는 데이타의 특성에 따라 가장 좋은 성능을 갖는 알고리즘이 결정되었고 그 성능의 척도는 데이타의 분포, 프로세서의 수, 연산에 사용되는 두 데이타의 크기의 차이, 비트 벡터의 사용 여부등으로 나타났다.