哈希匹配运算符中的低基数估计

Question

我正在尝试解决我们对 SQL Server 2008 R2 的报告查询之一的性能问题。

我已经包含了导致低估计的查询部分。这部分进一步与其他表连接。由于对这个的估计如此之低，进一步的连接最终会成为嵌套循环并导致查询永远运行。

select n.Transactionid
from nath n
WHERE StatusId = 3 and
Date IS NOT NULL and
NOT EXISTS (SELECT 1 FROM nath 
WHERE Transactionid= n.Transactionid
AND StatusId = 3
AND HistoryId < n.HistoryId)  

预计计划

哈希匹配的估计值仅为 1.17，但实际上有 550K 条记录出现。统计信息已更新为完整扫描。

我在我们的 SQL Server 2014 实例之一上运行了完全相同的查询，它产生了更好的结果；哈希匹配运算符的估计值为 557K。然后我尝试使用跟踪标志 9481 来强制使用 2014 年的旧基数估计器，估计值又回到 1。所以我认为这个问题与旧的 CE 估计自连接有关。

我在 SQL Server 2008 R2 上尝试了跟踪标志 4199，但这没有帮助。

实际执行计划

我不希望实际表名可见，因此我创建了具有较少列和不同表名和列名的类似表。估计比上面提到的略有偏差，但更大的问题仍然存在。

带有 TF 9481 的 SQL Server 2014

（我没有 SQL Server 2008 R2 测试环境）：

SQL Server 2014

请让我知道是否有办法解决这个错误的估计。

再现

可以使用以下脚本模拟该问题：

    create table nat ( c1 int identity(1,1) primary key,c2 int)
    
    declare @a int=1
    declare  @b int =1
     while @a<10000
     begin  
        set @b=1
         while @b<=5
         begin
                insert into nat select  @a
                set @b=@b+1
         end
     set @a=@a+1
     end

select * from nat a where not exists (select 1 from nat b where b.c2=a.c2
 and b.c1<a.c1) 
 OPTION(QUERYTRACEON 9481); -- estimated no of rows from hash match 1
select * from nat a where not exists (select 1 from nat b where b.c2=a.c2
 and b.c1<a.c1)  -- estimated no of rows from hash match 49995

---

我已经在 SQL Server 2012 上对上述查询进行了一些测试，但我无法使用跟踪标志 4199 强制执行新的基数估计器行为。
当前的测试结果：

• SQL 2014 - 对哈希匹配运算符的高估计
• SQL 2014 与 TF 9481 - 低 (1) 估计
• SQL 2012 - 低 (1) 估计
• 带有 TF 4199 的 SQL 2012 - 估计值仍然很低

我如何能够在 2014 年复制旧的基数行为，但无法在 2012 年获得新的 CE 估计值？

是不是该更改不是跟踪标志 4199 的一部分并且仅在 2014 年发生？

将 更改NOT EXISTS为左连接似乎会产生更好的估计。

Answer 1

在这种情况下，为什么一个基数估计模型产生比另一个更接近的结果的问题实际上并不那么有趣。原始CE估计没有找到匹配行的概率很小；新的CE计算，几乎可以肯定。两者都是“正确的”，只是基于不同的建模假设。从根本上说，多列半连接很难根据单列统计信息进行评估。

考虑查询试图做什么，以及我们如何以与 SQL Server 可用的统计信息更兼容的方式编写它，会更有趣。

一个关键观察是查询将返回每组一个值的行。在原始查询的情况下，即HistoryId每个具有最小值的行Transactionid。在 repro 中，c1对于每个不同的值，它是具有最小值的行c2。该NOT EXISTS查询是表达这一要求只是其中一种方法。

SQL Server 具有关于不同值（密度）的良好统计信息，因此我们需要做的就是以一种明确我们希望每个组一个值的方式编写查询。有很多方法可以做到这一点，例如（使用您的复制品）：

SELECT * 
FROM dbo.nat AS N
WHERE N.c1 =
(
    SELECT MIN(N2.c1) 
    FROM dbo.nat AS N2
    WHERE N2.c2 = N.c2
);

或者，等效地：

SELECT N.* 
FROM dbo.nat AS N
JOIN
(
    SELECT 
        N.c2,
        MIN(N.c1) AS c1
    FROM dbo.nat AS N
    GROUP BY 
        N.c2
) AS J
    ON J.c2 = N.c2
    AND J.c1 = N.c1;

这在 2008 R2、2012 和 2014（两个 CE 模型）中产生了 9999 行的准确估计：

使用自然索引（也可能是唯一的）：

CREATE INDEX i ON dbo.nat (c2, c1);

计划更简单：

根据索引和其他因素，您可能并不总是能够获得这种非常简单的计划表。我要说明的一点是，与更复杂的替代方案相比，使用基本分组和连接操作通常会从优化器（及其基数估计组件）获得更好的结果。

澄清问题中的一些误解的最后说明：“新 CE”于 2014 年推出。TF 4199 启用影响计划的优化器修复。TF 9481 指定原始（“legacy”）CE，并且仅在 2014 及更高版本上有效。