Return to Revisions

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.

So each level only has as input the level above not the entire result set accumulated so far.

The above is how it works logically. Physically recursive CTEs are currently always implemented with nested loops and a stack spool in SQL Server. This is described here and here.

If you remove the ORDER BY from your query the results are ordered as follows

+---------+
|    N    |
+---------+
|       3 |
|       5 |
|       7 |
|      49 |
|    2401 |
| 5764801 |
|      25 |
|     625 |
|  390625 |
|       9 |
|      81 |
|    6561 |
+---------+

This is because the execution plan operates very similarly to the following C#

using System;
using System.Collections.Generic;
using System.Diagnostics;

public class Program
{
    private static readonly Stack<Tuple<long, int>> StackSpool = new Stack<Tuple<long, int>>();

    private static void Main(string[] args)
    {
        //temp table #NUMS
        var nums = new[] { 3, 5, 7 };

        //Anchor member
        foreach (var number in nums)
            AddToStackSpoolAndEmit(number, 0);

        //Recursive part
        ProcessStackSpool();

        Console.WriteLine("Finished");
        Console.ReadLine();
    }

    private static void ProcessStackSpool()
    {
        //recursion base case
        if (StackSpool.Count == 0)
            return;

        var row = StackSpool.Pop();

        var thisLevel = row.Item2 + 1;
        var thisNum = row.Item1 * row.Item1;

        Debug.Assert(thisLevel <= 100, "max recursion level exceeded");

        if (thisNum < 10000000)
            AddToStackSpoolAndEmit(thisNum, thisLevel);

        ProcessStackSpool();
    }

    private static void AddToStackSpoolAndEmit(long number, int recursionLevel)
    {
        StackSpool.Push(Tuple.Create(number, recursionLevel));
        Console.WriteLine(number);
    }
}