In the sort-merge join of r  s, the scan in the algorithm of Figure 10.7 can be performed at no cost in I/O because it can be combined with the ?nal merging step of sorting r and s. Work out the details of such an algorithm.

Question

What will be an ideal response?

Answer 1

In the last merging stage of the sorting algorithm we will have n runs, r1,...,rn, of relation r sorted on the attribute A and m runs, s1,...,sm, of relations sorted on the attribute B. The merging stage of the join is combined with that last stage of
sorting as follows. We assume that there is a function getSmallest(X,[p1,...,pk]) which takes an attribute, X, and a list of union-compatible relations sorted on that attribute, and returns a tuple with the smallest value of X that exists in any of the p1,...,pk. The tuple is then deleted from the corresponding relation so that the next call to getSmallest() would return the tuple with the next smallest value, etc. The algorithm now becomes just a slight modi?cation of the merge step for sort-merge join presented in Figure 10.7:

```
Input: n runs, r1,. .., rn, of relation r sorted on the attribute A
m runs, s1,..., sm, of relation s sorted on the attribute B
Output: r daA=B s

Result := { } // initialize Result
tr := getSmallest(A,[r1,.. ., rn]) // get ?rst tuple
ts := getSmallest(B,[s1,..., sm])

while !eof(r) && !eof(s) do {
while !eof(r) && tr.A < ts.B do
tr := getSmallest(A,[r1,. .., rn]) // get next tuple
while !eof(s) && tr.A > ts.B do
ts := getSmallest(B,[s1,... , sm])
if tr.A = ts.B = c then { // for some const c
Result := (?A=c(r1 ? ... ? rn) × ?B=c(s1 ? .. . ? sm)) ? Result; tr
:= the next tuple t ? r where t[A]>c
}
}
return Result;

```