SQL Server Join Costs

SQL Server Join Costs , 1 SARG

Here we look at Loop, Hash and Merge joins with an equality value search argument (SARG) on one source only. The implication of the SARG for Hash and Merge joins is that the inner source access must be a scan. This is the third article in the Plan Cost versus Actual series:?Key Lookup ,?Plan Cost Cross-over ?and the first on Joins.

Some important details on the Hash join are in a separate article?Hash Join . The next article, Join costs 2 SARG , (Join-2 SARG ), examines the Loop, Hash and Merge joins with SARGs on each source. In this scenario, the Merge and Hash joins do not incur a table scan on one of the sources, and better illustrates join cost only. The second SARG also has implications for the Loop join. The discussion here pertains to degree of parallelism (DOP) 1. Parallel execution plans for joins will be covered in Parallel Plan Cost . DOP 1 is not the best showcase for Hash join, which is meant for higher degrees of parallelism.

Loop Join to Merge Join Cross-over

The example here is contrived to evaluate the impact of the cost model?in a join execution plan. The two queries below demonstrate the cross-over from a Nested Loops join to a Merge join. Not shown is the OPTION (MAXDOP 1).

The plan for the second query is a MERGE join with the join order reversed from the SQL. This is query optimizer doing its job. However, the plan cost is the same to 7 digits for either join order, so it is unclear why the optimizer chose the reverse order.

For the discussion on the execution plan, it is convenient to hint (directive or force) a MERGE join with both queries having the same join order.

The cross-over point for this example, is dependent on SQL Server max memory and the size of the second table. In this case, with max memory set to 8GB, cross-over occurs at just over 50,000 rows. At 50,028 rows, the plan is a Loop join. At 50,220 rows the plan cost model shows the Merge join as having slightly lower cost than the Loop join (forced).

Below are the Index Seek details to table T2 for the first query, showing 50,028 rows,

and the second query at 50,220 rows.

Below are the accesses to (inner source) table A. For the first query, the access is index seek using the join condition as the search argument for number of executions 50,028.

For the second query (right), the access is a scan of the entire table of nearly 1GB with costs:?I/O cost 0.003125 + (129775 pages ? 1) ÷ 1350 = = 96.132 and CPU cost is 0.0001581 + 13107300 rows × 0.0000011 per row = 14.4182.

Below are the joins details. For the first query, the join type is Nested Loops, having cost 0.00000418 per row times 50,028 rows = 0.209117.

The second query has a Merge join with CPU cost 27.6414. This appears to 0.00000218 per row from the inner source. The true cost is probably a function of the number of rows from each source? The Merge join base cost is about 0.0056.

The plan cost excluding the stream aggregate (tiny)) at 50,028 rows with Loop join is 137.987 and at 50,220 rows with Merge join is 138.332. Forcing a Loop join at 50,220 rows has a plan cost of 138.426.

Actual Cost at Cross-Over

The actual CPU and elapsed times (in milli-sec) with data in memory for the first query, Loop join 50,028 rows, is:

SQL Server Execution Times: CPU time = 63 ms, elapsed time = 79 ms.

The actual CPU and elapsed times with data in memory for the second query, Merge join 50,220 rows, is below. The actual costs are about the same for either join order.

SQL Server Execution Times: CPU time = 1250 ms, elapsed time = 1241 ms.

Plan Cost - Joins

A proper investigation into the cost of Merge and Hash Joins is not presented here. See the support article on?Hash Join ?for additional details. Numerical values and formulae on?Plan Costs ?have also been separated out so this article can focus on cost versus rows. Be aware the cost model has a number of dependencies, the number of columns and size of columns required, and number of rows from each source, outer and inner. There could also be dependencies on Max Server Memory. For Hash Join, the cardinality may be involved as well?

That said, the plan cost of for joins at DOP 1 on single column join condition taking the MAX of one datetime column from the inner source table only, is shown below. There is no search argument on the inner source table. For the Loop Join, the join condition can and is used as a search argument. For the Merge and Hash joins, the inner source access must be a scan.

Below is the same chart on a log-log scale. Base 10 for vertical scale and base 2 for horizontal scale.

As discussed above, the Merge join plan cost with 1GB scan becomes less expensive than the Loop Join at 50,220 rows. The Hash join becomes less expensive than the Loop Join between 111K and 112K rows.

The Hash join is about 58 higher in plan cost units than the Merge join. This comes from the number of rows processed at the inner source. In this example, because the indexes have both sources in order, the Merge join is always less expensive than the Hash join.

Batch Mode

At about 132K rows in this example (Edit: 131072 rows exactly, per estimated number of rows in the join operator), the Hash join changes to batch mode if Batch Mode on Rowstore is enabled (version 2019 and later). Again, this may depend on a number of factors not explored here. The grey line shows Hash join plan cost with Batch Mode disabled and is the only option (at DOP 1) for versions before Batch Mode.

The vertical step for Hash B at 132K rows does not really exist. It simply represents the start of when the query optimizer activates Batch Mode. For practical purposes, the very large majority of the cost in the row mode hash goes away in batch mode, leaving us with mostly the cost of the scan to the inner source.

Actual Cost - Joins

Below is the actual cost for the Loop, Merge and Hash Joins as described earlier in which there is a SARG only on the outer source. The Loop join can use the join condition as a SARG. In Merge and Hash, the inputs are processed separately and, in this case involves a scan of just under 1GB at 129,775 pages with 13,197,275 rows.

Recall from?Plan vs. Actual Key Lookup and Scan Costs ?that the actual Table Scan cost was around 650ms. The cost of the Merge join starts around 1230ms and rises to a larger degree than the scan only. The row mode Hash join starts around 1500ms and rises more than the Merge join. The plan cost has the Merge join as being one-fourth the table scan, but actual cost for data in memory has the Merge being comparable to the scan.

The plan cost of the Hash join is about 20% less than the scan but actual cost, again for data in memory, is 1.5X at lower row count and more at higher row count, then the scan.

The Batch Mode Hash join is substantially lower than the Row Mode Hash join. The cost in this example is about 850ms at the lower row counts, about 200ms more the table scan only. This is not the dramatic reduction of 80X indicated by the plan but is still a very big plus.

Below are the same actual costs on a log-log scale. Notice the Merge join does not become less expensive than the Loop join out to 873K rows. If we were to extrapolate the Loop and Merge join lines out, it appears they may cross at 1.2M rows.

The Hash join in Row Mode is always more expensive than the Merge join. In this example, the requirements for a merge join are met with the index and a separate Sort operation is not required. Sometimes, an execution plan may show a Sort operation after the source access, then feeding into a Merge join. In this case, the combined Sort and Merge operations may have plan cost very close to the Hash join operation.

Once batch mode conditions are met, the Hash join drops significantly to moderately more than just the inner source scan cost. The remaining hash join cost is somewhat more than indicated in the plan cost though.

It looks like the Hash join in batch mode becomes less expensive than the loop join about halfway between 655K and 873K rows.

Summary

The SQL Server Loop join plan has similar (identical actually) cost structure with the Key and RID Lookup, naturally because the Lookup uses the Nested Loops operator to access the main table. There are two consequential assumptions made by query optimizer. One is the assumption that leaf level data pages are not in buffer cache at the beginning of query execution. The second is non-sequential access incurs random like I/O having high cost (1/320) relative to consecutive page accesses (1/1350), expected to generate sequential I/O.

These two assumptions result in the join query with one SARG specified changing execution plan to a scan at about 50K rows when Merge join conditions are met, and 112K rows for a Hash join, incurring the 1GB table scan. In actual query execution with data in buffer cache, the true cross-over points are much higher row counts by a factor of seven or more. The Hash join only becomes lower cost at over 700K rows because of the recent Batch feature. The Merge join is not expected to cross until over 1M rows. Because of the radically different behavior between the plan model and actual with data in memory, we must be careful when the execution plan is in this nonconformity range.