Using EXCEPT in a recursive common table expression

Why does the following query return infinite rows? I would have expected the EXCEPT clause to terminate the recursion..

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

I came across this while trying to answer a question on Stack Overflow.

The BOL description of recursive CTEs describes the semantics of recursive execution as being as follows:

• Split the CTE expression into anchor and recursive members.

• Run the anchor member(s) creating the first invocation or base result set (T0).

• Run the recursive member(s) with Ti as an input and Ti+1 as an output.

• Repeat step 3 until an empty set is returned.

• Return the result set. This is a UNION ALL of T0 to Tn.

Note the above is a logical description. The physical order of operations can be somewhat different as illustrated here

Applying this to your CTE I would expect an infinite loop with the following pattern

+-----------+---------+---+---+---+
| Invocation| Results             |
+-----------+---------+---+---+---+
|         1 |       1 | 2 | 3 |   |
|         2 |       4 | 5 |   |   |
|         3 |       1 | 2 | 3 |   |
|         4 |       4 | 5 |   |   |
|         5 |       1 | 2 | 3 |   |
+-----------+---------+---+---+---+

Because

select a
from cte
where a in (1,2,3)

is the Anchor expression. This clearly returns 1,2,3 as T0

Thereafter the recursive expression runs

select a
from cte
except
select a
from r

With 1,2,3 as input that will yield an output of 4,5 as T1 then plugging that back in for the next round of recursion will return 1,2,3 and so on indefinitely.

This is not what actually happens however. These are the results of the first 5 invocations

+-----------+---------+---+---+---+
| 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 |
+-----------+---------+---+---+---+

From using OPTION (MAXRECURSION 1) and adjusting upwards in increments of 1 it can be seen that it enters a cycle where each successive level will continually toggle between outputting 1,2,3,4 and 1,2,3,5.

As discussed by @Quassnoi in this blog post. The pattern of observed results is as if each invocation is doing (1),(2),(3),(4),(5) EXCEPT (X) where X is the last row from the previous invocation.

Edit: After reading SQL Kiwi's excellent answer it is clear both why this occurs and that this is not the whole story in that there is still loads of stuff left on the stack that never can get processed.


Anchor Emits 1,2,3 to client Stack Contents 3,2,1


3 popped off stack, Stack Contents 2,1


The LASJ returns 1,2,4,5, Stack Contents 5,4,2,1,2,1


5 popped off stack, Stack Contents 4,2,1,2,1


The LASJ returns 1,2,3,4 Stack Contents 4,3,2,1,5,4,2,1,2,1


4 popped off stack, Stack Contents 3,2,1,5,4,2,1,2,1


The LASJ returns 1,2,3,5 Stack Contents 5,3,2,1,3,2,1,5,4,2,1,2,1


5 popped off stack, Stack Contents 3,2,1,3,2,1,5,4,2,1,2,1


The LASJ returns 1,2,3,4 Stack Contents
4,3,2,1,3,2,1,3,2,1,5,4,2,1,2,1

If you try and replace the recursive member with the logically equivalent (in the absence of duplicates / NULLs) expression

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

This is not allowed and raises the error "Recursive references are not allowed in subqueries." so perhaps it is an oversight that EXCEPT is even allowed in this case.

Addition:
Microsoft have now responded to my Connect Feedback as below


Jack's guess is correct: this should have been a syntax error;
recursive references should indeed not be allowed in EXCEPT clauses.
We plan to address this bug in an upcoming service release. In the
meantime, I would suggest to avoid recursive references in EXCEPT
clauses.


In restricting recursion over EXCEPT we follow the ANSI SQL standard,
which has included this restriction ever since recursion was
introduced (in 1999 I believe). There is no widespread agreement over
what the semantics should be for recursion over EXCEPT (also called
"unstratified negation") in declarative languages such as SQL. In
addition, it is notoriously hard (if not impossible) to implement such
semantics efficiently (for reasonably sized databases) in an RDBMS
system.

And looks like the eventual implementation was made in 2014 for databases with compatibility level of 120 or higher.


Recursive references in an EXCEPT clause generates an error in compliance with the ANSI SQL standard.

StackExchange Database Administrators Q#9638, answer score: 32