[prev] 47 [next]

Sort-Merge Join

Basic approach:
  • sort both relations on join attribute   (reminder: Join[R.i=S.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