数字表与递归 CTE 生成一系列数字

Question

为什么使用数字表比使用递归 CTE 动态生成它们要快得多？

numbers在我的机器上，给定一个包含 1 到 100000 数字的单列（主键）的表n，查询如下：

select n from numbers;

大约需要 400 毫秒才能完成。

使用递归 CTE 生成数字 1 到 100000：

with u as (
    select 1 as n
    union all
    select n + 1
    from u
    where n < 100000
)
select n
from u
option(maxrecursion 0);

在 SQL Server 2019 上大约需要 900 毫秒才能完成。

我的问题是，为什么第二个选项比第一个选项慢这么多？第一个不是从磁盘获取结果，因此应该更慢吗？

否则有什么办法可以让CTE跑得更快吗？因为在我看来，这是比在数据库中存储数字列表更优雅的解决方案。

Answer 1

第一个不是从磁盘获取结果，因此应该更慢吗？

100,000 个整数将适合大约 161 个数据页（假设未使用压缩） - 每行将为 11 个字节，并在槽数组中占用 2 个字节。

当您运行测试时，数据可能已经在缓存中。即使缓存中没有任何页面，也很可能在需要之前几乎所有页面都已通过预读机制读入缓存，因此 IO 等待时间极短，并且这又只是 CPU 密集型操作。（您可以用来SET STATISTICS IO ON查看实际需要多少物理读取和预读读取）

当然，从缓存中的数据页读取行是 SQL Server 所擅长的。从执行计划的角度来看，根本不复杂。正确的行可以从索引查找运算符（理想情况下或扫描运算符）返回，并直接输出到客户端，无需额外的运算符。

递归 CTE 功能是一种通用方法，始终使用基本相同的执行计划。来自锚点部分的行被添加到堆栈假脱机中，然后从假脱机中弹出（删除）以馈送到嵌套循环运算符，该运算符计算其内部子树上的递归部分并将值沿执行计划树传递到添加到堆栈假脱机（用于进一步递归）并返回给客户端。

所有这些执行计划操作都需要时间。我10,000,000在本地机器上尝试了最多的数字。总体查询持续时间为 2m 6s（其中 38 秒用于 9,999,999 次PAGELATCH_SH等待假tempdb脱机）

这些锁存器等待的原因在此处的惰性锁存器部分中进行了描述。表假脱机操作员持有页面上的锁存器，但是当索引假脱机操作员尝试插入下一个数字的行（在同一基础假脱机中）时，它会被另一个操作员阻止。因此必须进入释放锁存器并解锁自身的等待状态。（具体来说，它IndexDataSetSession::LocatePageForInsert大概解释了为什么它在模式下等待SH而不是在模式下等待EX）。在这种情况下，它们的数量相对较多，因为返回的每个数字都处于不同的递归级别，因此在再次调用表假脱机以重播该行之前，所有插入仅执行一行。

您可以在下面看到“每个操作员”的时间安排。表假脱机操作符（节点 6）花费相当多的时间，主要是因为它每次发出一行时都会从假脱机中删除该行。节点 0 是将行插入到假脱机中的操作符。本质上，每个返回的数字都会经历这个等待/插入/删除循环（尽管通过锚语句插入到假脱机中的单个初始行可以在不等待的情况下这样做）

当然，可以提供像 Postgresgenerate_series这样完全基于 CPU 的函数，并且仅致力于提供递增值的任务，事实上，这在 SQL Server 2022 中已完成。

在以前的版本中，在没有数字表的情况下生成数字的“最先进”方法可能是本页首先提到的方法。

Answer 2

递归 CTE 是一项占用 CPU 资源的操作，因为 SQL Server 会“循环”超出行。物化数字表或基于集合的 CTE 的执行速度会快得多。请注意报告的 CPU 和运行时间SET STATISTICS TIME ON。

号码表：

SELECT * FROM dbo.numbers;

 SQL Server Execution Times:
   CPU time = 16 ms,  elapsed time = 231 ms.

递归 CTE：

with u as (
    select 1 as n
    union all
    select n + 1
    from u
    where n < 100000
)
select n
from u
option(maxrecursion 0);

 SQL Server Execution Times:
   CPU time = 375 ms,  elapsed time = 529 ms.

基于集合的 CTE：

WITH 
     t10 AS (SELECT n FROM (VALUES(0),(0),(0),(0),(0),(0),(0),(0),(0),(0)) t(n))
    ,t1k AS (SELECT 0 AS n FROM t10 AS a CROSS JOIN t10 AS b CROSS JOIN t10 AS c)
    ,t100k AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT 0)) AS n FROM t1k AS a CROSS JOIN t10 AS b CROSS JOIN t10 AS c)
SELECT n
FROM t100k;

 SQL Server Execution Times:
   CPU time = 0 ms,  elapsed time = 223 ms.

数字表的一个优点是可以利用唯一索引来优化某些查询，尽管此处不适用。