在递归公用表表达式中使用 EXCEPT

Question

为什么以下查询返回无限行？我本来希望该EXCEPT条款终止递归..

with cte as (
    select *
    from (
        values(1),(2),(3),(4),(5)
    ) v (a)
)
,r as (
    select a
    from cte
    where a in (1,2,3)
    union all
    select a
    from (
        select a
        from cte
        except
        select a
        from r
    ) x
)
select a
from r

我在尝试回答Stack Overflow 上的一个问题时遇到了这个问题。

Answer 1

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

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

请注意，以上是逻辑描述。操作的物理顺序可能有所不同，如下所示

将此应用到您的 CTE 我希望有以下模式的无限循环

+-----------+---------+---+---+---+
| Invocation| Results             |
+-----------+---------+---+---+---+
|         1 |       1 | 2 | 3 |   |
|         2 |       4 | 5 |   |   |
|         3 |       1 | 2 | 3 |   |
|         4 |       4 | 5 |   |   |
|         5 |       1 | 2 | 3 |   |
+-----------+---------+---+---+---+ 

因为

select a
from cte
where a in (1,2,3)

是锚表达式。这显然返回1,2,3为T0

此后递归表达式运行

select a
from cte
except
select a
from r

使用1,2,3as 将产生4,5as输出的输入，T1然后将其插入下一轮递归将1,2,3无限期地返回，依此类推。

然而，这并不是实际发生的情况。这些是前 5 次调用的结果

+-----------+---------+---+---+---+
| Invocation| Results             |
+-----------+---------+---+---+---+
|         1 |       1 | 2 | 3 |   |
|         2 |       1 | 2 | 4 | 5 |
|         3 |       1 | 2 | 3 | 4 |
|         4 |       1 | 2 | 3 | 5 |
|         5 |       1 | 2 | 3 | 4 |
+-----------+---------+---+---+---+

从使用OPTION (MAXRECURSION 1)和增量向上调整1可以看出，它进入一个循环，每个连续级别将在输出1,2,3,4和 之间不断切换1,2,3,5。

正如@Quassnoi在这篇博文中所讨论的那样。结构的观察结果的模式，就好像每个调用都在做(1),(2),(3),(4),(5) EXCEPT (X)，其中X是从以前调用的最后一行。

编辑：在阅读SQL Kiwi 的优秀答案后，很清楚为什么会发生这种情况，而且这不是故事的全部，因为堆栈中仍然有很多东西永远无法处理。

锚定发射1,2,3到客户端堆栈内容3,2,1

3 弹出堆栈，堆栈内容 2,1

LASJ 返回1,2,4,5，堆栈内容5,4,2,1,2,1

5 弹出堆栈，堆栈内容 4,2,1,2,1

LASJ 返回1,2,3,4 堆栈内容4,3,2,1,5,4,2,1,2,1

4 弹出堆栈，堆栈内容 3,2,1,5,4,2,1,2,1

LASJ 返回1,2,3,5 堆栈内容5,3,2,1,3,2,1,5,4,2,1,2,1

5 弹出堆栈，堆栈内容 3,2,1,3,2,1,5,4,2,1,2,1

LASJ 返回1,2,3,4 堆栈内容 4,3,2,1,3,2,1,3,2,1,5,4,2,1,2,1

如果您尝试用逻辑上等价的（在没有重复/NULL 的情况下）表达式替换递归成员

select a
from (
    select a
    from cte
    where a not in 
    (select a
    from r)
) x

这是不允许的，并会引发错误“子查询中不允许递归引用”。所以也许EXCEPT在这种情况下甚至允许这是一种疏忽。

补充： 微软现在对我的Connect 反馈做出如下回应

Jack的猜测是正确的：这应该是语法错误；确实不应该在EXCEPT子句中允许递归引用。我们计划在即将发布的服务版本中解决此错误。同时，我建议避免在EXCEPT 子句中递归引用。

在限制递归时，EXCEPT我们遵循 ANSI SQL 标准，自从引入递归以来（我相信是 1999 年），该标准就包含了此限制。对于EXCEPTSQL 等声明性语言中的递归（也称为“非分层否定”）的语义应该是什么，还没有广泛的共识。此外，众所周知，在 RDBMS 系统中（对于合理大小的数据库）有效地实现这种语义是非常困难的（如果不是不可能的话）。

看起来最终实现是在 2014 年针对兼容级别为 120 或更高的数据库进行的。

EXCEPT 子句中的递归引用会生成符合 ANSI SQL 标准的错误。

Answer 2

有关递归 CTE 中的当前状态的信息，请参阅Martin Smith 的回答EXCEPT。

解释您所看到的内容以及原因：

我在这里使用了一个表变量，以使锚值和递归项之间的区别更清晰（它不会改变语义）。

DECLARE @V TABLE (a INTEGER NOT NULL)
INSERT  @V (a) VALUES (1),(2)
;
WITH rCTE AS 
(
    -- Anchor
    SELECT
        v.a
    FROM @V AS v

    UNION ALL

    -- Recursive
    SELECT
        x.a
    FROM
    (
        SELECT
            v2.a
        FROM @V AS v2
    
        EXCEPT
    
        SELECT
            r.a
        FROM rCTE AS r
    ) AS x
)
SELECT
    r2.a
FROM rCTE AS r2
OPTION (MAXRECURSION 0)

查询计划是：

执行从计划的根（SELECT）开始，控制将树向下传递到索引假脱机、串联，然后传递到顶级表扫描。

扫描的第一行向上传递树并（a）存储在堆栈假脱机中，（b）返回给客户端。没有定义第一行，但为了论证，让我们假设它是值为 {1} 的行。因此，出现的第一行是 {1}。

控制再次传递到表扫描（连接运算符在打开下一个之前消耗其最外层输入中的所有行）。扫描发出第二行（值 {2}），这再次向上传递树以存储在堆栈上并输出到客户端。客户端现在已收到序列 {1}, {2}。

采用 LIFO 堆栈顶部在左侧的约定，堆栈现在包含 {2, 1}。当控制再次传递给表扫描时，它不再报告更多的行，并且控制传递回连接运算符，后者打开它的第二个输入（它需要一个行传递给堆栈假脱机），并将控制传递给内部联接首次。

内连接在其外部输入上调用表假脱机，它从堆栈 {2} 中读取顶行并将其从工作表中删除。堆栈现在包含 {1}。

在其外部输入上收到一行后，内部连接将控制权向下传递给左反半连接 (LASJ)。这从其外部输入请求一行，将控制权传递给 Sort。Sort 是一个阻塞迭代器，因此它从 table 变量中读取所有行并按升序对它们进行排序（碰巧）。

因此，Sort 发出的第一行是值 {1}。LASJ 的内侧返回递归成员的当前值（刚刚从堆栈中弹出的值），即 {2}。LASJ 处的值是 {1} 和 {2}，因此发出 {1}，因为这些值不匹配。

这一行 {1} 沿着查询计划树向上流动到索引（堆栈）假脱机，在那里它被添加到堆栈中，现在包含 {1, 1}，并发送到客户端。客户端现在已收到序列 {1}、{2}、{1}。

控制现在传回串联，回到内侧（上次返回一行，可能会再次执行），通过内部联接向下传递到 LASJ。它再次读取其内部输入，从 Sort 获得值 {2}。

递归成员仍然是 {2}，因此这次 LASJ 找到 {2} 和 {2}，导致没有发出任何行。在其内部输入上找不到更多行（Sort 现在没有行了），控制权返回到 Inner Join。

Inner Join 读取其外部输入，这导致值 {1} 从堆栈 {1, 1} 中弹出，仅留下 {1} 堆栈。该过程现在重复，来自表扫描和排序的新调用的值 {2} 通过 LASJ 测试并被添加到堆栈，并传递给客户端，客户端现在已收到 {1}、{2}、 {1}、{2}……然后我们继续。

对于递归 CTE 计划中使用的堆栈线轴，我最喜欢的解释是 Craig Freedman 的。