Recursive CTE

Question

Post reply

Recursive CTE

santhosh_ms3

Default port

Points: 1482
More actions
April 27, 2011 at 2:22 am

#236384

Can someone explain how the below result arrives please ? :ermm:
with CTE(x)as
(
select x = 1
union all
select X=X+1 from CTE where x < 4
union all
select X=X+1 from CTE where x < 4
)
select x from CTE
GO
Result:
x
1
2
2
3
3
4
4
4
4
3
3
4
4
4
4

Viewing 7 posts - 1 through 6 (of 6 total)

You must be logged in to reply to this topic. Login to reply

Hunterwood SSCrazy Points: 2074 More actions · Answer 1

Hi,

Sure.

You have a Common Table Expression with one base query and two recursive queries, joined together by union all. The CTE is named CTE and have one column named x.

I changed your CTE slightly to get the answer:

with CTE(x, y)as

(

select x = cast(1 as numeric(5,3)), y = 0

union all

select X=cast(X+1.1 as numeric(5,3)), 1 from CTE where x < 4

union all

select X=cast(X+1.2 as numeric(5,3)), 2 from CTE where x < 4

)

select x, y from CTE

option (MAXRECURSION 3)

Now the first column returns the value that is tracable and the second column returns which query gave the specific result:

x y

--------

1.000 0 (first recursion)

2.100 1

2.200 2

--------

3.300 1 (second)

3.400 2

--------

4.500 1 (third)

4.600 2

4.400 1

4.500 2

3.200 1

3.300 2

4.400 1

4.500 2

4.300 1

4.400 2

By also setting the MAXRECURSION option to 1, 2 and 3 I could see which recursion gave what result (marked with lines above).

Now I think you can figure it out... 🙂

/Markus

ChrisM@home SSC-Insane Points: 24260 More actions · Answer 2

A recursive CTE can be difficult to interpret. I find it helps to map out the first few iterations using chained CTE's like this;

;WITH CTEAnchor (x) AS (SELECT x = 1),

CTE1 AS (

SELECT X = X + 1 FROM CTEAnchor WHERE x < 4

UNION ALL

SELECT X = X + 1 FROM CTEAnchor WHERE x < 4

),

CTE2 AS (

SELECT X = X + 1 FROM CTE1 WHERE x < 4

UNION ALL

SELECT X = X + 1 FROM CTE1 WHERE x < 4

),

CTE3 AS (

SELECT X = X + 1 FROM CTE2 WHERE x < 4

UNION ALL

SELECT X = X + 1 FROM CTE2 WHERE x < 4

)

SELECT * FROM CTEAnchor

UNION ALL

SELECT * FROM CTE1

UNION ALL

SELECT * FROM CTE2

UNION ALL

SELECT * FROM CTE3

This query yields exactly the same results as your recursive CTE, however the order is slightly different because of the way a rCTE is processed. So your results are explained as follows:

--Result:

x

1 -- anchor. "Visible" to first iteration.

-- First iteration yields two rows, where x = 2.

-- These two rows are "visible" to next iteration.

2 -- first set from first recursive part

2 -- first set from second recursive part

-- Second iteration uses results from first to yield two rows per recursive part, x = 3

-- These four rows are "visible" to next iteration.

3 -- Second set from first recursive part

3 -- Second set from second recursive part

-- Third iteration uses results from second to yield four rows per recursive part, x = 4

4 -- Third set from first recursive part

4 -- Third set from Second recursive part

[font="Arial"]^{Low-hanging fruit picker and defender of the moggies}[/font]

For better assistance in answering your questions, please read this[/url].

Understanding and using APPLY, (I)[/url] and (II)[/url] Paul White[/url]

Hidden RBAR: Triangular Joins[/url] / The "Numbers" or "Tally" Table: What it is and how it replaces a loop[/url] Jeff Moden[/url]

ChrisM@home SSC-Insane Points: 24260 More actions · Answer 3

Hunterwood (4/27/2011)
...
Now I think you can figure it out... 🙂
/Markus

Hi Markus

I can't figure out how you have a 3.n in your third recursion.

Reference: http://msdn.microsoft.com/en-us/library/ms186243.aspx

Edit: added reference.

[font="Arial"]^{Low-hanging fruit picker and defender of the moggies}[/font]

For better assistance in answering your questions, please read this[/url].

Understanding and using APPLY, (I)[/url] and (II)[/url] Paul White[/url]

Hidden RBAR: Triangular Joins[/url] / The "Numbers" or "Tally" Table: What it is and how it replaces a loop[/url] Jeff Moden[/url]

santhosh_ms3 Default port Points: 1482 More actions · Answer 4

Great,

Very clear explanations.

Thanks a lot.

Regards,

Santhosh.

Hunterwood SSCrazy Points: 2074 More actions · Answer 5

Hi Chris,

I don't know why, but it seems as if the CTE first follow one branch to the top, before following the next, but then all by a sudden all siblings are returned in one step.

If you try to change the "x < 4" to "x < 5", you will see the same behaviour; the first recursions just follow one branch to the top, and when the top is reached, the last recursion returns all other rows...

Strange... Anyone that can explain that behaviour? 😀

/Markus

ChrisM@home SSC-Insane Points: 24260 More actions · Answer 6

Hunterwood (4/27/2011)
Hi Chris,
I don't know why, but it seems as if the CTE first follow one branch to the top, before following the next, but then all by a sudden all siblings are returned in one step.
If you try to change the "x < 4" to "x < 5", you will see the same behaviour; the first recursions just follow one branch to the top, and when the top is reached, the last recursion returns all other rows...
Strange... Anyone that can explain that behaviour? 😀
/Markus

The MAXRECURSION hint doesn't appear to be reliable if there's more than one recursive element in the query.

[font="Arial"]^{Low-hanging fruit picker and defender of the moggies}[/font]

For better assistance in answering your questions, please read this[/url].

Understanding and using APPLY, (I)[/url] and (II)[/url] Paul White[/url]

Hidden RBAR: Triangular Joins[/url] / The "Numbers" or "Tally" Table: What it is and how it replaces a loop[/url] Jeff Moden[/url]