I was under the impression that recursive CTEs were set based, but in a recent SO post someone mentioned that they are loops.
Are recursive CTEs set based? Am I wrong to assume that a set based operation cannot be a loop?
Asked
Active
Viewed 944 times
5
-
[Related answer](http://stackoverflow.com/questions/7803640/how-cte-really-works/7807483#7807483) – Martin Smith Oct 19 '11 at 18:03
-
1+1 as it is still an excellent question. – JonH Oct 19 '11 at 18:07
-
Declarative vs procedural might be a more useful and meaningful distinction to make? – Martin Smith Oct 19 '11 at 18:52
3 Answers
2
If it is recursive it is still considered a loop. Although one statement is set based, calling it over and over can be considered a loop. This is an argument about the definition or wording based on the context being used. They are set based statements but the processing is considered in simple terms a looping process.
For those interested here is a nice little write up about performance with CTE's:
http://explainextended.com/2009/11/18/sql-server-are-the-recursive-ctes-really-set-based/
JonH
- 32,732
- 12
- 87
- 145
2
They are set based. Recursive sets are still sets.
But all set operations are, if you look with a powerful enough magnifier glass, loops. Ultimately the code runs on CPUs and CPUs execute a stream of serial instructions that operate on discrete regions of memory. In other words, there is no set oriented hardware. Being 'set oriented' is a logical concept. The fact that all SQL operations are ultimately implemented using some form of a loop is an implementation detail.
Remus Rusanu
- 288,378
- 40
- 442
- 569
-
Indeed, even Itzik Ben Gan's undoubtedly [set based numbers table generator](http://stackoverflow.com/questions/10819/sql-auxiliary-table-of-numbers/2663232#2663232) is still implemented as a bunch of nested loops in the query plan. – Martin Smith Oct 19 '11 at 18:08
0
I think the distinction that needs to be done is "tail recursion" versus "general recursion".
All tail recursions can be implemented as loops - without the need for a Stack.
General recursion support can also be implemented as a Loop - but with a stack.
Recursive CTEs are Tail recursions and hence essentially a Loop. The only difference is the terminating condition is handled by SQL semantics/execution engine. The output from each Loop iteration is UNIONed or whatever set op you specify.
Sarnath
- 1