Finding the end of a Relationship chain optimally

Question

I have a table that contains an id column, a parent column, and it's child column. So for every record, I know what record comes before it and what will come after it in a chain relationship, but from the individual record, I don't know what position it is within the chain nor what the first part or last part of the chain.

For demonstration purposes, assume we have the following setup. I realize that there are many design issues with this type of setup, but this is what I have to work with.

CREATE TABLE Relationships (
ID VARCHAR(4), 
ParentID VARCHAR(4),
ChildID VARCHAR(4)
)

-- Insert root entries with their children
INSERT INTO Relationships (ID, ParentID, ChildID)
VALUES ('0001', '', '0003'), ('0002', '', '0004')

-- Now add further entries for each relationship chain
INSERT INTO Relationships(ID, ParentID, ChildID)
VALUES('0003', '0001', '0005'), ('0005', '0003', '0006'), ('0006', '0005', '0007'), ('0007', '0006', ''), 
  ('0004', '0002', '')

--Now we have two chains of 0001 -> 0003 -> 0005 -> 0006 -> 0007 and 0002 ->   0004

With a recursive CTE like below, I can find how all records are related in their chain and their position within the chain.

WITH RelationshipChain AS (
SELECT ID, ParentID, ChildID, 0 AS Seq, ID AS RootID
FROM Relationships WHERE ParentID = ''
UNION ALL
SELECT r2.ID, r2.ParentID, r2.ChildID, rc.Seq + 1 AS Seq, rc.RootID AS RootID
FROM Relationships r2 
INNER JOIN RelationshipChain rc ON rc.ChildID = r2.ID 
)

SELECT * FROM RelationshipChain
ORDER BY RootID, Seq

For about 2 million records this runs in about 30 seconds which is pretty good, however if I try to also include what the final part of the chain, it takes 4x as long to run. Currently, I am doing it like this:

WITH RelationshipChain AS (
SELECT ID, ParentID, ChildID, 0 AS Seq, ID AS RootID
FROM Relationships WHERE ParentID = ''
UNION ALL
SELECT r2.ID, r2.ParentID, r2.ChildID, rc.Seq + 1 AS Seq, rc.RootID AS RootID
FROM Relationships r2 
INNER JOIN RelationshipChain rc ON rc.ChildID = r2.ID 
)

SELECT * 
FROM RelationshipChain rc
CROSS APPLY (
SELECT MAX(Seq) AS FinalSeq FROM RelationshipChain WHERE rc.RootID = RootID
) AS b
CROSS APPLY (
SELECT ID AS LastChild FROM RelationshipChain WHERE b.FinalSeq = seq AND rc.RootID = RootID
) AS c
ORDER BY RootID, Seq

Is there a way to do this more efficiently?

Answer 1

I don't have your dataset, so can't test if this is better, but it feels better. After building the chains, we reverse them to find the 'childest' item in each chain, then join back to the original chain.

-- The same as your first CTE
;WITH RelationshipChain AS (
SELECT ID, ParentID, ChildID, 0 AS Seq, ID AS RootID
FROM Relationships WHERE ParentID = ''
UNION ALL
SELECT r2.ID, r2.ParentID, r2.ChildID, rc.Seq + 1 AS Seq, rc.RootID AS RootID
FROM Relationships r2 
INNER JOIN RelationshipChain rc ON rc.ChildID = r2.ID 
)

-- This CTE is new and reverses the sense of the chains
, BackChain AS (
SELECT ID, RootID, ROW_NUMBER() OVER (PARTITION BY RootID ORDER BY Seq DESC) BackSeq
FROM RelationshipChain
)

-- Now we join each chain to the childest item in the reverse chain
SELECT 
    rc.ID
    , rc.ParentID
    , rc.ChildID
    , rc.Seq
    , rc.RootID
    , bc.ID ChainEndID
FROM RelationshipChain rc INNER JOIN BackChain bc ON RC.RootID = bc.RootID AND bc.BackSeq = 1
ORDER BY RootID, Seq

Results with your sample data:

ID   ParentID ChildID Seq         RootID ChainEndID
---- -------- ------- ----------- ------ ----------
0001          0003    0           0001   0007
0003 0001     0005    1           0001   0007
0005 0003     0006    2           0001   0007
0006 0005     0007    3           0001   0007
0007 0006             4           0001   0007
0002          0004    0           0002   0004
0004 0002             1           0002   0004

Indexes will help performance.