Image of Navigational Map linked to Home / Contents / Search Recursing SQL Server

by Ross Mack - GUI Computing
Image of Line Break

Round and round and round she goes. Where she stops, that's where the recordset comes out.

SQL Server is an excellent tool. The more I work with it the more I like it. Particularly as I am currently working with SQL Server 7.0, the latest release which has impressed me at every turn. Well, except for the Stored Procedure editing screen which is just too small, but the Query Profiler (w/isql) is a better tool for that anyway, and certainly much better than in previous versions. I digress.

I continue to find things that I am able to do in SQL 7 that would have been impossible (or too darn annoying) to do in SQL 6.5. I try to not even think about my Oracle and Sybase days any more. In this article, I will demonstrate some code that illustrates how to write recursive stored procedures. Something that was virtually impossible under 6.5 (I say virtually, as there may have been a way to do it, but I never found it). To achieve this we use a few tricks and one or two new features that you may find interesting. So, here we go.

I won't try to describe the situation that arose in my project that required me to write a recursive stored procedure, I would need to fully understand it myself before I did that. So, here is a simplified version of what we were trying to achieve.

Imagine you have two tables: tblTree and tblItem. Essentially tblItem stores data about, well… Items. For the sake of the example we will simply say that it stores a simple varchar field that we are interested in, and an IDENTITY column. The purpose of tblTree is to store the relationships between Items. It has a tree structure, where each record in tblTree has a parent record also in tblTree. Let's have a look at the table layouts so we can better follow the code:

tblItem
FieldTypeDescription
ItemIDint (identity)Unique ID, simply a record identifier.
ItemNamevarchar(50)Just a string, this is the data we are actually interested in.
tblTree
FieldTypeDescription
TreeID int (identity) Unique ID, a record identifier
ItemID intForeign Key to tblItem, this indicates which Item any given node in the tree structure represented by tblTree refers to.
ParentTreeIDintWhere this node is a child of another node, this is the TreeID of the parent. Where the node has no parents it is 0 (zero).

So, this data basically gives us a Tree structure with pointers to data items elsewhere. Just like you would do it in code.

So, what we want to do is write a stored procedure that, when passed an ID returns the tree from that item downward. If we pass a zero, the whole tree is returned. Yes, this example is a little contrived, but it demonstrates the technique in a simple way that you can than apply to other situations.

This might be a good time to point out that you can download a complete SQL script to create the tables, populate them and create the stored procedure we will go through the process of creating.

Now, let's create the stored procedure, section by section and I will explain it as we go.

CREATE PROCEDURE sp_Recurse
(
@TopID int
)
AS
SET NOCOUNT ON

This is really just the header section of the stored procedure. We have named it specified that we take one int parameter and have set the NOCOUNT option on. The reason why I set NOCOUNT on is that it can cause trouble when returning data through the SQL Server Native OLEDB provider. The Parameter is to tell us which element of the tree to recurse down from.

IF (@@NESTLEVEL = 1)
   BEGIN
      -- There may be an old one if we crashed and burned...
      IF EXISTS(SELECT name FROM tempdb..sysobjects WHERE name like '##RecurseTemp%')
         DROP TABLE [##RecurseTemp]
      CREATE TABLE ##RecurseTemp (
         ItemID int NULL,
         ItemName varchar (50) NULL,
         NestLevel int
         )
   END
   

This next section does a couple of interesting things. First of all it uses the system variable @@NESTLEVEL to determine what level of call nesting we are in. Essentially this tells us what level we are at in the call stack, when you call a stored procedure directly from VB or w/isql or something it's @@NESTLEVEL will be 1, if that stored procedure, in turn, calls another the @@NESTLEVEL of that second stored procedure will be 2. This is, fairly obviously, an important thing to know when calling a recursive stored procedure. The way I use it here is to determine if we are at the top level of calls. If we are, then we need to create the temporary table that we will use to store the results that we want to eventually return. This one temporary table will be used throughout the recursion to store all the data that will eventually be returned. In this first instance we just need to create it. You will be pleased to know that SQL Server places a known elephant in Cairo - it will not allow @@NESTLEVEL to exceed 32, so you can recurse a maximum of 32 levels.

Because I have been bitten too many times I check to see if the table already exists. To explain how I do that lets go through some background information.

Firstly, when you create a temporary table within a stored procedure you can do it two ways (unless you want to have to manually drop it yourself some time). You can create the table so that it exists only for the life of the stored procedure (when the stored procedure finishes it is automatically deleted) by prefixing the name with a single #. Alternately, you can have the temporary table persist for the life of the connection in which the stored procedure is being called. You do that by prefixing the table name with ##. What this actually causes SQL Server to do is create a table in the temporary database (tempdb) with the name you specify and with some system generated stuff at the end. If you are particularly interested you can demonstrate this with the following stored procedure:

CREATE PROC spTempTest AS
   SET NOCOUNT ON
   CREATE TABLE #TempTest (objName varchar(255))
   -- This will include the REAL name of the temp table we just created.
   INSERT INTO #TempTest (objName) SELECT NAME FROM tempdb..sysobjects
   SELECT * FROM #TempTest
   RETURN

Because I don't know exactly what the table will be called, but I do know what its name will start with, I use the LIKE operator to check for the existence of the table by querying the system table, sysobjects, in the tempdb database. If I detect that the table exists, I use the DROP TABLE statement to get rid of it. You will notice that in this call as I am passing ##RecurseTemp directly in the SQL statement SQL Server decodes it to the correct name. In the EXISTS check it is passed as a varchar (string) argument and so is not automatically decoded, that is why the LIKE operator must be used. Once I have made sure our temporary table does not exist, I create it using a simple CREATE TABLE statement.


INSERT INTO ##RecurseTemp SELECT I.*, @@NESTLEVEL FROM tblItem I INNER JOIN tblTree T ON T.ItemID = I.ItemID WHERE T.TreeID = @TopID

In this next statement of the stored procedure I take care of selecting into the temporary table the data for the tree node that was passed to us using the TopID parameter. This gives us the first (and top) node of our traversal. I also select into the temporary table the system variable @@NESTLEVEL, which is discussed above, so as to better demonstrate in the resultant recordset how the recursion actually happens. Apart from that this is a pretty simple INSERT statement. It uses a join to the Item table to extract the data that represents this node and that's about it.

DECLARE @ChildID int

DECLARE curRecurse CURSOR LOCAL FOR SELECT TreeID FROM tblTree WHERE ParentTreeID = @TopID
OPEN curRecurse
FETCH NEXT FROM curRecurse INTO @ChildID
WHILE (@@FETCH_STATUS = 0)
   BEGIN
      EXEC sp_Recurse @ChildID
      FETCH NEXT FROM curRecurse INTO @ChildID
   END
CLOSE curRecurse
DEALLOCATE curRecurse

In this code we are opening a cursor (think of this as like an ADO recordset within a stored procedure) so that we can iterate through all the records that are children of the record identified by the @TopID parameter. To put that another way, now that we have added the parent element to the temporary table (above) we go through each of it's children and add them to the temporary table. We do this by extracting their IDs from the table and calling this same stored procedure with each of those IDs as the @TopID parameter. As we have seen above the first thing this will do is add that item to the table and then check for children and so on and so on. Almost chicken and egg style. Almost.

There is an interesting feature here that exists in SQL Server 7.0 and allows us to actually do the recursion thing. In previous versions of SQL Server whenever a cursor variable was declared it was allocated in the global namespace. This meant that the cursor could be declared in one stored procedure and then be accessed from another. It also meant that you had to ensure that you always closed and DEALLOCATED your cursors so that the next time you ran your stored procedure it will be able to declare a new cursor using that name. Of course, if you have a stored procedure that calls itself while looping through the records in a cursor this would not work. What happens is the cursor is declared and when the first record is fetched it is passed into the stored procedure which attempts to declare the cursor and dies as a cursor with that name already exists. SQL 7 introduces a new facility to be able to declare cursors within the global or local namespace. By default they are still declared globally (so that existing code does not break), but it is now possible to declare them so that they are purely local to the stored procedure using them. This is essential in this case as it allows this stored procedure to declare a cursor with the same name even when calling itself.

This is implemented by including the LOCAL keyword in the DECLARE CURSOR statement, as you can see above. There is extensive information on this new feature in the online help if you want more information.

Apart from all that all this section of code does is loop through the cursor until such time as the @@FETCH_STATUS system variable indicates that there are no more records (this is sort of like Recordset.EOF in ADO).

IF (@@NESTLEVEL = 1)
   BEGIN
      SELECT * FROM ##RecurseTemp
      DROP TABLE ##RecurseTemp
   END

RETURN

The very end of the stored procedure is simply designed to round off the finalisation of the recursing we have been doing. Just as with the start of the stored procedure we use the @@NESTLEVEL system variable to detect when we are back at the top of the call stack. If this is the case we issue a simple SELECT statement to return all the data we have been collecting in our temporary table. This returns the data as a recordset back to the calling process. Once that has been done, we simply delete the temporary table, as we no longer need it (until the next time this stored procedure is called). Then we just finish off the stored procedure with the ubiquitous RETURN statement. That's all there is to it.

It took me some time, experimentation and poring over documentation to work out how to achieve the effect of recursive stored procedures. I also learnt a bit about SQL 7.0 while I was doing that, and found it to be an interesting challenge. In terms of our application it allowed us to offload some significant processing to the server that would otherwise have meant significantly more network traffic or development of an additional DCOM component. Using this approach was far more efficient and maintainable. Perhaps this approach will also be useful to you sometime in the future, it certainly opens up some possibilities that were previously unavailable.



Written by: Ross Mack
February '99

Image of Arrow linked to Previous Article Image of Arrow linked to Next Article
Image of Line Break
[HOME] [TABLE OF CONTENTS] [SEARCH]