Design a join algorithm that uses a join index. De?ne the notion of a clustered join index (there are three possibilities in the case of a binary join!) and consider the e?ect of clustering on the join algorithm.

Question

What will be an ideal response?

Answer 1

The actual join algorithm was described in Section 9.7.2. Here we only need to consider clustering and its e?ect on the algorithm.
We can possibly say that a join index, J, for r  s is clustered in either of the three cases:
1. When J is sorted on the r-part, i.e., the r-side rids in J are organized in the same order as their corresponding tuples in r
2. When J is sorted on the s-part
3. When J is sorted simultaneously on both parts, i.e., the r-side rids in J are organized in the order of their corresponding tuples in r and the s-side rids are organized in the order of the corresponding tuples in s.
Note that we can always achieve options (1) and (2) by simply sorting J on its r-side or s-side. In fact, it would be silly not to do so. For this reason, only the third possibility can be reasonably considered to deserve the name “clustered” join index. In the ?rst two cases, the join algorithm was described in Section 9.7.2. In the third case, the algorithm is reminiscent of the merge stage of the sort-merge join. We simply scan the join index and retrieve the pages of r and s that correspond to the matching tuples. Once the pages are in, we output the requisite joined tuples. Since the tuples in the index are organized in the same order as the tuples of both r and s, the join is computed in less than one scan of these relations. It takes less than one scan because only the pages that contain the tuples to be joined need to be retrieved (we know which pages these are because the join index gives us the exact rids).