order of recursion in stored procedure

[Dan]

I've encountered some strange behavior in a recursive procedure I'm
writing for a bill of materials. First let me ask directly if what I
think is happening is even possible:

It seems like the procedure is not following the recursion in serial
order, but in parallel. In other words, after one instance of the
procedure calls itself, it continues executing lines below the
recursion before the recursion is done. Is that possible? I looked
for SQL Server Options that might deal with recursion or threading but
I couldn't find anything.

Now let me explain what's happening in terms of the BoM. All the rows
I expect are returned, but not in the correct order. Let's assume the
following tree:

1
|-2
| |-5
| | |-7
| | \-8
| \-6
| \-9
|-3
| |-10
| |-11
| | |-13
| | \-14
| | |-15
| | |-16
| | \-17
| \-12
| \-18
| \-19
| \-20
| |-21
| \-22
\-4
\-23
|-24
\-25
\-26

This is stored in table P using MemberID and ParentID fields. For
example,

MemberID ParentID
-------- --------
1 NULL
2 1
3 1
4 1
5 2
6 2
(etc...)

Based on how I wrote the recursion (I will provide the procedure
below), I would expect output when starting from MemberID of 1 to look
like this:

MemberID Depth Sort
-------- ----- ----
2 1 1
5 2 2
7 3 3
8 3 4
6 2 5
9 3 6
(etc... basically, the line order of the graphical tree above, or a
counter-clockwise traverse around the tree)

Instead, I get this (I'll provide the whole thing because I don't see
a pattern):

MemberID Depth Sort
-------- ----- ----
2 1 1
5 2 2
3 1 2
10 2 3
7 3 3
4 1 3
6 2 3
9 3 4
23 2 4
8 3 4
11 2 4
13 3 5
12 2 5
24 3 5
25 3 6
18 3 6
14 3 6
15 4 7
19 4 7
26 4 7
20 5 8
16 4 8
17 4 9
21 6 9
22 6 10

Call me crazy, but it looks like my tree was parsed in the same order
that a set of dominos arranged in the same shape would topple. The
only way I could see that happening is if the recursion is non-linear,
allowing both children and siblings to be parsed simultaneously. It
would also explain why my sort counter didn't increment properly, but
the depth counter is always correct.

Now here are the procedures. There's also a Qty column, since this is
a BoM after all, but I didn't need to mention it for my illustration
of the problem above.

CREATE PROC makebom @root bigint
--
-- This would be called by the client to find all the parts and
quantities
-- under a specific part (@root)
--
AS
SET NOCOUNT ON
CREATE TABLE #result (MemberID bigint, Qty bigint, Depth bigint, sort
bigint)
EXEC bomrecurse @root, 1, 0
SET NOCOUNT OFF
SELECT MemberID, Qty, Depth, sort FROM #result ORDER BY sort
GO

CREATE PROC bomrecurse @root bigint, @depthcounter bigint,
@sortcounter bigint
--
-- This is the recursive procedure, called once by makebom, but
recalling
-- itself until the whole tree is parsed, filling the #result table
--
AS

DECLARE @memberid bigint, @qty bigint, @nextdepth bigint

DECLARE children_cursor CURSOR LOCAL FOR
SELECT MemberID, Qty FROM P
WHERE ParentID = @root
ORDER BY MemberID

OPEN children_cursor

FETCH NEXT FROM children_cursor
INTO @memberid, @qty

WHILE @@FETCH_STATUS = 0
BEGIN
SET @sortcounter = @sortcounter + 1
INSERT INTO #result VALUES (@memberid, @qty, @depthcounter,
@sortcounter)

SET @nextdepth = @depthcounter + 1
EXEC bomrecurse @memberid, @nextdepth, @sortcounter

FETCH NEXT FROM children_cursor
INTO @memberid, @qty
END

CLOSE children_cursor
DEALLOCATE children_cursor

GO
I'm surprised this even worked as well as it did because I'm a newbie
when it comes to stored procedures and I put this together from
examples I found around this group, online and in the T-SQL Help. So
feel free to comment on other aspects of my code or approach, but I'm
most interested in understanding the behavior of this recursion.

[Erland Sommarskog]

Dan (th*******@gmai l.com) writes:

I've encountered some strange behavior in a recursive procedure I'm
writing for a bill of materials. First let me ask directly if what I
think is happening is even possible:

It seems like the procedure is not following the recursion in serial
order, but in parallel. In other words, after one instance of the
procedure calls itself, it continues executing lines below the
recursion before the recursion is done. Is that possible?
No, it is not.

You included the code to your procedures, but unfortunately you did
not include any CREATE TABLE statements or INSERT statements with
sample data. (Thus, I would have to type those myself, and I am lazy.)

Then again, there is something in your code that I don't understand:
CREATE PROC bomrecurse @root bigint, @depthcounter bigint,
@sortcounter bigint
...
DECLARE children_cursor CURSOR LOCAL FOR
SELECT MemberID, Qty FROM P
WHERE ParentID = @root
ORDER BY MemberID

OPEN children_cursor

FETCH NEXT FROM children_cursor
INTO @memberid, @qty

WHILE @@FETCH_STATUS = 0
BEGIN
SET @sortcounter = @sortcounter + 1
INSERT INTO #result VALUES (@memberid, @qty, @depthcounter,
@sortcounter)

SET @nextdepth = @depthcounter + 1
EXEC bomrecurse @memberid, @nextdepth, @sortcounter

Say that you have a simple tree of two nodes A and B, which both have four
children that are leaf nodes. When you start with A, @sortcounter is 0,
which you increment and insert 1 into the table. Then you recurse, for
the four children you insert the values 2, 3, 4 and 5. Then you come back,
and for the B you insert 2 into #result and then 3, 4, 5 and 6 into
#result. It may be the late hour over here, but I don't really see what
the purpose might be with this. If I guess, shouldn't you make @sortcounter
an OUTPUT parameter, so that you get the value back from the recursion?

(Note that you need to specify OUTPUT both in CREATE PROCEDURE and in the
EXEC statement.)
--
Erland Sommarskog, SQL Server MVP, es****@sommarsk og.se

Books Online for SQL Server SP3 at
http://www.microsoft.com/sql/techinf...2000/books.asp

[Dan]

On Mon, 9 Aug 2004 22:31:52 +0000 (UTC), Erland Sommarskog
<es****@sommars kog.se> wrote:

You included the code to your procedures, but unfortunately you did
not include any CREATE TABLE statements or INSERT statements with
sample data. (Thus, I would have to type those myself, and I am lazy.)
I would have if I knew how to generate the INSERT with sample data.
(Have the server generate it, I mean. I'm not typing it all myself
either!) I could do the CREATE TABLE statement but without the data
that's rather useless.

CREATE PROC bomrecurse @root bigint, @depthcounter bigint,
@sortcounter bigint
...
DECLARE children_cursor CURSOR LOCAL FOR
SELECT MemberID, Qty FROM P
WHERE ParentID = @root
ORDER BY MemberID

OPEN children_cursor

FETCH NEXT FROM children_cursor
INTO @memberid, @qty

WHILE @@FETCH_STATUS = 0
BEGIN
SET @sortcounter = @sortcounter + 1
INSERT INTO #result VALUES (@memberid, @qty, @depthcounter,
@sortcounter)

SET @nextdepth = @depthcounter + 1
EXEC bomrecurse @memberid, @nextdepth, @sortcounter

Say that you have a simple tree of two nodes A and B, which both have four
children that are leaf nodes. When you start with A, @sortcounter is 0,
which you increment and insert 1 into the table. Then you recurse, for
the four children you insert the values 2, 3, 4 and 5. Then you come back,
and for the B you insert 2 into #result and then 3, 4, 5 and 6 into
#result. It may be the late hour over here, but I don't really see what
the purpose might be with this.

Good eye. My intent was to simply give each row a "sort" value equal
to its row number in the result table. This is unnecessary if the end
client doesn't REsort it, but I didn't wan to count on that. You're
right - it won't work as I wrote it.
If I guess, shouldn't you make @sortcounter
an OUTPUT parameter, so that you get the value back from the recursion?

(Note that you need to specify OUTPUT both in CREATE PROCEDURE and in the
EXEC statement.)

That sounds like the way to do it - thanks.

Still no idea why the tree is being parsed like dominos though?

[Dan]

Dan <th*******@goog le.com> wrote in message news:<s3******* *************** **********@4ax. com>...

On Mon, 9 Aug 2004 22:31:52 +0000 (UTC), Erland Sommarskog
<es****@sommars kog.se> wrote:

If I guess, shouldn't you make @sortcounter
an OUTPUT parameter, so that you get the value back from the recursion?

(Note that you need to specify OUTPUT both in CREATE PROCEDURE and in the
EXEC statement.)

That sounds like the way to do it - thanks.

Still no idea why the tree is being parsed like dominos though?

Nevermind. I suddenly see the light. :) The loss of @sortcounter's
value when it stepped out of recursion was what caused not only the
duplicate values but subsequently the apparent domino-order parsing.
I would've seen this sooner if I hadn't sorted by @sortcounter's
column.

Making the @sortcounter an OUTPUT parameter solved everything.
Thanks!

[Erland Sommarskog]

Dan (th*******@goog le.com) writes:

I would have if I knew how to generate the INSERT with sample data.
(Have the server generate it, I mean. I'm not typing it all myself
either!)

This is moot point now, since you were able to resolve your problem, but
permit me to point out that for this case an example of 10 rows should
probably do, which should not be a problem for you type if you were
interesting in getting assistance with the problem.

If you would need to script out many rows for some reason, there is
no builtin tool for this in SQL Server, however SQL Server MVP Vyas
Kondreddi has a nifty utility for this on his site,
http://vyaskn.tripod.com/code.htm#inserts
--
Erland Sommarskog, SQL Server MVP, es****@sommarsk og.se

Books Online for SQL Server SP3 at
http://www.microsoft.com/sql/techinf...2000/books.asp