SQL Server: are the recursive CTE’s really setbased?
Comments enabled. I *really* need your comment
Answering questions asked on the site.
Karl asks:
I've read your article about adjacency lists vs. nested sets in Oracle. A nice explanation, thanks.
You write that recursive operations are rowbased in Oracle and setbased in SQL Server.
Which approach is better in your opinion?
First, a quick reminder for those who have no idea what's this all about.
Recursive queries are useful to build the hierarchy trees, traverse graphs, generate arbitrary rowsets etc. Usually this involves joining a set with itself an arbitrary number of times.
A recursive query is usually defined by the anchor part (the initial rowset, or the base of recursion) and the recursive part (some operation over the previous resultset).
This is same as with the plain recursion: take some initial data as a parameter, modify it in some way and then pass the result of the modification as a new parameter to the same function.
Since SQL operates with sets, the input and the output if this function should also be the sets. And here is the main differences between the approaches used by Oracle on one side, and SQL Server, PostgreSQL and some more systems on the other side.
Oracle uses CONNECT BY
approach, while SQL Server uses recursive CTE approach.
CONNECT BY
A hierarchical query using a CONNECT BY
clause looks like this:
SELECT * FROM mytable START WITH start_with_condition CONNECT BY connect_by_condition (PRIOR mytable)
This query uses two clauses: START WITH
defines the anchor part, while CONNECT BY
defines the recursive parts.
It's an analog of this query:
SELECT * FROM mytable m1 CROSS APPLY ( SELECT m1.* UNION ALL SELECT * FROM mytable m2 CROSS APPLY ( SELECT m2.* UNION ALL SELECT * FROM mytable m3 CROSS APPLY ( SELECT m3.* UNION ALL … ) WHERE connect_by_condition(m2.*) ) WHERE connect_by_condition(m1.*) ) WHERE start_with_condition
On each iteration, exactly one record from the previous table is used. Each innermost query can use the values of only one record of the outermost set.
Here's an example rowset:
ID  Parent 

1  NULL 
2  NULL 
3  1 
4  1 
5  2 
6  2 
and a query over this rowset:
SELECT * FROM mytable START WITH parent IS NULL CONNECT BY parent = PRIOR id
The anchor part consists of two rows:
ID  Parent 

1  NULL 
2  NULL 
, but they are not returned as is. After a row had been returned, the recursive part is being applied to the row:
ID  Parent 

1  NULL 
Recursive condition applied: parent = 1 

2  NULL 
Recursive condition applied: parent = 2 
As you can see, the recursive step can only take the value of a single previous record as an input, while producing a resultset as an output.
The recursive steps are applied to each record independently.
CONNECT BY
recursion takes a single record as input and returns a set as an output. It is scalar by nature.
Recursive CTE
A recursive CTE looks like this:
WITH rows AS ( SELECT * FROM mytable WHERE anchor_condition UNION ALL SELECT * FROM set_operation(mytable, rows) ) SELECT * FROM rows
It's the same as the following:
WITH rows AS ( SELECT * FROM mytable WHERE anchor_condition ), rows2 AS ( SELECT * FROM set_operation(mytable, rows) ), rows3 AS ( SELECT * FROM set_operation(mytable, rows2) ), … SELECT * FROM rows UNION ALL SELECT * FROM rows2 UNION ALL SELECT * FROM rows3 UNION ALL …
A set_operation
can be any set operation: a JOIN
, a UNION
, an EXCEPT
, whatever. It may involve any number of other tables, functions, in other words everything — as long as it's result (also a set, of course) has the same number and datatypes of columns as the anchor part does.
Here's the example on the same sample data:
ID  Parent 

1  NULL 
2  NULL 
3  1 
4  1 
5  2 
6  2 
, but with a new query:
WITH rows AS ( SELECT * FROM mytable UNION ALL SELECT mytable.* FROM rows JOIN mytable ON mytable.parent = rows.id ) SELECT * FROM rows
The anchor part is the same:
ID  Parent 

1  NULL 
2  NULL 
and, unlike the CONNECT BY, it is returned at once. The recursive part is only applied when the previous resultset is known, and it's applied to the resultset as a whole:
ID  Parent 

1  NULL 
2  NULL 
Recursive part: a JOIN with (1, 2) 
, which yields all records of the original table (though not in the tree order)
Conclusions
From this, two importation conclusions can be drawn.
CONNECT BY
approach splits the sets returned by the recursion and applies the recursion to each individual record. This is less powerful, since a record is just a special case of a set, but the results naturally come out in the recursion order. CTE approach allows the recursion to process the set returned on the previous step as a whole. This is more powerful, since a set is a general case of a record, but it takes some extra effort to sort the resultset in the tree order had the need arose.
Everything that can be done using a CONNECT BY
approach can be done with a recursive CTE as well, but not vice versa. That's why it's safe to say that recursive CTE approach is more powerful.
However, what's good in theory, is not always as good in implementation.
SQL Server's implementation
SQL Server uses recursive CTE approach which is set based and more powerful. But SQL Server places some limitations on what you can use in the recursive part of the CTE. And severe limitations they are. You cannot use aggregates, cannot use OUTER JOINs
, cannot use TOP
. Here's the complete list.
What's the reason behind that?
Let's see again the analogs of these two approaches:
CONNECT BY
:
SELECT current_result.* FROM previous_result CROSS APPLY ( SELECT previous_result.* UNION ALL SELECT * FROM mytable WHERE condition(previous_result.*) ) AS current_result
Recursive CTE:
SELECT previous_result.* FROM previous_result UNION ALL SELECT current_result.* FROM set_operation(previous_result, mytable) AS current_result
The former query can always be rewritten as a latter:
SELECT previous_result.* FROM previous_result UNION ALL SELECT current_result.* FROM previous_result JOIN mytable ON condition(previous_result)
In the CROSS APPLY
, each row of the previous is returned, then the scalar condition
which returns true or false is checked for each row of mytable
and current row of the previous_result
. This can be rewritten as a JOIN
.
The reverse is not always true.
Under which conditions it is possible for a recursive CTE query to be rewritten as a CROSS APPLY
query?
For this to be possible, the set_operation
used in the second query should distribute over the UNION ALL
operation.
What does it mean?
The distributivity is a wellknown concept in algebra.
For instance, the multiplication is distributed over addition, this means that this condition:
x × (y + z) = (x × y) + (x × z)
is always true.
But further generalization, power, does not distribute over multiplication. The following condition:
x ^ (y × z) = (x ^ y) × (x ^ z)
does not always hold.
In other words, distributivity means that the order of operations is not important. You can add the results of multiplication just as well as multiply the results of addition, the final result will always be the same.
This was arithmetics, but concept of distributivity can be applied to relational algebra just as well. A set operation distributes over UNION ALL
if the following condition always holds:
set_operation(A UNION ALL B, C) = set_operation(A, C) UNION ALL set_operation(B, C)
It's easy to see that if the condition above is true, the two approaches to the recursion become the same.
Indeed, the operation over the UNION ALL
is the same as the UNION ALL
over the operations, which is the same as the operation applied to each record of the previous_result
. And the latter is exactly what CROSS APPLY
does: applies an operation to each record of the set and returns the resultsing sets combined together (as if with UNION ALL
).
A JOIN
distributes over UNION ALL
. However, DISTINCT
, aggregates, TOP
and some other operations do not.
Maximum over a UNION ALL
is not the same as the UNION ALL
of the maximums. TOP
of a UNION ALL
is not the same as the UNION ALL
of TOP
s, etc.
If we look closer into the restrictions put on the recursive operations by SQL Server we will see that placing these restrictions have one ultimate goal: to forbid all operations that do not distribute over UNION ALL
.
Aggregates are forbidden, TOP
is forbidden, DISTINCT
is forbidden. This is a conspiracy.
However, they cannot lie to the world all the time. They cannot conceal every fact. There are two operations they failed to forbid. And now it's a moment to reveal the truth.
EXCEPT
Consider a sample rowset:
ID 

1 
2 
3 
Now, let's make a recursive query over this rowset:
WITH mytable (id) AS ( SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 ), q AS ( SELECT id FROM mytable UNION ALL SELECT * FROM ( SELECT id FROM othertable EXCEPT SELECT * FROM q ) q2 ) SELECT TOP 20 * FROM q
What should this query return?
Being rewritten as simple SQL, it yields this:
WITH mytable (id) AS ( SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 ), anchor AS ( SELECT * FROM mytable ), recursive1 AS ( SELECT * FROM mytable EXCEPT SELECT * FROM anchor ), recursive2 AS ( SELECT * FROM mytable EXCEPT SELECT * FROM recursive1 ), recursive3 AS ( SELECT * FROM mytable EXCEPT SELECT * FROM recursive2 ), recursive4 AS ( SELECT * FROM mytable EXCEPT SELECT * FROM recursive3 )  , recursive5 AS  … SELECT *, 'anchor' AS setname FROM anchor UNION ALL SELECT *, 'recursive1' AS setname FROM recursive1 UNION ALL SELECT *, 'recursive2' AS setname FROM recursive2 UNION ALL SELECT *, 'recursive3' AS setname FROM recursive3 UNION ALL SELECT *, 'recursive4' AS setname FROM recursive4  UNION ALL  …
The setname
above is for the sake of clarity only, to distinguish between the sets combined with UNION ALL
.
Here's what this query returns:
id  setname  

1  anchor  
2  anchor  
3  anchor  
1  recursive2  
2  recursive2  
3  recursive2  
1  recursive4  
2  recursive4  
3  recursive4  
9 rows fetched in 0.0003s (0.0006s) 
We see that the query returns the whole anchor
part which is just a SELECT * FROM mytable
:
id  setname 

1  anchor 
2  anchor 
3  anchor 
The next part, recursive1
, applies the EXCEPT
operator to the mytable
and anchor
:
SELECT * FROM mytable EXCEPT SELECT * FROM anchor
But since mytable
and anchor
actually match, the result of this operation is an empty rowset. And that's why we don't see recursive1
in the resultset above.
The next part, recursive2
, applies EXCEPT
again:
SELECT * FROM mytable EXCEPT SELECT * FROM recursive1
This time, the second argument to EXCEPT
is empty, and each record from mytable
is returned:
id  setname 

1  recursive2 
2  recursive2 
3  recursive2 
, etc.
EXCEPT
applied to mytable
and an empty set yields a copy of mytable
. EXCEPT
applied to the mytable
and a copy of mytable
yields an empty set. Therefore, the final resultset will be endless, consisting of alternating empty sets and copies of mytable
.
The original recursive query, in theory, should return the same rowset. Let's check if it's really so:
WITH mytable (id) AS ( SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 ), othertable (id) AS ( SELECT 4 UNION ALL SELECT 5 ), q AS ( SELECT id FROM mytable UNION ALL SELECT * FROM ( SELECT id FROM mytable EXCEPT SELECT * FROM q ) q2 ) SELECT TOP 20 * FROM q OPTION (MAXRECURSION 4)
id 

1 
2 
3 
1 
2 
1 
3 
1 
2 
1 
3 
This differs much from what we expected to see.
Let's check what happened.
The anchor part returned the first three rows just as it had to:
id 

1 
2 
3 
The next set (recursive1
) should have been empty. But it has 2 rows instead:
id 

1 
2 
This could only happen it the EXCEPT
clause was applied to the last record of the anchor
set rather than to the whole anchor
:
SELECT * FROM mytable EXCEPT SELECT TOP 1 * FROM anchor ORDER BY id DESC
The query above would yield the same results.
In recursive2
, the EXCEPT
operator, had it been applied to the whole resultset returned by the previous query, would yield a single row 3. However, it returns 1 and 3, which means that EXCEPT
clause was again applied only to the last row.
This is not how a properly designed setbased recursive CTE should behave. But this is exactly how CONNECT BY
query behaves. It splits the recordset into separate records and applies the recursive part to each record individually.
ROW_NUMBER
Analytical functions without PARTITION BY
clause do not distribute over UNION ALL
as well.
A UNION ALL
of two queries containing the ROW_NUMBER
's is not the same as a ROW_NUMBER
applied to the results of a single UNION ALL
query. The latter would return a single consecutive counter, while the former would count the records in each query separately.
ROW_NUMBER
's, however, are still allowed in SQL Server 2005.
Consider this adjacency list rowset defining a tree:
ID  Parent 

1  NULL 
2  NULL 
3  1 
4  1 
5  2 
6  2 
and make a simple tree query over it:
WITH mytable (id, parent) AS ( SELECT 1, NULL UNION ALL SELECT 2, NULL UNION ALL SELECT 3, 1 UNION ALL SELECT 4, 1 UNION ALL SELECT 5, 2 UNION ALL SELECT 6, 2 ), q AS ( SELECT *, ROW_NUMBER() OVER (ORDER BY id) AS rn FROM mytable WHERE parent IS NULL UNION ALL SELECT mytable.*, ROW_NUMBER() OVER (ORDER BY mytable.id) FROM q JOIN mytable ON mytable.parent = q.id ) SELECT * FROM q
The tree is only two levels deep, that's why this query can be rewritten as this:
WITH mytable (id, parent) AS ( SELECT 1, NULL UNION ALL SELECT 2, NULL UNION ALL SELECT 3, 1 UNION ALL SELECT 4, 1 UNION ALL SELECT 5, 2 UNION ALL SELECT 6, 2 ), anchor AS ( SELECT *, ROW_NUMBER() OVER (ORDER BY id) AS rn FROM mytable WHERE parent IS NULL ), recursive1 AS ( SELECT mytable.*, ROW_NUMBER() OVER (ORDER BY mytable.id) AS rn FROM anchor JOIN mytable ON mytable.parent = anchor.id ) SELECT * FROM anchor UNION ALL SELECT * FROM recursive1
id  parent  rn  

1  1  
2  2  
3  1  1  
4  1  2  
5  2  3  
6  2  4  
6 rows fetched in 0.0004s (0.0012s) 
The recursive part returns 4 records and calculates a ROW_NUMBER
over this set. The values returned by ROW_NUMBER
are from 1 to 4, just as they should be.
Now, let's check the recursive query:
WITH mytable (id, parent) AS ( SELECT 1, NULL UNION ALL SELECT 2, NULL UNION ALL SELECT 3, 1 UNION ALL SELECT 4, 1 UNION ALL SELECT 5, 2 UNION ALL SELECT 6, 2 ), q AS ( SELECT *, ROW_NUMBER() OVER (ORDER BY id) AS rn FROM mytable WHERE parent IS NULL UNION ALL SELECT mytable.*, ROW_NUMBER() OVER (ORDER BY mytable.id) FROM q JOIN mytable ON mytable.parent = q.id ) SELECT * FROM q
id  parent  rn  

1  1  
2  2  
5  2  1  
6  2  2  
3  1  1  
4  1  2  
6 rows fetched in 0.0003s (0.0011s) 
See now?
The ROW_NUMBER
's are not consecutive. Instead of a single sequence from 1 to 4, there are two sequences from 1 to 2.
Again, that's exactly what a CONNECT BY
query (or a CROSS APPLY
) would return.
Summary
There are two approaches to implementing a recursive query:
 One approach is recordbased. A recursive part takes a record as a parameter and returns a set. It is then separately applied to each record of the set returned . This approach is implemented by Oracle in
CONNECT BY
queries.  Another approach is setbased. A recursive part takes a set as a parameter, processes it as a whole and returns a new set. It is then passed as a parameter to the next iteration. This approach can be implemented by recursive CTE's
The recordbased approach is better for building hierarchies because it naturally returns the records in the tree order. However, it's less powerful in theory.
The setbased approach is more powerful in theory, since it can process a set as a whole and more complex conditions can be applied. Extra effort is required to sort the resulting recorset in the tree order but it is still possible though less efficient.
In theory, recursive CTE's are more powerful and therefore should be preferred.
SQL Server nominally impelements recursive CTE's, but in fact they are no more than CONNECT BY
queries in disguise. No real setbased operations can be performed over these CTE's, only the recordbased ones.
SQL Server efficiently combines limitations of the recordbased approach used by CONNECT BY
with the absence of the natural tree ordering implied by the setbased approach used by recursive CTE's.
That's why I'd say that Oracle as of 10g implements recursive queries better than SQL Server as of 2005.
Hope that helps.
I'm always glad to answer the questions regarding database queries.