直方图外的基数估计

Question

设置

我在理解基数估计时遇到了一些麻烦。这是我的测试设置：

• Stack Overflow 数据库 2010 版
• SQL Server 2017 CU15+GDR (KB4505225) - 14.0.3192.2
• 新 CE（兼容级别 140）

我有这个过程：

USE StackOverflow2010;
GO

CREATE OR ALTER PROCEDURE #sp_PostsByCommentCount
    @CommentCount int
AS
BEGIN
    SELECT * 
    FROM dbo.Posts p
    WHERE 
        p.CommentCount = @CommentCount
    OPTION (RECOMPILE); 
END;
GO

dbo.Posts表上没有非聚集索引或统计信息（在 上有聚集索引Id）。

当为此要求估计计划时，“估计行数”dbo.Posts是 1,934.99：

EXEC #sp_PostsByCommentCount @CommentCount = 51;

当我询问估计计划时，自动创建了以下统计对象：

DBCC SHOW_STATISTICS('dbo.Posts', [_WA_Sys_00000006_0519C6AF]);

其中的亮点是：

• 统计数据的采样率非常低，为 1.81% (67,796 / 3,744,192)
• 仅使用了 31 个直方图步骤
• “所有密度”值为0.03030303（采样了 33 个不同的值）
• RANGE_HI_KEY直方图中的最后一个是 50，其中EQ_ROWS1

题

传递任何高于 50（最多并包括 2,147,483,647）的值会导致 1,934.99 行估计。 使用什么计算或值来产生这个估计？ 顺便说一下，遗留基数估计器产生 1 行的估计值。

我试过的

以下是我的一些理论，我尝试过的事情，或者我在调查时能够挖掘的其他信息。

密度向量

我最初认为它是密度向量，就像我使用OPTION (OPTIMIZE FOR UNKNOWN). 但是这个 stats 对象的密度向量是 3,744,192 * 0.03030303 = 113,460，所以不是这样。

扩展事件

我尝试运行一个扩展事件会话来收集query_optimizer_estimate_cardinality事件（我从 Paul White 的博客文章Cardinality Estimation: Combining Density Statistics 中了解到），并获得了以下有趣的花絮：

<CalculatorList>
  <FilterCalculator CalculatorName="CSelCalcColumnInInterval" Selectivity="-1.000" 
                    CalculatorFailed="true" TableName="[p]" ColumnName="CommentCount" />

  <FilterCalculator CalculatorName="CSelCalcAscendingKeyFilter" Selectivity="0.001" 
                    TableName="[p]" ColumnName="CommentCount" UseAverageFrequency="true" 
                    StatId="4" />
</CalculatorList>

所以看起来CSelCalcAscendingKeyFilter计算器被使用了（另一个说它失败了，不管这意味着什么）。该列不是键，也不是唯一的，也不是必须升序，但无论如何。

对这个词做一些谷歌搜索让我找到了一些博客文章：

• Joe Sack - CSelCalcAscendingKeyFilter 计算器，
• Itzik Ben-Gan - Seek and You Shall Scan Part II: Ascending Keys

这些帖子表明，新的 CE 将这些直方图外估计值基于密度向量和统计数据的修改计数器的组合。不幸的是，我已经排除了密度向量（我认为？！），并且修改计数器为零（sys.dm_db_stats_properties无论如何）。

跟踪标志

Forrest建议我打开 TF 2363 以获取有关估计过程的更多信息。我认为该输出中最相关的事情是：

Plan for computation:

  CSelCalcAscendingKeyFilter(avg. freq., QCOL: [p].CommentCount)

Selectivity: 0.000516798

这是一个突破（感谢 Forrest！）：这个0.000516798数字（在Selectivity="0.001"上面的 XE属性中似乎被四舍五入了）乘以表中的行数是我一直在寻找的估计值 (1,934.99)。

我可能遗漏了一些明显的东西，但我无法逆向工程该选择性值是如何在CSelCalcAscendingKeyFilter计算器中产生的。

Answer 1

根据我的测试，越界基数估计只是行数的平方根，下界为自上次统计更新以来添加的行数，上界为每个值的平均行数。

在您的情况下，1,934.99 = SQRT(3744192)

测试设置如下：

--setup
USE TestDB
ALTER DATABASE [TestDB] SET AUTO_UPDATE_STATISTICS OFF
GO

DROP TABLE IF EXISTS dbo.Hist

CREATE TABLE dbo.Hist (
ID int identity primary key,
Num int
)

INSERT dbo.Hist
SELECT TOP 300
(ROW_NUMBER() OVER(ORDER BY(SELECT 1/0)))%3
FROM master..spt_values a
CROSS JOIN master..spt_values b

--Get estimated plan
--don't forget to run right after setup to auto-create stats
SELECT *
FROM dbo.Hist
WHERE Num = 1000

--gradually add rows, then rerun estimate above
INSERT dbo.Hist
SELECT TOP 100
-1
FROM master..spt_values a

--I sure hope you weren't testing this in prod (cleanup)
ALTER DATABASE [TestDB] SET AUTO_UPDATE_STATISTICS ON
GO

令人惊讶的是，这种方法甚至生成了行估计数：20 个总行数为 400，30 个行数为 900，40 个行数为 1600，等等。

尽管超过 10000，行估计最大为 100，这是现有统计信息中每个值的行数。由于 sqrt(300) > 10，仅添加 10 行会将估计值设置为 10。

因此，可以使用以下公式表示估计值：

Estimate = MIN(SQRT(AC), MIN(AR, MC))

请注意，如果对统计数据进行采样，则不考虑 MC。于是公式变成：

Estimate = MIN(SQRT(AC), AR))

在哪里

• MC 是“修改计数”（自创建统计以来的修改数量）
• AC 是“调整后的基数”（统计中的行数加上 MC），
• AR 是每个值的平均行数（统计中的行数除以列中的不同值）

这些估算值的公式以及有关计算器的其他详细信息可以在此博客文章中找到：从 CSelCalcAscendingKeyFilter Calculator 分析估算值