为什么在这些计划中对唯一索引进行（相同）1000 次搜索的估计成本不同？

Question

在下面的查询中，估计两个执行计划对唯一索引执行 1,000 次搜索。

查找是由对同一源表的有序扫描驱动的，因此看起来最终应该以相同的顺序查找相同的值。

两个嵌套循环都有 <NestedLoops Optimized="false" WithOrderedPrefetch="true">

任何人都知道为什么这个任务在第一个计划中的成本为 0.172434，而在第二个计划中为 3.01702？

（问题的原因是第一个查询被建议作为优化，因为计划成本明显低得多。它实际上在我看来好像它做了更多的工作，但我只是试图解释这种差异.. .)

设置

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;

查询 1 _{“粘贴计划”链接}

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;

查询 2 _{“粘贴计划”链接}

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; 

查询 1

查询 2

以上已在 SQL Server 2014 (SP2) (KB3171021) - 12.0.5000.0 (X64) 上测试

---

@Joe Obbish在评论中指出，一个更简单的重现将是

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

对比

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

对于 1,000 行的临时表，上述两个仍然具有相同的带有嵌套循环的计划形状和没有派生表的计划看起来更便宜，但是对于 10,000 行的临时表和上述相同的目标表，成本的差异确实改变了计划形状（完整扫描和合并连接似乎比昂贵的搜索更具吸引力）显示这种成本差异可能会产生影响，而不仅仅是使比较计划变得更加困难。

Answer 1

任何人都知道为什么这个任务在第一个计划中的成本为 0.172434，而在第二个计划中为 3.01702？

一般而言，假设随机 I/O 模式，嵌套循环连接下方的内侧查找成本。后续访问有一个简单的基于替换的减少，考虑到所需页面已经被前一次迭代带入内存的机会。这种基本评估会产生标准（更高）的成本。

还有另一个成本计算输入，Smart Seek Costing，关于它的细节知之甚少。我的猜测（这就是现阶段的全部内容）是 SSC 尝试更详细地评估内部查找 I/O 成本，可能是通过考虑本地排序和/或要获取的值范围。谁知道。

例如，第一个查找操作不仅会引入所请求的行，还会引入该页面上的所有行（按索引顺序）。鉴于整体访问模式，即使禁用预读和预取，在 1000 次搜索中获取 1000 行也只需要 2 次物理读取。从这个角度来看，默认的 I/O 成本代表了一个显着的高估，而 SSC 调整后的成本更接近现实。

在循环或多或少直接驱动索引查找的情况下，SSC 最有效，并且连接外部引用是查找操作的基础，这似乎是合理的。据我所知，SSC 总是尝试进行合适的物理操作，但是当其他操作将查找与连接分开时，通常不会产生向下调整。简单的过滤器是一个例外，也许是因为 SQL Server 经常可以将它们推送到数据访问运算符中。在任何情况下，优化器都非常支持选择。

不幸的是，子查询外部投影的计算标量似乎在这里干扰了 SSC。计算标量通常重新定位在连接上方，但这些标量必须保持原位。即便如此，大多数普通的计算标量对优化来说是相当透明的，所以这有点令人惊讶。

无论如何，当物理操作PhyOp_Range是通过对索引的简单选择产生时SelIdxToRng，SSC 是有效的。当采用更复杂的SelToIdxStrategy（在表上选择索引策略）时，结果会PhyOp_Range运行 SSC，但不会导致减少。同样，似乎更简单、更直接的操作最适合 SSC。

我希望我能确切地告诉你 SSC 是做什么的，并显示准确的计算，但我不知道这些细节。如果您想探索自己可用的有限跟踪输出，您可以使用未记录的跟踪标志 2398。示例输出是：

智能搜索成本 (7.1) :: 1.34078e+154 , 0.001

该示例与备忘录组 7、备选方案 1 相关，显示成本上限和因子 0.001。要查看更清晰的因素，请确保在没有并行性的情况下重建表，以便页面尽可能密集。如果不这样做，对于示例 Target 表，该因子更像是 0.000821。当然，那里有一些相当明显的关系。

也可以使用未记录的跟踪标志 2399 禁用 SSC。当该标志处于活动状态时，两个成本都是较高的值。

Answer 2

不确定这是一个答案，但评论有点长。造成差异的原因纯粹是我的猜测，也许可以供其他人思考。

带有执行计划的简化查询。

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;

这些真正可能导致相同执行计划的等效查询之间的主要区别在于计算标量运算符。我不知道为什么它必须在那里，但我想优化器可以优化派生表。

我的猜测是计算标量的存在是造成第二次查询的 IO 成本的原因。

从优化器内部：计划成本

CPU 成本计算为第一行的 0.0001581 和后续行的 0.000011。
...
0.003125 的 I/O 成本正好是 1/320 – 反映了模型的假设，即磁盘子系统每秒可以执行 320 次随机 I/O 操作
...
成本计算组件足够聪明，可以识别出需要从磁盘引入的页永远不能超过存储整个表所需的页数。

在我的情况下，该表需要 5618 页，并且要从 1000000 行中获取 1000 行，估计所需的页数为 5.618，IO 成本为 0.015625。

两个查询的 CPU 成本接缝相同，为0.0001581 * 1000 executions = 0.1581。

因此，根据上面链接的文章，我们可以计算出第一个查询的成本为 0.173725。

假设我对计算标量如何造成混乱的 IO 成本是正确的，它可以计算为 3.2831。

不完全是计划中显示的内容，但它就在附近。

Answer 3

（作为对保罗回答的评论会更好，但我还没有足够的代表。）

我想提供DBCC我曾经得出的接近结论的跟踪标志列表（和一些陈述），以防将来调查类似的差异会有所帮助。所有这些都不应该用于生产。

首先，我查看了最终备忘录以了解正在使用哪些物理运算符。根据图形执行计划，它们看起来肯定是一样的。因此，我使用了跟踪标志3604和8615，第一个将输出定向到客户端，第二个显示最终备忘录：

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);

从 回溯Root Group，我发现这些几乎相同的PhyOp_Range运算符：

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)

对我来说唯一明显的区别是2.0and 3.0，它们分别指的是“备忘录组 2，原始”和“备忘录组 3，原始”。检查备忘录，这些指的是同一件事-因此尚未发现差异。

其次，我查看了一堆对我来说毫无结果的跟踪标志 - 但有一些有趣的内容。我从本杰明·内瓦雷斯（Benjamin Nevarez）那里举起最多。我一直在寻找有关应用于一种情况而不是另一种情况的优化规则的线索。

 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 );

第三，我查看了哪些规则适用于我们PhyOp_Range看起来如此相似的 s。我使用了 Paul 在博客文章中提到的几个跟踪标志。

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 );

从输出中，我们看到直接JOIN应用此规则来获得我们的PhyOp_Rangeoperator: Rule Result: group=7 2 <SelIdxToRng>PhyOp_Range 1 ASC 2 (Distance = 2)。子选择改为应用此规则：Rule Result: group=9 2 <SelToIdxStrategy>PhyOp_Range 1 ASC 3 (Distance = 2)。这也是您看到与每个规则关联的“智能搜索成本”信息的地方。对于指示-JOIN这是输出（对我来说）Smart seek costing (7.2) :: 1.34078e+154 , 0.001。对于子选择，这是输出：Smart seek costing (9.2) :: 1.34078e+154 , 1。

最后，我无法得出太多结论——但保罗的回答弥补了大部分差距。我想查看更多有关智能搜索成本的信息。