在遞歸公用表表達式中使用 EXCEPT

為什麼以下查詢返回無限行？我本來希望該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的問題時遇到了這個問題。

有關遞歸 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}。

控制權再次傳遞給 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 的。

引用自：https://dba.stackexchange.com/questions/9638