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…

---

My 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.”

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.”



“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.



“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…