Sort-Merge Join
Basic approach:
- sort both relations on join attribute
(reminder: Join [i=j] (R,S))
- scan together using merge to form result
(r,s) tuples
Advantages:
- no need to deal with "entire" S relation for each r tuple
- deal with runs of matching R and S tuples
Disadvantages:
- cost of sorting both relations
(already sorted on join key?)
- some rescanning required when long runs of S tuples
|