15.19

Design a variant of the hybrid merge-join algorithm for the case where both relations are not physically sorted, but both have a sorted secondary index on the join attributes.

---

Let \(r\) and \(s\) be the two relations that are unsorted but have an ordered secondary index (such as B+-trees) on the join attributes. We use an algorithm similar to the one given on Figure 15.7, but instead of acting on the actual relations, it will operate on the leaf nodes of the indices of \(r\) and \(s\). The result file contains addresses for tuples of \(r\) and addresses for tuples of \(s\). We will first sort the file on the addresses for tuples of \(r\) and retrieve the actual tuples in physical storage order and concatenate them with their counterparts of \(s\). We will then sort this new file on the addresses of \(s\) and retrieve them in phyiscal storage order. This will complete the join.