在递归公共表表达式中使用除

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

我试图回答一个 问题 在堆栈溢出上。

Answer 1

看 马丁·史密斯的答案 有关当前状态的信息 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)

查询计划是：

执行始于计划的根（选择），然后控制将树向下传递到索引线轴，串联，然后转到顶级表扫描。

扫描中的第一行通过树向上，是（a）存储在堆栈线轴中，（b）返回给客户端。为了参数，首先未定义哪一行，但让我们假设它是带有{1}的行。因此，出现的第一行是{1}。

控制再次传递到表扫描（串联操作员在打开下一个输入之前，将所有行从其最外面的输入中消耗掉）。扫描排放第二行（值{2}），然后再次将树通过以存储在堆栈上并输出到客户端的树。客户现在已经收到了序列{1}，{2}。

采用一个约定，其中lifo堆栈的顶部在左侧，堆栈现在包含{2，1}。随着控件再次传递到表扫描，它不再报告行，并且控制权传递回串联操作员，该连接操作员将打开其第二个输入（它需要一行才能传递到堆栈吊杆），然后控制传递到内部连接。首次。

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

在其外部输入上收到一行后，内联连接将其内部输入传递到左反间隙连接（LASJ）。这会从其外部输入中请求一行，将控件传递到排序。排序是一个阻止迭代器，因此它从表变量中读取所有行并将它们分类为上升（如它发生的那样）。

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

此行{1}将查询计划树流到索引（堆栈）线轴上，并将其添加到堆栈中，该堆栈现在包含{1，1}，并发射到客户端。客户端现在已收到序列{1}，{2}，{1}。

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

递归成员仍然是{2}，因此LASJ发现{2}和{2}，导致没有排放。在其内部输入上没有更多的行（现在排出行），控制权传递到内部连接。

内部连接读取其外部输入，从而导致值{1}从堆栈{1，1}中弹出，并将堆栈仅{1}留下。现在，该过程重复，并从表扫描的新调用中进行值{2}，然后对通过LASJ测试进行排序并添加到堆栈中，然后传递给客户端，该客户端已收到{1}，{2}，{2}， {1}，{2} ...和我们去。

我的最爱 解释 Craig Freedman's是递归CTE计划中使用的堆栈线轴。

Answer 2

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

1. 将CTE表达式分为锚和递归成员。
2. 运行锚定成员创建第一个调用或基础结果集（T0）。
3. 将递归成员作为输入运行，将Ti+1作为输出运行。
4. 重复步骤3，直到返回空套。
5. 返回结果集。这是整个T0到TN的联盟。

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

将此应用于您的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,3 作为输入，将产生输出 4,5 作为 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猕猴桃的出色答案 很明显，为什么会发生这种情况，这并不是整个故事，因为堆栈上仍然有很多东西永远无法处理。

锚发射 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

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

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

这是不允许的，并提出了错误“递归参考在子征中不允许参考”。所以也许这是一种监督 EXCEPT 在这种情况下甚至允许。

添加：微软现在回应了我的 连接反馈 如下

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

限制递归 EXCEPT 我们遵循ANSI SQL标准，自从引入递归以来（我相信1999年），该标准一直在其中。关于语义应该递归的语义应该是什么，没有广泛的协议 EXCEPT （也称为“未分层的否定”）在诸如SQL之类的声明语言中。此外，众所周知，在RDBMS系统中有效地（对于合理尺寸的数据库）有效地实施此类语义是很难的。

看起来最终实施是在2014年为数据库做出的 兼容性水平为120或更高.

除了子句中，递归引用符合ANSI SQL标准，会产生错误。