Ken Robertson's Blog

Ramblings of a .NET developer

Which is better in SQL Server: Recursion or Temp tables?

I have a little dilemma.  For nGallery, we want to update it so the “picture count” returns the number of pictures in the album and all of its subalbums, not just in that one album.  One thing that complicates it is that you can have subsubalbums, or even subsubsubalbums.  Do there is no quick and easy way to “select count(*) from albums where it is this album or is child of this album”.

There are two ways I could do this... with a recursive stored procedure or a stored procedure that uses a temporary table.  Which does SQL Server handle faster though?  Well, shouldn't say faster... faster != better, necessarily.  The recursive function would just parse the album “tree” (get to think back to my fun binary tree exercises in Data Structures classes!  seriously, loved that class).  The one that uses a temporary table would just loop adding the IDs of albums under the main one until none are left, then just do a “select count(*) from pictures where albumID in (select id from #tmp)”.

I've always thought temporary tables was slow because it had a lot of overhead, but I also tend to think of recursion as a little bit riskier... plus, it could have its own memory overhead, and I don't know if SQL Server has a stack limit.

Posted: Mar 09 2004, 03:39 PM by qgyen | with 20 comment(s)
Filed under:

Comments

denny said:

why not just keep a counter?

AddPicture == COunter++

DeletePicture == Counter--

make that apply to the whole album and you have a sum as a simple number.

so one time you run a script to find the current totals and add them to your db in anew column of type int.

update the function that adds pictures and the one that deletes them

no looping, no temp tables, no recusion....

or is that too simple an idea??
# March 9, 2004 7:00 PM

Shannon C said:

Use a table variable over a temp table.
# March 9, 2004 7:23 PM

Jason Mauss said:

If you've got the ID value for the top-most album you could do some self-joins to get all the sub-album ID values, right? Maybe use the self-join as a nested subquery? Like SELECT COUNT(*) AS Value FROM Table WHERE albumID IN (SELF-JOIN SELECT Query here) ? Just a thought.
# March 9, 2004 7:26 PM

Jon Galloway said:

The only way you'll really know is to test it out. Some options:
1) (you're not going to do this, but it's interesting) - use nested sets rather than self joins - http://www.intelligententerprise.com/001020/celko.jhtml?_requestid=57775
2) run a trigger that updates counts on insert. i hate triggers, so next...
3) pick a maximum depth and do a limited set of self joins. if you decide you'll only go 10 levels deep, you can just left join on youself 10 times (not the end of the world) and get your count there
4) select back with "for xml auto / explicit" and xslt to filter. possibly less impact on your sql server, but slower response.
5) use recursion to load an @temp table - i'd pick that over the #temp table and select your count - i've used that it was slow. we looked at moving it into a sql job that would update a "counts" table every few minutes so the update would be faster. if you do this, test with indexes on your temp table

out of all of the above, i'd go with 3 - pick a max depth, write an ugly self join that goes 10 or 15 levels deep, and avoid both temp tables and recursion.
# March 9, 2004 7:48 PM

Phil Scott said:

I'd have to look this up, but I believe SQL Server will choke on itself if you go more than 32 levels deep. But as everyone else has said, you really have to try it out.

Personally, I don't think it would be that bad to make some recursive calls.
# March 9, 2004 8:03 PM

Phil Scott said:

Just checked it out: by creating a simple stored procedure that just calls itself a bunch
Server: Msg 217, Level 16, State 1, Procedure Recursive, Line 6
Maximum stored procedure, function, trigger, or view nesting level exceeded (limit 32).
# March 9, 2004 8:08 PM

Phil Scott said:

Ok, now I look like a stalker. Something that I would try to do is simply build a list of the appropriate AlbumID's using recursive calls. This shouldn't be very resource intensive at all. Even if someone goes bonkers and creates a nesting 6 or 7 level deeps, you could bounce through that list in no time.

Then use the exec statement to do something like 'SELECT COUNT(*) FROM Album WHERE AlbumID IN (" + AlbumIdList + ')'
# March 9, 2004 8:17 PM

Jesse Ezell said:

http://weblogs.asp.net/jezell/archive/2004/03/10/87010.aspx
# March 9, 2004 10:42 PM

Frans Bouma said:

Store your trees in a more SQL friendlier way. See this posting of Joe Celko: (google groups, made it shorter using tinyurl)

http://tinyurl.com/2abk7

You can then read all albums in a tree in 1 SQL statement and thus do the calculations in 1 go.

Recursive procs are not going to work, a temptable is very slow compared to a table variable. You can also consider a couple of triggers which manage your count field.
# March 10, 2004 3:39 AM

Ken Robertson said:

Thanks for the article, Frans! I'll look into implementing this with nGallery in the next revision (we're currently in a code freeze getting ready to release). This is exactly what I needed for reordering an organizational chart table at work.

For nGallery, I ended up implementing it using a stored procedure that calls a recursive used defined function that gets all of the totals and adds them up. It works fairly well. I didn't want to make any structural changes since we are very close to a release and this was the last thing on my todo list. In the next version, I think I might look into reordering the table structure.
# March 10, 2004 2:07 PM

TrackBack said:

# March 10, 2004 5:04 PM

TrackBack said:

# March 20, 2004 11:46 AM

Sky said:

I came across your question via Ken Robertson's blog page at http://weblogs.asp.net/jezell/archive/2004/03/10/87010.aspx#111012 where I posted a summary of the different techniques that I have come across for dealing with recursion. Since you mentioned Celko's, thought I might post that there is a variation known as Farrady(sp?) Fractals. Looks interesting since it solves some of the update mess of Celko's.

Cheers!

PS: Celko's solution was a bit of a downer for me. At first blush it looked great. But then realized it is best suited for FEW updates: I've clocked sqlserver doing about 1000 straight updates per second, and for a decent tree, that's not very many nodes... -- and don't forget that you have to freeze the whole table for the update -- effectively blocking out usage of it until done.

Then again, as I write this, it just dawned on me that that one could do that in a temp table, and then replace the original, although I didn't try that when I was messing around with the theory. Hum. Maybe it aint so bad after all !
# April 10, 2004 7:45 PM

TrackBack said:

# April 27, 2004 6:56 PM

TrackBack said:

# April 27, 2004 7:01 PM

rajgangina said:

USe Temptable it is better
# May 27, 2004 8:06 AM

s said:

s
# June 13, 2004 10:17 AM

marklar said:

replace the entire tree with a cached scalar table! sounds processor intensive.  (in reply to modifying celko's adjacency list design)

recursion is limited to 32 levels, but alot of hierarchies don't exceed this extent.

# September 12, 2008 2:58 PM

marklar said:

woops nested set.  no edit.

# September 12, 2008 3:01 PM

Daddy53 said:

Ottawa Tribe of Oklahoma v. ,

# October 22, 2009 8:54 PM
Leave a Comment

(required) 

(required) 

(optional)

(required)