Finding efficient procedures for implementing relational database operations, such as the join, is an important database problem. This thesis proposes join processing when the access paths available are nonclustered indexes on the join attributes for both relations participating in the join. When nonclustered indexes are available, there is a trade-off between the amount of main memory buffer needed and the number of page accesses for the join operation. This problem has been examined in two different perspectives. The first is to reduce the maximum buffer size so that no page involved in the join is fetched more than once. This implies that we need to determine a sequence of pages that are brought into the buffer. The second is to reduce the number of page accesses for a fixed buffer size. We show that it is unlikely that a polynomial time solution exists for the optimal solutions of two problems by using a graph model.
For the first perspective, we also introduce a graph model, so called a page connectivity graph, and give an upper bound on the buffer size using it. We propose an upper bound on the buffer size by introducing a vertex cover of a page connectivity graph and prove that the proposed upper bound is not greater than the buffer size required in the nested-block join algorithm. We also show that the buffer size needed are more reducible than the upper bound when a page connectivity graph can be partitioned by the cut vertices. By using the property of the cut vertices, two algorithm of finding the buffer size with no page reaccess are proposed. The results of the experimental comparisons show that the proposed algorithms are more efficient than the other algorithm.
We employ a partitioning technique in order to solve the second problem. The hash-partitioned algorithm is explained as one of the partition-based methods. An inherited problem, so called bucket overflows, of the hash-partitioned algorithm was pointed, and we show that it can be solved by using the information of indexes, and modify the hash-partitioned algorithm, so called modified partition-based algorithm. In order to reduce the partitioning cost of the partition-based algorithms, we propose new algorithms, so called basic algorithm and general algorithm. By using the information of indexes, two algorithms partitions one relation, while the hash-partitioned method must partition both relations. Then, we show that is reduces the cost of partitioning dramatically. And also the new algorithms are compared with the partition-based algorithms with respect to the number of page assesses in the secondary storage. From the analytical and experimental comparisons, we show that if the ratio of the sizes of both relations is greater than the duplication factor of the join attribute values of the larger relation, the proposed algorithms outperform the hash-partitioned algorithm and the modified partition-based join algorithm for the most cases.
We propose another problem of the join operations when a single index is available and the available buffer size is fixed. Based on the facts that the general algorithm only partitions one relation and a simple index can be produced with relatively low cost as compared to the partitioning cost of one relation, we apply the general algorithm to the join operations when a single index is available and the available buffer size is fixed. We show that a simple index is a sorted list of (KEY, TID) pairs and its cost is much less than the cost of partitioning a relation. The comparisons of performances are also executed by the experimental method and from their results, we show that even if a single index is available, the general algorithm is more efficient than the hash-partitioned algorithm under the reasonable values of the parameters.
본 논문은 관계형 데이타 베이스 관리 시스템에서 가장 많이 사용되고 그 비용 이 큰 결합연산에 관하여 비군집 색인이 사용 가능 할때 결합연산에 관한 연구이다. 일반적으로 비색인이 사용 가능한 연산에서는 할당되어야 하는 주기억 장치의 량(버퍼 크기)과 보조 기억장치의 액세스 수와는 Trade-Off가 있다. 이 문제는 다음과 같은 두가지 관점에서 연구되어 왔다. 첫째는 결합연산에 참가하는 모든 데이타 페이지에 대하여 단한번의 액세스만으로 결합연산을 수행할 수 있는 최소의 버퍼 크기를 찾는 것이며, 두번째 문제는 버퍼 크기가 고정되어 주어졌을때 최소의 액세스로 결합연산을 수행할 수 있는 데이타 페이지 액세스 순서는 무엇인가 하는 것이다. 두 문제 모두 최적의 해를 구하는 것은 NP문제로 알려져 있다.
본 논문에서는 첫번째 문제를 풀기 위해서 그래프 모델 (PCG:Page Connectivity Graph)을 도입하였고 이것을 이용하여 버퍼 크기에 대한 Upper Bound를 제시 하였다. 그리고 이 Upper Bound는 작은 릴레이션의 크기 보다 항상 작다는 것을 증명하였다. 또한 일반적인 PCG에는 많은 Cut Vertex를 포함하고 있다는 사실로 부터 이 Upper Bound 를 이용하여 버퍼 크기를 크게 줄이는 두개의 알고리즘을 제안하였고 기존의 알고리즘과 실험적 성능 비교를 통하여 그 성능 향상 효과가 크다는 것을 보였다.
두번째 문제는 기존의 결합연산 기법으로 널리 알려진 분할 기법을 도입하여 하나의 해결책으로 제시하였다. 이것을 위하여 먼저 기존의 해쉬 분할 알고리즘을 설명 하였고 이 알고리즘의 고유한 문제점인 Bucket Overflow가 지적 되었다. 본 논문에서는 색인을 이용하므로써 이러한 문제를 해결할 수 있도록 해쉬 분할 알고리즘을 수정하였고 그 성능을 해석적으로 분석 하였다. 또한 기존의 분할 기법의 분할 비용을 줄이기 위하여 새로운 알고리즘 즉, Basic 알고리즘과 General 알고리즘을 제시하였다. 이들은 기존의 분할 기법들이 반드시 두 릴레이션을 분할 해야 하는 것에 반하여 새로운 알고리즘들은 하나의 릴레이션만 분할 하면 된다는 것이 주된 개념이다. 새로운 알고리즘들이 페이지 액세스 수를 크게 줄인다는 것을 보이기 위하여 본 논문은 기존의 분할 기법 알고리즘과 해석적, 실험적 비교를 통하여 성능 비교를 하였다. 해석적 비교를 통하여 제안된 알고리즘들이 기존의 분할 기법 알고리즘보다 좋은 성능을 가질 수 있는 파라메타 값들의 경계치를 찾았으며 이러한 경계치들은 현실적으로 일어날 수 있는 파라메타 값들을 포함 한다는 것을 보였다. 실험적 비교에서는 해석적 비교에서 찾아진 파라메타 값들의 경계치를 기초로 하여 얼마나 좋은 성능을 나타내는지를 보여 주었다.
본 논문에서는 위에서 제시된 두가지 문제점에 더하여 단지 하나의 릴레이션에 대한 색인이 사용 가능할때 결합 연산에 관하여 연구 되었다. 이것은 정렬된 (KEY,TID) 리스트의 구성이 하나의 릴레이션을 분할하는 것보다 훨씬 비용이 작다는 사실로 부터 정렬된 (KEY,TID)리스트를 만든후 앞에서 제안한 General 알고리즘에 적용하는 것이다. 본 논문에서는 정렬된 (KEY, TID)리스트에 대한 비용을 분석하므로써 하나의 색인만 사용 할때 조차도 제안된 알고리즘이 좋은 성능을 낸다는 것을 실험을 통하여 보였다.
