Want to create a nested set in SQL Server?

Some time ago I found myself in the unenviable position of wanting to modify a table, which contained several thousand rows, to use a nested set. Having exhausted all of my usual research techniques to no avail, I then set about writing my own procedure to accomplish this mighty feat.

Then I got stuck. And frustrated. And bored. And it was nearly home time. So I bravely gave up and just used XML instead. Alas, my XML-based-system was time-consuming and heavy handed and I don't like XML, so I kept coming back to SQL in the hopes of finding an elegant solution.

For the purpose of this post, I'm going to assume you know what a nested set is and what it does. It may also be worth looking at SQL Server's hierarchyid stuff as an alternative to all this nested set stuff as (spoiler alert), my SQL procedure wasn't entirely elegant.

Anyway, let's get down to it. Imagine you have a table called MyTable that looks something like this:

Your first step is to create two additional columns, LeftLimit and RightLimit - both being nullable integers (again, I'm operating under the assumption that you know how to do this). So now our table looks like this:

So far, so good. Now here's your SQL:

USE [my_db]
GO
SET ANSI_NULLS ON
GO
SET QUOTED_IDENTIFIER ON
GO
CREATE PROCEDURE [dbo].[nest_things]

    @MyId int = 0

AS
BEGIN

    SET NOCOUNT ON;

    DECLARE @ParentId int, @LeftLimit int, @RightLimit int

    SET @ParentId = ISNULL((SELECT ParentId FROM MyTable WHERE MyId = @MyId), 0)

    SET @LeftLimit = (SELECT TOP 1 RightLimit FROM MyTable WHERE ParentID = @ParentId ORDER BY RightLimit DESC)

    IF @LeftLimit IS NULL
    BEGIN

        SET @LeftLimit = ISNULL((SELECT TOP 1 LeftLimit FROM MyTable WHERE MyId = @ParentId), 0)

    END

    SET @LeftLimit = @LeftLimit + 1
    SET @RightLimit = @LeftLimit + 1

    UPDATE
        MyTable
    SET
        LeftLimit = LeftLimit + 2
    WHERE
        LeftLimit >= @LeftLimit

    UPDATE
        MyTable
    SET
        RightLimit = RightLimit + 2
    WHERE
        RightLimit >= @LeftLimit

    UPDATE
        MyTable
    SET
        LeftLimit = @LeftLimit,
        RightLimit = @RightLimit
    WHERE
        MyId = @MyId

    IF EXISTS(SELECT MyId FROM MyTable WHERE ParentID = @MyId)
    BEGIN

        DECLARE @ChildId int
        WHILE(1 = 1)
        BEGIN

            SELECT TOP 1
                @ChildId = MyId
            FROM
                MyTable
            WHERE
                ParentID = @MyId
                AND LeftLimit IS NULL
            ORDER BY
                CatName

            IF @@ROWCOUNT = 0 BREAK;

            EXEC nest_Things @ChildId

        END

    END

END

Just execute the procedure that's created, passing your top-level Id as the parameter, and you've got your nested set. Job done! Though I guess I should explain what's happening here.

SET @ParentId = ISNULL((SELECT ParentId FROM MyTable WHERE MyId = @MyId), 0)

SET @LeftLimit = (SELECT TOP 1 RightLimit FROM MyTable WHERE ParentID = @ParentId ORDER BY RightLimit DESC)

IF @LeftLimit IS NULL
BEGIN

    SET @LeftLimit = ISNULL((SELECT TOP 1 LeftLimit FROM MyTable WHERE MyId = @ParentId), 0)

END

SET @LeftLimit = @LeftLimit + 1
SET @RightLimit = @LeftLimit + 1

For brevity's sake (and to avoid being patronising) I'll not explain our variable declarations. First, we grab the ParentId. Next we grab the highest RightLimit of the children of our shared parent. If there aren't any, we grab the LeftLimit of the Parent. If we don't have that, we just use 0 (zero). Then we add 1 to our new LeftLimit, since we don't want duplicates, and add 1 again for our new RightLimit.

UPDATE
    MyTable
SET
    LeftLimit = LeftLimit + 2
WHERE
    LeftLimit >= @LeftLimit

UPDATE
    MyTable
SET
    RightLimit = RightLimit + 2
WHERE
    RightLimit >= @LeftLimit

Now we're increasing the LeftLimit and RightLimit of every row that has a higher L/R Limit than our new ones.

UPDATE
    MyTable
SET
    LeftLimit = @LeftLimit,
    RightLimit = @RightLimit
WHERE
    MyId = @MyId

And now we've updated our current row with its new Limits. So far, so easy, right?

IF EXISTS(SELECT MyId FROM MyTable WHERE ParentID = @MyId)
BEGIN

    DECLARE @ChildId int
    WHILE(1 = 1)
    BEGIN

        SELECT TOP 1
            @ChildId = MyId
        FROM
            MyTable
        WHERE
            ParentID = @MyId
            AND LeftLimit IS NULL
        ORDER BY
            CatName

        IF @@ROWCOUNT = 0 BREAK;

        EXEC nest_Things @ChildId

    END

END

I know, I know. It's pretty horrible. So first we're checking to see if any children exist. Next we create a seemingly-infinite WHILE loop. Inside that loop, we select the first Child row of our current row (the one we just updated above). Then we check that we actually have a Child row, otherwise IF @@ROWCOUNT = 0 BREAK; will exit the seemingly-infinite WHILE loop. And if we do have a Child row, we execute the procedure again, but passing through the ChildId as a parameter. That way we loop through every row shuffling the Limit values around until every single row has a LeftLimit and RightLimit.

So that's our lot. It's not pretty but it works. It's not particularly fast or efficient either. On my last use it took roughly ninety seconds to run on a table of about 3,000 rows.

So, yeah. Use at your own risk.

Posted by Jake at 02/06/2015 09:39:21