sqlsql-servercommon-table-expressionrecursive-cte

Using recursive CTE to generate hierarchy results ordered by depth without the use of heiarchyid


I would like to query hierarchy results ordered by depth first without the use of SQL's heiarchyid built in function. Essentially, I am hoping to accomplish the depth ordering without any fancy functions.

I have provided a temp table below that contains these records:

Id p_Id order1 name1
1 null 1 josh
2 null 2 mary
3 null 3 george
4 1 1 joe
5 1 2 jeff
6 2 1 marg
7 2 2 moore
8 2 3 max
9 3 1 gal
10 3 2 guy
11 4 1 tod
12 4 2 ava
13 9 1 ron
14 9 2 bill
15 9 100 pat

where p_Id is the id of the parent record, and order1 is essentially just the ordering of which the depth first output should be displayed. To show why my query does not fully work, I made the order1 of the last record 100 instead of say, 3. However this should not ultimately matter since 100 and 3 both come after the previous order1 value, 2. An example of a correct result table is shown below:

Id p_Id order1 name1 Descendants
1 null 1 josh josh
4 1 1 joe josh/joe
11 4 1 tod josh/joe/tod
12 4 2 ava josh/joe/ava
5 1 2 jeff josh/jeff
2 null 2 mary mary
6 2 1 marg mary/marg
7 2 2 moore mary/moore
8 2 3 max mary/max
3 null 3 george george
9 3 1 gal george/gal
13 9 1 ron george/gal/ron
15 9 2 bill george/gal/bill
14 9 100 pat george/gal/pat
10 3 2 guy george/guy

Where an example of my results are shown below:

Id p_Id order1 name1 Descendants levels
1 null 1 josh josh .1
4 1 1 joe josh/joe .1.1
11 4 1 tod josh/joe/tod .1.1.1
12 4 2 ava josh/joe/ava .1.1.2
5 1 2 jeff josh/jeff .1.2
2 null 2 mary mary .2
6 2 1 marg mary/marg .2.1
7 2 2 moore mary/moore .2.2
8 2 3 max mary/max .2.3
3 null 3 george george .3
9 3 1 gal george/gal .3.1
13 9 1 ron george/gal/ron .3.1.1
15 9 100 pat george/gal/pat .3.1.100
14 9 2 bill george/gal/bill .3.1.2
10 3 2 guy george/guy .3.2

where I have created a levels column that essentially concatenates the order1 values and separates them with a period. This almost returns the correct results, but due to the fact that I am ordering by this string (of numbers and periods), the levels value of .3.1.100 will come before .3.1.2 , which is not what the desired output should look like. I am sure there is a different method to return the correct depth order. See below for the code that generates a temp table, and the code that I used to generate the incorrect output that I have so far.

if object_id('tempdb..#t1') is not null drop table #t1
CREATE TABLE #t1 (Id int, p_Id int, order1 int, name1 varchar(150))


INSERT into #t1 VALUES 
   (1, null, 1, 'josh'),
   (2, null, 2, 'mary'),
   (3, null, 3, 'george'),
   (4, 1, 1, 'joe'),
   (5, 1, 2, 'jeff'),
   (6, 2, 1, 'marg'),
   (7, 2, 2, 'moore'),
   (8, 2, 3, 'max'),
   (9, 3, 1, 'gal'),
   (10, 3, 2, 'guy'),
   (11, 4, 1, 'tod'),
   (12, 4, 2, 'ava'),
   (13, 9, 1, 'ron'),
   (14, 9, 2, 'bill'),
   (100, 9, 100, 'pat');

select * from #t1

-- Looking to generate heiarchy results ordered by depth --
; with structure as (

    -- Non-recursive term.
    -- Select the records where p_Id is null

    select  p.Id,
            p.p_Id,
            p.order1,
            p.name1,
            cast(p.name1 as varchar(64)) as Descendants,
            cast(concat('.', p.order1) as varchar(150)) as levels 
        from #t1 p 
        where p.p_Id is null

        union all

        -- Recursive term.
        -- Treat the records from previous iteration as parents.
        -- Stop when none of the current records have any further sub records.

        select  c.Id,
                c.p_Id,
                c.order1,
                c.name1,
                cast(concat(p.Descendants, '/', c.name1) as varchar(64)) as Descendants,
                cast(concat(p.levels, '.', c.order1) as varchar(150)) as levels
            from #t1 c                               -- c being the 'child' records
                inner join structure p                   -- p being the 'parent' records
                    on c.p_Id = p.Id

)

select  *
    from structure
    order by replace(levels, '.', '') asc

Solution

  • Take II. As pointed out by OP my original answer fails for more than 10 children. So what we can do (OP's suggestion) is pad the values out with zeros to a constant length. But what length? We need to take the largest number of children under a node and add this to the largest value or order, so for the example provided this is 100 + 3, and then take the length of that (3) and pad every order with zeros to 3 digits long. This means we will always be ordering as desired.

    declare @PadLength int = 0;
    
    select @PadLength = max(children)
    from (
        select len(convert(varchar(12),max(order1)+count(*))) children
        from #t1
        group by p_Id
    ) x;
    
    -- Looking to generate heiarchy results ordered by depth --
    with structure as (
        -- Non-recursive term
        -- Select the records where p_Id is null
        select
            p.Id [Id]
            , p.p_Id [ParentId]
            , p.order1 [OrderBy]
            , p.name1 [Name]
            , cast(p.name1 as varchar(64)) Descendants
            , concat('.', right(replicate('0',@Padlength) + convert(varchar(12),p.order1), @PadLength)) Levels
        from #t1 p 
        where p.p_Id is null
    
        union all
    
        -- Recursive term
        -- Treat the records from previous iteration as parents.
        -- Stop when none of the current records have any further sub records.
        select
            c.Id,
            c.p_Id,
            c.order1,
            c.name1,
            cast(concat(p.Descendants, '/', c.name1) as varchar(64)),
            concat(p.levels, '.', right(replicate('0',@Padlength) + convert(varchar(12),c.order1), @PadLength))
        from #t1 c -- c being the 'child' records
        inner join structure p on c.p_Id = p.Id -- p being the 'parent' records
    )
    select *
    from structure
    order by replace(levels, '.', '') asc;