Sort-Merge Join

With this strategy, the DBMS will use a traditional merge on the two sorted files. If the two files are already sorted on the join column, then the cost is simply

C = be + bd = 10,000 + 5 = 10,005 block accesses.

If the files are unsorted, the cost of sorting must be factored into the equation. We approximate the sorting as C_sort = blog₂b for a file with b disk blocks.

C = be + bd + Csortbd + Csortbe = 10,000 + 5 + 140,000 + 10 = 150,015 block accesses.