# Sort-merge Join Algorithm Assignment Help

The nested-loop join, exhaustive comparisons are not quite useful in numerous conditions. One possibility to avoid this is the following:

• Each relation tends to be sorted on the join attributes.
• After that, each relation tends to be scanned in the order of the join attributes. Tuples which satisfy the join condition tend to be merged to form the result relation.
• This method is known as the sort-merge join.

## Sort-Merge Join (R, S):

• Sort R & S on the join column, after that scan them to do a “merge”, as well as result outcome tuples.
• Advance scan associated with R until current R-tuple > = current S tuple, after that advance scan associated with S until current S-tuple >= current R tuple, do that until current R tuple = current S tuple.
• At this point, all R tuples along with same value in Ri (current R group) and all S tuples along with same value in Sj (current S group) match, output < r, s > for all pairs associated with this kind of tuples.
• Then resume scanning R as well as S.
• R is scanned once, every S group is scanned as soon as for each matching R tuple.

### Example of Sort-Merge Join: • Cost: M log M + N log N + (M+N)
• The cost of scanning, M+N, could be M*N
• With 35, 100 or 300 buffer pages, both Reserves and Sailors can be sorted in 2 passes, total join cost: 7500.