在递归公共表表达式中使用除
-
16-10-2019 - |
题
为什么以下查询返回无限行?我会期望 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
我试图回答一个 问题 在堆栈溢出上。
解决方案
看 马丁·史密斯的答案 有关当前状态的信息 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计划中使用的堆栈线轴。
其他提示
递归CTE的BOL描述 将递归执行的语义描述为如下:
- 将CTE表达式分为锚和递归成员。
- 运行锚定成员创建第一个调用或基础结果集(T0)。
- 将递归成员作为输入运行,将Ti+1作为输出运行。
- 重复步骤3,直到返回空套。
- 返回结果集。这是整个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标准,会产生错误。