|
The Merge Join algorithm reads two inputs that are both ordered by the join attributes. For each row of the left input, the algorithm reads all of the matching rows of the right input by accessing the rows in sorted order.
If the inputs are not already ordered by the join attributes (perhaps because of an earlier merge join or because an index was used to satisfy a search condition), then the optimizer adds a sort to produce the correct row order. This sort adds cost to the merge join.
One advantage of a Merge Join compared to a Hash Join is that the cost of sorting can be amortized over several joins, provided that the merge joins are over the same attributes. The optimizer chooses Merge Join over a Hash Join if the sizes of the inputs are likely to be similar, or if it can amortize the cost of the sort over several operations.