Select rows from hierarchy based on related nodes

Question

I have a self-referencing table Foo

[Id] int NOT NULL,
[ParentId] int NULL,   --Foreign key to [Id]
[Type] char(1) NOT NULL

[Id] is clustered primary key, indexes on [ParentId] and [Type] columns.

Assume a maximum depth of 1 on the hierarchy (child nodes cannot have child nodes).

---

I want to get all rows of Foo that satisfy the following:

• Type is A
• Has a B in its family tree
• Has a C or D in its family tree

The following query using JOIN's returns the desired results, but the performance is terrible

SELECT DISTINCT [Main].*

FROM Foo AS [Main]

--[Main] may not be root node
LEFT OUTER JOIN Foo AS [Parent]
    ON [Parent].[Id] = [Main].[ParentId]

--Must have a B in tree
INNER JOIN Foo AS [NodeB]
    ON (
        [NodeB].[Pid] = [Main].[Pid]            --Sibling
            OR [NodeB].[ParentId] = [Main].[Id] --Child
            OR [NodeB].[Id] = [Parent].[Id]     --Parent
    )
        AND [NodeB].[Type] = 'B'

--Must have a C or D in tree
INNER JOIN Foo AS [NodeCD]
    ON (
        [NodeCD].[Pid] = [Main].[Pid]            --Sibling
            OR [NodeCD].[ParentId] = [Main].[Id] --Child
            OR [NodeCD].[Id] = [Parent].[Id]     --Parent
    )
        AND [NodeCD].[Type] IN ('C', 'D')

WHERE [Main].[Type] = 'A'

From actual execution plan limited to looking only at first 10,000 of 650,000 rows

---

If I remove the --Parent lines from the query

OR [NodeB].[Id] = [Parent].[Id]  --Parent
OR [NodeCD].[Id] = [Parent].[Id] --Parent

then execution becomes almost instantaneous, but it misses the cases where the A is a child and has only one sibling

Misses this:    Catches this:
B               B
├A              ├A
└C              ├B
                └C

---

I have tried to come up with a CTE to do this, as it seems more promising in terms of performance, but I have been unable to figure how to exclude those trees that do not satisfy the criteria.

CTE so far

WITH [Parent] AS 
(
SELECT  *
FROM    [Foo]
WHERE   [ParentId] IS NULL

UNION ALL
SELECT  [Child].*
FROM    Foo AS [Child]
JOIN    [Parent]
ON      [Child].[ParentId] = [Parent].Id
WHERE   [Child].[Type] = 'P'

UNION ALL
SELECT  [ChildCD].*
FROM    Foo AS [ChildCD]
JOIN    [Parent]
ON      [ChildCD].[ParentId] = [Parent].Id
WHERE   [ChildCD].[Type] IN ('C', 'D')
)

SELECT  *
FROM [Parent]
WHERE [Type] = 'I';

However, if I try to add the Sibling-Child-Parent OR statements, I hit the maximum recursion level of 100.

---

SQL Fiddle with test data

Answer 1

I cannot predict efficiency but here is another solution:

SELECT *
FROM Foo AS f
WHERE Type = 'A'
  AND ParentId IS NULL
  AND EXISTS 
      ( SELECT *
        FROM Foo AS ch
        WHERE ch.ParentId = f.Id
          AND ch.Type = 'B'
      )
  AND EXISTS 
      ( SELECT *
        FROM Foo AS ch
        WHERE ch.ParentId = f.Id
          AND ch.Type IN ('C', 'D')
      ) 
UNION ALL

SELECT *
FROM Foo AS f
WHERE Type = 'A'
  AND ParentId IS NOT NULL
  AND EXISTS
    ( SELECT 1
      FROM
          ( SELECT *
            FROM (VALUES ('B'), ('C'), ('D')) AS x (Type)
          EXCEPT
            SELECT p.Type
            FROM Foo AS p
            WHERE f.ParentId = p.Id
          EXCEPT
            SELECT sib.Type
            FROM Foo AS sib
            WHERE f.ParentId = sib.ParentId
          ) AS x
       HAVING MIN(Type) = MAX(Type) AND MIN(Type) <> 'B'
           OR MIN(Type) IS NULL
    ) ; 

Tested in SQLfiddle

Answer 2

The case where the node being examined is a root node is sufficiently distinct from the case where it is a child node, that you will probably be better off querying the two separately and forming the UNION ALL of the two sets. You can simplify, however, with a common table expression that identifies those trees that contain the nodes you're after. Overall, that might look like this:

WITH [TargetFamilies] AS (
    SELECT
      COALESCE(ParentId, Id) AS FamilyId
    FROM Foo
    GROUP BY COALESCE(ParentId, Id)
    HAVING 
      COUNT(CASE Type WHEN 'B' THEN 1 END) > 0
      AND COUNT(CASE Type WHEN 'C' THEN 1 WHEN 'D' THEN 1 END) > 0
)

-- root nodes
SELECT [Main].*
FROM
  Foo AS [Main]
  JOIN [TargetFamilies] ON [Main].Id = [TargetFamilies].FamilyId
WHERE
  [Main].Type = 'A'

UNION ALL

-- child nodes
SELECT 
  [Main].*
FROM
  Foo AS [Main]
  JOIN [TargetFamilies] ON [Main].ParentId = [TargetFamilies].FamilyId
WHERE
  [Main].Type = 'A'

Answer 3

With recursive CTE. This will work for any multilevel hierarchy:

DECLARE @t TABLE
    (
      ID INT ,
      ParentID INT ,
      Type CHAR(1)
    )

INSERT  INTO @t
VALUES  ( 1, NULL, 'A' ),
        ( 2, 1, 'B' ),
        ( 3, NULL, 'C' ),
        ( 4, NULL, 'A' ),
        ( 5, 4, 'B' ),
        ( 6, 4, 'C' ),
        ( 7, NULL, 'A' ),
        ( 8, 7, 'B' ),
        ( 9, 8, 'D' ),
        ( 10, NULL, 'D' ),
        ( 11, 10, 'A' ),
        ( 12, 11, 'B' ),
        ( 13, 8, 'D' );

WITH    cte1
          AS ( SELECT   ID ,
                        ParentID ,
                        Type ,
                        ID AS GroupID ,
                        0 AS B ,
                        0 AS CD
               FROM     @t
               WHERE    Type = 'A'
               UNION ALL
               SELECT   t.ID ,
                        t.ParentID ,
                        t.Type ,
                        c.GroupID ,
                        CASE WHEN t.Type = 'B' THEN 1
                             ELSE 0
                        END ,
                        CASE WHEN t.Type IN ( 'C', 'D' ) THEN 1
                             ELSE 0
                        END
               FROM     @t t
                        JOIN cte1 c ON t.ParentID = c.ID
             ),
        cte2
          AS ( SELECT   ID ,
                        ParentID ,
                        Type ,
                        ID AS GroupID ,
                        0 AS B ,
                        0 AS CD
               FROM     @t
               WHERE    Type = 'A'
               UNION ALL
               SELECT   t.ID ,
                        t.ParentID ,
                        t.Type ,
                        c.GroupID ,
                        CASE WHEN t.Type = 'B' THEN 1
                             ELSE 0
                        END ,
                        CASE WHEN t.Type IN ( 'C', 'D' ) THEN 1
                             ELSE 0
                        END
               FROM     @t t
                        JOIN cte2 c ON t.ID = c.ParentID
             ),
        filter
          AS ( SELECT   ID ,
                        Type ,
                        SUM(B) OVER ( PARTITION BY GroupID ) AS B ,
                        SUM(CD) OVER ( PARTITION BY GroupID ) AS CD
               FROM     ( SELECT    *
                          FROM      cte1
                          UNION
                          SELECT    *
                          FROM      cte2
                        ) t
             )
    SELECT  t.*
    FROM    filter f
            JOIN @t t ON t.ID = f.ID
    WHERE   f.Type = 'A'
            AND B > 0
            AND cd > 0

Output:

ID  ParentID    Type
4   NULL        A
7   NULL        A
11  10          A

Answer 4

How about something like this?

select
    [F].[Id]
from
    [Foo] [F]
where
    [F].[Type] = 'A' and
    (
        (
            [F].[ParentId] is null and
            exists (select 1 from [Foo] [Child] where [F].[Id] = [Child].[ParentId] and [Child].[Type] = 'B') and
            exists (select 1 from [Foo] [Child] where [F].[Id] = [Child].[ParentId] and [Child].[Type] in ('C', 'D'))
        ) or
        (
            [F].[ParentId] is not null and
            exists (select 1 from [Foo] [ParentOrSibling] where [F].[ParentId] in ([ParentOrSibling].[Id], [ParentOrSibling].[ParentId]) and [ParentOrSibling].[Type] = 'B') and
            exists (select 1 from [Foo] [ParentOrSibling] where [F].[ParentId] in ([ParentOrSibling].[Id], [ParentOrSibling].[ParentId]) and [ParentOrSibling].[Type] in ('C', 'D'))
        )
    );

Answer 5

Jeez, this took longer than I thought and there certainly must a better way, but here is my take on it:

WITH CTE AS
(
    SELECT Id, ParentId FamilyId, [Type]
    FROM dbo.Foo
    UNION
    SELECT A.Id, B.Id, B.[Type]
    FROM dbo.Foo A
    INNER JOIN dbo.Foo B
        ON A.ParentId = B.Id
)
SELECT DISTINCT B.Id
FROM CTE A
INNER JOIN dbo.Foo B
    ON A.Id = B.Id
    OR A.FamilyId = B.Id
WHERE B.[Type] = 'A'
AND EXISTS( SELECT 1 FROM CTE
            WHERE FamilyId = A.FamilyId
            AND [Type] = 'B')
AND EXISTS( SELECT 1 FROM CTE
            WHERE FamilyId = A.FamilyId
            AND [Type] IN ('C','D'));

Here is the modified sqlfiddle.

Answer 6

It's not easy to optimize it with this set of data, but maybe try this. The LEFT OUTER JOIN seems to be superfluous. Also, the execution plan don't show a 96% hit at an inner loop.

SELECT DISTINCT [Main].*
FROM Foo AS [Main]


--Must have a B in tree
INNER JOIN Foo AS [NodeB]
    ON (
        [NodeB].[ParentId] = [Main].[ParentId]            --Sibling
            OR [NodeB].[ParentId] = [Main].[Id] --Child
            OR [NodeB].[Id] = [Main].[ParentId]     --Parent
    )
        AND [NodeB].[Type] = 'B'

--Must have a C or D in tree
INNER JOIN Foo AS [NodeCD]
    ON (
        [NodeCD].[ParentId] = [Main].[ParentId]            --Sibling
            OR [NodeCD].[ParentId] = [Main].[Id] --Child
            OR [NodeCD].[Id] = [Main].[ParentId]     --Parent
    )
        AND [NodeCD].[Type] IN ('C', 'D')

WHERE [Main].[Type] = 'A'

Please post your result. Hope this will help.