Getting all including and excluding parents of children in a tree

Question

I have a query like the simplified version below, which produces the results table below it.

In this case, the data consists of two tree structures of three levels each.

What I need, for each tree ('root'), is each child along with all the parents which include it and all the parents which exclude it.

The query works--but the execution time is extremely slow due to the cross apply method used.

Is there another way to do this that might be faster?

DECLARE @Data TABLE (Rt VARCHAR(MAX), Parent VARCHAR(MAX), Child VARCHAR(MAX))
INSERT INTO @Data (Rt, Parent, Child) VALUES
    ('root1', 'parent1', 'child1'),
    ('root1', 'parent1', 'child2'),
    ('root1', 'parent2', 'child1'),
    ('root1', 'parent2', 'child2'),
    ('root1', 'parent2', 'child3'),
    ('root1', 'parent3', 'child2'),
    ('root1', 'parent3', 'child3'),
    ('root1', 'parent4', 'child4'),
    ('root1', 'parent5', 'child2'),
    ('root2', 'parent6', 'child1'),
    ('root2', 'parent7', 'child5')

SELECT 
    D.Rt 'Root'
    , D.Child
    , STRING_AGG(D.Parent, ', ') 'In-Parents'
    , STRING_AGG(xP.Parent, ', ') 'Ex-Parents'
FROM @Data D
CROSS APPLY (
    SELECT
        Di.Parent
    FROM @Data Di
    WHERE Di.Rt = D.Rt
    EXCEPT
    SELECT
        Dii.Parent
    FROM @Data Dii
    WHERE
        Dii.Rt = D.Rt
        AND Dii.Child = D.Child
) AS xP
GROUP BY
    D.Rt
    , D.Child

Root	Child	In-Parents	Ex-Parents
root1	child1	parent1, parent2	parent3, parent4, parent5
	child2	parent1, parent2, parent3, parent5	parent4
	child3	parent2, parent3	parent1, parent4, parent5
	child4	parent4	parent1, parent2, parent3, parent5
root2	child1	parent6	parent7
	child5	parent7	parent6

In case the code above doesn't work (I don't have access to STRING_AGG), here is what I'm actually using to get these results:

DECLARE @Data TABLE (Rt VARCHAR(MAX), Parent VARCHAR(MAX), Child VARCHAR(MAX))
INSERT INTO @Data (Rt, Parent, Child) VALUES
    ('root1', 'parent1', 'child1'),
    ('root1', 'parent1', 'child2'),
    ('root1', 'parent2', 'child1'),
    ('root1', 'parent2', 'child2'),
    ('root1', 'parent2', 'child3'),
    ('root1', 'parent3', 'child2'),
    ('root1', 'parent3', 'child3'),
    ('root1', 'parent4', 'child4'),
    ('root1', 'parent5', 'child2'),
    ('root2', 'parent6', 'child1'),
    ('root2', 'parent7', 'child5')

; WITH Res AS (
    SELECT 
        D.Rt
        , D.Child
        , D.Parent 'InParent'
        , xP.Parent 'ExParent'
    FROM @Data D
    CROSS APPLY (
        SELECT
            Di.Parent
        FROM @Data Di
        WHERE Di.Rt = D.Rt
        EXCEPT
        SELECT
            Dii.Parent
        FROM @Data Dii
        WHERE
            Dii.Rt = D.Rt
            AND Dii.Child = D.Child
    ) AS xP
)

SELECT
    IIF(R.Rt = LAG(R.Rt, 1) OVER(ORDER BY R.Rt, R.Child), '', R.Rt) 'Root'
    , R.Child
    , STUFF((
        SELECT ', ' + R2.InParent
        FROM Res R2
        WHERE
            R2.Rt = R.Rt
            AND R2.Child = R.Child
        FOR XML PATH(''), TYPE
    ).value('.', 'NVARCHAR(MAX)'), 1, 1, '') 'In-Parents'
    , STUFF((
        SELECT ', ' + R2.ExParent
        FROM Res R2
        WHERE
            R2.Rt = R.Rt
            AND R2.Child = R.Child
        FOR XML PATH(''), TYPE
    ).value('.', 'NVARCHAR(MAX)'), 1, 1, '') 'Ex-Parents'
FROM Res R
GROUP BY
    R.Rt
    , R.Child
ORDER BY
    R.Rt
    , R.Child

The Impaler · Answer

I would try to produce all parent-child combinations first, and then test if they are present in the data. For example:

select
  p.root, 
  c.child,
  string_agg(d.parent, ', ') as in_parents,
  string_agg(case when d.parent is null then p.parent end, ', ') as ex_parents  
from (select distinct root, parent from data) p
join (select distinct root, child from data) c on c.root = p.root
left join data d on d.root = p.root and d.parent = p.parent 
                and d.root = c.root and d.child = c.child
group by p.root, c.child
order by p.root, c.child

Result:

 root   child   in_parents                          ex_parents                         
 ------ ------- ----------------------------------- ---------------------------------- 
 root1  child1  parent1, parent2                    parent3, parent4, parent5          
 root1  child2  parent1, parent2, parent3, parent5  parent4                            
 root1  child3  parent2, parent3                    parent1, parent4, parent5          
 root1  child4  parent4                             parent1, parent2, parent3, parent5 
 root2  child1  parent6                             parent7                            
 root2  child5  parent7                             parent6

See running example at db<>fiddle.

Now, if you don't need VARCHAR(MAX) but instead something like VARCHAR(100) can do, then you could try speeding up the query by using an index in the form:

create index ix1 on data (root, parent, child);

If the query is still slow, please post the execution plan.

Getting all including and excluding parents of children in a tree

1 Answers