Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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
share|improve this question

migrated from stackoverflow.com Dec 22 '11 at 19:44

This question came from our site for professional and enthusiast programmers.

3  
BTW Did this come up in a real world case? Struggling to think when you would want to do this? –  Martin Smith Dec 23 '11 at 14:12
    
I was trying to answer another SO question! stackoverflow.com/questions/8597430/… (the accepted answer was a lot more elegant than mine!) –  Tom Hunter Dec 23 '11 at 16:55

2 Answers 2

up vote 13 down vote accepted

I'm using a table variable here, to make the distinction between the anchor values and recursive item clearer (it does not change the semantic).

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)

The query plan is:

Recursive CTE Plan

Execution starts at the root of the plan (the SELECT) and control passes down the tree to the Index Spool, Concatenation, and then to the top-level Table Scan.

The first row from the scan passes up the tree and is (a) stored in the Stack Spool, and (b) returned to the client. Which row is first is not defined, but let us assume it is the row with the value {1}, for the sake of argument. The first row to appear is therefore {1}.

Control again passes down to the Table Scan (the Concatenation operator consumes all rows from its outermost input before opening the next one). The scan emits the second row (value {2}), and this again passes up the tree to be stored on the stack and output to the client. The client has now received the sequence {1}, {2}.

Adopting a convention where the top of the LIFO stack is on the left, the stack now contains {2, 1}. As control again passes to the Table Scan, it reports no more rows, and control passes back to the Concatenation operator, which opens it's second input (it needs a row to pass up to the stack spool), and control passes to the Inner Join for the first time.

The Inner join calls the Table Spool on its outer input, which reads the top row from the stack {2} and deletes it from the worktable. The stack now contains {1}.

Having received a row on its outer input, the Inner Join passes control down its inner input to the Left Anti-Semi Join (LASJ). This requests a row from its outer input, passing control to the Sort. Sort is a blocking iterator, so it reads all rows from the table variable and sorts them ascending (as it happens).

The first row emitted by the Sort is therefore the value {1}. The inner side of the LASJ returns the current value of the recursive member (the value just popped off the stack), which is {2}. The values at the LASJ are {1} and {2} so {1} is emitted, since the values do not match.

This row {1} flows up the query plan tree to the Index (Stack) Spool where it is added to the stack, which now contains {1, 1}, and emitted to the client. The client has now received the sequence {1}, {2}, {1}.

Control now passes back to the Concatenation, back down the inner side (it returned a row last time, might do again), down through the Inner Join, to the LASJ. It reads its inner input again, obtaining the value {2} from the Sort.

The recursive member is still {2}, so this time the LASJ finds {2} and {2}, resulting in no row being emitted. Finding no more rows on its inner input (the Sort is now out of rows), control passes back up to the Inner Join.

The Inner Join reads its outer input, which results in the value {1} being popped off the stack {1, 1}, leaving the stack with just {1}. The process now repeats, with the value {2} from a new invocation of the Table Scan and Sort passing the LASJ test and being added to the stack, and passes to the client, which has now received {1}, {2}, {1}, {2}...and round we go.

My favourite explanation of the Stack spool used in recursive CTE plans is Craig Freedman's.

Paul

share|improve this answer
1  
+1 Thanks for providing this explanation, I was still puzzling over how to reconcile the observed results with the plan but that clears things up nicely. My only slight point of confusion remaining is when does the compute scalar that increments the recursion level get executed? The plan appears to show that this happens for each row emitted from the stack but that can't be right in general terms can it? And does it ever get decremented as the stack unwinds? –  Martin Smith Dec 23 '11 at 10:29
1  
Hi Martin, Craig's post explains the compute scalars - there can be two sets, one generated internally and one to compute the sort of 'level' of recursion often added by users to rCTEs. Unfortunately, the present example makes it difficult to add a 'level' since the recursive reference is on the wrong side of the EXCEPT. Paul –  Paul White Dec 23 '11 at 13:27
    
Ah I see now. I hadn't read it properly. Sorry! I thought it was incrementing the same expression i.e. doing something like [Expr1017] = Scalar Operator([Expr1017]+(1)) so was acting like a global variable. Now I see it actually does [Expr1017] = Scalar Operator([Expr1016]+(1)) where Expr1016 is pulled from the spool itself. –  Martin Smith Dec 23 '11 at 14:11

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

  1. Split the CTE expression into anchor and recursive members.
  2. Run the anchor member(s) creating the first invocation or base result set (T0).
  3. Run the recursive member(s) with Ti as an input and Ti+1 as an output.
  4. Repeat step 3 until an empty set is returned.
  5. 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.

share|improve this answer
1  
Does your "It is important to realise" really mean that the recursive part can only see the rows added by the most recent recursion? It can't look arbitrarily far back into what's been aggregated to date? That would be surprising. –  AakashM Dec 22 '11 at 14:50
4  
@AakashM - Yes inside the recursive CTE the reference to r only includes the set of rows most recently added. Of course the outer reference to r when doing the final select refers to the whole set. I'm thinking that this odd EXCEPT behaviour is likely a bug though. Even if where a in (1,2,3) is removed from the select so select a from cte except select a from r should definitely be empty then it still enters an infinite loop. –  Martin Smith Dec 22 '11 at 14:54
    
Thanks for reporting this on MS Connect @MartinSmith, I was thinking of doing the same. +1 for describing the latest-only (instead of consolidated) rows returned from r behaviour - very clear. Still, actual results do seem strange though.. –  Tom Hunter Dec 22 '11 at 15:56
3  
Just in case you are interested: PostgreSQL immediately throws an error: "recursive reference to query "r" must not appear within EXCEPT" and Oracle complains: "recursive WITH clause must reference itself directly in one of the UNION ALL branches" –  a_horse_with_no_name Dec 23 '11 at 13:41
1  
@a_horse_with_no_name - Seems SQL Server should have forbidden it too. –  Martin Smith Dec 31 '11 at 12:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.