T- SQL - How to get all descendants of a given element in a hierarchical table

• Download script - 1.24 KB

Introduction

It's common in an e-commerce website to retrieve all products from a given category, including all descendant categories. This article provides a T-SQL table valued function with a simple solution to this problem. We assume that categories are defined in a hierarchical table with a self referencing foreign key.

Using the code

First, we have to create the hierarchical table (in order to keep things simple, we use Name as the table key):

CREATE TABLE [dbo].[Category](
    [ParentName] [varchar](20) NULL,
    [Name] [varchar](20) NOT NULL,
 CONSTRAINT [PK_Category] PRIMARY KEY CLUSTERED 
(
    [Name] ASC
)
) ON [PRIMARY]

GO

ALTER TABLE [dbo].[Category]  ADD  
CONSTRAINT [FK_Category_Category] FOREIGN KEY([ParentName])
REFERENCES [dbo].[Category] ([Name])
GO

Then, we create a recursive Stored Procedure that we will use to populate the table with test data:

CREATE PROC spCreateChilds

@ParentName    varchar(20),
@BaseName        varchar(20),
@Level        integer,
@MaxDepth        integer,
@ChildNumber    integer
        
AS

IF @Level < @MaxDepth
 BEGIN

  DECLARE @I Integer

  SET @I = 1

  WHILE (@I < @ChildNumber AND @ParentName IS NOT NULL) OR @I = 1
   BEGIN

    INSERT INTO Category
    (Name, ParentName)
    VALUES        
    (ISNULL(@BaseName, '') + CASE WHEN 
          @BaseName IS NULL THEN '' ELSE '.' END  
          + CAST(@I as varchar), @ParentName)

    DECLARE @ExecParentName varchar(20)
    DECLARE @ExecBaseName varchar(20)
    DECLARE @ExecLevel int

    SET @ExecParentName = ISNULL(@BaseName, '') + 
         CASE WHEN @BaseName IS NULL 
     THEN '' ELSE '.' END  + CAST(@I as varchar)
    SET @ExecBaseName = ISNULL(@BaseName, '') 
         + CASE WHEN @BaseName IS NULL THEN '' ELSE '.' END  + 
         CAST(@I as varchar)
    SET @ExecLevel = @Level +1

    EXECUTE [dbo].[spCreateChilds] 
            @ExecParentName
           ,@ExecBaseName
           ,@ExecLevel
           ,@MaxDepth
           ,@ChildNumber

    SET @I = @I + 1

 END                
END

And, of course, we call it!

EXECUTE [dbo].[spCreateChilds] 
            NULL
           ,NULL
           ,1
           ,4  -- 4 hierarchical levels
           ,30 -- 30 childs per category

Now, our table is full of test data, it's time to define our functions.

The first function retrieves all the ancestors, and it's quite simple:

CREATE FUNCTION [dbo].[GetAscendantCategories] 
(    
    @CategoryName varchar(20)
)
RETURNS @Result TABLE  (Name varchar(20))
AS
    BEGIN

    WHILE @CategoryName IS NOT NULL
        BEGIN
            INSERT INTO @Result
            SELECT    @CategoryName
            
            SELECT     @CategoryName = ParentName
            FROM     dbo.Category
            WHERE   Name = @CategoryName
    
        END
    
    RETURN     
END

The second function is the one we will actually use. It retrieves all the descendants of a row:

CREATE FUNCTION [dbo].[GetDescendantCategories] 
(    
    @CategoryName varchar(20)
)
RETURNS @Result TABLE  (Name varchar(20))
AS
    BEGIN

    INSERT INTO @Result
    SELECT 
            Name
    FROM     
            dbo.Category C
    WHERE     @CategoryName in (
                       SELECT P.Name 
                       FROM GetAscendantCategories(C.Name) P)
    
    RETURN     
END

And now, we can test it, passing a test key!

SELECT * 
FROM [dbo].[GetDescendantCategories] ('1.2')

It's easy to use this function in product retrieval queries. Here's an example (let's suppose we have a table called Product with a field CategoryName and a foreign key from this field to the Category table):

SELECT *
FROM Product P
INNER JOIN [dbo].[GetDescendantCategories] ('1.2') C
ON P.CategoryKey = C.Name

Optimization

OK, that's cool, but I realized this solution is really very slow. It's much better if we use a common table expression. Here's the new function (thanks to Eddie de Bears):

CREATE FUNCTION [dbo].[GetDescendantCategories]
(
    @CategoryName varchar(20)
)
RETURNS @Result TABLE (Name varchar(20)) AS BEGIN


    WITH Result (Name)
    AS
    (
        SELECT Name
        FROM Category
        WHERE Name = @CategoryName
        UNION ALL
        SELECT C.Name FROM Category C
        INNER JOIN Result R ON C.ParentName = R.Name
    )
    INSERT INTO @Result
    SELECT Name
    FROM Result

    RETURN

END