Search code examples
sqlsql-servert-sqlnested-sets

Materializing the path of Nested Set hierarchy in T-SQL


I have a table containing details on my company's chart of accounts - this data is essentially stored in nested sets (on SQL Server 2014), with each record having a left and right anchor - there are no Parent IDs.

Sample Data:

ID  LeftAnchor  RightAnchor  Name     
 1           0           25  Root     
 2           1           16  Group 1  
 3           2            9  Group 1.1
 4           3            4  Account 1
 5           5            6  Account 2
 6           7            8  Account 3
 7          10           15  Group 1.2
 8          11           12  Account 4
 9          13           14  Account 5
10          17           24  Group 2  
11          18           23  Group 2.1
12          19           20  Account 1
13          21           22  Account 1

I need to materialize the path for each record, so that my output looks like this:

ID  LeftAnchor  RightAnchor  Name       MaterializedPath
 1           0           25  Root       Root
 2           1           16  Group 1    Root > Group 1
 3           2            9  Group 1.1  Root > Group 1 > Group 1.1
 4           3            4  Account 1  Root > Group 1 > Group 1.1 > Account 1
 5           5            6  Account 2  Root > Group 1 > Group 1.1 > Account 2
 6           7            8  Account 3  Root > Group 1 > Group 1.1 > Account 3
 7          10           15  Group 1.2  Root > Group 1 > Group 1.2
 8          11           12  Account 4  Root > Group 1 > Group 1.2 > Acount 4
 9          13           14  Account 5  Root > Group 1 > Group 1.2 > Account 5
10          17           24  Group 2    Root > Group 2
11          18           23  Group 2.1  Root > Group 2 > Group 2.1
12          19           20  Account 1  Root > Group 2 > Group 2.1 > Account 10
13          21           22  Account 1  Root > Group 2 > Group 2.1 > Account 11

Whilst I've managed to achieve this using CTEs, the query is deathly slow. It takes just shy of two minutes to run with around 1200 records in the output.

Here's a simplified version of my code:

;with accounts as
(
    -- Chart of Accounts
    select AccountId, LeftAnchor, RightAnchor, Name
    from ChartOfAccounts
    -- dirty great where clause snipped
)
, parents as
(
    -- Work out the Parent Nodes
    select c.AccountId, p.AccountId [ParentId]
    from accounts c
    left join accounts p on (p.LeftAnchor = (
        select max(i.LeftAnchor)
        from accounts i
        where i.LeftAnchor<c.LeftAnchor
        and i.RightAnchor>c.RightAnchor
    ))
)
, path as
(
    -- Calculate the Account path for each node

    -- Root Node
    select c.AccountId, c.LeftAnchor, c.RightAnchor, 0 [Level], convert(varchar(max), c.name) [MaterializedPath]
    from accounts c
    where c.LeftAnchor = (select min(LeftAnchor) from chart)

    union all

    -- Children
    select n.AccountId, n.LeftAnchor, n.RightAnchor, p.level+1, p.path + ' > ' + n.name
    from accounts n
    inner join parents x on (n.AccountId=x.AccountId)
    inner join path p on (x.ParentId=p.AccountId)
)
select * from path order by LeftAnchor

Ideally this query should only take a couple of seconds (max) to run. I can't make any changes to the database itself (read-only connection), so can anyone come up with a better way to write this query?


Solution

  • After your comments, I realized no need for the CTE... you already have the range keys.

    Example

    Select A.*
          ,Path = Replace(Path,'&gt;','>')
     From YourTable A
     Cross Apply (
                    Select Path = Stuff((Select ' > ' +Name 
                                          From (
                                                Select LeftAnchor,Name
                                                 From  YourTable
                                                 Where A.LeftAnchor between LeftAnchor and RightAnchor 
                                               ) B1
                                          Order By LeftAnchor
                                          For XML Path (''))
                                        ,1,6,'')
                 ) B
     Order By LeftAnchor
    

    Returns

    enter image description here