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

Question

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

在我的机器上，给定一个 table 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

递归 CTE 是一项 CPU 昂贵的操作，因为 SQL 服务器“循环”超出范围行。物化数字 table 或基于集合的 CTE 将执行得更快。请注意 CPU 和在我的工作站 (YMMV) 上用 SET STATISTICS TIME ON 报告的经过时间。

号码table:

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.

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

Answer 2

当您将列声明为主键时，SQL 服务器会创建一个聚簇索引，因此这意味着如果您使用主键 table 查询 SQL 服务器查询优化器完全知道该列在哪里。换句话说，此查询尽可能高效，最少 CPU 时间和逻辑读取。要查看这两种方法之间差异的详细视图，请使用 Ctrl+m 运行查询启用执行计划并比较两个执行计划。

Answer 3

Isn't the first one fetching results from disk, and should therefore be slower?

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

当您运行测试时，数据可能已经在缓存中了。即使 none 在缓存中，也很有可能几乎所有的页面在需要之前就已经被预读机制读入缓存，因此 IO 等待是最少的，它又只是一个 CPU绑定操作。（您可以使用 SET STATISTICS IO ON 查看实际需要多少物理读取和预读读取）

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

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

所有这些执行计划操作都需要时间。我在我的本地机器上尝试了最大 10,000,000 的数字。总查询持续时间为 2 分钟 6 秒（其中 38 秒正好花费在 9,999,999 PAGELATCH_SH 等待假脱机 tempdb 中）

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

您可以在下面看到“每个运营商”的时间安排。 table 假脱机运算符（节点 6）花费大量时间，主要是因为它每次发出一个行时都会从假脱机中删除行。节点 0 是将行插入假脱机的操作员。基本上每个返回的数字都会经历这个 wait/insert/delete 循环（尽管由锚语句插入假脱机的单个初始行可以这样做而无需等待）

当然可以提供类似 Postgres 的功能 generate_series one that is entirely CPU based and just dedicated to the task of supplying incrementing values and this could outperform the disc based table approach but as yet no such dedicated function has been implemented in the product. Until such time the current "state of the art" approach to produce numbers without a numbers table is probably the one mentioned first in this page。

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

Numbers table vs recursive CTE to generate a range of numbers

sql

tsql

sql-server