Performance characteristics of Nested Loop, Merge Join and Hash Join

Nested loop, merge join and hash join is common operators which you will find out in execution plan as long as your query contains any logical joins (inner join, outer join, cross join, semi join). These 3 brothers are classified into physical joins. For performance perspective, they fit in some conditions. I would tell you characteristics for each of them.

Nested loop join is best to handle small input sets with index on inner input set specified by join key. It is suitable for OLTP where there are a large number of concurrent users. It supports equijoin though not required, and either left outer join and left (anti) semi join. If you have dynamic cursor, make sure nested loop is the only brother that is in. you can rely ordering issue if you want it gets ordered based on outer input.

Merge join is best to handle medium to large input sets. A better query plan will come up with index one- to-many merge join so that it would be able to support large number of concurrent users. Notice that at least one equijoin required in join predicate, so that optimizer will prefer merge join. Planning carefully to your tempdb database capacity is recommended if you found many-to-many merge join. Compared to join spectrum at nested loop, merge join supports all logical join. Because no inner and outer hierarchy like nested loop, merge join can preserve order of either of input sets.

Last brother of physical join is hash join. The join is best to large input sets. This typical characteristics will be found in datawarehouse environment with parallel query execution, so it supports limited number of concurrent users. Hash join will hold its output until all rows of first input set are completely build into hash table, and remember that hash join will be in-memory storage so it takes memory. If memory is not sufficient, it will spill out to tempdb as temporary repository of build table, in worst case it turns out to bailout. And like merge join, it supports all logical joins and at least one equijoin required.


Eamples:

select * from test1 a inner merge join test4 b on a.id=b.iselect * from test1 a inner hash join test4 b on a.id=b.iselect


see the execution planfor above query
* from test1 a inner loop join test4 b on a.id=b.i