How to traverse a path in a table with id & parentId?

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:

Find the ID of 'A' which is 1

Find the ID of 'B' whose parent is 'A' (id:1) which would be id:2

Find the ID of 'C' whose parent is 'B' (id:2) which would be id:3

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.

You should try to avoid using scalar function as much as possible. They are horribly inefficient. Even worse when you start throwing loops inside them. This sounds to me like a very typical recursive cte. Not really sure though why you would pass this a delimited list of names. — Sean Lange, May 12 '16 at 21:20
@SeanLange - thank you, am aware of the inefficiencies of a scalar function - this is just a requirement I have. — Denis, May 12 '16 at 21:23
Strange requirement but whatever. If you really want some help can you post some details? Is this a recursive query or are you just trying to parse a delimited list and do a query for each value? — Sean Lange, May 12 '16 at 21:28
A recursive query would be best here, but I don't understand your requirements. You input the value `'A/B/C/E/'` but you get out `5`. Why 5? — JNevill, May 12 '16 at 21:30
I think I understand now. You really need to simply pass in 'A', not the whole tree. Then let your recursive cte figure out the rest of the path. — Sean Lange, May 12 '16 at 21:32
@SeanLange That's what I was thinking. You pass in a single value and you get out the bottom node of the hierarchy. — JNevill, May 12 '16 at 21:33

score 3 · Answer 1 · answered May 13 '16 at 03:29

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

Denis · Accepted Answer · 2016-05-12T21:59:20.883

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

score 0 · Answer 3 · answered May 12 '16 at 21:38

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.

beat you to it by 3 minutes :-) Thanks for the tip! – Denis May 12 '16 at 22:03 — Denis, May 12 '16 at 22:03

How to traverse a path in a table with id & parentId?

3 Answers3

Linked