为什么 SQL Server 估计在插入一些行后从连接中会发出更少的行？

Question

下面是我在生产中遇到的事情的简化版本（在处理异常大量批次的一天，计划变得灾难性地更糟）。

已使用新的基数估计器针对 2014 年和 2016 年对 repro 进行了测试。

CREATE TABLE T1 (FromDate  DATE, ToDate DATE, SomeId INT, BatchNumber INT);

INSERT INTO T1
SELECT TOP 1000 FromDate = '2017-01-01',
                ToDate = '2017-01-01',
                SomeId = ROW_NUMBER() OVER (ORDER BY @@SPID) -1,
                BatchNumber = 1
FROM   master..spt_values v1

CREATE TABLE T2 (SomeDateTime DATETIME, SomeId INT, INDEX IX(SomeDateTime));

INSERT INTO T2
SELECT TOP 1000000 '2017-01-01',
                   ROW_NUMBER() OVER (ORDER BY @@SPID) %1000
FROM   master..spt_values v1,
       master..spt_values v2

T1 包含 1,000 行。

的FromDate，ToDate以及BatchNumber在所有的人都一样。该不同点是唯一的值SomeId与之间的值0和999

+------------+------------+--------+-----------+
|  FromDate  |   ToDate   | SomeId | BatchNumber |
+------------+------------+--------+-----------+
| 2017-01-01 | 2017-01-01 |      0 |         1 |
| 2017-01-01 | 2017-01-01 |      1 |         1 |
....
| 2017-01-01 | 2017-01-01 |    998 |         1 |
| 2017-01-01 | 2017-01-01 |    999 |         1 |
+------------+------------+--------+-----------+

T2 包含 100 万行

但只有 1,000 个不同的。每个重复 1,000 次，如下所示。

+-------------------------+--------+-------+
|      SomeDateTime       | SomeId | Count |
+-------------------------+--------+-------+
| 2017-01-01 00:00:00.000 |      0 |  1000 |
| 2017-01-01 00:00:00.000 |      1 |  1000 |
...
| 2017-01-01 00:00:00.000 |    998 |  1000 |
| 2017-01-01 00:00:00.000 |    999 |  1000 |
+-------------------------+--------+-------+

执行以下

SELECT *
FROM   T1
       INNER JOIN T2
               ON CAST(t2.SomeDateTime AS DATE) BETWEEN T1.FromDate AND T1.ToDate
                  AND T1.SomeId = T2.SomeId
WHERE  T1.BatchNumber = 1

在我的机器上大约需要 7 秒。实际行和估计行对于计划中的所有运算符都是完美的。

现在将 3,000 个额外批次添加到 T1（批次编号为 2 到 3001）。这些每个克隆批次编号 1 的现有千行

INSERT INTO T1
SELECT T1.FromDate,
       T1.ToDate,
       T1.SomeId,
       Nums.NewBatchNumber
FROM   T1
       CROSS JOIN (SELECT TOP (3000) 1 + ROW_NUMBER() OVER (ORDER BY @@SPID) AS NewBatchNumber
                   FROM   master..spt_values v1, master..spt_values v2) Nums 

并更新运气的统计数据

 UPDATE STATISTICS T1 WITH FULLSCAN

并再次运行原始查询。

SELECT *
FROM   T1
       INNER JOIN T2
               ON CAST(t2.SomeDateTime AS DATE) BETWEEN T1.FromDate AND T1.ToDate
                  AND T1.SomeId = T2.SomeId
WHERE  T1.BatchNumber = 1

在杀死它之前，我让它运行了一分钟。到那时它已经输出了 40,380 行，所以我想输出完整的一百万需要 25 分钟。

唯一改变的是我添加了一些与T1.BatchNumber = 1谓词不匹配的额外行。

然而，现在计划已经改变。它改为使用嵌套循环，虽然从 出来的行数t1仍然正确估计为 1,000 (?)，但连接行数的估计现在已从 100 万下降到一千 (?)。

所以问题是...

为什么添加额外的行会以BatchNumber <> 1某种方式影响何时加入的行的估计BatchNumber = 1？

向表中添加行最终会减少整个查询中的估计行数，这似乎违反直觉。

Answer 1

重要的是要记住，在更改查询或表中的数据时不能保证一致性。查询优化器可能会切换到使用不同的基数估计方法（例如使用密度而不是直方图），这会使两个查询看起来彼此不一致。话虽如此，查询优化器似乎在您的情况下做出了不合理的选择，所以让我们深入研究。

您的演示太复杂了，所以我将使用一个更简单的示例，我认为该示例显示了相同的行为。开始数据准备和表定义：

DROP TABLE dbo.T1 IF EXISTS;
CREATE TABLE dbo.T1 (FromDate DATE, ToDate DATE, SomeId INT);

INSERT INTO dbo.T1 WITH (TABLOCK)
SELECT TOP 1000 NULL, NULL, 1
FROM master..spt_values v1;

DROP TABLE dbo.T2 IF EXISTS;
CREATE TABLE dbo.T2 (SomeDateTime DATETIME, INDEX IX(SomeDateTime));

INSERT INTO dbo.T2 WITH (TABLOCK)
SELECT TOP 2 NULL
FROM master..spt_values v1
CROSS JOIN master..spt_values v2;

这是SELECT要调查的查询：

SELECT *
FROM T1
INNER JOIN T2 ON t2.SomeDateTime BETWEEN T1.FromDate AND T1.ToDate
WHERE T1.SomeId = 1;

这个查询非常简单，因此我们可以在没有任何跟踪标志的情况下计算出基数估计的公式。但是，我将尝试使用 TF 2363，以便更好地说明优化器中发生的事情。目前还不清楚我是否会成功。

定义以下变量：

C1 = 表 T1 中的行数

C2 = 表 T2 中的行数

S1=T1.SomeId过滤器的选择性

我的主张是上述查询的基数估计如下：

1. 当>= * 时：C2S1C1

C2* 下限为* S1S1C1

2. 当< * ：C2S1C1

164.317* * 上限为 *C2S1S1C1

让我们通过一些示例，虽然我不会通过我测试的每一个。对于初始数据准备，我们有：

C1 = 1000

C2 = 2

S1 = 1.0

因此，基数估计应该是：

2 * 164.317 = 328.634

下面的不可能伪造的屏幕截图证明了这一点：

使用未记录的跟踪标志 2363，我们可以获得一些关于正在发生的事情的线索：

Plan for computation:

  CSelCalcColumnInInterval

      Column: QCOL: [SE_DB2].[dbo].[T1].SomeId

Loaded histogram for column QCOL: [SE_DB2].[dbo].[T1].SomeId from stats with id 2

Selectivity: 1

Stats collection generated: 

  CStCollFilter(ID=3, CARD=1000)

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

End selectivity computation

Begin selectivity computation

Input tree:

...

Plan for computation:

  CSelCalcSimpleJoinWithUpperBound (Using base cardinality)

      CSelCalcOneSided (RIGHT)

          CSelCalcCombineFilters_ExponentialBackoff (AND)

              CSelCalcFixedFilter (0.3)

              CSelCalcFixedFilter (0.3)

Selectivity: 0.164317

Stats collection generated: 

  CStCollJoin(ID=4, CARD=328.634 x_jtInner)

      CStCollFilter(ID=3, CARD=1000)

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

      CStCollBaseTable(ID=2, CARD=2 TBL: T2)

End selectivity computation

使用新的 CE，我们得到了通常的 16% 估计BETWEEN。这是由于新的 2014 CE 的指数退避。每个不等式的基数估计值为 0.3，因此BETWEEN计算为 0.3 * sqrt(0.3) = 0.164317。将 16% 的选择性乘以 T2 和 T1 中的行数，我们得到我们的估计。似乎足够合理。让我们将行数T2增加到 7。现在我们有以下内容：

C1 = 1000

C2 = 7

S1 = 1.0

因此，基数估计应该是 1000，因为：

7 * 164.317 = 1150 > 1000

查询计划证实了这一点：

我们可以再看一眼 TF 2363，但看起来选择性在幕后进行了调整以尊重上限。我怀疑这会CSelCalcSimpleJoinWithUpperBound阻止基数估计值超过 1000。

Loaded histogram for column QCOL: [SE_DB2].[dbo].[T1].SomeId from stats with id 2

Selectivity: 1

Stats collection generated: 

  CStCollFilter(ID=3, CARD=1000)

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

End selectivity computation

Begin selectivity computation

Input tree:

...

Plan for computation:

  CSelCalcSimpleJoinWithUpperBound (Using base cardinality)

      CSelCalcOneSided (RIGHT)

          CSelCalcCombineFilters_ExponentialBackoff (AND)

              CSelCalcFixedFilter (0.3)

              CSelCalcFixedFilter (0.3)

Selectivity: 0.142857

Stats collection generated: 

  CStCollJoin(ID=4, CARD=1000 x_jtInner)

      CStCollFilter(ID=3, CARD=1000)

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

      CStCollBaseTable(ID=2, CARD=7 TBL: T2)

让我们T2达到 50000 行。现在我们有：

C1 = 1000

C2 = 50000

S1 = 1.0

因此，基数估计应该是：

50000 * 1.0 = 50000

查询计划再次确认了这一点。在您已经弄清楚公式之后，更容易猜测估计值：

TF输出：

Loaded histogram for column QCOL: [SE_DB2].[dbo].[T1].SomeId from stats with id 2

Selectivity: 1

Stats collection generated: 

  CStCollFilter(ID=3, CARD=1000)

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

...

Plan for computation:

  CSelCalcSimpleJoinWithUpperBound (Using base cardinality)

      CSelCalcOneSided (RIGHT)

          CSelCalcCombineFilters_ExponentialBackoff (AND)

              CSelCalcFixedFilter (0.3)

              CSelCalcFixedFilter (0.3)

Selectivity: 0.001

Stats collection generated: 

  CStCollJoin(ID=4, CARD=50000 x_jtInner)

      CStCollFilter(ID=3, CARD=1000)

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

      CStCollBaseTable(ID=2, CARD=50000 TBL: T2)

对于此示例，指数退避似乎无关紧要：

5000 * 1000 * 0.001 = 50000。

现在让我们向 T1 添加 3k 行，SomeId值为 0。这样做的代码：

INSERT INTO T1 WITH (TABLOCK)
SELECT TOP 3000 NULL, NULL, 0
FROM   master..spt_values v1,
       master..spt_values v2;

UPDATE STATISTICS T1 WITH FULLSCAN;

现在我们有：

C1 = 4000

C2 = 50000

S1 = 0.25

因此，基数估计应该是：

50000 * 0.25 = 12500

查询计划证实了这一点：

这与您在问题中提到的行为相同。我向表中添加了不相关的行，基数估计值降低了。为什么会这样？注意粗线：

Loaded histogram for column QCOL: [SE_DB2].[dbo].[T1].SomeId from stats with id 2

选择性：0.25

Stats collection generated: 

  CStCollFilter(ID=3, CARD=1000)

      CStCollBaseTable(ID=1, CARD=4000 TBL: T1)

End selectivity computation

Begin selectivity computation

Input tree:

...

Plan for computation:

  CSelCalcSimpleJoinWithUpperBound (Using base cardinality)

      CSelCalcOneSided (RIGHT)

          CSelCalcCombineFilters_ExponentialBackoff (AND)

              CSelCalcFixedFilter (0.3)

              CSelCalcFixedFilter (0.3)

选择性：0.00025

Stats collection generated: 

  CStCollJoin(ID=4, CARD=12500 x_jtInner)

      CStCollFilter(ID=3, CARD=1000)

          CStCollBaseTable(ID=1, CARD=4000 TBL: T1)

      CStCollBaseTable(ID=2, CARD=50000 TBL: T2)

End selectivity computation

似乎这种情况的基数估计计算如下：

C1* * * / ( * )S1C2S1S1C1

或者对于这个特定的例子：

4000 * 0.25 * 50000 * 0.25 / (0.25 * 4000) = 12500

通用公式当然可以简化为：

C2 * S1

这是我上面声称的公式。似乎有一些不应该取消的取消。我希望总行数T1与估计值相关。

如果我们插入更多行，T1我们可以看到下界在起作用：

INSERT INTO T1 WITH (TABLOCK)
SELECT TOP 997000 NULL, NULL, 0
FROM   master..spt_values v1,
       master..spt_values v2;

UPDATE STATISTICS T1 WITH FULLSCAN;

在这种情况下，基数估计为 1000 行。我将省略查询计划和 TF 2363 输出。

最后，这种行为非常可疑，但我不知道是否有足够的信息来声明它是否是一个错误。我的示例与您的重现并不完全匹配，但我相信我观察到了相同的一般行为。另外我想说的是，您选择初始数据的方式有点幸运。优化器似乎进行了大量的猜测，所以我不会太纠结于原始查询返回 100 万行与估计完全匹配的事实。