Home, Parent: SQL Server Cost Based Optimizer
AdventureWorks, Index Seek, Key Lookups, Table Scan, Joins, Insert, Update, Delete,
Parallelism I, Parallelism II, Parallelism III,

Nested Loops, Hash and Merge Joins

Since SQL Server is a relational database, we are most interested in joins. The three main types of joins are Nested Loops, Hash and Merge, the details of which are described in BOL. For some reason, Hash and Merge joins are poorly understand and frequently associated with poor performing queries.

The query below joins two tables with a search argument on one table yielding exactly one row.

SELECT SalesOrderID FROM Sales.Customer c
INNER JOIN Sales.SalesOrderHeader o ON o.CustomerID = c.CustomerID WHERE c.CustomerID = 13497

The execution plan with details is shown below. The upper symbol (the Clustered Index Seek in this case) to the Nested Loops Inner Join is the outer source, and the lower symbol is the inner source.

Warning

The operations here are exactly the same as in the key lookup, except that now the inner source can have multiple rows.

In an actual production database, there are frequent joins between the Customers and the Orders tables and between Orders and Order Details. Each of these joins are one-to-many. For illustrative purposes here, it is desirable to demonstrate one-to-one joins. For this reason, a duplicate copy of the SalesOrderHeader table is created as SalesOrderHdr1 with the same primary key clustered on SalesOrderID.

The queries below involve a one-to-one join for 213 rows for the first SARG parameters and 214 rows for the second. The normal (not hinted) execution plan for the first query, with the first SARG parameters is a loop join. The next three queries all use the second SARG parameters. The second query forces a loop join with a hint, the third query does not hint, and the fourth query hints a hash join.

SELECT d.SubTotal FROM Sales.SalesOrderHeader h
INNER JOIN Sales.SalesOrderHdr1 d ON d.SalesOrderID = h.SalesOrderID
WHERE h.CustomerID BETWEEN 11091 AND 11161

SELECT d.SubTotal FROM Sales.SalesOrderHeader h
INNER LOOP JOIN Sales.SalesOrderHdr1 d ON d.SalesOrderID = h.SalesOrderID
WHERE h.CustomerID BETWEEN 11091 AND 11162

SELECT d.SubTotal FROM Sales.SalesOrderHeader h
INNER JOIN Sales.SalesOrderHdr1 d ON d.SalesOrderID = h.SalesOrderID
WHERE h.CustomerID BETWEEN 11091 AND 11162

SELECT d.SubTotal FROM Sales.SalesOrderHeader h
INNER HASH JOIN Sales .SalesOrderHdr1 d ON d.SalesOrderID = h.SalesOrderID
WHERE h.CustomerID BETWEEN 11091 AND 11162

The execution plans for the four queries are shown below. The first three queries all have approximately the same plan cost. Only the forced hash join has a moderately higher cost.

The reason the execution plan changes (without hints) from the index seek with nested loops join to a table scan with a hash or merge join is that the cost of the loop join inner source is somewhat linear with the number of rows from the outer source, with each outer source row contributing the standard random IO cost of 0.003125, while the alternative plans has the high fixed cost of the table scan operation, and a relatively low cost per row. So at some point the scan becomes faster than the repeated index seeks to the inner source.

For some reason, people see the third or fourth execution plans, with the hash or merge joins, and draw the conclusion that hash and merge joins are associated with poor performance, overlooking the fact that the main contribution in the plan cost is the scan operation.

The Nested Loops operations for the first and second queries are shown below. The details for the first query, an unforced nested loops join, outer (Index Seek) and inner (Clustered Index Seek) sources are shown below.

Below are the outer and inner source details for the second query, the forced Loop Join.

The first query has estimated rows 225 and the second to fourth queries have estimated rows 227.7. As stated above, the actual rows are 213 and 214 respectively. The total plan cost for the first query is 0.639851 and 0.646008 for the second.

The third query, Merge Join, details are shown below. The index seek operation is the same as in the second query, and is not shown again. The total plan cost of the third query is 0.645527, just slightly lower than the loop join plan (0.646008) for the same SARG parameters.

Below is the cost detail for Hash Match operation of the fourth query. The index seek and clustered index scan operations are the same is in the third query.

Below are the actual execution statistics for the above four queries. As before, the first query below is a dummy. The second to fifth lines are for the four queries of interest. The second row is the query without hints, using the first SARG parameters with 225 rows estimated and 213 actual. The third row is the query with the Loop Join hint using the second SARG parameters with 227 rows estimated and 214 actual. As in the key lookup example, the true cost for one additional row is less. Again, due to the run-to-run variations, one should not drawn conclusions from this.

The execution stats below return a single row aggregate instead of multiple rows.

While the plan costs and logical reads for the four queries of interest above are similar, the actual worker time is much higher for the queries involving the clustered index scan. As before, the above tests were conducted with all data in memory. There was no physical disk IO, as assumed by the plan cost model.

More on Hash and Merge Joins

To better demonstrate the hash and merge join, another duplicate of the SalesOrderHeader table is created as SalesOrderHdr2, with the difference being the clustered index is now [CustomerID, SalesOrderID]. In an actual production database, the tables SalesOrderHeader and SalesOrderDetail would both have a cluster key leading with CustomerID.

Below are the execution plans for a single row one-to-one join with the normal Nested Loops join, along with forced Merge and Hash joins.

As before the Nested Loops joins has a cost structure of 0.00000418 per row with no base cost.

The Merge Join base cost is 0.0056022 for the first row (base cost) plus approximately 0.00000640 for each additional row. The Hash Match cost structure is a base of 0.01776509, plus 0.00001509 per additional row or 0.000015266

The four queries used to demonstrate to change in execution plan are shown below. Notice that the SARG parameters are now much contracted, between down to 11094 and 11095 from 11161 and 11162.

SELECT d.SubTotal FROM Sales.SalesOrderHeader h
INNER JOIN Sales.SalesOrderHdr2 d ON d.SalesOrderID = h.SalesOrderID
WHERE h.CustomerID BETWEEN 11091 AND 11094 AND d.CustomerID = h.CustomerID

SELECT d.SubTotal FROM Sales.SalesOrderHeader h
INNER LOOP JOIN Sales.SalesOrderHdr2 d ON d.SalesOrderID = h.SalesOrderID
WHERE h.CustomerID BETWEEN 11091 AND 11095 AND d.CustomerID = h.CustomerID

SELECT d.SubTotal FROM Sales.SalesOrderHeader h
INNER JOIN Sales.SalesOrderHdr2 d ON d.SalesOrderID = h.SalesOrderID
WHERE h.CustomerID BETWEEN 11091 AND 11095 AND d.CustomerID = h.CustomerID

SELECT d.SubTotal FROM Sales.SalesOrderHeader h
INNER HASH JOIN Sales.SalesOrderHdr2 d ON d.SalesOrderID = h.SalesOrderID
WHERE h.CustomerID BETWEEN 11091 AND 11095 AND d.CustomerID = h.CustomerID

The execution plans are shown below. The plan costs for the first three queries are very close. Only the plan with the hash join is substantially more expensive.

The outer (Index Seek) and inner (Clustered Index Seek) source details for the first query are shown below.

Below are the outer and inner source details for the second query. Note the estimated row from the Index Seek for the first query is 35.76 rows and 38.35 rows for the second query. The actual row counts are 37 and 40 respectively.

Above are the Nested Loops details for the first and second query, showing estimated row counts at 34.8 and 37.4 rows and the total plan costs as 0.0122817 and 0.0127068 respectively.

Below are the Clustered Index Seek and Index Seek details for the third and fourth queries. Each operation is the same between the two queries.

Below are the Merge Join and Hash Match details

If we were to examine a forced Merge and Hash joins for 2 rows, we would see that the fixed base cost for a Merge Join operation is approximately 0.0056 and for a Hash Match operation 0.01778. Since the inner source is executed in a single operation, the Hash and Merge operations do not incurred the 0.003125 IO cost per assessed row. If the SARG is specific on only of the two tables of a join, then a hash or merge join would require a scan on the other source. This is why joins involving few rows and one SARG are Loop Joins.

Only when the IO cost for the inner source becomes large enough to offset the full table scan cost on the inner source and the merge or hash base cost does the plan change become possible. Since we have already described how the SQL Server CBO underestimates table scan cost when all data is in memory, the true cost of a join can jump suddenly on the shift from a loop join to a scan with hash or merge, even though the plan costs are comparable. The hash and merge joins can be more efficient than a loop, especially when a selective SARG is specified on both sources and the right indexes are available. The SQL Server optimizer does not deliberately use a less efficient plan.

The result set below shows the execution stats for the dummy query and the four queries described above. The unforced and forced loop joins have approximately the same cost. The unforced Merge Join is slightly lower cost than the loop joins, and the forced hash join is substantially more expensive than loop or merge.

Let us now look at the three execution plan types with the parameters from the original join demonstrations (between 11091 and 11162) for 199 and 200 rows. A join hint is used to force the Loop and Hash joins. The query plan without hints has a merge join.

Below are the execution stats after the dummy query. The merge join has the lowest cost, the loop join the second lowest. The hash join still has the higher cost, but the difference is closing. At higher row counts, the hash join can be lower cost the than loop join. Note that the Merge Join requires that rows be in sorted order, otherwise a sort operation, which has additional cost, is required. A regular merge join also requires the join to be one-to-many. Otherwise a separate many-to-many merge join is required, which is more expensive than a one-to-many merge.