Why does the estimated cost of (the same) 1000 seeks on a unique index differ in these plans?

Question

In the queries below both execution plans are estimated to perform 1,000 seeks on a unique index.

The seeks are driven by an ordered scan on the same source table so seemingly should end up seeking the same values in the same order.

Both nested loops have <NestedLoops Optimized="false" WithOrderedPrefetch="true">

Anyone know why this task is costed at 0.172434 in the first plan but 3.01702 in the second?

(The reason for the question is that the first query was suggested to me as an optimisation due to the apparent much lower plan cost. It actually looks to me as though it does more work but I'm just attempting to explain the discrepancy...)

Setup

CREATE TABLE dbo.Target(KeyCol int PRIMARY KEY, OtherCol char(32) NOT NULL);

CREATE TABLE dbo.Staging(KeyCol int PRIMARY KEY, OtherCol char(32) NOT NULL); 

INSERT INTO dbo.Target
SELECT TOP (1000000) ROW_NUMBER() OVER (ORDER BY @@SPID), LEFT(NEWID(),32)
FROM master..spt_values v1,  
     master..spt_values v2;

INSERT INTO dbo.Staging
SELECT TOP (1000) ROW_NUMBER() OVER (ORDER BY @@SPID), LEFT(NEWID(),32)
FROM master..spt_values v1;

Query 1 _{"Paste the plan" link}

WITH T
     AS (SELECT *
         FROM   Target AS T
         WHERE  T.KeyCol IN (SELECT S.KeyCol
                             FROM   Staging AS S))
MERGE T
USING Staging S
ON ( T.KeyCol = S.KeyCol )
WHEN NOT MATCHED THEN
  INSERT ( KeyCol, OtherCol )
  VALUES(S.KeyCol, S.OtherCol )
WHEN MATCHED AND T.OtherCol > S.OtherCol THEN
  UPDATE SET T.OtherCol = S.OtherCol;

Query 2 _{"Paste the plan" link}

MERGE Target T
USING Staging S
ON ( T.KeyCol = S.KeyCol )
WHEN NOT MATCHED THEN
  INSERT ( KeyCol, OtherCol )
  VALUES( S.KeyCol, S.OtherCol )
WHEN MATCHED AND T.OtherCol > S.OtherCol THEN
  UPDATE SET T.OtherCol = S.OtherCol; 

Query 1

Query 2

The above was tested on SQL Server 2014 (SP2) (KB3171021) - 12.0.5000.0 (X64)

---

@Joe Obbish points out in the comments that a simpler repro would be

SELECT *
FROM staging AS S 
  LEFT OUTER JOIN Target AS T 
    ON T.KeyCol = S.KeyCol;

vs

SELECT *
FROM staging AS S 
  LEFT OUTER JOIN (SELECT * FROM Target) AS T 
    ON T.KeyCol = S.KeyCol;

For the 1,000 row staging table both of the above still have the same plan shape with nested loops and the plan without the derived table appearing cheaper, but for a 10,000 row staging table and same target table as above the difference in costs does change the plan shape (with a full scan and merge join seeming relatively more attractive than expensively costed seeks) showing this cost discrepancy can have implications other than just making it harder to compare plans.

Answer 1

Anyone know why this task is costed at 0.172434 in the first plan but 3.01702 in the second?

Generally speaking, an inner side seek below a nested loops join is costed assuming a random I/O pattern. There is a simple replacement-based reduction for subsequent accesses, accounting for the chance that the required page has already been brought into memory by a previous iteration. This basic assessment produces the standard (higher) cost.

There is another costing input, Smart Seek Costing, about which little detail is known. My guess (and that is all it is at this stage) is that SSC attempts to assess inner side seek I/O cost in more detail, perhaps by considering local ordering and/or the range of values to fetch. Who knows.

For example, the first seeking operation brings in not just the requested row, but all rows on that page (in index order). Given the overall access pattern, fetching the 1000 rows in 1000 seeks requires only 2 physical reads, even with read-ahead and prefetching disabled. From that perspective, the default I/O costing represents a significant overestimate, and the SSC-adjusted cost is closer to reality.

It seems reasonable to expect that SSC would be most effective where the loop drives an index seek more or less directly, and the join outer reference is the basis of the seeking operation. From what I can tell, SSC is always attempted for suitable physical operations, but most often produces no downward adjustment when the seek is separated from the join by other operations. Simple filters are one exception to this, perhaps because SQL Server can often push these into the data access operator. In any case, the optimizer has pretty deep support for selections.

It is unfortunate that the Compute Scalar for the subquery outer projections seems to interfere with SSC here. Compute Scalars are usually relocated above the join, but these ones have to stay where they are. Even so, most normal Compute Scalars are pretty transparent to optimization, so this is a bit surprising.

Regardless, when the physical operation PhyOp_Range is produced from a simple selection on an index SelIdxToRng, SSC is effective. When the more complex SelToIdxStrategy (selection on a table to an index strategy) is employed, the resulting PhyOp_Range runs SSC but results in no reduction. Again, it seems that simpler, more direct operations work best with SSC.

I wish I could tell you exactly what SSC does, and show the exact calculations, but I don't know those details. If you want to explore the limited trace output available for yourself, you can employ undocumented trace flag 2398. An example output is:

Smart seek costing (7.1) :: 1.34078e+154 , 0.001

That example relates to memo group 7, alternative 1, showing a cost upper bound, and a factor of 0.001. To see cleaner factors, be sure to rebuild the tables without parallelism so the pages are as dense as possible. Without doing that, the factor is more like 0.000821 for your example Target table. There are some fairly obvious relationships there, of course.

SSC can also be disabled with undocumented trace flag 2399. With that flag active, both costs are the higher value.

Answer 2

Not sure this is an answer but it is a bit long for a comment. The cause of the difference is pure speculation on my part and can perhaps be food for thought to others.

Simplified queries with execution plans.

SELECT S.KeyCol, 
       S.OtherCol,
       T.*
FROM staging AS S 
  LEFT OUTER JOIN Target AS T 
    ON T.KeyCol = S.KeyCol;

SELECT S.KeyCol, 
       S.OtherCol,
       T.*
FROM staging AS S 
  LEFT OUTER JOIN (
                  SELECT *
                  FROM Target
                  ) AS T 
    ON T.KeyCol = S.KeyCol;

The main difference between these equivalent queries that really could result in identical execution plans is the compute scalar operator. I don't know why it has to be there but I guess that is as far as the optimizer can go to optimize away the derived table.

My guess is that the presence of the compute scalar is what is mucking up the IO cost for the second query.

From Inside the Optimizer: Plan Costing

The CPU cost is calculated as 0.0001581 for the first row, and 0.000011 for subsequent rows.
...
The I/O cost of 0.003125 is exactly 1/320 – reflecting the model’s assumption that the disk subsystem can perform 320 random I/O operations per second
...
the costing component is smart enough to recognise that the total number of pages that need to be brought in from disk can never exceed the number of pages required to store the whole table.

In my case the table takes 5618 pages and to get 1000 rows from 1000000 rows the estimated number of pages needed is 5.618 giving the IO Cost of 0.015625.

The CPU Cost for both queries seams to be the same, 0.0001581 * 1000 executions = 0.1581.

So according to the article linked above we can calculate the cost for the first query to be 0.173725.

And assuming I'm correct about how the compute scalar is making a mess of IO Cost it can be calculated to 3.2831.

Not exactly what is shown in the plans but it is right there in the neighbourhood.

Answer 3

(This would be better as a comment to Paul's answer, but I don't have enough rep yet.)

I wanted to provide the list of trace flags (and a couple DBCC statements) I used to come to a near-conclusion, in case it will be helpful to investigate similar discrepancies in the future. All of these should not be used on production.

First, I had a look at the Final Memo to see what physical operators were being used. They certainly look the same according to the graphical execution plans. So, I used trace flags 3604 and 8615, the first directs output to the client and the second reveals the Final Memo:

SELECT S.*, T.KeyCol
FROM Staging AS S
      LEFT OUTER JOIN Target AS T
       ON T.KeyCol = S.KeyCol
OPTION(QUERYTRACEON 3604, -- Output client info
       QUERYTRACEON 8615, -- Shows Final Memo structure
       RECOMPILE);

Tracing back from the Root Group, I found these nearly identical PhyOp_Range operators:

1. PhyOp_Range 1 ASC 2.0 Cost(RowGoal 0,ReW 0,ReB 999,Dist 1000,Total 1000)= 0.175559(Distance = 2)
2. PhyOp_Range 1 ASC 3.0 Cost(RowGoal 0,ReW 0,ReB 999,Dist 1000,Total 1000)= 3.01702(Distance = 2)

The only obvious difference to me was the 2.0 and 3.0, which refer to their respective "memo group 2, original" and "memo group 3, original". Checking the memo, these refer to the same thing - so no differences revealed yet.

Second, I looked into a whole mess of trace flags that proved fruitless to me - but have some interesting content. I lifted most from Benjamin Nevarez. I was looking for clues as to optimization rules that were applied in one case and not the other.

 SELECT S.*, T.KeyCol
 FROM Staging AS S
      LEFT OUTER JOIN Target AS T
        ON T.KeyCol = S.KeyCol
 OPTION (QUERYTRACEON 3604, -- Output info to client
         QUERYTRACEON 2363, -- Show stats and cardinality info
         QUERYTRACEON 8675, -- Show optimization process info
         QUERYTRACEON 8606, -- Show logical query trees
         QUERYTRACEON 8607, -- Show physical query tree
         QUERYTRACEON 2372, -- Show memory utilization info for optimization stages 
         QUERYTRACEON 2373, -- Show memory utilization info for applying rules
         RECOMPILE );

Third, I looked at which rules were applied for our PhyOp_Ranges that look so similar. I used a couple trace flags mentioned by Paul in a blog post.

SELECT S.*, T.KeyCol
FROM Staging AS S
      LEFT OUTER JOIN (SELECT KeyCol
                      FROM Target) AS T
       ON T.KeyCol = S.KeyCol
OPTION (QUERYTRACEON 3604, -- Output info to client
        QUERYTRACEON 8619, -- Show applied optimization rules
        QUERYTRACEON 8620, -- Show rule-to-memo info
        QUERYTRACEON 8621, -- Show resulting tree
        QUERYTRACEON 2398, -- Show "smart seek costing"
        RECOMPILE );

From the output, we see that the direct-JOIN applied this rule to get our PhyOp_Range operator: Rule Result: group=7 2 <SelIdxToRng>PhyOp_Range 1 ASC 2 (Distance = 2). The subselect applied this rule instead: Rule Result: group=9 2 <SelToIdxStrategy>PhyOp_Range 1 ASC 3 (Distance = 2). This is also where you see the "smart seek costing" info associated with each rule. For the direct-JOIN this is the output (for me): Smart seek costing (7.2) :: 1.34078e+154 , 0.001. For the subselect, this is the output: Smart seek costing (9.2) :: 1.34078e+154 , 1.

In the end, I couldn't conclude much - but Paul's answer closes most of the gap. I'd like to see some more info on smart seek costing.

Answer 4

This is not really an answer either - as Mikael noted, it's difficult to discuss this problem in the comments...

Interestingly, if you convert the subquery (select KeyCol FROM Target) into an inline TVF, you see the plan, and its costs, are the same as the simple original query:

CREATE FUNCTION dbo.cs_test()
RETURNS TABLE
WITH SCHEMABINDING
AS 
RETURN (
    SELECT KeyCol FROM dbo.Target
    );

/* "normal" variant */
SELECT S.KeyCol, s.OtherCol, T.KeyCol 
FROM staging AS S 
    LEFT OUTER JOIN Target AS T ON T.KeyCol = S.KeyCol;

/* "subquery" variant */
SELECT S.KeyCol, s.OtherCol, T.KeyCol 
FROM staging AS S 
    LEFT OUTER JOIN (SELECT KeyCol FROM Target) AS T ON T.KeyCol = S.KeyCol;

/* "inline-TVF" variant */
SELECT S.KeyCol, s.OtherCol, T.KeyCol 
FROM staging AS S 
    LEFT OUTER JOIN dbo.cs_test() t ON s.KeyCol = t.Keycol

The query plans (pastetheplan link):

Deduction leads me to believe the costing engine is confused about the potential impact this type of subquery can have.

Take for instance, the following:

SELECT S.KeyCol, s.OtherCol, T.KeyCol 
FROM staging AS S 
    LEFT OUTER JOIN (
        SELECT KeyCol = CHECKSUM(NEWID()) 
        FROM Target
        ) AS T ON T.KeyCol = S.KeyCol;

How would you cost that? The query optimizer chooses a very similar plan to the "subquery" variant above, containing a compute scalar (pastetheplan.com link):

The compute scalar has a quite different cost from the "subquery" variant shown above, however it is still simply a guess since the query optimizer has no way of knowing, a priori, what the number of rows returned might be. The plan uses a hash match for the left outer join since the row estimates are unknowable and therefore set to the number of rows in the Target table.

I don't have a great conclusion from this except that I agree with the work Mikael did in his answer, and am hopeful someone else can come up with a better answer.