Recursive SQL queries: How do they work?

Linchi Shea — Thu, 16 Apr 2009 04:36:00 GMT

Recursive SQL queries are built with recursive common table expressions (CTEs). You can look at the execution semantics of a recursive CTE from two different, but equivalent, perspectives.

We can call the first one the UNION ALL view. The following pseudo code that illustrates how a recursive CTE executes is taken from the SQL Server 2005 Books Online:

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.

This is an intuitive, and—some may even argue—is very much a set-based view of recursive CTEs because it is described with query resultsets and the UNION ALL operator.

The second approach can be labeled as the stack view. The following pseudo code defines the execution semantics of a recursive CTE:

Run the anchor member and push the resultset in a stack.
Let a cursor point to the first row from the bottom of the stack.
Use the current row to evaluate the recursive member, and push the resultset into the stack.
Move the cursor one row up in the stack.
Repeat Step 3 until the cursor is moved beyond the top of the stack.

If you don’t like the word ‘cursor’, replace it with the word ‘pointer’ J. As far as I know, the stack view is much less talked about in the SQL Server community. But it's always good to have different perspectives on the same thing.

I personally find the stack view less intuitive, though it is actually closer to how a recursive CTE is implemented. When I think about solving a problem with a recursive CTE, I always think with the UNION ALL view. However, one of the DB2 gurus I used to work with insists that the stack view suits him just fine, and he finds it intuitive enough that it is how he thinks when approaching a problem with recursive CTEs.

For you folks reading this post, most of you probably think in terms of the UNION ALL of the resultsets when working with recursive CTEs. But I could be wrong.

Linchi Shea : Recursive CTEs

Recursive SQL queries: How do they work?