嵌套循环运算符使用什么方法/公式进行行估计？

Question

AdventureWorks 中的以下简单查询：

SELECT  *
FROM    Person.Person p
        JOIN HumanResources.Employee e
            ON p.BusinessEntityID = e.BusinessEntityID

给出以下执行计划：

新的估算器计划

如果我查看上面的计划，我可以看到索引扫描和索引搜索都（正确）估计了 290 行，但是，连接两者的估计循环运算符估计了 279 行。

旧估算器

旧的估计器也正确地猜测了搜索和扫描中的 290 行，但嵌套循环估计了 289 行，在这个查询的情况下这是一个更好的估计。

那么在新 CE 的情况下，优化器估计当它连接索引扫描中的 290 行和索引查找中的 290 行时，是否会有 11 行不匹配？

它使用什么方法/公式来进行这个估计？

我所说的任何方法都是正确的，它已经从早期的 CE 版本改变了，因为它做出了不同的估计？

我意识到新 CE 的“坏”估计不足以损害性能，我只是想了解估计器处理

Answer 1

SQL Server 估计联接的基数，而不是物理运算符。无论使用何种物理运算符（散列、合并、嵌套循环或应用），所讨论的内部连接都将具有相同的估计。物理运算符可能会影响显示，但逻辑连接的选择性是相同的。

这样一来，逻辑连接估计仍然是一个复杂的话题。有许多有效的方法来产生估计。Dimitry Piliugin在 SQL Server中的Join Estimation Internals 中很好地涵盖了两个主要替代方案。您还可以在 Microsoft 论文Optimizing Your Query Plans with the SQL Server 2014 Cardinality Estimator 中找到原始和最新 CE 模型之间的一般差异。

使用直方图估计连接选择性时会出现一个主要区别。最近的 CE 模型使用粗对齐，正如我在SQL Server Join Estimation using Histogram Coarse Alignment 中所述。最初的 CE 对每一步使用线性插值的精细对齐，这可以提供更准确的估计，但也可能更多变。

您可能会注意到，使用 Simple Join（使用 Dima 提供的跟踪标志 9479）可以为您的测试查询提供“完美”的估计。

即使直方图可用，也有一个 TF 会强制优化器使用 Simple Join 算法。我会给你这个用于测试和教育目的。

在其他（更常见的）情况下，简单的连接会产生可怕的结果。这就是基数估计的本质。

有关的：

• SQL Server 的优化器如何估计联接表中的行数？
• 在 SQL Server 中应用基数估计问题