Help on Performance issue on Recursive CTE

mister.magoo (10/11/2012)

---

Really baffling why the inserts are so slow during the run...

Can you try switching the index on #results to a clustered one?

CREATE CLUSTERED INDEX #IXS ON #RESULTS(LEVEL);

haiao2000 (10/11/2012)

---

Maybe this will give another angle to look at. There are 2 ways I can benefit from this query if I can get it runs fast enough.

1) get all the tree nodes (which we have been trying, so far it is not fast enough)

2) just end as soon as at least one of the nodes has a modification status of 1 (IsDirty=1)? Which is the best way to handle this?

CREATE TABLE #Result(ID INT NOT NULL, ParentID UNIQUEIDENTIFIER NOT NULL, ChildID UNIQUEIDENTIFIER, IsDirty Bit, LEVEL INT IDENTITY(1,1) NOT NULL);

CREATE INDEX #IXS1 ON #Result(LEVEL) INCLUDE(ChildID);

CREATE INDEX #IXS2 ON #Result(IsDirty);

SET IDENTITY_INSERT #Result ON;

--pop the top level node to the temp table

INSERT #Result(ID,ParentID,ChildID,IsDirty,LEVEL)

SELECT ID,ParentID,ChildID,IsDirty,1 FROM MyTable WHERE ParentID = @ObjectID;

--recursive until no more children

WHILE @@ROWCOUNT > 0 BEGIN

INSERT #Result(ID,ParentID,ChildID,IsDirty, LEVEL)

SELECT S.ID, S.ParentID,S.ChildID,S.IsDirty, SCOPE_IDENTITY()+1

FROM #Result AS R

INNER JOIN MyTable S ON S.ParentID = R.ChildID

WHERE LEVEL = SCOPE_IDENTITY();

--for item #2 above, I am thinking to add this, but I am sure it is not the best idea. anythought?

--the problem with this is when non of the nodes with IsDirty=1 then it takes at minimum, the same amount of time to traverse all nodes

IF EXISTS(SELECT ChildID FROM #Result WHERE LEVEL=SCOPE_IDENTITY() AND IsDirty=1)

BREAK;

END

SET IDENTITY_INSERT #Result OFF;

SELECT * FROM #Result

mister.magoo (10/11/2012)

---

haiao2000 (10/11/2012)

---

Maybe this will give another angle to look at. There are 2 ways I can benefit from this query if I can get it runs fast enough.

1) get all the tree nodes (which we have been trying, so far it is not fast enough)

2) just end as soon as at least one of the nodes has a modification status of 1 (IsDirty=1)? Which is the best way to handle this?

CREATE TABLE #Result(ID INT NOT NULL, ParentID UNIQUEIDENTIFIER NOT NULL, ChildID UNIQUEIDENTIFIER, IsDirty Bit, LEVEL INT IDENTITY(1,1) NOT NULL);

CREATE INDEX #IXS1 ON #Result(LEVEL) INCLUDE(ChildID);

CREATE INDEX #IXS2 ON #Result(IsDirty);

SET IDENTITY_INSERT #Result ON;

--pop the top level node to the temp table

INSERT #Result(ID,ParentID,ChildID,IsDirty,LEVEL)

SELECT ID,ParentID,ChildID,IsDirty,1 FROM MyTable WHERE ParentID = @ObjectID;

--recursive until no more children

WHILE @@ROWCOUNT > 0 BEGIN

INSERT #Result(ID,ParentID,ChildID,IsDirty, LEVEL)

SELECT S.ID, S.ParentID,S.ChildID,S.IsDirty, SCOPE_IDENTITY()+1

FROM #Result AS R

INNER JOIN MyTable S ON S.ParentID = R.ChildID

WHERE LEVEL = SCOPE_IDENTITY();

--for item #2 above, I am thinking to add this, but I am sure it is not the best idea. anythought?

--the problem with this is when non of the nodes with IsDirty=1 then it takes at minimum, the same amount of time to traverse all nodes

IF EXISTS(SELECT ChildID FROM #Result WHERE LEVEL=SCOPE_IDENTITY() AND IsDirty=1)

BREAK;

END

SET IDENTITY_INSERT #Result OFF;

SELECT * FROM #Result

Maybe...if you do try that, do it like this, in the WHILE...and add an index on ISDIRTY in #RESULTS

WHILE @@ROWCOUNT>0 AND NOT EXISTS(SELECT 1 FROM #RESULTS WHERE ISDIRTY=1)

INSERT #RESULTS(ID,PARENTID,CHILDID,LEVEL,ISDIRTY)

SELECT S.ID,S.PARENTID,S.CHILDID,SCOPE_IDENTITY()+1,S.ISDIRTY

FROM #RESULTS AS R

JOIN #SOURCE AS S

ON S.PARENTID = R.CHILDID

WHERE LEVEL = SCOPE_IDENTITY();

What is bugging me is why you are seeing such long delays in inserting into #results - that is really odd.

haiao2000 (10/11/2012)

---

I upload new execution plan . if someone can help identify one more break thru like MM did would be a home run for me.

Thanks in advance.

Jeff Moden (10/11/2012)

---

haiao2000 (10/11/2012)

---

I upload new execution plan . if someone can help identify one more break thru like MM did would be a home run for me.

Thanks in advance.

Is this the same data as on your other post???

mister.magoo (10/12/2012)

---

Here is my sample data creation: 10,000,000 + rows in tempdb - you may want to put it somewhere else...it's about 1GB of data.

Oh, and it relies on a TALLY table called TALLY with a column called N.

See here for one if you need it : http://qa.sqlservercentral.com/scripts/Advanced+SQL/62486/

-- Include this if you want to rebuild the source table later - takes about 2 to 3 minutes

-- DROP TABLE #SOURCE;

IF OBJECT_ID('TEMPDB..#SOURCE') IS NULL

BEGIN

CREATE TABLE #SOURCE(ID INT IDENTITY(1,1) NOT NULL, PARENTID UNIQUEIDENTIFIER NOT NULL, CHILDID UNIQUEIDENTIFIER, ISDIRTY CHAR(1) DEFAULT('N'));

CREATE UNIQUE CLUSTERED INDEX #IX_CLUST ON #SOURCE (PARENTID,CHILDID);

-- CREATE LEVEL 1 <- 100 ROWS

INSERT #SOURCE(PARENTID,CHILDID)

SELECT TOP 100 NEWID(),NEWID()

FROM TALLY

-- CREATE LEVEL 2 <- ~ 10,000 ROWS

INSERT #SOURCE(PARENTID,CHILDID)

SELECT CHILDID,NEWID()

FROM #SOURCE,TALLY

WHERE N<100

-- CREATE LEVEL 3 <- ~ 100,000 ROWS

INSERT #SOURCE(PARENTID,CHILDID)

SELECT CHILDID,NEWID()

FROM #SOURCE,TALLY

WHERE N<100

AND ID >100

-- CREATE LEVEL 4 <- ~ 10,000,000 ROWS

INSERT #SOURCE(PARENTID,CHILDID,ISDIRTY)

SELECT CHILDID,NEWID(),'Y'

FROM #SOURCE,TALLY

WHERE N<10

AND ID >10100

-- Add an index just to make the selection of a starting point quicker

CREATE INDEX #IX_ID ON #SOURCE (ID);

END

And the results table :

-- Prepare a temp table to hold the result set

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,ISDIRTY CHAR(1)) ;

-- Add an index to aid with recursion

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

-- Add an index to help with the decision of when to stop - when ISDIRTY="Y"

CREATE INDEX #IXDIRTY ON #RESULTS(ISDIRTY);

-- We need this to be able to insert the LEVEL value

SET IDENTITY_INSERT #RESULTS ON;

Now add the first level to the results table:

-- Get the starting point, arbritrarily chosen as row with ID=1 - they all have the same number of children, so it doesn't matter.

DECLARE @START UNIQUEIDENTIFIER;

SELECT TOP 1 @START = PARENTID FROM #SOURCE ORDER BY ID OPTION(FAST 1);

-- INSERT the first row in our hierarchy - level 1

INSERT #RESULTS(ID,PARENTID,CHILDID,LEVEL,ISDIRTY)

SELECT ID,PARENTID,CHILDID,1,ISDIRTY

FROM #SOURCE

WHERE PARENTID=@START;

And process the rest...

-- Do a dirty old loop (only iterates once per level in the hierarchy) while we haven't hit out stop condition and there were rows found

WHILE @@ROWCOUNT>0 AND NOT EXISTS(SELECT 1 FROM #RESULTS WHERE ISDIRTY='Y')

-- pick up the last inserted set and go find their children to insert to the table with an incremented LEVEL

INSERT #RESULTS(ID,PARENTID,CHILDID,LEVEL,ISDIRTY)

SELECT S.ID,S.PARENTID,S.CHILDID,SCOPE_IDENTITY()+1,S.ISDIRTY

FROM #RESULTS AS R

JOIN #SOURCE AS S

ON S.PARENTID = R.CHILDID

WHERE LEVEL = SCOPE_IDENTITY()

OPTION( RECOMPILE );

-- the WHILE loop only repeats the INSERT, nothing else

SET IDENTITY_INSERT #RESULTS OFF;

With this data, you will see the highest wait times at level 3 and 4, but if you stop the query at level 3 by adding

AND SCOPE_IDENTITY()<3

to the WHILE condition, then run this - the level 4 SELECT:

SELECT S.ID,S.PARENTID,S.CHILDID,S.ISDIRTY

FROM #RESULTS AS R

JOIN #SOURCE AS S

ON S.PARENTID = R.CHILDID

WHERE LEVEL = 3

You will see that it takes a long time (15-20 secs) just to select the data.

I get this execution plan: http://qa.sqlservercentral.com/Forums/Attachment12601.aspx

If something can be done to speed up this select, then we've cracked it - but at the moment I cannot see how.

The fact that that last SELECT takes 15-20 secs with a clean buffer, but zero seconds once the data is cached kind of points towards there just being a physical limit on the speed of reading that many rows from this sort of data? maybe? Or is it just a matter of the join being slow? I can't see the wood for the trees now, so maybe one of the more intelligent beings can help...