Query Processing and Execution - SQL Server 2012 Internals and Troubleshooting - page 133

TABLE 5-1: SQL Server Join Types

JOIN TYPE BENEFIT

Nested loop Good for small tables where there is an index on the inner table on the join key

Merge join Good for medium-size tables where there are ordered indexes, or where the

output needs to be ordered

Hash join Good for medium to large tables. Works well with parallel plans, and scales well.

Nested Loop
The nested loop join is the original SQL Server join type. The behavior of a nested loop is to scan all
the rows in one table (the outer table) and for each row in that table, it then scans every row in the
other table (the inner table). If the rows in the outer and inner tables match, then the row is included
in the results.

The performance of this join is directly proportional to the number of rows in each table. It
performs well when there are relatively few rows in one of the tables, which would be chosen as
the inner table, and more rows in the other table, which would be used as the outer table. If both
tables have a relatively large number of rows, then this join starts to take a very long time.

Merge
The merge join needs its inputs to be sorted, so ideally the tables should be indexed on the join
column. Then the operator iterates through rows from both tables at the same time, working down
the rows, looking for matches. Because the inputs are ordered, this enables the join to proceed
quickly, and to end as soon as any range is satisi ed.

Hash
The hash join operates in two phases. During the i rst phase, known as the build phase , the smaller
of the two tables is scanned and the rows are placed into a hash table that is ideally stored in mem-
ory; but for very large tables, it can be written to disk. When every row in the build input table is
hashed, the second phase starts. During the second phase, known as the probe phase , rows from
the larger of the two tables are compared to the contents of the hash table, using the same hashing
algorithm that was used to create the build table hash. Any matching rows are passed to the output.

The hash join has variations on this processing that can deal with very large tables, so the hash join
is the join of choice for very large input tables, especially when running on multiprocessor systems
where parallel plans are allowed.

HASH WARNINGS

Hash warnings are SQL Proi ler events that are generated when hash recursion, or
hash bailout, occurs. Hash recursion happens when the output from the hash opera-
tion doesn't i t entirely in memory. Hash bailout occurs when hash recursion reaches
its maximum level of recursion, and a new plan has to be chosen.

continues