Selecting from hierarchies like Managers and Employees

Question

Selecting from hierarchies like Managers and Employees

Viewing 5 posts - 46 through 49 (of 49 total)

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

Jeff Moden SSC Guru Points: 1004378 More actions · Answer 1

Chuck Hoffman-291200 (5/6/2012)
Jeff, Kevin, tmarkham et. al.,
Nice job! I'm truly impressed.
I'm a long time believer in the value of peer review. Just look at what came of this discussion.

Thanks for the feedback, Chuck. I apologize for kind of hijacking your thread. :blush: And you're absolutely spot on. I've been amazed at some of the things that come in discussions of articles. Thanks for taking the time to post it.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Jeff Moden SSC Guru Points: 1004378 More actions · Answer 2

miika.langille (5/7/2012)
Would you care to elaborate on why the new version of the while loop code works so much better? Showing conclusive proof is great, but if people don't actually understand why its better, then they may not be inclined to use it (or, even worse, they will then use this method blindly without thinking, which was your original problem with rCTEs!). So, to really round out this great discussion, a summary of why/how each method performed better or worse than the others would be great.
As I see it:
Chuck's original query:
While loop, but still set based (no cursors).
"Expensive" subqueries on individual rows to determine set inclusion.
Kevin's rCTE:
Made better use of sets and avoided subqueries applied to individual rows
Still looping over the entire "work table" each time a new set was added?
(How does this method avoid duplicates from being produced? Does the rCTE do it automatically?)
Jeff's while loop v2:
While loop, but still set based, same as original query.
Good use of @CurrentHierarchyLevel to restrict the search to only the "leaf" level nodes.
No need for subqueries, so all operations are on sets.
And, as a final question, could the rCTE likewise be improved with something like the @CurrentHierarchyLevel to restrict the join set, or would the cost of determining this value outweigh the benefit?

The WHERE NOT EXISTS was the truly expensive subquery according to the execution plan. On the 5 level, it created an internal row set from the work table of almost 19 million rows and grew exponentionally for each additional level. It looked to me like it was seeking every row in the worktable for each row in the lookup on the employee table. A hidden Cartesian Join of sorts. The 4th level had an internal rowset of more than 1.4 million rows.

The reason why the rCTE got beat by the While Loop is because it estimated only 1 or 2 rows for each block and didn't come up with the "optimal" plan for each iteration. Further, a lot of rCTEs tend to produce some very high reads. So high that even logical reads end up being quite costly. Could it be made better? I don't know. Perhaps I'll give it a try.

Other than that small bit of extra information, you were very much spot on. Thanks for taking the time to post it.

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Jeff Moden SSC Guru Points: 1004378 More actions · Answer 3

I forgot to look at the execution plans for the loops. They, too, grossly underestimate the number of rows even with a better index. So it has to be just the fact that the recursive CTE simply does more reads than the While Loop.

I got rid of the index on the ManagerID column (it wasn't being used) and added a covering index for the rCTE.

CREATE NONCLUSTERED INDEX IX_Composite01 ON [dbo].[Employee]

(

ManagerID ASC,

EmployeeID ASC,

EmployeeName ASC

)

;

It proved of little help to either the rCTE or the While Loop.

Testing down loop at level 1...

Testing down loop at level 2...

Testing down loop at level 3...

Testing down loop at level 4...

Testing down loop at level 5...

Testing down loop at level 6...

Testing down loop at level 7...

Testing down loop at level 8...

Testing down loop at level 9...

Testing down loop at level 10...

Testing down recursive at level 1...

Testing down recursive at level 2...

Testing down recursive at level 3...

Testing down recursive at level 4...

Testing down recursive at level 5...

Testing down recursive at level 6...

Testing down recursive at level 7...

Testing down recursive at level 8...

Testing down recursive at level 9...

Testing down recursive at level 10...

TestID Direction Method Level Rows DurationMS RowsPerMS

----------- ---------- -------------------- ----------- ----------- ----------- ----------------------

3 Down While Loop 3 635 46 13.804347826087

6 Down While Loop 6 22652 2223 10.1898335582546

5 Down While Loop 5 8487 843 10.067615658363

7 Down While Loop 7 51210 5446 9.40323172970988

9 Down While Loop 9 174164 18976 9.1781197301855

12 Down Recursive 2 116 13 8.92307692307692

8 Down While Loop 8 100762 11953 8.42985024679997

4 Down While Loop 4 2611 313 8.34185303514377

10 Down While Loop 10 270622 35330 7.6598358335692

17 Down Recursive 7 51210 6936 7.38321799307958

15 Down Recursive 5 8487 1230 6.9

18 Down Recursive 8 100762 15053 6.69381518634159

16 Down Recursive 6 22652 3523 6.42974737439682

19 Down Recursive 9 174164 28560 6.09817927170868

20 Down Recursive 10 270622 47200 5.73351694915254

14 Down Recursive 4 2611 570 4.58070175438596

13 Down Recursive 3 635 160 3.96875

2 Down While Loop 2 116 33 3.51515151515152

11 Down Recursive 1 18 10 1.8

1 Down While Loop 1 18 173 0.104046242774566

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)

Kristian Ask SSC Eights! Points: 907 More actions · Answer 4

Jeff,

Great reading!

I was reading the entire post just waiting for your test.... good thing you already did it once. Personally I've been replacing quite a few rCTEs because they just don't perform that well.

Interesting reading:

http://blogs.msdn.com/b/sqlcat/archive/2011/04/28/optimize-recursive-cte-query.aspx

/K

Jeff Moden SSC Guru Points: 1004378 More actions · Answer 5

Kristian Ask (5/10/2012)
Jeff,
Great reading!
I was reading the entire post just waiting for your test.... good thing you already did it once. Personally I've been replacing quite a few rCTEs because they just don't perform that well.
Interesting reading:
http://blogs.msdn.com/b/sqlcat/archive/2011/04/28/optimize-recursive-cte-query.aspx
/K

Hi Kristian. Thanks for the feedback on this.

Even if I hadn't done it before, I'd still be demanding proof of performance from all these peopole that made such claims. I don't tolerate claims of performance well based on any type of personal opinion or supposed experience. It's nothing per personal (heh, unless they insist :-P)... it's just too bloody subjective. In fact, I recently did that on another thread were I didn't actually know what the outcome would be because I've never used Regex before. Fortunately, other good folks have taken up the banner and have done some testing. Regex lost on some of the simple tests by 45 to 1 and I'm not talking milliseconds either.

Are all rCTEs bad and comparatively slow? That's a broad subject and I'll only say that it's been demonstrated that rCTEs can have some pretty severe performance problems in many cases. I've also seen it where they've performed brilliantly although no one wrote equivalent While Loop code to compare it to. The answer for those things not already proven is and always will be "It Depends" until some writes a definitive and comparable test.

I just hope the people making the qualitative claims of performance on this thread have learned something because there were a bunch of them and some of them were adamant. 😉

--Jeff Moden

RBAR is pronounced "ree-bar" and is a "Modenism" for Row-By-Agonizing-Row.
First step towards the paradigm shift of writing Set Based code:
________Stop thinking about what you want to do to a ROW... think, instead, of what you want to do to a COLUMN.

Change is inevitable... Change for the better is not.

Helpful Links:
How to post code problems
How to Post Performance Problems
Create a Tally Function (fnTally)