Join during merge: an improved sort based algorithm (Q1066681)

Several algorithms have been proposed to perform the join operation in database applications. These algorithms can be classified at a first level into two main classes: those which are based on the existence of auxiliary data structures, like indexes and inter-file links, and those which do not use any auxiliary data structures. This paper deals with the latter class (i.e., it assumes that auxiliary data structures are not available for the join). The algorithms for performing the join in absence of auxiliary data structures can be further partitioned into two main subclasses: the ''nested'' algorithms and the ''sort-based'' algorithm. This paper describes and analyzes an improvement of the classical sort- based algorithm. The proposed improvement consists in avoiding to sort completely both files; the join is performed when the files have been partially sorted into subfiles. The new algorithm is called ''Join-during- merge'', because the join operation is performed instead of the last merge pass of the sort operation. In fact two different algorithms which are based on the above idea are proposed and analysed, called one-way and two-way join-during-merge. The join-during-merge algorithm is compared with the classical sort-based algorithm with respect to the required page fetches and it is shown that it behaves always better. Therefore, this paper suggests to use the join-during-merge algorithm instead of the sort-based algorithm in all cases where the sort-based algorithm was considered convenient.