How does a Recursive CTE run, line by line?
I think I've got the format of Recursive CTEs down well enough to write one, but still find myself frustrated to no end that I cannot manually process one (pretend to be the SQL engine myself and reach the result set with pen and paper). I've found this, which is close to what I'm looking for, but not detailed enough. I have no problem tracing through a C++ recursive function and understanding how it runs -- but for SQL I don't understand why or how the engine knows to stop. Does the anchor and recursive block get called everytime, or is the anchor skipped in later iterations? (I doubt it but I'm trying to expression my confusion about the way it seems to jump around.) If the anchor is called each time, how does the anchor not appear multiple times in the final result? I hope someone can just do a break down line 1 line 2, etc. what happens and what is "in memory" as the result set accumulates.
I've taken the liberty of stealing my example from this page, since it seems to be the easiest to understand.
DECLARE @tbl TABLE (
Id INT
, [Name] VARCHAR(20)
, ParentId INT
)
INSERT INTO @tbl( Id, Name, ParentId )
VALUES
(1, 'Europe', NULL)
,(2, 'Asia', NULL)
,(3, 'Germany', 1)
,(4, 'UK', 1)
,(5, 'China', 2)
,(6, 'India', 2)
,(7, 'Scotland', 4)
,(8, 'Edinburgh', 7)
,(9, 'Leith', 8)
;
WITH abcd
AS (
-- anchor
SELECT id, Name, ParentID,
CAST(Name AS VARCHAR(1000)) AS Path
FROM @tbl
WHERE ParentId IS NULL
UNION ALL
--recursive member
SELECT t.id, t.Name, t.ParentID,
CAST((a.path + '/' + t.Name) AS VARCHAR(1000)) AS "Path"
FROM @tbl AS t
JOIN abcd AS a
ON t.ParentId = a.id
)
SELECT * FROM abcd
Solution 1:
Think of a recursive CTE as of an endless UNION ALL:
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
…
In your case, that would be:
WITH abcd1 AS
(
SELECT *
FROM @tbl t
WHERE ParentId IS NULL
),
abcd2 AS
(
SELECT t.*
FROM abcd1
JOIN @tbl t
ON t.ParentID = abcd1.id
),
abcd3 AS
(
SELECT t.*
FROM abcd2
JOIN @tbl t
ON t.ParentID = abcd2.id
),
abcd4 AS
(
SELECT t.*
FROM abcd3
JOIN @tbl t
ON t.ParentID = abcd3.id
),
abcd5 AS
(
SELECT t.*
FROM abcd4
JOIN @tbl t
ON t.ParentID = abcd4.id
),
abcd6 AS
(
SELECT t.*
FROM abcd5
JOIN @tbl t
ON t.ParentID = abcd5.id
)
SELECT *
FROM abcd1
UNION ALL
SELECT *
FROM abcd2
UNION ALL
SELECT *
FROM abcd3
UNION ALL
SELECT *
FROM abcd4
UNION ALL
SELECT *
FROM abcd5
UNION ALL
SELECT *
FROM abcd6
Since abcd6 yields no results, this implies a stopping condition.
Theoretically, a recursive CTE can be infinite, but practically, SQL Server tries to forbid the queries that would lead to infinite recordsets.
You may want to read this article:
- SQL Server: are the recursive CTE’s really set-based?
Solution 2:
The algorithm that CTE use is:
- Execute the anchor part, get result r0
- Execute the recursive part, using r0 as input, and get result r1 (not null)
- Execute the recursive part, using r1 as input, and get result r2 (not null)
- Execute the recursive part, using r3 as input, and get result r3 (not null) ...
- Execute the recursive part, using r(n-1) as input, and output rn (null). This time rn is null, so we use UNION ALL to combine r0, r1, r2 ... r(n-1) and that's the final result
Lets take an example:
WITH cte ( value )
AS (
SELECT 1
UNION ALL
SELECT value + 1
FROM cte
WHERE value < 4
)
SELECT *
FROM cte
The result of this query is:
value
-----------
1
2
3
4
(4 row(s) affected)
Let's examine it step by step:
Execute anchor query (SELECT 1), we got:
r0 = 1
cte = r0 = 1
|
|
V
Now we execute
SELECT value + 1 FROM cte WHERE value < 4
Since cte is r0 (only has 1), we got:
r1 = 2
cte = r1 = 2
|
|
V
Now we execute
SELECT value + 1 FROM cte WHERE value < 4
Since cte is r1 (only has 2), we got:
r2 = 3
cte = r2 = 3
|
|
V
Now we execute
SELECT value + 1 FROM cte WHERE value < 4
Since cte is r2 (only has 3), we got:
r3 = 4
cte = r3 = 4
|
|
V
Now we execute
SELECT value + 1 FROM cte WHERE value < 4
Since cte is r3 (only has 4), we got:
r4 = NULL (because r3 (4) is equal to 4, not less than 4)
Now we stop the recursion!
|
|
V
Let's calculate the final result:
R = r0 union all
r1 union all
r2 union all
r3 union all
= 1 union all
2 union all
3 union all
4 union all
= 1
2
3
4
Solution 3:
I think it breaks down like this:
The anchor statement is executed. This gives you a set of results, called the base set, or T0.
The recursive statement is executed, using T0 as the table to execute the query against. This happens automatically when you query a CTE.
If the recursive member returns some results, it creates a new set, T1. The recursive member is then executed again, using T1 as input, creating T2 if there are any results.
Step 3 continues until no more results are generated, OR the maximum number of recursions has been met, as set by the MAX_RECURSION option.
This page probably explains it best. It has a step-by-step walkthrough of the execution path of a CTE.
Solution 4:
You were probably wanting this link. No, the anchor is not executed multiple times (it couldn't be, then union all would require that all of the results appear). Details at previous link.