Join operations using nonclustered indexes

Abstract

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. When nonclustered indexes are available, there is a trace-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 implise 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 partitionbased methods. An inherited problem, so called bucket overflows, of the hashpartitioned algorithm was ponited, and we show that it can be soved by using the information of indexes, and modify the hash-parti...