In the previous lab we discussed the limitation of a recursive stored procedure. You cannot perform recursion for more than 32 levels. I promised that in the next post, I will show you a new version of the stored procedure that works for more than 32 levels. Before I jump into that, I would like to present a solution to process cases where more than 32 levels of recursion is needed.
I am still experimenting with this solution. I will be glad to hear your comments on this.
The solution that I am trying to present uses a WHILE loop that runs on top of a stack-like table. A table variable is used to mimic the stack and that gives the capability of performing unlimited levels of recursion.
Before we look at the solution, let us create some sample data. I would like to take the same example we saw in the previous lab, but add an additional 32 levels under the 'books' category.
IF OBJECT_ID('Categories') IS NOT NULL
DROP TABLE Categories
GO
CREATE TABLE Categories (
CategoryID INT,
CategoryName VARCHAR(20),
ParentID INT, ItemCount INT)
GO
INSERT INTO Categories (
CategoryID,
CategoryName,
ParentID)
SELECT 1, 'Books', NULL UNION ALL
SELECT 3, 'Computers', 1 UNION ALL
SELECT 16, 'Computers2', 3 UNION ALL
SELECT 17, 'Computers3', 16 UNION ALL
SELECT 18, 'Computers4', 17 UNION ALL
SELECT 19, 'Computers5', 18 UNION ALL
SELECT 20, 'Computers6', 19 UNION ALL
SELECT 21, 'Computers7', 20 UNION ALL
SELECT 22, 'Computers8', 21 UNION ALL
SELECT 23, 'Computers9', 22 UNION ALL
SELECT 24, 'Computers10', 23 UNION ALL
SELECT 25, 'Computers11', 24 UNION ALL
SELECT 26, 'Computers12', 25 UNION ALL
SELECT 27, 'Computers13', 26 UNION ALL
SELECT 28, 'Computers14', 27 UNION ALL
SELECT 29, 'Computers15', 28 UNION ALL
SELECT 30, 'Computers16', 29 UNION ALL
SELECT 31, 'Computers17', 30 UNION ALL
SELECT 32, 'Computers18', 31 UNION ALL
SELECT 33, 'Computers19', 32 UNION ALL
SELECT 34, 'Computers20', 33 UNION ALL
SELECT 35, 'Computers21', 34 UNION ALL
SELECT 36, 'Computers22', 35 UNION ALL
SELECT 37, 'Computers23', 36 UNION ALL
SELECT 38, 'Computers24', 37 UNION ALL
SELECT 39, 'Computers25', 38 UNION ALL
SELECT 40, 'Computers26', 39 UNION ALL
SELECT 41, 'Computers27', 40 UNION ALL
SELECT 42, 'Computers28', 41 UNION ALL
SELECT 43, 'Computers29', 42 UNION ALL
SELECT 44, 'Computers30', 43 UNION ALL
SELECT 45, 'Computers31', 44 UNION ALL
SELECT 5, 'SQL Server', 45 UNION ALL
SELECT 7, 'TSQL Programming', 5 UNION ALL
SELECT 8, 'Performance Tuning', 5 UNION ALL
SELECT 9, 'SSRS', 5 UNION ALL
SELECT 10, 'SSIS', 5 UNION ALL
SELECT 6, 'ASP.NET', 3 UNION ALL
SELECT 4, 'Fiction', 1 UNION ALL
SELECT 2, 'Software', NULL UNION ALL
SELECT 11, 'Tools and Utilities', 2 UNION ALL
SELECT 12, 'Games', 2 UNION ALL
SELECT 13, 'XBox 360', 12 UNION ALL
SELECT 14, 'Windows XP', 12 UNION ALL
SELECT 15, 'Windows Vista', 12
This is how the hierarchy of these categories look like.
/*
Books
Computers
ASP.NET
Computers2
Computers3
Computers4
Computers5
Computers6
Computers7
Computers8
Computers9
Computers10
Computers11
Computers12
Computers13
Computers14
Computers15
Computers16
Computers17
Computers18
Computers19
Computers20
Computers21
Computers22
Computers23
Computers24
Computers25
Computers26
Computers27
Computers28
Computers29
Computers30
Computers31
SQL Server
TSQL Programming
Performance Tuning
SSRS
SSIS
Fiction
Software
Tools and Utilities
Games
XBox 360
Windows XP
Windows Vista
*/
To make sure that SQL Server generates an error after 32 levels of recursion, lets run the following code. [You need the scripts in the previous lab to run this]
EXECUTE UpdateItemCount @Debug = 1
/*
Msg 217, Level 16, State 1, Procedure
RecursiveUpdateItemCount, Line 68
Maximum stored procedure, function,
trigger, or view nesting level exceeded (limit 32).
*/
Now, let us see the script that generates a recursive tree of these categories using the approach this lab presents. The code below does nothing, but just generate a column that counts the level of each category in the hierarchy. We will use this code in the next lab, where we will write an update procedure to update the item count of categories beyond 32 levels.
-- Silence please....
SET NOCOUNT ON
-- --------------------------------------------------------------
-- Let us generate the category relationship chain using
-- a custom logic. We will use a memory table as a custom-stack
-- --------------------------------------------------------------
-- stack table
DECLARE @stack TABLE (
AutoID INT IDENTITY,
lvl INT,
CategoryID int,
ParentID INT)
-- output table
DECLARE @output TABLE(
lvl INT,
CategoryID INT,
ParentID INT)
-- Populate the output table with root level categories
INSERT INTO @output (lvl, CategoryID, ParentID)
SELECT 0, CategoryID, ParentID
FROM Categories
WHERE ParentID IS NULL
-- Populate the stack table with root level categories
INSERT INTO @stack (lvl, CategoryID, ParentID)
SELECT 0, CategoryID, ParentID
FROM Categories
WHERE ParentID IS NULL
-- Generate the category relationship chain
DECLARE @id INT, @lvl INT
WHILE EXISTS(SELECT * FROM @stack) BEGIN
-- take the last row from the stack
SELECT TOP 1
@id = CategoryID,
@lvl = lvl
FROM @stack
ORDER BY AutoID DESC
-- delete the row from stack
DELETE FROM @stack WHERE CategoryID = @id
-- process matching rows and insert to output
INSERT INTO @output (lvl, CategoryID, ParentID)
SELECT @lvl + 1, CategoryID, ParentID
FROM Categories
WHERE ParentID = @id
-- add to stack too.
INSERT INTO @stack (lvl, CategoryID, ParentID)
SELECT @lvl + 1, CategoryID, ParentID
FROM Categories
WHERE ParentID = @id
END
-- --------------------------------------------------------------
-- The memory table @output has the relationship hierarchy
-- Let us print the information.
-- --------------------------------------------------------------
SELECT
o.lvl AS Level,
REPLICATE(' ', lvl * 1) + c.CategoryName
FROM Categories c
INNER JOIN @output o ON o.CategoryID = c.CategoryID
/*
OUTPUT:
Level CategoryName
----------- ------------------------------------------------------------
0 Books
1 Computers
2 Computers2
3 Computers3
4 Computers4
5 Computers5
6 Computers6
7 Computers7
8 Computers8
9 Computers9
10 Computers10
11 Computers11
12 Computers12
13 Computers13
14 Computers14
15 Computers15
16 Computers16
17 Computers17
18 Computers18
19 Computers19
20 Computers20
21 Computers21
22 Computers22
23 Computers23
24 Computers24
25 Computers25
26 Computers26
27 Computers27
28 Computers28
29 Computers29
30 Computers30
31 Computers31
32 SQL Server
33 TSQL Programming
33 Performance Tuning
33 SSRS
33 SSIS
2 ASP.NET
1 Fiction
0 Software
1 Tools and Utilities
1 Games
2 XBox 360
2 Windows XP
2 Windows Vista
*/
Well, we did not do anything other than generating the level of each category in the chain. In the next lab, I we will use this logic to update the item count of categories recursively.
SEE ALSO
- TSQL Lab 10 - Performing recursive updates in SQL Server
- TSQL Lab 11 - Writing a recursive procedure to update the count of child items under each parent category
- TSQL Lab 12 - Writing a recursive procedure to handle more than 32 levels
- TSQL Lab 14 - Performing a recursive update for more than 32 levels
- TSQL Lab 18 - Performing Recursive Updates using CTE
- TSQL Lab 20 - Performing recursive updates using a BOTTOM to TOP recursive CTE