Hidden RBAR: Counting with Recursive CTE's

Question

Hidden RBAR: Counting with Recursive CTE's

Viewing 15 posts - 16 through 30 (of 73 total)

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

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

drew.georgopulos (8/8/2011)
Good God i had no idea reading could make me feel so smart!...now it just has to sink in
Thank you very much for explaining the intracacies of each path.
drew

Heh... sorry about the very slow lead-in on Pseudo-Cursors. Drew. At the risk of causing some of the more experienced users to nod off, I wanted to make absolutely sure that even a total Neophyte to SQL would understand the idea.

Thanks for stopping by and thanks for the feedback.

--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: 1003863 More actions · Answer 2

CELKO (8/8/2011)
This was really good. I was surprised that the WHILE loop did so better than the rCTE. I was expecting the loop to be a bit better because it does not have to touch a table except to write an integer, but I expected the optimizer to turn the rCTE into a loop.

Thanks for stopping by and for the feedback, Joe. I think I'm regretting not including a While Loop in the coded demonstration in the article. Maybe I'll go back and add it in along with the results in the graphs, as well. I've just got to find the time to do that.

Shifiting gears, how's the 2nd edition of "Trees" coming along?

--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: 1003863 More actions · Answer 3

mcannistra (8/8/2011)
Thank you Jeff for your wonderful post.
It has been extremely helpful to achieve faster speed in a test case I was creating on sql azure.
I referenced your post in the Microsoft forum where I had already started a thread before finding your precious info:
http://social.msdn.microsoft.com/Forums/en-US/ssdsgetstarted/thread/c368315a-1bf1-4353-b0af-c4cfbb44b2c1
Cheers,
Mario

Thanks for the read and the feedback, Mario. Just remember... I didn't invent any of these methods (they've all been around for a very long time) especially the Cascading CTE method. That's Itzik Ben-Gan's. The only thing I did differently was to include some optimizations that a bunch of us here at SSC have added over time, one of which is the Base 10 counts. Itzik used Base 2 in his and, IIRC, was also the first to use the "TOP" optimization.

And thanks for the mention on the MSDN forum. I'm glad you could put one of the methods to good use so quickly.

--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: 1003863 More actions · Answer 4

Kenneth Wymore (8/8/2011)
Nice article! Thanks for the performance stats with the examples. I sense that I have some production code to rewrite now.... 🙂

BWAA_HAAA!!! It'll be a "Fire Drill" for sure, Kenneth. 🙂

As Frank pointed out in a post above, not all rCTE's are bad. The article was only concerned with "Counting" rCTE's. It's worthwhile to to compare methods before deciding which method to put into production. Usually, I avoid rCTE's altogether simply because I can usually find or build a bit a set based code but I do test rCTE solutions as well as others in my "need for speed". 🙂

Thanks for the read and the feedback.

--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: 1003863 More actions · Answer 5

SQLRNNR (8/8/2011)
Great Article Jeff.

Thanks for stopping by, Jason. Always a pleasure. 🙂

--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)

terrance.steadman SSCrazy Points: 2097 More actions · Answer 6

Jeff Moden (8/8/2011)
Heh... yeah... the ol' "hot ice" trick works pretty well but makes the beer taste pretty bad. That's why I use the "Chill'n'Tap" method, instead. 😛
Thanks for stopping by and for the feedback. Hmmmm. "Pseudo-Counters". You may have just coined your own term for the 3 counting methods in the article that use "Pseudo-Cursors". 🙂

I don't know the "hot ice" trick. I was thinking how alcohol itself does not freeze in a regular freezer. It's freezing temperature is just too low. I was considering more like Jello shots. Add unflavored gelatine and put in the fridge.

"Pseudo-Counters" I must have had counter on the brain or *something*.

Gatekeeper SSCommitted Points: 1633 More actions · Answer 7

Another fantastic RBAR article by the director of DAR, Department of Anti-RBAR!

One drawback with Itzik-Style Cross-Joins going out to E8 is making sure you limit E8's results as soon as possible. Otherwise, you'll calculate all 100 million rows, which is very expensive. Don't execute the code below, just do the estimated query plan.

DECLARE @List varchar(max) = REPLICATE(CAST('a,b,c,d,e,f,' as varchar(max)), 50000)

;WITH

E1(N) AS (

SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL

SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1

), -- 1*10^1 or 10 rows

E2(N) AS (SELECT 1 FROM E1 a, E1 b), -- 1*10^2 or 100 rows

E4(N) AS (SELECT 1 FROM E2 a, E2 b), -- 1*10^4 or 10,000 rows

E8(N) AS (SELECT 1 FROM E4 a, E4 b), -- 1*10^8 or 100,000,000 rows

Num(N) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM E8)

SELECT N FROM Num WHERE SUBSTRING(@List, N, 1) = ','

;WITH

E1(N) AS (

SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL

SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1

), -- 1*10^1 or 10 rows

E2(N) AS (SELECT 1 FROM E1 a, E1 b), -- 1*10^2 or 100 rows

E4(N) AS (SELECT 1 FROM E2 a, E2 b), -- 1*10^4 or 10,000 rows

E8(N) AS (SELECT 1 FROM E4 a, E4 b), -- 1*10^8 or 100,000,000 rows

Num(N) AS (SELECT TOP (DATALENGTH(ISNULL(@List,1))) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM E8)

SELECT N FROM Num WHERE SUBSTRING(@List, N, 1) = ','

/* Anything is possible but is it worth it? */

Jeff Moden SSC Guru Points: 1003863 More actions · Answer 8

Gatekeeper (8/8/2011)
Another fantastic RBAR article by the director of DAR, Department of Anti-RBAR!
One drawback with Itzik-Style Cross-Joins going out to E8 is making sure you limit E8's results as soon as possible. Otherwise, you'll calculate all 100 million rows, which is very expensive. Don't execute the code below, just do the estimated query plan.
DECLARE @List varchar(max) = REPLICATE(CAST('a,b,c,d,e,f,' as varchar(max)), 50000)
;WITH
E1(N) AS (
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1
), -- 1*10^1 or 10 rows
E2(N) AS (SELECT 1 FROM E1 a, E1 b), -- 1*10^2 or 100 rows
E4(N) AS (SELECT 1 FROM E2 a, E2 b), -- 1*10^4 or 10,000 rows
E8(N) AS (SELECT 1 FROM E4 a, E4 b), -- 1*10^8 or 100,000,000 rows
Num(N) AS (SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM E8)
SELECT N FROM Num WHERE SUBSTRING(@List, N, 1) = ','
;WITH
E1(N) AS (
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL
SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1 UNION ALL SELECT 1
), -- 1*10^1 or 10 rows
E2(N) AS (SELECT 1 FROM E1 a, E1 b), -- 1*10^2 or 100 rows
E4(N) AS (SELECT 1 FROM E2 a, E2 b), -- 1*10^4 or 10,000 rows
E8(N) AS (SELECT 1 FROM E4 a, E4 b), -- 1*10^8 or 100,000,000 rows
Num(N) AS (SELECT TOP (DATALENGTH(ISNULL(@List,1))) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) FROM E8)
SELECT N FROM Num WHERE SUBSTRING(@List, N, 1) = ','

Outstanding. Another good point to emphasize that I didn't emphasize in the article. Thanks.

Ben-Gan published his "TOP" optimization a couple of years ago for the very reason you mention and I was sure to include it in the code in the article.

Thanks for the read and the thoughtful feedback, Gatekeeper.

--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)

Evil Kraig F SSC Guru Points: 100851 More actions · Answer 9

Say Jeff, Excellent examples and walkthroughs as always to not only understand that it's sub-optimal, but WHY, and WHERE, and how to prove it to both yourself and your boss when you need to.

The best part about it is that you can take your own code, compare it to the samples, and it helps you check your own work against it with the necessary optimization pieces swapped in/out. One of the best parts of the code your dust bunnies write for you under threat of no more popsicles.

Thanks again!

- Craig Farrell

Never stop learning, even if it hurts. Ego bruises are practically mandatory as you learn unless you've never risked enough to make a mistake.

For better assistance in answering your questions[/url] | Forum Netiquette
For index/tuning help, follow these directions.[/url] |Tally Tables[/url]
Twitter: @AnyWayDBA

Jeff Moden SSC Guru Points: 1003863 More actions · Answer 10

terrance.steadman (8/8/2011)
Jeff Moden (8/8/2011)
Heh... yeah... the ol' "hot ice" trick works pretty well but makes the beer taste pretty bad. That's why I use the "Chill'n'Tap" method, instead. 😛
Thanks for stopping by and for the feedback. Hmmmm. "Pseudo-Counters". You may have just coined your own term for the 3 counting methods in the article that use "Pseudo-Cursors". 🙂
I don't know the "hot ice" trick. I was thinking how alcohol itself does not freeze in a regular freezer. It's freezing temperature is just too low. I was considering more like Jello shots. Add unflavored gelatine and put in the fridge.
"Pseudo-Counters" I must have had counter on the brain or *something*.

Beer has some interesting freezing qualities... take it down to somewhere between 26 and 28^oF and it's still liquid. Give it a little bit of a sharp rap and all the beer in the bottle will turn to ice in just several seconds.

The "Hot Ice" trick requires a chemical that you can make from regular household items like vinegar and (IIRC) baking soda and (IIRC) Isopropyl alcohol which, of course, is poison to drink. Makes a really cool (no pun intended) effect though. Hmmm... I wonder if it'll still work with Ethanol.

--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)

terrance.steadman SSCrazy Points: 2097 More actions · Answer 11

Jeff Moden (8/8/2011)
Beer has some interesting freezing qualities... take it down to somewhere between 26 and 28^oF and it's still liquid. Give it a little bit of a sharp rap and all the beer in the bottle will turn to ice in just several seconds.
The "Hot Ice" trick requires a chemical that you can make from regular household items like vinegar and (IIRC) baking soda and (IIRC) Isopropyl alcohol which, of course, is poison to drink. Makes a really cool (no pun intended) effect though. Hmmm... I wonder if it'll still work with Ethanol.

The same freezing trick works with soda pop too. We used to leave our 2 liters sitting in the snow on our porch. It would stay liquid until you "accidently" bumped it. Then it would suddenly freeze solid as a rock. A lot of fun to watch. Unfortunately, the pop would be rather flat when if finally thawed out.

There are heat packs that are sold from China and Hong Kong that contains the same chemical that is used in Salt and Vinegar potato chips. It has the same freezing effect as the beer and pop, but at a higher temperature. (http://beneforce.com/informationfaq/reusableheatpacks/sodiumacetatehow.htm).

Andy DBA SSCommitted Points: 1776 More actions · Answer 12

majorbloodnock (8/8/2011) ... No-one with any taste buds would take a perfectly acceptable alcoholic drink and cool it so much that it freezes...

A perfectly acceptable alcoholic drink? Have you ever tasted Canadian "beer"? I'm guessing the whole idea behind the popsicles is to numb the taste buds...

Sorry, don't mean to pick on Canadian beer. Most American "beer"s aren't palatable either unless they're too cold to taste. That's why we have a brand where graphics on the can change color when it's cold enough for consumption!

Oh yeah, Great article, Jeff!

John Dempsey Hall of Fame Points: 3225 More actions · Answer 13

Great article Jeff with great explanations & examples.

Jeff Moden SSC Guru Points: 1003863 More actions · Answer 14

Evil Kraig F (8/8/2011)
Say Jeff, Excellent examples and walkthroughs as always to not only understand that it's sub-optimal, but WHY, and WHERE, and how to prove it to both yourself and your boss when you need to.
The best part about it is that you can take your own code, compare it to the samples, and it helps you check your own work against it with the necessary optimization pieces swapped in/out. One of the best parts of the code your dust bunnies write for you under threat of no more popsicles.
Thanks again!

Awesome new handle, Craig. The dust bunnies like it, too! 🙂 And that's some great feedback. I'm just glad the dust bunnies will work for the occasional beer popsicle . 😛 Thanks, Craig.

--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: 1003863 More actions · Answer 15

Andy DBA (8/8/2011)
Oh yeah, Great article, Jeff!

BWAA-HAAA!!! Admit it... you only came for the beer! 😛

Thanks for the read and the feedback, Andy.

--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)