主页 / dba / 问题 / 9638
Accepted
Tom Hunter
Asked: 2011-12-22 17:27:09 +0800 CST

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

  • 772

为什么以下查询返回无限行？我本来希望该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的问题时遇到了这个问题。

sql-server sql-server-2008

2 个回答

  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因此，在这种情况下，甚至允许这种疏忽。

    补充： 微软现在已经回复了我的连接反馈如下

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

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

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

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

    • 32
  2. Best Answer

    有关递归 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)

    查询计划为：

    递归 CTE 计划

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

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

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

    采用 LIFO 堆栈顶部在左侧的约定，堆栈现在包含 {2, 1}。当控制再次传递给 Table Scan 时，它不再报告任何行，并且控制传递回 Concatenation 运算符，这将打开它的第二个输入（它需要一行传递到堆栈假脱机），并且控制传递给 Inner Join首次。

    Inner join 在其外部输入上调用 Table Spool，它从堆栈 {2} 中读取顶行并将其从工作表中删除。堆栈现在包含 {1}。

    在其外部输入上收到一行后，Inner Join 将控制权向下传递到其内部输入到 Left Anti-Semi Join (LASJ)。这从其外部输入请求一行，将控制权传递给排序。Sort 是一个阻塞迭代器，因此它从 table 变量中读取所有行并按升序对它们进行排序（当它发生时）。

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

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

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

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

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

    对于递归 CTE 计划中使用的 Stack spool，我最喜欢的解释是 Craig Freedman 的。

    • 27

相关问题