This is just a (semi) educated guess, and is probably completely wrong. Interesting question, by the way.
T-SQL is a declarative language; perhaps a recursive CTE is translated into a cursor-style operation where the results from the left side of the UNION ALL is appended into a temporary table, then the right side of the UNION ALL is applied to the values in the left side.
So, first we insert the output of the left side of the UNION ALL into the result set, then we insert the results of the right side of the UNION ALL applied to the left side, and insert that into the result set. The left side is then replaced with the output from the right side, and the right side is applied again to the "new" left side. Something like this:
- {3,5,7} -> result set
- recursive statements applied to {3,5,7}, which is {9,25,49}. {9,25,49} is added to result set, and replaces the left side of the UNION ALL.
- recursive statements applied to {9,25,49}, which is {81,625,2401}. {81,625,2401} is added to result set, and replaces the left side of the UNION ALL.
- recursive statements applied to {81,625,2401}, which is {6561,390625,5764801}. {6561,390625,5764801} is added to result set.
- Cursor is complete, since next iteration results in the WHERE clause returning false.
You can see this behavior in the execution plan for the recursive CTE:
This is step 1 above, where the left side of the UNION ALL is added to the output:
This is the right side of the UNION ALL where the output is concatenated to the result set:
