为什么子查询将行估计减少到 1？

Question

考虑以下人为但简单的查询：

SELECT 
  ID
, CASE
    WHEN ID <> 0 
    THEN (SELECT TOP 1 ID FROM X_OTHER_TABLE) 
    ELSE (SELECT TOP 1 ID FROM X_OTHER_TABLE_2) 
  END AS ID2
FROM X_HEAP;

我希望此查询的最终行估计值等于X_HEAP表中的行数。无论我在子查询中做什么，对于行估计都无关紧要，因为它无法过滤掉任何行。但是，在 SQL Server 2016 上，由于子查询，我看到行估计值减少到 1：

为什么会发生这种情况？我该怎么办？

使用正确的语法很容易重现这个问题。这是一组可以执行此操作的表定义：

CREATE TABLE dbo.X_HEAP (ID INT NOT NULL)
CREATE TABLE dbo.X_OTHER_TABLE (ID INT NOT NULL);
CREATE TABLE dbo.X_OTHER_TABLE_2 (ID INT NOT NULL);

INSERT INTO dbo.X_HEAP WITH (TABLOCK)
SELECT TOP (1000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL))
FROM master..spt_values;

CREATE STATISTICS X_HEAP__ID ON X_HEAP (ID) WITH FULLSCAN;

数据库小提琴链接。

Answer 1

这绝对看起来像是意外行为。确实，基数估计不需要在计划的每一步都保持一致，但这是一个相对简单的查询计划，最终的基数估计与查询正在执行的操作不一致。如此低的基数估计可能导致在更复杂的计划中下游其他表的连接类型和访问方法选择不当。

通过反复试验，我们可以提出一些没有出现问题的类似查询：

SELECT 
  ID
, CASE
    WHEN ID <> 0 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    ELSE (SELECT -1) 
  END AS ID2
FROM dbo.X_HEAP;

SELECT 
  ID
, CASE
    WHEN ID < 500 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    WHEN ID >= 500 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
  END AS ID2
FROM dbo.X_HEAP;

我们还可以提出更多出现问题的查询：

SELECT 
  ID
, CASE
    WHEN ID < 500 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    WHEN ID >= 500 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
    ELSE (SELECT TOP 1 ID FROM X_OTHER_TABLE) 
  END AS ID2
FROM dbo.X_HEAP;

SELECT 
  ID
, CASE
    WHEN ID = 0 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    ELSE (SELECT -1) 
  END AS ID2
FROM dbo.X_HEAP;

SELECT 
  ID
, CASE
    WHEN ID = 0 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    ELSE (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
  END AS ID2
FROM dbo.X_HEAP;

似乎有一个模式：如果 中存在一个CASE不希望执行的表达式，并且结果表达式是针对表的子查询，那么在该表达式之后，行估计值下降到 1。

如果我针对具有聚集索引的表编写查询，则规则会有所改变。我们可以使用相同的数据：

CREATE TABLE dbo.X_CI (ID INT NOT NULL, PRIMARY KEY (ID))

INSERT INTO dbo.X_CI WITH (TABLOCK)
SELECT * FROM dbo.X_HEAP;

UPDATE STATISTICS X_CI WITH FULLSCAN;

此查询有 1000 行的最终估计：

SELECT 
  ID
, CASE
    WHEN ID = 0 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
    ELSE (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
  END
FROM dbo.X_CI;

但是这个查询有 1 行最终估计：

SELECT 
  ID
, CASE
    WHEN ID <> 0 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    ELSE (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
  END
FROM dbo.X_CI;

为了进一步深入研究，我们可以使用未记录的跟踪标志 2363来获取有关查询优化器如何执行选择性计算的信息。我发现将该跟踪标志与未记录的跟踪标志 8606配对很有帮助。TF 2363 似乎为简化树和项目规范化后的树提供了选择性计算。启用两个跟踪标志可以清楚地表明哪些计算适用于哪棵树。

让我们针对问题中发布的原始查询尝试一下：

SELECT 
  ID
, CASE
    WHEN ID <> 0 
    THEN (SELECT TOP 1 ID FROM X_OTHER_TABLE) 
    ELSE (SELECT TOP 1 ID FROM X_OTHER_TABLE_2) 
  END AS ID2
FROM X_HEAP
OPTION (QUERYTRACEON 3604, QUERYTRACEON 2363, QUERYTRACEON 8606);

以下是我认为相关的部分输出以及一些评论：

Plan for computation:

  CSelCalcColumnInInterval -- this is the type of calculator used

      Column: QCOL: [SE_DB].[dbo].[X_HEAP].ID -- this is the column used for the calculation

Pass-through selectivity: 0 -- all rows are expected to have a true value for the case expression

Stats collection generated: 

  CStCollOuterJoin(ID=8, CARD=1000 x_jtLeftOuter) -- the row estimate after the join will still be 1000

      CStCollBaseTable(ID=1, CARD=1000 TBL: X_HEAP)

      CStCollBaseTable(ID=2, CARD=1 TBL: X_OTHER_TABLE)

...

Plan for computation:

  CSelCalcColumnInInterval

      Column: QCOL: [SE_DB].[dbo].[X_HEAP].ID

Pass-through selectivity: 1 -- no rows are expected to have a true value for the case expression

Stats collection generated: 

  CStCollOuterJoin(ID=9, CARD=1 x_jtLeftOuter) -- the row estimate after the join will still be 1

      CStCollOuterJoin(ID=8, CARD=1000 x_jtLeftOuter) -- here is the row estimate after the previous join

          CStCollBaseTable(ID=1, CARD=1000 TBL: X_HEAP)

          CStCollBaseTable(ID=2, CARD=1 TBL: X_OTHER_TABLE)

      CStCollBaseTable(ID=3, CARD=1 TBL: X_OTHER_TABLE_2)

现在让我们为没有问题的类似查询尝试它。我将使用这个：

SELECT 
  ID
, CASE
    WHEN ID <> 0 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    ELSE (SELECT -1) 
  END AS ID2
FROM dbo.X_HEAP
OPTION (QUERYTRACEON 3604, QUERYTRACEON 2363, QUERYTRACEON 8606);

最后调试输出：

Plan for computation:

  CSelCalcColumnInInterval

      Column: QCOL: [SE_DB].[dbo].[X_HEAP].ID

Pass-through selectivity: 1

Stats collection generated: 

  CStCollOuterJoin(ID=9, CARD=1000 x_jtLeftOuter)

      CStCollOuterJoin(ID=8, CARD=1000 x_jtLeftOuter)

          CStCollBaseTable(ID=1, CARD=1000 TBL: dbo.X_HEAP)

          CStCollBaseTable(ID=2, CARD=1 TBL: dbo.X_OTHER_TABLE)

      CStCollConstTable(ID=4, CARD=1) -- this is different than before because we select a constant instead of from a table

让我们尝试另一个存在错误行估计的查询：

SELECT 
  ID
, CASE
    WHEN ID < 500 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    WHEN ID >= 500 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
    ELSE (SELECT TOP 1 ID FROM X_OTHER_TABLE) 
  END AS ID2
FROM dbo.X_HEAP
OPTION (QUERYTRACEON 3604, QUERYTRACEON 2363, QUERYTRACEON 8606);

在传递选择性 = 1 之后，基数估计最终下降到 1 行。在选择性为 0.501 和 0.499 之后，基数估计被保留。

Plan for computation:

 CSelCalcColumnInInterval

      Column: QCOL: [SE_DB].[dbo].[X_HEAP].ID

Pass-through selectivity: 0.501

...

Plan for computation:

  CSelCalcColumnInInterval

      Column: QCOL: [SE_DB].[dbo].[X_HEAP].ID

Pass-through selectivity: 0.499

...

Plan for computation:

  CSelCalcColumnInInterval

      Column: QCOL: [SE_DB].[dbo].[X_HEAP].ID

Pass-through selectivity: 1

Stats collection generated: 

  CStCollOuterJoin(ID=12, CARD=1 x_jtLeftOuter) -- this is associated with the ELSE expression

      CStCollOuterJoin(ID=11, CARD=1000 x_jtLeftOuter)

          CStCollOuterJoin(ID=10, CARD=1000 x_jtLeftOuter)

              CStCollBaseTable(ID=1, CARD=1000 TBL: dbo.X_HEAP)

              CStCollBaseTable(ID=2, CARD=1 TBL: dbo.X_OTHER_TABLE)

          CStCollBaseTable(ID=3, CARD=1 TBL: dbo.X_OTHER_TABLE_2)

      CStCollBaseTable(ID=4, CARD=1 TBL: X_OTHER_TABLE)

让我们再次切换到另一个没有问题的类似查询。我将使用这个：

SELECT 
  ID
, CASE
    WHEN ID < 500 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    WHEN ID >= 500 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
  END AS ID2
FROM dbo.X_HEAP
OPTION (QUERYTRACEON 3604, QUERYTRACEON 2363, QUERYTRACEON 8606);

在调试输出中，从来没有一个步骤的传递选择性为 1。基数估计保持在 1000 行。

Plan for computation:

  CSelCalcColumnInInterval

      Column: QCOL: [SE_DB].[dbo].[X_HEAP].ID

Pass-through selectivity: 0.499

Stats collection generated: 

  CStCollOuterJoin(ID=9, CARD=1000 x_jtLeftOuter)

      CStCollOuterJoin(ID=8, CARD=1000 x_jtLeftOuter)

          CStCollBaseTable(ID=1, CARD=1000 TBL: dbo.X_HEAP)

          CStCollBaseTable(ID=2, CARD=1 TBL: dbo.X_OTHER_TABLE)

      CStCollBaseTable(ID=3, CARD=1 TBL: dbo.X_OTHER_TABLE_2)

End selectivity computation

当查询涉及带有聚集索引的表时，查询会怎样？考虑以下带有行估计问题的查询：

SELECT 
  ID
, CASE
    WHEN ID <> 0 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
    ELSE (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
  END
FROM dbo.X_CI
OPTION (QUERYTRACEON 3604, QUERYTRACEON 2363, QUERYTRACEON 8606);

调试输出的结尾与我们已经看到的类似：

Plan for computation:

  CSelCalcColumnInInterval

      Column: QCOL: [SE_DB].[dbo].[X_CI].ID

Pass-through selectivity: 1

Stats collection generated: 

  CStCollOuterJoin(ID=9, CARD=1 x_jtLeftOuter)

      CStCollOuterJoin(ID=8, CARD=1000 x_jtLeftOuter)

          CStCollBaseTable(ID=1, CARD=1000 TBL: dbo.X_CI)

          CStCollBaseTable(ID=2, CARD=1 TBL: dbo.X_OTHER_TABLE)

      CStCollBaseTable(ID=3, CARD=1 TBL: dbo.X_OTHER_TABLE_2)

但是，针对没有问题的 CI 的查询具有不同的输出。使用此查询：

SELECT 
  ID
, CASE
    WHEN ID = 0 
    THEN (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE_2) 
    ELSE (SELECT TOP 1 ID FROM dbo.X_OTHER_TABLE) 
  END
FROM dbo.X_CI
OPTION (QUERYTRACEON 3604, QUERYTRACEON 2363, QUERYTRACEON 8606);

结果在使用不同的计算器。CSelCalcColumnInInterval不再出现：

Plan for computation:

  CSelCalcFixedFilter (0.559)

Pass-through selectivity: 0.559

Stats collection generated: 

  CStCollOuterJoin(ID=8, CARD=1000 x_jtLeftOuter)

      CStCollBaseTable(ID=1, CARD=1000 TBL: dbo.X_CI)

      CStCollBaseTable(ID=2, CARD=1 TBL: dbo.X_OTHER_TABLE_2)

...

Plan for computation:

  CSelCalcUniqueKeyFilter

Pass-through selectivity: 0.001

Stats collection generated: 

  CStCollOuterJoin(ID=9, CARD=1000 x_jtLeftOuter)

      CStCollOuterJoin(ID=8, CARD=1000 x_jtLeftOuter)

          CStCollBaseTable(ID=1, CARD=1000 TBL: dbo.X_CI)

          CStCollBaseTable(ID=2, CARD=1 TBL: dbo.X_OTHER_TABLE_2)

      CStCollBaseTable(ID=3, CARD=1 TBL: dbo.X_OTHER_TABLE)

总之，在以下条件下，我们似乎在子查询之后得到了错误的行估计：

1. 使用CSelCalcColumnInInterval选择性计算器。我不知道什么时候使用它，但是当基表是堆时它似乎更频繁地出现。

2. 传递选择性 = 1。换言之，CASE对于所有行，其中一个表达式的计算结果为假。CASE对于所有行，第一个表达式的计算结果是否为真并不重要。

3. 有一个外部连接到CStCollBaseTable. 换句话说，CASE结果表达式是针对表的子查询。恒定值将不起作用。

也许在这些情况下，查询优化器无意中将传递选择性应用于外部表的行估计，而不是应用于嵌套循环内部部分的工作。这会将行估计减少到 1。

我找到了两种解决方法。使用APPLY代替子查询时，我无法重现该问题。跟踪标志 2363 的输出与APPLY. 这是重写问题中原始查询的一种方法：

SELECT 
  h.ID
, a.ID2
FROM X_HEAP h
OUTER APPLY
(
SELECT CASE
    WHEN ID <> 0 
    THEN (SELECT TOP 1 ID FROM X_OTHER_TABLE) 
    ELSE (SELECT TOP 1 ID FROM X_OTHER_TABLE_2) 
  END
) a(ID2);

旧版 CE 似乎也避免了这个问题。

SELECT 
  ID
, CASE
    WHEN ID <> 0 
    THEN (SELECT TOP 1 ID FROM X_OTHER_TABLE) 
    ELSE (SELECT TOP 1 ID FROM X_OTHER_TABLE_2) 
  END AS ID2
FROM X_HEAP
OPTION (USE HINT('FORCE_LEGACY_CARDINALITY_ESTIMATION'));

已为此问题提交了一个连接项目（Paul White 在他的回答中提供了一些详细信息）。

Answer 2

这种基数估计 (CE) 问题在以下情况下会出现：

1. 联接是带有传递谓词的外联接
2. 传递谓词的选择性估计恰好为 1。

注意：用于确定选择性的特定计算器并不重要。

细节

该CE计算外的选择性加入的总和的：

• 具有相同谓词的内连接选择性
• 具有相同谓词的反连接选择性

外连接和内连接之间的唯一区别是外连接还返回与连接谓词不匹配的行。反连接恰恰提供了这种差异。内连接和反连接的基数估计比直接外连接更容易。

连接选择性估计过程非常简单：

• 首先，评估传递谓词的选择性。 SPT
  • 这是使用适合具体情况的计算器来完成的。
  • 谓词是整个事物，包括任何否定IsFalseOrNull组件。
• 内连接选择性：= 1 - SPT
• 反连接选择性：= SPT

反联接表示将“通过”联接的行。内连接表示不会“通过”的行。请注意，“通过”是指流经连接的行而根本不运行内侧。强调：连接将返回所有行，区别在于在出现之前运行连接内侧的行和不运行的行。

显然，添加到应该总是给出 1 的总选择性，这意味着所有行都由连接返回，正如预期的那样。1 - SPTSPT

实际上，上述计算的工作原理与对除 1 之外的所有值所描述的完全一样。SPT

当= 1 时，内连接和反连接选择性都被估计为零，从而产生一行的基数估计（对于整个连接）。据我所知，这是无意的，应该报告为错误。SPT

一个相关问题

由于单独的 CE 限制，此错误比人们想象的更可能出现。当CASE表达式使用EXISTS子句时会出现这种情况（很常见）。例如，来自问题的以下修改后的查询不会遇到意外的基数估计：

-- This is fine
SELECT 
    CASE
        WHEN XH.ID = 1
        THEN (SELECT TOP (1) XOT.ID FROM dbo.X_OTHER_TABLE AS XOT) 
    END
FROM dbo.X_HEAP AS XH;

引入一个琐碎EXISTS的问题确实会导致问题浮出水面：

-- This is not fine
SELECT 
    CASE
        WHEN EXISTS (SELECT 1 WHERE XH.ID = 1)
        THEN (SELECT TOP (1) XOT.ID FROM dbo.X_OTHER_TABLE AS XOT) 
    END
FROM dbo.X_HEAP AS XH;

UsingEXISTS为执行计划引入了半连接（突出显示）：

半连接的估计很好。问题是 CE 将关联的探针列视为简单的投影，固定选择性为 1：

-- This is fine
SELECT 
    CASE
        WHEN XH.ID = 1
        THEN (SELECT TOP (1) XOT.ID FROM dbo.X_OTHER_TABLE AS XOT) 
    END
FROM dbo.X_HEAP AS XH;

无论EXISTS条款的内容如何，​​这都会自动满足此 CE 问题所需的条件之一。

有关重要的背景信息，请参阅Craig Freedman 的表达式中的子查询CASE。