How do you get all ancestors of a node using SQL Server 2008 hierarchyid?

Question

Given a table with a hierarchyid type column, how do you write a query to return all rows that are ancestors of a specific node?

There is an IsDescendantOf() function, which is perfect for getting the children, but there's no corresponding IsAncestorOf() function to return ancestors (and the absence of a GetAncestors() function seems like quite an oversight.)

Stephanestephani

Isn't child.IsDescendantOf(parent) the same as parent.IsAncestorOf(child)? – Pushcart

@Pushcart Yes, if IsAncestorOf(node) had existed, they would be equivalent. No need for recursive queries for this. – Outspeak

Answer 1

The most commonly used approach would be a recursive Common Table Expression (CTE)

WITH Ancestors(Id, [Name], AncestorId) AS
(
      SELECT
            Id, [Name], Id.GetAncestor(1)
      FROM
            dbo.HierarchyTable
      WHERE
            Name = 'Joe Blow'  -- or whatever you need to select that node

      UNION ALL

      SELECT
            ht.Id, ht.[Name], ht.Id.GetAncestor(1)
      FROM
            dbo.HierarchyTable ht
      INNER JOIN 
            Ancestors a ON ht.Id = a.AncestorId
)
SELECT *, Id.ToString() FROM Ancestors

(adapted from a Simon Ince blog post)

Simon Ince also proposes a second approach where he just basically reverses the condition - instead of detecting those person entries that are an ancestor of the target person, he turns the check around:

DECLARE @person hierarchyid

SELECT @person = Id
FROM dbo.HierachyTable
WHERE [Name] = 'Joe Blow';

SELECT
    Id, Id.ToString() AS [Path], 
    Id.GetLevel() AS [Level],
    Id.GetAncestor(1),
    Name
FROM 
    dbo.HierarchyTable
WHERE 
    @person.IsDescendantOf(Id) = 1

This will select all the rows from your table, where the target person you're interested in is a descendant of - any level down the hierarchy. So this will find that target person's immediate and non-immediate ancestors all the way up to the root.

Branum

In that blogpost, isn't this CTE solution then followed by a simpler one ("This works fine, but is it the optimum way of achieving it? Nope. Let’s try again!") ? – Goren

@AakashM: yes, there is a second option, indeed - not one that I would probably use, but it will work, too, from the looks of it. – Branum

I know this is very old, but I write this for future readers: The method from "Simon Ince blog post" is nearly 100 times slower than the "CTE" method when the execution plan doesn't exist. – Alcaide

Yup @Achilles, it is probably because the query becomes non-sargable when you apply IsDescendantOf function to ID of every row. I am always getting an index scan with the query. The recursive CTE seems to be a much better option. – Imperium

Answer 2

Declare @hid hierarchyid=0x5D10 -- Child hierarchy id

SELECT
*
FROM 
  dbo.TableName
WHERE 
  @hid.IsDescendantOf(ParentHierarchyId) = 1

Unman

Even if you have an index on the hierarchyID, it will have to evaluate IsDesendentOf for every row, no? I think I have a better way (see my answer) – Palatine

Answer 3

I wrote a user-defined table-valued function that expands a hierarchyid value into its constituent ancestors. The output can then be joined back on the hierarchyid column to get those ancestors specifically.

alter function dbo.GetAllAncestors(@h hierarchyid, @ReturnSelf bit)
returns table
as return
 select @h.GetAncestor(n.Number) as h
 from dbo.Numbers as n
 where n.Number <= @h.GetLevel()
  or (@ReturnSelf = 1 and n.Number = 0)

 union all

 select @h
 where @ReturnSelf = 1
go

To go about using it:

select child.ID, parent.ID
from dbo.yourTable as child
cross apply dbo.GetAllAncestors(child.hid, 1) as a
join dbo.yourTable as parent
   on parent.hid = a.h

Palatine

please help me to solve this problem. #44016761 – Creep

I recently had to solve this problem and I believe this is the best solution offered here. The other solutions that pass a column reference into IsDescendantOf() have to resolve that predicate in the Query Executor and not the Storage Engine. If you have any amount of data, performance will be terrible. – Roscoeroscommon

I've since written aCLR function that does the same thing. – Palatine

I like how you think. I'm going to steal that idea. – Roscoeroscommon

Answer 4

Perfecting Ben Thui's answer which I find to be the best one so far...

The approach below allows to retrieve not only one but potentially several leaf rows and their ascendants in one single query.

Create Or Alter Function dbo.GetAllAncestors
(
    @Path       HierarchyId,
    @WithSelf   Bit = 1,
    @MinLevel   Int = 0,
    @MaxLevel   Int = Null
)
Returns Table
As
Return

With Ancestor As
(
    Select  @Path As Path
    Union All

    Select  Path.GetAncestor(1)
    From    Ancestor
    Where   Path.GetLevel() > 0
)

Select  Path, Path.GetLevel() As Level
From    Ancestor
Where   (@WithSelf = 1 Or Path <> @Path)
And     Path.GetLevel() >= Case When @MinLevel < 0 Or @MinLevel Is Null Then 0 Else @MinLevel End
And     (@MaxLevel Is Null Or Path.GetLevel() <= @MaxLevel)

To use:

-- This assumes the table has a Path HierarchyId colum, and the values are unique and indexed.

-- If you know the path
Select *
From MyTable
Where Path In
(
    Select Path From dbo.GetAllAncestors(@ThePath, Default, Default, Default)
)

-- If you don't know the path
Select *
From MyTable t1
Where Path In 
(
    Select Path
    From   MyTable t2
           Cross Apply dbo.GetAllAncestors(t2.Path, Default, Default, Default)
    Where  /* Find the leaf record(s) here.
              Note that if multiple rows match, they will all be returned as well as their parents in a single roundtrip. */
)

Homework

Answer 5

DECLARE @hid_Specific HIERARCHYID 
SET @hid_Specific = '/1/1/3/1/';

SELECT hrchy_id,* FROM tblHierarchyData 
WHERE PATINDEX(hrchy_id.ToString() + '%', @hid_Specific.ToString()) = 1

Desiccant

Could you please add an explanation to your solution? – Aeolus