.

# 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.

.