SQL Server 2014：对不一致的自连接基数估计有什么解释？

Question

考虑 SQL Server 2014 中的以下查询计划：

在查询计划中，自联接ar.fId = ar.fId产生 1 行的估计值。然而，这是一个逻辑上不一致的估计：ar有20,608行和只有一个不同的值fId（准确地反映在统计数据中）。因此，此连接会生成行 ( ~424MMrows)的完整叉积，从而导致查询运行数小时。

我很难理解为什么 SQL Server 会得出一个很容易证明与统计数据不一致的估计值。有任何想法吗？

初步调查和其他细节

根据 Paul在此处的回答，用于估计连接基数的 SQL 2012 和 SQL 2014 启发式方法似乎都应该可以轻松处理需要比较两个相同直方图的情况。

我从跟踪标志 2363 的输出开始，但不太容易理解。请问下面的片段意味着SQL Server在比较直方图fId和bId以估计选择性的只加入使用fId？如果是这样，那显然是不正确的。还是我误读了跟踪标志输出？

Plan for computation:
  CSelCalcExpressionComparedToExpression( QCOL: [ar].fId x_cmpEq QCOL: [ar].fId )
Loaded histogram for column QCOL: [ar].bId from stats with id 3
Loaded histogram for column QCOL: [ar].fId from stats with id 1
Selectivity: 0

请注意，我提出了几种解决方法，它们包含在完整的重现脚本中，并将此查询降低到毫秒级。此问题的重点是了解行为、如何在将来的查询中避免它，以及确定它是否是应向 Microsoft 提交的错误。

这是一个完整的重现脚本，这是跟踪标志 2363的完整输出，这里是查询和表定义，以防您想在不打开完整脚本的情况下快速查看它们：

WITH cte AS (
    SELECT ar.fId, 
        ar.bId,
        MIN(CONVERT(INT, ar.isT)) AS isT,
        MAX(CONVERT(INT, tcr.isS)) AS isS
    FROM  #SQL2014MinMaxAggregateCardinalityBug_ar ar 
    LEFT OUTER JOIN #SQL2014MinMaxAggregateCardinalityBug_tcr tcr
        ON tcr.rId = 508
        AND tcr.fId = ar.fId
        AND tcr.bId = ar.bId
    GROUP BY ar.fId, ar.bId
)
SELECT s.fId, s.bId, s.isS, t.isS
FROM cte s 
JOIN cte t 
    ON t.fId = s.fId 
    AND t.isT = 1

---

CREATE TABLE #SQL2014MinMaxAggregateCardinalityBug_ar (
    fId INT NOT NULL,
    bId INT NOT NULL,
    isT BIT NOT NULL
    PRIMARY KEY (fId, bId)
)

CREATE TABLE #SQL2014MinMaxAggregateCardinalityBug_tcr (
    rId INT NOT NULL,
    fId INT NOT NULL,
    bId INT NOT NULL,
    isS BIT NOT NULL
    PRIMARY KEY (rId, fId, bId, isS)
)

Answer 1

我很难理解为什么 SQL Server 会得出一个很容易证明与统计数据不一致的估计值。

一致性

没有一致性的一般保证。可以使用不同的统计方法在不同时间对不同（但逻辑上等效）的子树计算估计值。

说连接这两个相同的子树应该产生叉积的逻辑没有错，但同样没有说推理的选择比任何其他选择更合理。

初步估计

在您的特定情况下，连接的初始基数估计不在两个相同的子树上执行。当时的树形是：

  LogOp_Join
     LogOp_GbAgg
        LogOp_LeftOuterJoin
           LogOp_Get TBL: ar
           日志操作选择
              LogOp_Get TBL：tcr
              ScaOp_Comp x_cmpEq
                 ScaOp_Identifier [tcr].rId
                 ScaOp_Const 值=508
           ScaOp_Logical x_lopAnd
              ScaOp_Comp x_cmpEq
                 ScaOp_Identifier [ar].fId
                 ScaOp_Identifier [tcr].fId
              ScaOp_Comp x_cmpEq
                 ScaOp_Identifier [ar].bId
                 ScaOp_Identifier [tcr].bId
        AncOp_PrjList 
           AncOp_PrjEl Expr1003 
              ScaOp_AggFunc stopMax
                 ScaOp_Convert int
                    ScaOp_Identifier [tcr].isS
     日志操作选择
        LogOp_GbAgg
           LogOp_LeftOuterJoin
              LogOp_Get TBL: ar
              日志操作选择
                 LogOp_Get TBL：tcr
                 ScaOp_Comp x_cmpEq
                    ScaOp_Identifier [tcr].rId
                    ScaOp_Const 值=508
              ScaOp_Logical x_lopAnd
                 ScaOp_Comp x_cmpEq
                    ScaOp_Identifier [ar].fId
                    ScaOp_Identifier [tcr].fId
                 ScaOp_Comp x_cmpEq
                    ScaOp_Identifier [ar].bId
                    ScaOp_Identifier [tcr].bId
           AncOp_PrjList 
              AncOp_PrjEl Expr1006 
                 ScaOp_AggFunc stopMin
                    ScaOp_Convert int
                       ScaOp_Identifier [ar].isT
              AncOp_PrjEl Expr1007 
                 ScaOp_AggFunc stopMax
                    ScaOp_Convert int
                       ScaOp_Identifier [tcr].isS
        ScaOp_Comp x_cmpEq
           ScaOp_Identifier Expr1006 
           ScaOp_Const 值=1
     ScaOp_Comp x_cmpEq
        ScaOp_Identifier QCOL: [ar].fId
        ScaOp_Identifier QCOL: [ar].fId

第一个连接输入已经简化了一个未投影的聚合，第二个连接输入将谓词t.isT = 1推送到它下面，其中t.isT是MIN(CONVERT(INT, ar.isT))。尽管如此，isT谓词的选择性计算仍可CSelCalcColumnInInterval用于直方图：

  CSelCalcColumnInInterval
      列： COL： Expr1006 

列 QCOL 的加载直方图：[ar].isT 来自 id 3 的统计信息

选择性：4.85248e-005

生成的统计信息集合： 
  CStCollFilter(ID=11, CARD=1)
      CStCollGroupBy(ID=10, CARD=20608)
          CStCollOuterJoin(ID=9, CARD=20608 x_jtLeftOuter)
              CStCollBaseTable(ID=3, CARD=20608 TBL: ar)
              CStCollFilter(ID=8, CARD=1)
                  CStCollBaseTable(ID=4, CARD=28 TBL: tcr)

（正确的）期望是通过这个谓词将 20,608 行减少到 1 行。

加入估计

现在的问题变成了来自另一个连接输入的 20,608 行如何与这一行匹配：

  LogOp_Join
      CStCollGroupBy(ID=7, CARD=20608)
          CStCollOuterJoin(ID=6, CARD=20608 x_jtLeftOuter)
              ...

      CStCollFilter(ID=11, CARD=1)
          CStCollGroupBy(ID=10, CARD=20608)
              ...

      ScaOp_Comp x_cmpEq
          ScaOp_Identifier QCOL: [ar].fId
          ScaOp_Identifier QCOL: [ar].fId

通常有几种不同的方法来估计连接。例如，我们可以：

• 在每个子树中的每个计划算子上导出新的直方图，在连接处对齐它们（根据需要插入步长值），并查看它们如何匹配；或者
• 对直方图进行更简单的“粗略”对齐（使用最小值和最大值，而不是逐步）；或者
• 单独计算连接列的单独选择性（来自基表，没有任何过滤），然后添加非连接谓词的选择性效果。
• ...

根据使用的基数估计器和一些启发式方法，可以使用其中的任何一个（或变体）。有关详细信息，请参阅 Microsoft 白皮书使用 SQL Server 2014 Cardinality Estimator 优化您的查询计划。

漏洞？

现在，如问题中所述，在这种情况下，“简单”单列连接 (on fId) 使用CSelCalcExpressionComparedToExpression计算器：

计算计划：

  CSelCalcExpressionComparedToExpression [ar].fId x_cmpEq [ar].fId

加载 QCOL 列的直方图：[ar].bId 来自 id 为 2 的统计信息
已加载 QCOL 列的直方图：[ar].fId 来自 id 为 1 的统计信息

选择性：0

此计算评估将 20,608 行与 1 个过滤行连接起来的选择性为零：没有行匹配（在最终计划中报告为一行）。这是错误的吗？是的，这里的新 CE 中可能存在错误。有人可能会争辩说 1 行将匹配所有行或不匹配所有行，因此结果可能是合理的，但有理由不相信。

细节实际上相当棘手，但估计基于未过滤的fId直方图，通过过滤器的选择性修改，给20608 * 20608 * 4.85248e-005 = 20608出行是非常合理的。

遵循此计算意味着使用计算器CSelCalcSimpleJoinWithDistinctCounts而不是CSelCalcExpressionComparedToExpression. 没有记录的方法可以执行此操作，但是如果您好奇，可以启用未记录的跟踪标志 9479：

请注意，最终连接从两个单行输入生成 20,608 行，但这并不奇怪。它与原始 CE 在 TF 9481 下产生的计划相同。

我提到细节很棘手（而且调查起来很费时），但据我所知，问题的根本原因与 predicate 相关，其rId = 508选择性为零。这个零估计以正常方式提升到一行，当它考虑输入树中的较低谓词（因此加载 的统计信息bId）时，这似乎有助于相关连接处的零选择性估计。

允许外连接保持零行内侧估计（而不是提升到一行）（因此所有外行都符合条件）使用任一计算器都可以提供“无错误”连接估计。如果您有兴趣探索这一点，未记录的跟踪标志是 9473（单独）：

连接基数估计的行为CSelCalcExpressionComparedToExpression也可以修改为不考虑bId另一个未记录的变化标志 (9494)。我提到所有这些是因为我知道你对这些事情感兴趣；不是因为他们提供了解决方案。在您向 Microsoft 报告问题并且他们解决（或不解决）问题之前，以不同方式表达查询可能是最好的前进方式。无论行为是否有意，他们都应该有兴趣了解回归。

最后，整理复制脚本中提到的另一件事：问题计划中过滤器的最终位置是基于成本的探索GbAggAfterJoinSel将聚合和过滤器移动到连接上方的结果，因为连接输出具有如此小的行数。如您所料，过滤器最初位于连接下方。