How to traverse a path in a table with id & parent

Question

Suppose I have a table like:

id    |   parentId   |  name
 1          NULL         A
 2            1          B
 3            2          C
 4            1          E
 5            3          E

I am trying to write a scalar function I can call as:

SELECT dbo.GetId('A/B/C/E') which would produce "5" if we use the above reference table. The function would do the following steps:

1. Find the ID of 'A' which is 1
2. Find the ID of 'B' whose parent is 'A' (id:1) which would be id:2
3. Find the ID of 'C' whose parent is 'B' (id:2) which would be id:3
4. Find the ID of 'E' whose parent is 'C' (id:3) which would be id:5

I was trying to do it with a WHILE loop but it was getting very complicated very fast... Just thinking there must be a simple way to do this.

Answer 1

CTE version is not optimized way to get the hierarchical data. (Refer MSDN Blog)

You should do something like as mentioned below. It's tested for 10 millions of records and is 300 times faster than CTE version :)

Declare @table table(Id int, ParentId int, Name varchar(10))
insert into @table values(1,NULL,'A')
insert into @table values(2,1,'B')
insert into @table values(3,2,'C')
insert into @table values(4,1,'E')
insert into @table values(5,3,'E')

DECLARE @Counter tinyint = 0;

IF OBJECT_ID('TEMPDB..#ITEM') IS NOT NULL
DROP TABLE #ITEM

CREATE TABLE #ITEM
(
 ID int not null 
,ParentID int
,Name VARCHAR(MAX)
,lvl int not null
,RootID int not null
)

INSERT INTO #ITEM
    (ID,lvl,ParentID,Name,RootID)
SELECT   Id
        ,0 AS LVL
        ,ParentId
        ,Name
        ,Id AS RootID
FROM            
    @table
WHERE
        ISNULL(ParentId,-1) = -1

WHILE @@ROWCOUNT > 0
    BEGIN
        SET @Counter += 1
        insert into #ITEM(ID,ParentId,Name,lvl,RootID)
        SELECT  ci.ID
                ,ci.ParentId
                ,ci.Name
                ,@Counter as cntr
                ,ch.RootID
        FROM    
            @table AS ci
        INNER JOIN
            #ITEM AS pr 
        ON
            CI.ParentId=PR.ID
        LEFT OUTER JOIN
            #ITEM AS ch
        ON  ch.ID=pr.ID
        WHERE           
                ISNULL(ci.ParentId, -1) > 0
            AND PR.lvl = @Counter - 1
END

select * from #ITEM

Answer 2

Here is an example of functional rcte based on your sample data and requirements as I understand them.

if OBJECT_ID('tempdb..#Something') is not null
    drop table #Something

create table #Something
(
    id int
    , parentId int
    , name char(1)
)

insert #Something
select 1, NULL, 'A' union all
select 2, 1, 'B' union all
select 3, 2, 'C' union all
select 4, 1, 'E' union all
select 5, 3, 'E'

declare @Root char(1) = 'A';

with MyData as
(
    select *
    from #Something
    where name = @Root

    union all

    select s.*
    from #Something s
    join MyData d on d.id = s.parentId
)

select *
from MyData

Note that if you change the value of your variable the output will adjust. I would make this an inline table valued function.

Answer 3

I think I have it based on @SeanLange's recommendation to use a recursive CTE (above in the comments):

CREATE FUNCTION GetID 
(
    @path VARCHAR(MAX)
)

/* TEST:
SELECT dbo.GetID('A/B/C/E')

*/
RETURNS INT 
AS
BEGIN
    DECLARE @ID INT;

    WITH cte AS (
        SELECT p.id ,
               p.parentId ,
               CAST(p.name AS VARCHAR(MAX)) AS name
        FROM tblT p
        WHERE parentId IS NULL

        UNION ALL
        SELECT p.id ,
               p.parentId ,
               CAST(pcte.name + '/' + p.name AS VARCHAR(MAX)) AS name
        FROM dbo.tblT p
        INNER JOIN cte pcte ON
            pcte.id = p.parentId
    )
    SELECT @ID = id
    FROM cte
    WHERE name = @path

    RETURN @ID
END