Выберите строки из иерархии на основе связанных узлов

Question

У меня есть автореферентная таблица Foo

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

[Id] является кластерными первичным ключом, индексы на [ParentId] и [Type] столбцов.

Предположим, что максимальная глубина 1 в иерархии (дочерние узлы не могут иметь дочерние узлы).

---

Я хочу, чтобы все строки Foo, которые удовлетворяют следующим образом:

• Тип является
• Имеет B в семейном дереве
• Имеет CилиD в генеалогическом древе

Следующий запрос с использованием JOIN возвращает желаемых результатов, но производительность страшен

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' 

От фактического плана выполнения ограничивается только глядя на первые 10 000 из 650 000 строк

---

Если я удаляю --Парентные линии из запроса

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

, то выполнение становится почти мгновенно, но он пропускает случаи, когда А является дочерним и имеет только один родственный

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

---

Я пытался придумать КТР, чтобы сделать это, так как это кажется более перспективным с точки зрения производительности, но я не смог понять, как исключить те деревья, которые не удовлетворяют критериям.

КТР до сих пор

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'; 

Однако, если я пытаюсь добавить Sibling-Child-Родитель или заявления, я ударил максимальный уровень рекурсии 100.

---

SQL Fiddle with test data

Answer 1

Случай, когда рассматривается узел является корневым узлом достаточно отличается от случая, когда он является дочерним узлом, что вы вероятно, будет лучше запросить два отдельно и сформировать UNION ALL двух наборов. Однако вы можете упростить общее табличное выражение, которое идентифицирует те деревья, которые содержат узлы, которые вы используете. В целом, это может выглядеть следующим образом:

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 2

Нелегко оптимизировать его с помощью этого набора данных, но, возможно, попробуйте это. LEFT OUTER JOIN кажется излишним. Кроме того, план выполнения не показывает 96% -ный удар во внутреннем цикле.

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' 

Сообщите, пожалуйста, свой результат. Надеюсь, это поможет.

Answer 3

Jeez, это заняло больше времени, чем я думал, и там, конечно, должно быть лучший путь, но вот мой взгляд на него:

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 4

Как насчет чего-то подобного?

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

С рекурсивным CTE. Это будет работать для любой многоуровневой иерархии:

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 

Выход:

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

Answer 6

Я не могу предсказать эффективность, но здесь другое решение:

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 
    ) ; 

Испытан в SQLfiddle