The problem for improving performances of database management systems has attracted great interests during the two decades. This thesis is, especially, concerned with the problem for improving the performance of the join operation, which is one of the most frequently used and one of the most complex operations in the relational database management systems.
Two partition-based join algorithms, the sort-partitioned join and the select partitioned join algorithms, are proposed for reducing the number of secondary storage accesses in single processor computers. We further investigate for the efficient partitioning techniques and propose two improved versions of the sort-partitioned join and an improved version of the select-partitioned join. Analytic comparisons show that the two proposed partition-based join algorithms always outperforms the sort-merge join and performs better than the hash-partitioned join in most cases. The analyses for the proposed join algorithms are validated in practical situations by simulation experiments. The simulation experiments show that the improved version of the select-partitioned join performs best in most cases.
We propose a general execution model for the parallel execution of the partition-based join algorithms on a hypercube database computer and, from the execution model, several parallel partition-based join algorithms are designed, analyzed, and compared. The hypercube database computer consists of a set of subcubes where each subcube shares a secondary storage device. The execution model consists of three phases; global partitioning phase, local partitioning phase, and local joining phase. The partitioning schemes studied for the single processor computers are extended and applied for each execution phase of the execution model. Several promising parallel partition-based join algorithms are derived from the execution model and their performances are analyzed in terms of computation cost, communication cost, and I/O cost. From the analytic comparisons, we can observe the followings. The cost for each join algorithm is reduced to approximately half, if the number of disk nodes are doubled. The hash-partitioning scheme is well suited for the global partitioning phase. For the local partitioning and local joining phases, however, the ordered partitioning schemes, the sort-partitioning and select-partitioning schemes, are preferable and especially the sort-partitioning scheme performs best. The proposed partitioning schemes play an important role for improving the performance of the join on the hypercube database computer, especially when either the amount of the resources, such as the disk nodes and the diskless nodes, increases or the size differential of two relations increases.
지난 20여년 동안 데이타 베이스 관리 시스템(database management system)의 성능 향상에 관한 문제는 많은 관심을 끌어 왔다. 이 논문에서는 특히 관계형 데이타 베이스 시스템(relational database system)에서 가장 자주 사용되면서도 또한 가장 복잡한 연산으로 알려진 결합연산(join operation)의 성능향상에 관한 문제를 다루고 있다.
우선, 단일 프로세서 컴퓨터상에서 보조기억장치 접근횟수를 줄이기 위하여, 두 가지의, 분할에 기초한 결합연산 알고리즘인 정렬-분할(sort-partitioned) 결합알고리즘과 선택-분할(select-partitioned) 결합알고리즘을 제안하였다. 효율적인 분할방법에 관한 연구결과 정렬-분할 결합방법을 개선한 두가지의 새로운 결합알고리즘을 제안 하였으며 선택-분할 결합방법을 개선한 다른 하나의 결합알고리즘을 제안하였다. 이들 결합알고리즘들을 분석 비교한 결과, 제안된 알고리즘들이 기존에 널리사용되고 있는 정렬-합병(sort-merge) 결합알고리즘보다 항상 좋은 성능을 나타내었으며, 현재까지 가장 효율적인 결합알고리즘중 하나로 알려진 해쉬-분할(hash-partitioned) 결합알고리즘 보다도 대부분의 경우에 앞서는 것으로 판명되었다. 제안된 알고리즘들에대한 분석의 정당성을 확인하기 위하여 실제적인 상황을 가상한 모의실험을 하였다. 모의실험결과 선택-분할 결합방법을 개선한 알고리즘이 거의 모든경우에 앞서는 것을 알 수 있었다.
초격자구조(hypercube) 데이타 베이스 컴퓨터상에서 분할에 기초한 결합알고리즘들을 병렬 수행시키기 위한 일반적인 수행모델을 제안하였으며, 제안된 수행모델로 부터 몇가지의 분할에 기초한 결합알고리즘들을 설계하고 분석, 비교하였다. 여기서 사용된 초격자구조 컴퓨터는 몇개의 부분격자(subcube)들로 구성되며 각 부분격자당 하나씩의 보조기억장치를 연결시켜 놓은 구조를 갖고 있다. 수행모델은 크게 전체분할단계(global partitioning phase), 국소분할단계(local partitioning phase), 국소결합단계(local joining phase)등 세 단계로 이루어져 있다. 각 수행단계에는 앞에서 연구되었던, 해쉬-분할, 정렬-분할, 선택-분할등 세가지 분할기법이 적용가능하다. 이상으로 부터 27가지의 서로다른 결합알고리즘들을 유도해 낼 수 있지만 그 중 가장 성능이 우수할 것으로 예상되는 몇가지 결합알고리즘들을 선택하여 이들의 성능을 연산시간, 통신시간, 입출력시간을 단위로하여 분석하였다. 분석결과 다음과 같은 사실들을 알 수 있었다. 보조기억장치를 갖는 단위 컴퓨터의 수를 두배로 하였을 때에 결합연산의 수행시간은 거의 반으로 줄어드는 것을 알 수 있었다. 전체분할단계에는 해쉬-분할 기법이 가장 적절한 것으로 나타났다. 그러나 국소분할과 국소결합단계에서는 제안된 순서화된 분할 기법들이 더 우수한 성능을 보였으며, 특히 정렬-분할 기법이 가장 유리한 것으로 판명되었다. 결론적으로, 제안된 분할 기법들이 초격자구조 데이타 베이스 컴퓨터에서의 결합연산의 성능향상에 중요한 역할을 하는 것으로 나타났으며, 특히 단위컴퓨터의 갯수가 증가할수록 또한 두 릴레이션(relation)의 크기차가 커질수록 좋은 성능을 나타내는 것으로 나타났다.
