Algorithms and Performance Evaluation of Join Processing on KD-Tree Indexed Relations.

This paper proposes a new join processing algorithm for the KD-tree indexed relations. The processing is evaluated by a simulation and the effectiveness is demonstrated. The KD-tree index is one of the typical multidimensional clustering data structures. A flexible database can be constructed which provides uniform access characteristics in regard to the multiple attributes. On the other hand, the data structure is made complex, and the traditional join processing technique for the ordinary one-dimensional clustering relation, which maintains the physical order, cannot be applied. Also, there has not been proposed a join technique for the KD-tree indexed relations. This paper introduces anew the concepts called "wave" and "join range," and proposes an efficient join algorithm for the KD-tree indexed relations. Then an extended algorithm is proposed by introducing the garbage collection function into the forementioned basic algorithm, where the unnecessary tuples on the main memory can be eliminated dynamically. Each of those algorithms is evaluated by a simulation, and the effectiveness is verified. When the order of the join attribute is not preserved, the join processing by the hash-based algorithm, which at present is considered the fastest, requires two read scannings and one write scanning, while the best algorithm proposed in this paper can execute the processing by almost one read scanning. Thus, a drastic improvement of the performance can be expected for the join processing by the proposed algorithm. [ABSTRACT FROM AUTHOR]