SQL: execution model for recursive CTEs

I’m trying to understand how recursive CTEs are executed and particularly what causes them to terminate. Here’s a simple example:

WITH cte_increment(n) AS (
    SELECT -- Select 1
        0
    UNION ALL -- Union
    SELECT -- Select 2
        n + 1
    FROM -- From
        cte_increment
    WHERE -- Where
        n < 6
)
SELECT
    *
FROM
    cte_increment
;

My current mental model is that when the expression is invoked, the clauses should be executed in this order:

1. Select 1
2. From
3. Where
4. Select 2
5. Union

However, I don’t think that can be happening because the From clause recursively invokes the same expression, which would restart the same process one level deeper. That would lead to infinite recursions, which would only stop when it hit the recursion limit.

My question is, how does the CTE ever check its termination condition?

Thanks in advance for your help!

Answer

So, “recursion” is a little bit of a misnomer here. It is really iterative, starting at the anchor condition. Perhaps a more accurate term would be “induction”, in the mathematical sense.

Each iteration only uses the rows from the previous iteration. It doesn’t use all the rows from the CTE.

So, the first iteration generates:

0

The second only sees the 1 and generates

1

The third only sees the 2 and generates

2

And so on until you get to where the where condition says “no more”.