Recursive SQL queries: How do they work?

Yes - its UNION ALL for me, though I have on occasion thought of the anchor as creating a number of 'threads' (just conceptually!) where each thread is one row that then executes against the recursive part, if you see what I mean.  On occasion, it has helped me recognize situations where recursion might be useful, which I would not have spotted otherwise.

A developer friend insists that he can think 'recursively' naturally - making it easy to recognize recursion opportunities...sadly I lack that particular gene :c)

Hi Linchi,

Great post!

The key thing most important to me in all of this is understanding that each row of the anchor part (and subsequently, each row of the recursive part) will cause the recursive part to run once.  This is cause for the massive inefficiency associated with recursive CTEs... I hope that they can be converted to use a more "set-based" approach in the future.

Yep, it's UNION ALL for me. Because it's a set. The stack view seems for suitable for a non-set coder.

Brian:

Linchi's point, as far as I can tell, is that there is no set with recursive CTEs.  It's an illusion of a set.  You can verify that yourself by looking at the query plan, statistics, or creatively applying ROW_NUMBER in the recursive part (Google a bit and you should be able to find an example I've posted on a few forums).  

Set is an illusion with recursive CTEs. But then, we must be careful about at which level we are talking about set-based solutions. One could argue that DBMS vendors are free to implement recursive CTEs and any other SQL constructs however they want internally as long as the defined meaning of the construct is maintained. For instance, a SELECT statement may be internally implemented with walking a pointer through a memory data structure, and no set-base purist would give a fuss about that, right?

With respct to recursive CTEs, the question is: should we expect the UNION ALL pseudo code given in BOL to be the actual implementation of a SQL Server recursive CTE? The answer is no (a yes would contradict the set-based view I reckon). Recursive CTEs are valued for their declarative nature, not for their being a super-construct that will be pre-processed (or expanded or transformed) into a composition of some other SQL constructs. Being declarative is being set-oriented, one could argue.

The other question, of course, is: is the stack-based implementation of recursive CTEs, as described above, always the best for performance? The answer here is not that clear. My impression is that the vendors who have implemented recursive CTEs seem to have reached a consensus that the stack approach is the way to implement recursive CTEs. There may be research to support this.

My limited experience led me to believe that even with the stack approach, there are variations (such as pruning the intermediate 'results' or the stack size more aggressively or earlier in the process) that could have resulted in better performance.

Personally, I believe the performance problems of recursive CTEs all seem to stem from the fact that there is no way to materialize prior CTEs (or cache and control the results of prior CTEs) when their materialization actually makes sense semantically.

Linchi: Assuming that there is at least one equijoin between the anchor and the recursive part, I don't see why the current row-by-row spool approach is necessary.  Why is it possible to build a spool, but not to optimize a bit further and build a hash table for each intermediate set, based on the join predicate?  

Adam;

I'd love to see that. But note that if an intermediate set is 'materialized' (with a hash or whatever algorithm), the execution semantics of the recursive CTE would be different from how a recursive CTE is currently implemented because the materialized intermediate result can become stale. This is not necessarily bad because in many situations the nature of the problem or data can guarantee the correctness of the final result regardless whether an intermediate result is stale or not. In these cases, what you described would be a great welcome performance wise.

Hi Linchi,

OK, then limit that solution to when the user is running SNAPSHOT or RCSI?  Works for me :-)

This sounds like it could run very slowly in general. Does it?

Neal: Yep.  It's a beast.

After weeks of putting it off, I finally found the time and spent the last day and a half judging the

nice one