在递归公用表表达式中使用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

#1 楼

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

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

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

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是一个阻塞的迭代器，因此它从表变量中读取所有行并对其进行升序排序（发生这种情况）。

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

此行{1}沿查询计划树向上流动到索引（堆栈）将其添加到堆栈中的假脱机，该堆栈现在包含{1，1}，并发出给客户端。客户端现在已接收到序列{1}，{2}，{1}。

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

递归成员仍然是{2}，因此这一次LASJ找到了{2}和{2}，结果是没有行被发出。在其内部输入上不再找到任何行（排序现在不在行中），控制权将传递回内部联接。

内部联接读取其外部输入，结果为值{1 }从堆栈{1，1}中弹出，仅剩下{1}。现在，该过程重复进行，新的表扫描和排序调用中的值{2}通过LASJ测试并被添加到堆栈中，并传递给客户端，客户端现在已经收到{1}，{2}， {1}，{2} ...回过头来。

对于递归CTE计划中使用的Stack假脱机，我最喜欢的解释是Craig Freedman's。

#2 楼

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


将CTE表达式拆分为锚点和递归成员。
运行锚点成员创建第一个调用或基本结果集（T0）。
以Ti作为输入并以Ti + 1作为输出运行递归成员。重复步骤3直到返回空集。
返回结果集。这是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)

是Anchor表达式。这显然将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 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也是一个疏忽。

添加：
Microsoft现在对我的“连接反馈”做出了如下响应



杰克的猜测是正确的：这应该是语法错误；
确实不应在EXCEPT子句中使用递归引用。
我们计划在即将发布的服务版本中解决此错误。同时，我建议避免在EXCEPT
在限制对EXCEPT的递归时，我们遵循ANSI SQL标准，
其中包括自从引入递归以来一直存在这种限制（我相信是在1999年）。在诸如SQL之类的声明性语言中，对于在EXCEPT上进行递归的语义（也称为“未分层否定”）没有广泛的共识。另外，众所周知，在RDBMS
系统中（对于合理大小的数据库）有效地实现这种
语义（如果不是不可能的话）是很困难的。


/>似乎最终在2014年实现了兼容性级别为120或更高的数据库。


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