Tuesday, March 9, 2010

This Article On Recurson Is Entitled “This Article On Recursion Is Entitled “This Article… ∞” ”

This blog entry is participating in T-SQL Tuesday #004, hosted this month by Mike Walsh. You are invited to visit his blog to join the party and read more blogs participating in this month’s theme: IO.

So, get a stiff drink (you’ll need it) and perhaps a Motrin or two, and then sit back and read on…




DrosteMy head was spinning as I entered the local Starbucks. I guess it had been a mistake to watch The Matrix and The Thirteenth Floor back-to-back last night. I vowed never to do anything like that again.

My briefcase felt as heavy as an anchor on the Titanic, which seemed appropriate because I also had a feeling of dread in addition to my dizziness. Instead of standing in line for a drink, I decided to find a table first. I saw an open one in the corner, and started heading toward it. But vertigo hit me like a truck and…

Everything went black.

. . . . .   . . .

“Whoa, take it easy there,” a man said. “Good thing I caught you… I happened to be standing right next to you when you collapsed. Are you okay?”

“Jeez, I guess so,” I said, trying to recover, “I don’t know what came over me.”

“Well, you got the partners kind of worried.”

“Partners?” I asked.

“That’s what Starbucks calls their employees,” the man said. “Just like Disneyland calls their employees cast members… like everybody there is in a movie or something… but who’s watching the movie I wonder?”

“Sorry I asked,” I said.

The kind stranger led me to his table and sat me down and he sat opposite me. There was a laptop computer open in front of him, and next to it was a book entitled Gödel, Escher, Bach.

“Sorry about all the trouble,” I said. “I guess I’ve been overworked lately.”

“It’s no trouble. Do you want to talk about it?”

“Er… I don’t even know you.”

“I’m Rick,” he said, extending a hand.

“Hi Rick. I’m Brad”, I said, shaking it.

“Do you want something to drink?” Rick asked. “I’m having a Droste.”

“A what?” I asked.

“Droste. It’s a Dutch cocoa.”

“Is it any good?”

“Well, to be honest, I don’t really care about the taste. What fascinates me is their logo. Take a look at the picture on the box.”

“Where? What box?”

“Up there,” said Rick.

“What? The ceiling?”

“No, you’re not looking at the right place. It’s up there, next to the beginning of our conversation.”

I shook my head. “I don’t know what the hell you’re talking about. I guess I really am out of it today.”

“How about a glass of water?” Rick offered. “I just happen to have one right here.” He produced a really odd-shaped container partly filled with ice water.

“How am I supposed to drink water out of that thing?” I asked. “What the heck is it anyway?”

“It’s a Klein Bottle,” said Rick.

“Er… no thanks,” I said. “Actually, I’ve just decided I’m not thirsty.”

“You mentioned overwork,” said Rick. “Sometimes it helps to talk things out, even to a total stranger.”

I looked at him. He seemed genuinely concerned. “Well, maybe you’re right,” I said. “I’m under a lot of pressure… I have a blog that I have to write by next Tuesday.”

“What’s the blog about?” asked Rick.

“It’s about SQL Server,” I said.

“Oh yeah, sure, I know SQL Server,” said Rick. “And SQL is one of my favorite TLA’s.”

“TLA?” I asked.

“TLA is a three-letter acronym for Three-Letter Acronym,” said Rick.

I digested that comment. “Er… uh… okay.”

“Please continue,” said Rick, “You were talking about SQL.”

“Yeah, well, I want to participate in this T-SQL Tuesday Blog Party, and I have to come up with a blog about a certain subject. This month’s subject is IO.”

“That’s weird,” said Rick. “You have to write a SQL-related blog about one of Jupiter’s moons?”

“No, not the proper noun Io… the acronym IO.”

“Oh, sorry, I didn't notice the capitalized ‘O’,” said Rick. “IO, huh? As in Information Overload? Is that why you collapsed?”

“No,” I said. “IO stands for Input/Output. And that subject seems more hardware or admin related. I’m more on the developer side of the spectrum.”

“Hey, I have an idea,” Rick said. “Since we were talking about TLA’s earlier, why don’t you blog about CTE’s? Specifically, Recursive CTE’s.”

“What do those have to do with IO?” I asked.

“Well, for one thing, their output is the same as their input,” said Rick. “Kind of like the Klein Bottle there, whose outside is the same as its inside.”

Ignoring the Klein Bottle, I said, “That’s true about Recursive CTE’s, but it doesn’t seem like enough to blog about.”

“I’ll show you what I mean,” said Rick. He scooted his chair closer to me and turned his laptop so that we could both see the screen. The topmost window was a browser that was on Microsoft’s search site Bing.

“I’ve never tried Bing,” I said. “How does it compare to Google?”

“Funny you should mention that,” he said. “I don’t have any opinion of Bing one way or the other. I just like what it stands for.”

“What do you mean?”

“Bing is a recursive acronym that stands for Bing Is Not Google,” he said.

“I didn’t know that.”

“Well, it’s a rumor, but it’s interesting anyway,” said Rick. He ALT+TABbed to SSMS 2008, which was already running on his computer. “Take a look at this Recursive CTE query.”

with RecursiveCTE(String)
as
(
/* Anchor Portion */
select cast('AA' as varchar(10))
union all
select cast('BB' as varchar(10))

union all

/* Recursive Portion */
select cast(String+'X' as varchar(10))
from RecursiveCTE
where len(String)<5
)
select String
from RecursiveCTE
/* option (maxrecursion 100) (This is the default) */
/*
String
------
AA
BB
BBX
BBXX
BBXXX
AAX
AAXX
AAXXX
*/
“Okay,” I said. “What about it?”

“Don’t you wonder why the rows come out in the order they did? You’ll notice I have no ORDER BY in the query.”

“Yeah,” I said. “I’ve seen that kind of thing before, but never really investigated it. I would have thought that AA and BB would come out first, followed by AAX and BBX, and then AAXX and BBXX, and so on.”

“Here’s why,” said Rick. “Take a look at the execution plan, which I’ve amended with some number labels next to each operator. And here’s the same query with some comments that indicate what parts relate to which operators in the plan.”

Simple Recursive Query Execution Plan

with RecursiveCTE(String) /* Spool Operator (#2) */
as
(
/* Anchor Portion: Constant Scan Opeartor (#5) */
select cast('AA' as varchar(10))
union all
select cast('BB' as varchar(10))

union all /* Concatenation Operator (#3) */

/* Recursive Portion */
select cast(String+'X' as varchar(10)) /* Compute Scalar Operator (#10) */
from RecursiveCTE /* Spool Operator (#9) */
where len(String)<5 /* Filter Operator (#11) */
)
select String /* SELECT Operator (#1) */
from RecursiveCTE /* Spool Operator (#2) */
/* option (maxrecursion 100) (This is the default... enforced by Assert (#6) */
“There’s your output/input right there,” said Rick. He pointed to both the Spool operators #2 and #9. “Every row that #2 hands over to the SELECT (#1) for output gets stored into a temporary table (or spool) so that it can act as input over here at #9.”

“Okay,” I said.

“Well, you won’t find this anywhere in the graphical plan, but if you look at the XML or Text plan, you’ll see a new clue. Here’s the Text plan:”

/*
with RecursiveCTE(String)...select String from RecursiveCTE
|--Index Spool(WITH STACK)
|--Concatenation
|--Compute Scalar(DEFINE:([Expr1006]=(0)))
| |--Constant Scan(VALUES:(('AA'),('BB')))
|--Assert(WHERE:(CASE WHEN [Expr1008]>(100) THEN (0) ELSE NULL END))
|--Nested Loops(Inner Join, OUTER REFERENCES:([Expr1008], [Recr1003]))
|--Compute Scalar(DEFINE:([Expr1008]=[Expr1007]+(1)))
| |--Table Spool(WITH STACK)
|--Compute Scalar(DEFINE:([Expr1004]=CONVERT(varchar(10),[Recr1003]+'X')))
|--Filter(WHERE:(STARTUP EXPR(len([Recr1003])<(5))))
|--Constant Scan
*/
“Oh, I see it,” I said. “The Spool is actually a Stack… it’s a LIFO kind of thing… Last In First Out. But in this case it’s more like LOFI… Last Output First Input. So the Anchor part of the query immediately outputs the AA and the BB, which both go into the stack, and then the Recursive part of the query pops the Last-Out value of BB off the stack and processes it as input, which in turn produces and outputs BBX, which gets popped off the stack and processed as input, which produces BBXX, and so on. And when all the BB productions are done, the AA is still in the stack waiting to be processed as input, and it goes through the same cycle… AAX and AAXX and AAXXX.”

“Exactly,” said Rick. “The key here is the Stack Spool… but the important part is that by using this logic, it forces the engine to process the rows one at a time, which is not very ideal, and that can sometimes be disastrous. Let me illustrate… Look at this simple aggregate query, which just produces Monthly Sales by Product in AdventureWorks.”

select ProductID
,Yr
,Mth
,Sales=sum(LineTotal)
from Sales.SalesOrderHeader soh
cross apply (select Yr=year(OrderDate)
,Mth=month(OrderDate)) F
join Sales.SalesOrderDetail sod on soh.SalesOrderID=sod.SalesOrderID
group by ProductID
,Yr
,Mth
order by ProductID
,Yr
,Mth
/*
ProductID Yr Mth Sales
--------- ---- --- ------------
707 2001 7 484.476000
707 2001 8 1170.817000
707 2001 9 1110.257500
707 2001 10 827.646500
707 2001 11 1554.360500
. . .
999 2004 2 35639.340000
999 2004 3 44063.184000
999 2004 4 48275.106000
999 2004 5 52703.024000
999 2004 6 50679.357476
(3890 Rows Total)
*/
“As you can see, that produced 3890 rows. Now let’s say that you want to show running totals for each Product as the months progress. The traditional way of doing that is to do a self-join and a SUM() aggregate, but just for the sake of demonstration, we’ll do it via a Recursive CTE. Here’s what I mean.”

with MonthlyStats as
(
select ProductID
,Yr
,Mth
,Sales=sum(LineTotal)
,RowNum=row_number() over (partition by ProductID
order by Yr,Mth)
from Sales.SalesOrderHeader soh
cross apply (select Yr=year(OrderDate)
,Mth=month(OrderDate)) F
join Sales.SalesOrderDetail sod on soh.SalesOrderID=sod.SalesOrderID
group by ProductID
,Yr
,Mth
)
,
RunningTotals as
(
/* Anchor Portion */
select ProductID
,Yr
,Mth
,Sales
,RunningSales=Sales
,RowNum
from MonthlyStats
where RowNum=1
union all
/* Recursive Portion */
select r.ProductID
,m.Yr
,m.Mth
,m.Sales
,r.RunningSales+m.Sales
,m.RowNum
from RunningTotals r
join MonthlyStats m on r.ProductID=m.ProductID
and r.RowNum+1=m.RowNum
)
select ProductID
,Yr
,Mth
,Sales
,RunningSales
from RunningTotals
order by ProductID
,Yr
,Mth
“The query uses a CTE called MonthlyStats that does that aggregation I showed you previously, producing those 3890 rows, and it uses ROW_NUMBER() to sequence the data. Then that data is used as the main driving table for the RunningTotals Recursive CTE. The Anchor Portion gets all the RowNums of 1, and then the Recursive Portion uses that as its input getting RowNum+1, and so on and so on, until there are no more RowNums left.”

“Okay, I can see that,” I said.

“Let’s run the query.” He pushed the F5 key.

We waited… and we waited… and we waited.

“Hey, while we’re waiting for that to finish, can I ask you something?” said Rick.

“Sure.”

“What is a question that mentions the word umbrella for no apparent reason?”

I hesitated, and then said, “Er… um… you just asked one.”

“Oh, so I did! You’re right!”

“You’re really weird, Rick. You take a lot of getting used to.”

“Yeah, a lot of people say that. Hopefully the readers of this conversation will appreciate me.”

“Readers?” I asked.

“Hey, you out there… yes, I’m talking to you,” Rick said to no one in particular. “Pay attention now: When you aren’t looking at it, this entire dialog is in Spanish.” He paused for a second, and then said, “Hah! Made you look away for a second, didn’t I?”

“Uh… Rick… Who are you talking to?”

“Here’s another one, dear reader. Look closely: .siht ekil ti gnidaer eb d`uoy ,werbeH ni erew ecnetnes siht fI”

“Rick, what’s going on? You’re talking absolute nonsense.”

“Aww, I’m just having a little fun. I’m passing time waiting for this query to finish.”

He smiled at me. I gave him a guarded look.

“Anyway… back to business,” he said. “Why do you think this query is taking so long?” Rick asked.

“Well,” I said, happy to be talking shop again, “Since all output of a Recursive CTE acts as its own input, and since we know the MonthlyStats CTE produces 3890 rows, that means the Recursive Portion of the CTE is going to process those 3890 rows as input… one at a time.”

“True, but there’s more to it than that,” said Rick. He cancelled the query. “I don’t think you want to wait for that to finish. It will take over an hour, in fact, it takes 69 minutes.”

“You’re kidding,” I said.

“No, I’m serious. Anyway, you’re right in that the Recursive Portion of the query will process those 3890 rows as input, but in order to do that, it actually has to execute the MonthlyStats CTE 3890 separate times. The JOIN and the aggregation and sort and ROW_NUMBER() executions occurring over and over 3890 times! Here, I’ll show you. Here’s a copy of the Actual Execution Plan. It’s probably too tiny for you to see, so just click on it to see a larger version of it in another browser window.”

Recursive Query Actual Execution Plan

“Huh?” I said. “Click on it? Browser window?”

“Oh, sorry,” said Rick. “I was talking to somebody else.” He traced a rectangle around the Anchor Portion and the Recursive Portion of the query with his finger. “See… they are identical. Both are doing the JOIN and a sort and the SUM aggregate and the ROW_NUMBER() sequencing. Look at the Index Scan of the Sales.SalesOrderHeader table, for example, in the upper right-hand corner. That table has 31,465 rows in it, and the Anchor Portion of the query executed the Scan once, so it spit out a total of 31,465 rows. But in the Recursive Portion, those same 31,465 rows of the table got scanned 3890 times, spitting out a grand cumulative total of 122,398,850 rows. “

“Yuck,” I said.

“The Merge Join is even worse. In the Anchor Portion, you can see that it processes 121,317 rows. In the Recursive Portion, it processes 121,317 rows 3890 times, for a grand total of 471,923,130 rows.”

“Sheesh!”

“All of this work, just to produce 3890 lousy rows in the final result. By the way, here are the Profiler statistics for the query.”

/*
CPU........ 2,833,093ms
Reads...... 9,197,296
Writes..... 315
Duration... 4,124,269ms = 68.74min
*/
“Well,” I suggested, “It’s obviously a problem using a CTE as the driving table of the Recursive CTE. I’ll bet we could improve performance by putting the MonthlyStats information into a temporary table. And not only that… We could also create an index on the RowNum and ProductID columns and then use that indexed table as the driver.”

“Exactly right. I’ve already done that. Here’s the code to create the temp table and create an index.”

if object_id('tempdb..#MonthlyStats','U') is not null drop table #MonthlyStats

select ProductID
,Yr
,Mth
,Sales=sum(LineTotal)
,RowNum=row_number() over (partition by ProductID
order by Yr,Mth)
into #MonthlyStats
from Sales.SalesOrderHeader soh
cross apply (select Yr=year(OrderDate)
,Mth=month(OrderDate)) F
join Sales.SalesOrderDetail sod on soh.SalesOrderID=sod.SalesOrderID
group by ProductID
,Yr
,Mth

create clustered index Ix_RowProd on #MonthlyStats (RowNum,ProductID)
“And here’s the query that uses that table to drive the Recursive CTE.”

with RunningTotals as
(
/* Anchor Portion */
select ProductID
,Yr
,Mth
,Sales
,RunningSales=Sales
,RowNum
from #MonthlyStats
where RowNum=1
union all
/* Recursive Portion */
select r.ProductID
,m.Yr
,m.Mth
,m.Sales
,r.RunningSales+m.Sales
,m.RowNum
from RunningTotals r
join #MonthlyStats m on r.ProductID=m.ProductID
and r.RowNum+1=m.RowNum
)
select ProductID
,Yr
,Mth
,Sales
,RunningSales
from RunningTotals
order by ProductID
,Yr
,Mth
He pushed the F5 key and it finished in less than a second. “Much better than the last query,” said Rick. “This approach ran in just a fractal of the time.”

“Fractal?”

“Pardon?” asked Rick.

“I think you meant to say fraction… the approach ran in just a fraction of the time.”

“Oh… perhaps I did. Anyway, Profiler shows only 37962 reads… way better than 9 million reads, wouldn’t you say? The Recursive Portion of the query still executed 3890 times, but because of our index on RowNum and ProductID, it only had to do a SEEK 3890 times into the #MonthlyStats temp table… much better than 3890 SCANs (on 2 tables) and 3890 JOINs and 3890 Sorts and 3890 Aggregations and 3890 Sequencing Calculations.”

“Excellent,” I said.

“But, as much as I like the concept of Recursive CTE’s, the fact that they process one row at a time off the Stack Spool is not very efficient. Take a closer look at the makeup of our #MonthlyStats table.”

select Level=coalesce(str(RowNum,5),'Total')
,NumRows=count(*)
from #MonthlyStats
group by RowNum with rollup
/*
Level NumRows
----- -------
1 266
2 265
3 261
4 252
5 251
6 251
7 245
8 244
9 240
10 220
11 219
12 219
13 107
14 70
15 67
. . .
35 12
36 12
37 7
Total 3890
*/
“Our Anchor, which gets all the RowNums of 1, will end up outputting 266 rows… immediately. Then the Recursive Portion will do the RowNums of 2 and 3 and so on. But it will not do them in groups… it will do them one agonizing row at a time via the Spool Stack.”

“True,” I said.

“Well, what if we did do it in groups instead?”

“I see,” I said. “We could process the 266 Anchor rows into a temp table, then use it to process the 2nd level of 265 rows, and then use that to process the 3rd level of 261 rows, and so on and so on, until we’ve done all 37 levels. It’s just a loop.”

“Yes,” said Rick. “An intelligent loop that processes sets of rows instead if individual rows. That’s what SQL does best. Here’s the query that does just that.”

if object_id('tempdb..#RunningTotals','U') is not null drop table #RunningTotals

/* Anchor Portion */
select ProductID
,Yr
,Mth
,Sales
,RunningSales=Sales
,RowNum
into #RunningTotals
from #MonthlyStats
where RowNum=1

/* "Pseudo-Recursive" Portion */
declare @r int = 0
while 1=1
begin
set @r=@r+1
insert #RunningTotals
select r.ProductID
,m.Yr
,m.Mth
,m.Sales
,r.RunningSales+m.Sales
,m.RowNum
from #RunningTotals r
join #MonthlyStats m on r.ProductID=m.ProductID
where r.RowNum=@r and m.RowNum=@r+1
if @@rowcount=0 break
end

select ProductID
,Yr
,Mth
,Sales
,RunningSales
from #RunningTotals
order by ProductID
,Yr
,Mth
Rick hit the F5 key. The query finished in half a second. “This query is just as fast as the recursive query, but it has a third of the reads… 13716 vs 37962.”

“That’s great!” I said.

“We’re doing essentially the same thing as the recursive query, using a table’s output as its own input, but we’re just doing it more efficiently.”

“So it seems our lesson here is that Recursive CTE’s are cool and convenient, but if you use them, then you should only process very very small tables or appropriately-indexed tables. And if you’re a real stickler for maximum efficiency and keeping down the number of Reads, you should throw the Recursive CTE out the window and instead code a loop to intelligently process groups of rows at a time.”

“Sad, but true,” said Rick. “If you abandon Recursion, it will set you free… So to speak.”

I looked at him with admiration. “Hey, Rick, I really appreciate you taking the time to show me this stuff.”

“Oh, it’s no problem. You contributed to this conversation just as much as I did… more than you realize. I just initiated it.”

“Well, you certainly seem to know your stuff.”

“A lot of it is just repetition… I like repeating things over and over again. And I like challenging the brain… I enjoy mind-bending stuff.” He paused and continued. “Oh yeah, and I also read about all of this somewhere.”

“Oh, swell, I guess that means that I can’t use it for my blog then.”

“Don’t worry, you won’t have a problem with that. I have a printed copy of the article where I read about this. Would you like to see it?”

“Sure.”

“Hold on. It’s in my briefcase.”

He leaned over and reached for something on the floor that I hadn’t noticed before.

“That’s the weirdest-looking briefcase I’ve ever seen,” I said.

“It’s a tesseract.”

“What’s a tesseract?”

“Just click on the link in my last sentence and you can learn all about it,” he said.

“Huh? Click on what?”

“Ah, here it is,” he said. He pulled a sheet of paper out of his weird briefcase. But it was no ordinary sheet of paper. Its ends were joined together forming a loop with a half-twist… It was a Möbius strip. He pointed to a location on the strip. “You can start reading here,” he indicated.

I started reading:

“Whoa, take it easy there,” a man said. “Good thing I caught you… I happened to be standing right next to you when you collapsed. Are you okay?”

“Jeez, I guess so,” I said, trying to recover, “I don’t know what came over me.”

“Well, you got the partners kind of---


“Wait a minute,” I said. “This is too weird.”

I stood up…. perhaps too fast… I started to feel dizzy. “What’s going on here? Who the hell are you?”

“I told you, my name is Rick,” he said with a wink and a smile. “Rick Cursion.”

Everything went black.

Mobius Strip, Tesseract, Fractals, Klein Bottle, GEB, Droste, Rewind

“Whoa, take it easy there,” a man said. “Good thing I caught you… I happened to be standing right next to you when you collapsed. Are you okay?”

“Jeez, I guess so,” I said, trying to recover, “I don’t know what came over me.”

“Well, you got the partners kind of worried.”

“Partners?” I asked.

“That’s what Starbucks calls their employees,” the man said. “Just like Disneyland calls their employees cast members…

13 comments:

  1. Good stuff! ... but OUCH my head hurts now, I need to re-read this later.

    ReplyDelete
  2. @StefBauer: Wow, you're a fast reader!... I only posted it 9 minutes ago. Thanks for the comment.

    ReplyDelete
  3. That's great. What a brilliant style and you even worked some really good SQL examples in there. CTEs are one of the areas of functionality I probably play with the least in T-SQL so it was good to see the good and the bad/ugly of them.

    Yes, I even highlighted that last sentence to see how far it went. I hope to someday meet you in person if we are at the same community event sometime. Perhaps PASS in 2010.

    Thanks for the contribution. Good learning with some laughter at the end. I think I'll have some fun on wikipedia with some of the links you sent also.

    I'll also be giving this a second read and looking more closely at the examples.

    ReplyDelete
  4. Okay, lets start a new status quo: As long as I say nothing, you can assume that I've commented: "Awesome as always".

    I appreciated the style. How Rick is the only one who knew he was in a blog post.

    P.S: G.E.B. is my favorite book.

    P.P.S. my favorite droste image: http://www.flickr.com/photos/dmswart/220651564/

    ReplyDelete
  5. @Mike(Walsh): Thanks! Glad you enjoyed it. Hopefully I can attend PASS this year... if not, please let me know if you're ever in the Bay Area.

    @Michael: Thanks... I'm probably going to have to take it easy for a while... this post completely consumed my days last week... but it was fun... except for my brain exploding. I'll have to re-read G.E.B. again... it's been over 25 years since I read it the first time... (Oh, and BTW, nice Droste image... I'm glad you don't that crazy guy's looks either... LOL)

    ReplyDelete
  6. Brad,

    I really enjoy your style. A mix of T-SQL, fun, and imagination.

    Just hilarious!!!

    AMB

    ReplyDelete
  7. Good writer and nice story you write in your blog you need a batter response for your story so, write your story & articles in www.addmyarticles.com good luck nice job keep it up article directories submission

    ReplyDelete
  8. Great article Brad, funny and full of food for brain :)

    ReplyDelete
  9. This comment has been removed by a blog administrator.

    ReplyDelete
  10. What an amazing style. Love this! Great post.

    ReplyDelete
  11. I hadn't seen this before, Brad. Fun story and awesome explanation of the performance problems associated with recursion.

    --Jeff Moden

    ReplyDelete
  12. Brad, this is the best technical blog post I have ever read. Wow. I’ve linked to this on my blog and recommended it to everyone including those not interested in SQL because it is awesome. As for me, I am at the perfect point in my SQL skills development to absorb and benefit from the technical content. Thank you!

    ReplyDelete
  13. I was sitting around at SQL Saturday #177 in Silicon Valley on Feb23 and checked my email, and saw your comment on my blog, and you made my day. Thank you so much for your kind words!

    ReplyDelete