Finding Top level parent of each row of a table [SQL Server 2008]

Question

I have following two tables

Table Person

Table RelationHierarchy

ParentId   CHildId
   2         1
   3         2
   4         3

This will form a tree like structure

ParentId and ChildId are foreign keys of Id column of Person Table

I need to write SQL that Can fetch me Top Level Parent i-e Root of Each Person.

Following CTE can do this for Each. I converted that to a Function and ran it for each row of Person. I have got about 3k rows in Person table and it takes about 10 Secs to do that. Can anyone suggest a approach that can take less. The Problem is the function that runs following CTE runs 3k times

DECLARE @childID INT 
SET @childID  = 1 --chield to search

;WITH RCTE AS
(
SELECT *, 1 AS Lvl FROM RelationHierarchy 
WHERE ChildID = @childID

UNION ALL

SELECT rh.*, Lvl+1 AS Lvl FROM dbo.RelationHierarchy rh
INNER JOIN RCTE rc ON rh.CHildId = rc.ParentId
 )
SELECT TOP 1 id, Name
FROM RCTE r
inner JOIN dbo.Person p ON p.id = r.ParentId
ORDER BY lvl DESC

Couldn't make this query run for each row of person table. Any help would be much appreciated — InTheWorldOfCodingApplications, Jul 17 '13 at 15:31
What i want is Top level parent of each Person and if parent Doesn't exist then NULL or PersonId — InTheWorldOfCodingApplications, Jul 17 '13 at 15:33
@user1711287 I have updated my answer in the original question - http://stackoverflow.com/questions/17676944/finding-a-top-level-parent-in-sql/17677469 — Nenad Zivkovic, Jul 17 '13 at 15:35

score 2 · Accepted Answer · edited May 23 '17 at 12:14

2

I have also updated the answer in the original question, but never-mind, here is a copy also:

;WITH RCTE AS
(
    SELECT  ParentId, ChildId, 1 AS Lvl FROM RelationHierarchy 

    UNION ALL

    SELECT rh.ParentId, rc.ChildId, Lvl+1 AS Lvl 
    FROM dbo.RelationHierarchy rh
    INNER JOIN RCTE rc ON rh.ChildId = rc.ParentId
)
,CTE_RN AS 
(
    SELECT *, ROW_NUMBER() OVER (PARTITION BY r.ChildID ORDER BY r.Lvl DESC) RN
    FROM RCTE r

)
SELECT pc.Id AS ChildID, pc.Name AS ChildName, r.ParentId, pp.Name AS ParentName
FROM dbo.Person pc 
LEFT JOIN CTE_RN r ON pc.id = r.CHildId AND  RN =1
LEFT JOIN dbo.Person pp ON pp.id = r.ParentId

SQLFiddle DEMO

Note that the slight difference is in recursive part of CTE. ChildID is now rewritten each time from the anchor part. Also addition is ROW_NUMBER() function (and new CTE) to get the top level for each child at the end.

EDIT - Version2

After finding a performance issues with first query, here is an improved version. Going from top-to-bottom, instead of other way around - eliminating creating of extra rows in CTE, should be much faster on high number of recursions:

;WITH RCTE AS
(
    SELECT  ParentId, CHildId, 1 AS Lvl FROM RelationHierarchy r1
    WHERE NOT EXISTS (SELECT * FROM RelationHierarchy r2 WHERE r2.CHildId = r1.ParentId)

    UNION ALL

    SELECT rc.ParentId, rh.CHildId, Lvl+1 AS Lvl 
    FROM dbo.RelationHierarchy rh
    INNER JOIN RCTE rc ON rc.CHildId = rh.ParentId
)
SELECT pc.Id AS ChildID, pc.Name AS ChildName, r.ParentId, pp.Name AS ParentName
FROM dbo.Person pc 
LEFT JOIN RCTE r ON pc.id = r.CHildId
LEFT JOIN dbo.Person pp ON pp.id = r.ParentId

SQLFiddle DEMO

edited May 23 '17 at 12:14

Community

1
1

answered Jul 17 '13 at 15:38

Nenad Zivkovic

18,221
6
42
55

Can we get All Persons regardless whether they have a Parent of Not. If Parent Exist then ParentId and ParentName will display it but it parent doesn't exist then it can be NULL. I am just wondering Can we do this in CTE or I should do a LEFT join Between Person and Result of this CTE? – InTheWorldOfCodingApplications Jul 17 '13 at 15:45
@user1711287 LEFT JOIN between Person and CTE - answer updated – Nenad Zivkovic Jul 17 '13 at 15:46
As soon as you get a tree more than 100 deep , the code bombs: http://sqlfiddle.com/#!6/2205e/1 – Petio Ivanov Jul 18 '13 at 19:51
@PetioIvanov: Hi, thanks for your testing. First, about that "bombing" - 100 is default max recursion for CTE (made to prevent infinite loops). If more than 100 recursions is needed it can be changed with a clause. `OPTION (MAXRECURSION 0)` at the end will set to unlimited. Second - that 10000 levels of hierarchy example is a bit strange - and unlikely in real data. Even a 10000 employees company will likely have no more then 5-6 level of hierarchy between CEO and lowest-ranked employees. And query should have no problem in that scenario. – Nenad Zivkovic Jul 19 '13 at 07:36
@PetioIvanov: And at the end, third, and most important - you are right, there was a flaw in the query, as it was creating to many rows in recursion (like Cartesian product) and selecting only a good ones at the end. http://sqlfiddle.com/#!6/2205e/3 - here is rewritten, fixed example, that can handle thousands of recursion in timely manner. I will update the answer also with other idea (going from top to bottom, instead the other way around). – Nenad Zivkovic Jul 19 '13 at 07:38

score 0 · Answer 2 · answered Jul 17 '13 at 16:12

You could try to use a loop. As you will get many levels of recursion with your approach:

declare @child int = 0
declare @parent int = 1 --child to search
while @child <> @parent 
BEGIN
set @child = @parent
select  @parent = Parentid from @parentchild  where ChildID = @child
END
select @parent

score 0 · Answer 3 · answered Jul 17 '13 at 16:46

Another way to do this in a loop if you wanted to work with sets is:

SELECT *
    INTO #parentchild
from RelationHierarchy 


WHILE EXISTS
(select 1 from  #parentchild A inner join #parentchild B on A.ChildID = B.ParentID Where A.ParentID <> B.ParentID )
BEGIN
update B set B.ParentID = A.ParentID
from #parentchild A inner join #parentchild B on A.ChildID = B.ParentID
END

select * from #parentchild

Finding Top level parent of each row of a table [SQL Server 2008]

3 Answers3

Linked