[prev] 52 [next]

Sort-Merge Join (cont)

Cost of sort-merge join.

Step 1: sort each relation that is not already sorted:

  • Cost = ∑i 2.bi (1 + logN-1(bi /N))    (with N buffers)
Step 2: merge sorted relations:
  • if every run of values in S fits completely in buffers,
    merge requires single scan,   Cost = bR + bS
  • if some runs in of values in S are larger than buffers,
    need to re-scan run for each corresponding value from R