Materializing the path of Nested Set hierarchy in T-SQL

Question

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.LeftAnchorc.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?

Materializing the path of Nested Set hierarchy in T-SQL

3 Answers