Help on Performance issue on Recursive CTE

CREATE TABLE #TempCTE (ID BIGINT, ParentID uniqueidentifier, ObjectID uniqueidentifier)
INSERT INTO #TempCTE

SELECT 1,convert(uniqueidentifier, 'B4ED3C39-9626-44B6-93D9-000B37BDA575'),convert(uniqueidentifier,'95C1A774-C79B-4861-AAB4-09E8070188FB') UNION ALL
SELECT 2,convert(uniqueidentifier, 'C4ED3C39-9626-44B6-93D9-000B37BDA575'),convert(uniqueidentifier,'95C1A774-C79B-4861-AAB4-09E8070188FB') UNION ALL
SELECT 3,convert(uniqueidentifier, 'B4ED3C39-9626-44B6-93D9-000B37BDA575'),convert(uniqueidentifier,'5A116CF5-BD94-46F7-9533-4576D83CC6B0') UNION ALL
SELECT 4,convert(uniqueidentifier, '95C1A774-C79B-4861-AAB4-09E8070188FB'),convert(uniqueidentifier,'E43FB52B-863D-4D28-95B5-2871CC823721') UNION ALL
SELECT 5,convert(uniqueidentifier, 'E43FB52B-863D-4D28-95B5-2871CC823721'),convert(uniqueidentifier,'3C571CC5-FE52-4453-AFDC-313EBF9CF05F') UNION ALL
SELECT 6,convert(uniqueidentifier, 'E43FB52B-863D-4D28-95B5-2871CC823721'),convert(uniqueidentifier,'68B7C10A-D03E-4F99-9737-6D4CED3B4692') UNION ALL
SELECT 7,convert(uniqueidentifier, 'E43FB52B-863D-4D28-95B5-2871CC823721'),convert(uniqueidentifier,'DD74A988-99F8-4BF7-B884-7DDE14264D0C') UNION ALL
SELECT 8,convert(uniqueidentifier, 'D77FB52B-863D-4D28-95B5-2871CC823721'),convert(uniqueidentifier,'DD74A988-99F8-4BF7-B884-7DDE14264D0C')

--get nodes recursive, this is where slowness be
;WITH TempCTE AS
(
SELECT ParentID, ObjectID, 0 as Depth
FROM #TempCTE
WHERE ParentID='B4ED3C39-9626-44B6-93D9-000B37BDA575'

UNION ALL

SELECT T1.ParentID, T1.ObjectID, Depth + 1
FROM #TempCTE T1
INNER JOIN TempCTE T2 on T2.ObjectID = T1.ParentID

)
SELECT TOP 100 PERCENT *
FROM TempCTE
ORDER BY ParentID ;

DROP TABLE #TempCTE

IF OBJECT_ID('TEMPDB..#RESULTS') IS NOT NULL
DROP TABLE #RESULTS;

CREATE TABLE #RESULTS(ID INT NOT NULL, PARENTID UNIQUEIDENTIFIER NOT NULL, CHILDID UNIQUEIDENTIFIER, LEVEL INT IDENTITY(1,1) NOT NULL);

CREATE INDEX #IXS ON #RESULTS(LEVEL) INCLUDE(CHILDID);

WHILE @@ROWCOUNT>0
INSERT #RESULTS(ID,PARENTID,CHILDID,LEVEL)
SELECT S.ID,S.PARENTID,S.CHILDID,SCOPE_IDENTITY()+1
FROM #RESULTS AS R
JOIN #SOURCE AS S
ON S.PARENTID = R.CHILDID
WHERE LEVEL = SCOPE_IDENTITY();

mister.magoo (10/10/2012)

Hi there, I would like to offer you my own twist on this using the "identity hack".

The outline of the logic is to replace the recusive cte with a recursive INSERT managed by a WHILE statement and the "identity hack".

First you are going to need somewhere to store the results


IF OBJECT_ID('TEMPDB..#RESULTS') IS NOT NULL 
	DROP TABLE #RESULTS;

CREATE TABLE #RESULTS(ID INT NOT NULL, PARENTID UNIQUEIDENTIFIER NOT NULL, CHILDID UNIQUEIDENTIFIER, LEVEL INT IDENTITY(1,1) NOT NULL);

CREATE INDEX #IXS ON #RESULTS(LEVEL) INCLUDE(CHILDID);

The results table matches your source data, with an extra identity column which has an index with an included column of childid.

Next you need to allow identity inserts on the results table...


SET IDENTITY_INSERT #RESULTS ON;

And pop the head of the list into the results with a "Level" of 1.


INSERT #RESULTS(ID,PARENTID,CHILDID,LEVEL)
SELECT ID,PARENTID,CHILDID,1
FROM #SOURCE
WHERE PARENTID=@START;

Now for the "recursive" bit


WHILE @@ROWCOUNT>0
	INSERT #RESULTS(ID,PARENTID,CHILDID,LEVEL)
	SELECT S.ID,S.PARENTID,S.CHILDID,SCOPE_IDENTITY()+1
	FROM #RESULTS AS R
	JOIN #SOURCE AS S
	ON S.PARENTID = R.CHILDID
	WHERE LEVEL = SCOPE_IDENTITY();

Explanation of this code:

WHILE @@ROWCOUNT>0 just repeats the INSERT until it processes zero rows (you have run out of CHILDREN)

The INSERT, uses SCOPE_IDENTITY two ways.

1. to SELECT all the ROWS that were last added to the results table
2. to INSERT the new Level value (last value + 1)

Finally, turn off identity insert and select your results.


SET IDENTITY_INSERT #RESULTS OFF;

SELECT *
FROM #RESULTS;

Using this approach I can "walk the tree" for a four level (44000 results) setup in a 4.5 Million row source table in seconds, whereas the recursive CTE takes too long to bother timing it.

Try it out, see if it helps.