sql - 根据相关节点从层次结构中选择行

Question

我有一个自引用表 Foo

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

[Id]是聚簇主键，索引位于 [ParentId]和 [Type]列。

假设层次结构的最大深度为 1(子节点不能有子节点)。

我想获得满足以下条件的所有 Foo 行:

类型是 A

拥有 乙在其家谱中

拥有 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'

从实际执行计划限制为仅查看 650,000 行中的前 10,000


如果我从查询中删除 --Parent 行

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

然后执行几乎是瞬间的，但它错过了 A 是 child 并且只有一个兄弟的情况

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

我试图想出一个 CTE 来做到这一点，因为它在性能方面似乎更有希望，但我一直无法弄清楚如何排除那些不满足标准的树。

到目前为止的 CTE

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-Parent OR 语句，则会达到最大递归级别 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'