Efficient way to get ancestors - materialized path

Question

I have a hierarchical data structure stored using materialized paths.

Table:Files

node  parentNode  name    path
 100    NULL       f1     /f1/
 101    100        f2     /f1/f2/
 102    101        f3     /f1/f2/f3/

I have the node column as primary key(clustered)

Now if I want to find the ancestors of f3, given the path, I do something like this:

SELECT * FROM Files WHERE '/f1/f2/f3/' LIKE [path] + '%'

The problem with this is, the execution plan uses a clustered index scan( which I think SQL server defaults to for table scans)

Is there anyway I can find the ancestors of a node, given the path in a more efficient manner, preferably not using a CTE? I also have a depth column at my disposal if required.

Answer 1

If you have slow moving hierarchies, consider adding Range Keys. They facilitate navigation, filtration, and/or aggregration without the need of recursion.

The Range keys indicate ownership between X and Y. The range keys are especially helpful when dealing with large hierarchies (180K nodes).

The following is a simplified example, but may help.

Sample Hier Build

--Drop Table #MyHier

Declare @YourTable table (id int,ParentId  int,Name varchar(50))
Insert into @YourTable values 
 (11, NULL,'A')
,(12, 11   ,'B')
,(13, 12   ,'F')
,(14, 13   ,'C')
,(15, 13   ,'D')
,(16, 11   ,'E')
,(17, 12   ,'G')
,(18, NULL ,'M')
,(19, 18   ,'N')
,(20, 18   ,'O')
,(21, 20   ,'P')

Declare @Top    int         = null      --<<  Sets top of Hier Try 3 
Declare @Nest   varchar(25) = '|-----'  --<<  Optional: Added for readability

;with cteP as (
      Select Seq  = cast(10000+Row_Number() over (Order by Name) as varchar(500))
            ,ID
            ,ParentId 
            ,Lvl=1
            ,Name 
            ,Path = cast('/'+Name+'/' as varchar(500))
      From   @YourTable 
      Where  IsNull(@Top,-1) = case when @Top is null then isnull(ParentId ,-1) else ID end
      Union  All
      Select Seq  = cast(concat(p.Seq,'.',10000+Row_Number() over (Order by r.Name)) as varchar(500))
            ,r.ID
            ,r.ParentId 
            ,p.Lvl+1
            ,r.Name 
            ,cast(p.path + '/'+r.Name+'/' as varchar(500))
      From   @YourTable r
      Join   cteP p on r.ParentId  = p.ID)
     ,cteR1 as (Select *,R1=Row_Number() over (Order By Seq) From cteP)
     ,cteR2 as (Select A.ID,R2=Max(B.R1) From cteR1 A Join cteR1 B on (B.Seq like A.Seq+'%') Group By A.Seq,A.ID )
Select A.R1  
      ,B.R2
      ,A.ID
      ,A.ParentId 
      ,A.Lvl
      ,Name = Replicate(@Nest,A.Lvl-1) + A.Name
      ,Path
 Into  #MyHier
 From cteR1 A
 Join cteR2 B on A.ID=B.ID

Select Full Hier

-- Get The Full Hier
Select * 
 From #MyHier
 Order By R1

Returns

Get Ancestors

-- Get Ancestors of a Node
Declare @GetAncestors int = 15
Select A.* 
 From  #MyHier A
 Join  (Select R1 From #MyHier Where ID=@GetAncestors) B
   on  B.R1 between A.R1 and A.R2
 Order By A.R1

Returns

Select Descendants

-- Get Descendants of a Node
Declare @GetDesendants int = 12
Select A.* 
 From  #MyHier A
 Join  (Select R1,R2 From #MyHier Where ID=@GetDesendants) B
   on  A.R1 between B.R1 and B.R2
 Order By A.R1

Returns