SQL 递归实际上是如何工作的？

Question

从其他编程语言转向 SQL，递归查询的结构看起来很奇怪。一步步走过来，仿佛分崩离析。

考虑以下简单示例：

CREATE TABLE #NUMS
(N BIGINT);

INSERT INTO #NUMS
VALUES (3), (5), (7);

WITH R AS
(
    SELECT N FROM #NUMS
    UNION ALL
    SELECT N*N AS N FROM R WHERE N*N < 10000000
)
SELECT N FROM R ORDER BY N;

让我们来看看吧。

首先，执行锚成员并将结果集放入 R。因此 R 被初始化为 {3, 5, 7}。

然后，执行低于 UNION ALL 并且第一次执行递归成员。它在 R 上执行（即，在我们目前手头的 R 上：{3, 5, 7}）。这导致 {9, 25, 49}。

这个新结果有什么用？它是否将 {9, 25, 49} 附加到现有的 {3, 5, 7}，标记结果联合 R，然后从那里继续递归？或者它是否将 R 重新定义为这个新结果 {9, 25, 49} 并在以后进行所有联合？

两种选择都没有意义。

如果 R 现在是 {3, 5, 7, 9, 25, 49} 并且我们执行递归的下一次迭代，那么我们最终会得到 {9, 25, 49, 81, 625, 2401} 并且我们已经输了 {3, 5, 7}。

如果 R 现在只有 {9, 25, 49}，那么我们就有了标签错误的问题。R 被理解为锚成员结果集和所有后续递归成员结果集的联合。而 {9, 25, 49} 只是 R 的一个组成部分。它不是我们迄今为止累积的完整 R。因此，将递归成员写为从 R 中选择是没有意义的。

---

我当然感谢@Max Vernon 和@Michael S. 在下面详细介绍的内容。即，（1）所有组件都被创建到递归限制或空集，然后（2）所有组件被联合在一起。这就是我理解 SQL 递归实际工作的方式。

如果我们重新设计 SQL，也许我们会强制执行更清晰和明确的语法，如下所示：

WITH R AS
(
    SELECT   N
    INTO     R[0]
    FROM     #NUMS
    UNION ALL
    SELECT   N*N AS N
    INTO     R[K+1]
    FROM     R[K]
    WHERE    N*N < 10000000
)
SELECT N FROM R ORDER BY N;

有点像数学中的归纳证明。

目前 SQL 递归的问题在于它的编写方式令人困惑。它的写法是说每个组件都是通过从 R 中选择而形成的，但这并不意味着到目前为止已经（或似乎已经）构造了完整的 R。它仅表示前一个组件。

Answer 1

递归 CTE 的 BOL 描述描述了递归执行的语义如下：

1. 将 CTE 表达式拆分为锚和递归成员。
2. 运行创建第一个调用或基本结果集 (T0) 的锚点成员。
3. 以 Ti 作为输入和 Ti+1 作为输出运行递归成员。
4. 重复步骤 3，直到返回一个空集。
5. 返回结果集。这是 T0 到 Tn 的 UNION ALL。

因此，每个级别仅将高于此级别的级别作为输入，而不是迄今为止累积的整个结果集。

以上是如何工作的逻辑。物理递归 CTE 目前总是使用嵌套循环和 SQL Server 中的堆栈假脱机来实现。这在此处和此处进行了描述，这意味着实际上每个递归元素只是与上一级的父行一起工作，而不是整个级别。但是递归 CTE 中对允许语法的各种限制意味着这种方法有效。

如果您ORDER BY从查询中删除 ，结果的排序如下

+---------+
|    N    |
+---------+
|       3 |
|       5 |
|       7 |
|      49 |
|    2401 |
| 5764801 |
|      25 |
|     625 |
|  390625 |
|       9 |
|      81 |
|    6561 |
+---------+

这是因为执行计划的操作与以下非常相似 C#

using System;
using System.Collections.Generic;
using System.Diagnostics;

public class Program
{
    private static readonly Stack<dynamic> StackSpool = new Stack<dynamic>();

    private static void Main(string[] args)
    {
        //temp table #NUMS
        var nums = new[] { 3, 5, 7 };

        //Anchor member
        foreach (var number in nums)
            AddToStackSpoolAndEmit(number, 0);

        //Recursive part
        ProcessStackSpool();

        Console.WriteLine("Finished");
        Console.ReadLine();
    }

    private static void AddToStackSpoolAndEmit(long number, int recursionLevel)
    {
        StackSpool.Push(new { N = number, RecursionLevel = recursionLevel });
        Console.WriteLine(number);
    }

    private static void ProcessStackSpool()
    {
        //recursion base case
        if (StackSpool.Count == 0)
            return;

        var row = StackSpool.Pop();

        int thisLevel = row.RecursionLevel + 1;
        long thisN = row.N * row.N;

        Debug.Assert(thisLevel <= 100, "max recursion level exceeded");

        if (thisN < 10000000)
            AddToStackSpoolAndEmit(thisN, thisLevel);

        ProcessStackSpool();
    }
}

NB1：如上所述，在3处理锚成员的第一个子级时，有关其兄弟级5和7和它们的子级的所有信息已经从线轴中丢弃并且不再可访问。

NB2：上面的 C# 与执行计划具有相同的整体语义，但执行计划中的流程并不相同，因为操作符以流水线执行方式工作。这是一个简单的示例，用于演示该方法的要点。有关计划本身的更多详细信息，请参阅较早的链接。

NB3：堆栈假脱机本身显然是作为一个非唯一的聚集索引实现的，其中包含递归级别的键列和根据需要添加的唯一标识符（来源）

Answer 2

这只是一个（半）有根据的猜测，可能是完全错误的。有趣的问题，顺便说一句。

T-SQL 是一种声明性语言；也许递归 CTE 被转换为游标式操作，其中 UNION ALL 左侧的结果附加到临时表中，然后 UNION ALL 的右侧应用于左侧的值。

所以，首先我们将UNION ALL左边的输出插入到结果集中，然后我们将应用到左边的UNION ALL右边的结果插入到结果集中。然后左侧被右侧的输出替换，右侧再次应用于“新”左侧。像这样的东西：

1. {3,5,7} -> 结果集
2. 递归语句应用于 {3,5,7}，即 {9,25,49}。{9,25,49} 被添加到结果集中，并替换了 UNION ALL 的左侧。
3. 递归语句应用于 {9,25,49}，即 {81,625,2401}。{81,625,2401} 添加到结果集中，并替换UNION ALL 的左侧。
4. 递归语句应用于 {81,625,2401}，即 {6561,390625,5764801}。{6561,390625,5764801} 添加到结果集中。
5. 光标已完成，因为下一次迭代导致 WHERE 子句返回 false。

您可以在递归 CTE 的执行计划中看到此行为：

这是上面的第 1 步，将 UNION ALL 的左侧添加到输出中：

这是 UNION ALL 的右侧，输出连接到结果集：

Answer 3

SQL Server 文档，其中提到了_Ti和Ti + ₁既不是很容易理解，也不是对实际实现的准确描述。

\n\n

基本思想是查询的递归部分查看所有先前的结果，但仅查看一次。

\n\n

了解其他数据库如何实现这一点（以获得相同的结果）可能会有所帮助。Postgres文档：

\n\n

\n

递归查询评估

\n\n

\n
1. 评估非递归项。对于UNION（但不是UNION ALL），丢弃重复的行。将所有剩余行包含在递归查询的结果中，并将它们放入临时工作表中中。
\n
2. 只要工作表不为空，请重复以下步骤:\n \n
   \n
   1. 评估递归项，用工作表的当前内容替换递归自引用。对于UNION（但不是UNION ALL），丢弃重复行以及与任何先前结果行重复的行。将所有剩余行包含在递归查询的结果中，并将它们放入临时中间表中中。
   \n
   2. 将工作表的内容替换为中间表的内容，然后清空中间表。
   \n
\n

\n\n

注意
\n 严格来说，这个过程是迭代而不是递归，而是RECURSIVESQL 标准委员会选择的术语。

\n

\n\n

SQLite文档暗示了一种稍微不同的实现，这种一次一行算法可能是最容易理解的：

\n\n

\n

计算递归表内容的基本算法如下：

\n\n

\n
1. 运行initial-select并将结果添加到队列中。
\n
2. 当队列不为空时：\n \n
   \n
   1. 从队列中提取一行。
   \n
   2. 将该单行插入到递归表中
   \n
   3. 假设刚刚提取的单行是递归表中的唯一行，然后运行recursive-select​​，将所有结果添加到队列中。
   \n
\n

\n\n

上述基本程序可以通过以下附加规则进行修改：

\n\n

\n
• 如果 UNION 运算符将initial-select与 相连接recursive-select，则只有在先前没有将相同的行添加到队列中的情况下，才将行添加到队列中。即使重复的行已经通过递归步骤从队列中提取出来，重复的行在添加到队列之前也会被丢弃。如果运算符是 UNION ALL，则由 和 生成的所有行initial-select始终recursive-select会添加到队列中，即使它们是重复的。
  \n [\xe2\x80\xa6]
\n

\n

\n