递归cte查询是否可以进行分支修剪

Question

这是受问题的启发-我想出了一个解决方案，但我对其效率表示怀疑。

重述问题：

我们有 2 个表：Person 和 Parent
Person包含每个人的基本数据
Parent 是一个加入 table 关联的人及其 parents
每个人可以有多个parents
我们想接收每个人的数据以及他们所有祖先的列表 - 每个祖先在自己的行中
如果没有祖先，我们只有该人的一行，parentId 为空

数据格式如下：

人table

Id <PK>
Name

Parent table

Id<PK>
ParentPersonId <FK into Person >

Person 有值 PK 的行

1, 'Jim'
2, 'John'
3, 'Anna'
4, 'Peter'

Parent 具有值

的行

1, 2
1, 3
2, 3
3, 4

所以人 1 有祖先 2、3、4

我想要以下形式的输出

id  name    parentPersonId
--------------------------
1   Jim     2
1   Jim     3
1   Jim     4
2   John    3
2   John    4
3   Anna    4
4   Peter   (null)

我的解决方案使用递归 CTE 查询，但我担心它会产生太多行，因为每个子树都可以输入多次。我需要用 distinct 过滤掉重复项，执行计划表明，即使使用这个简单的数据，对 distinct 进行排序也需要 50% 的时间。这是我的查询：

WITH cte_org AS 
(
    SELECT per.id, per.name, par.parentPersonId
    FROM Person per 
    LEFT JOIN Parent par ON per.id = par.id
    UNION ALL
    SELECT o.id, o.name, rec.parentPersonId
    FROM Parent rec
    INNER JOIN cte_org o ON o.parentPersonId = rec.id
    WHERE rec.parentPersonId IS NOT NULL
)
SELECT DISTINCT *
FROM cte_org
ORDER BY id, parentPersonId;

http://sqlfiddle.com/#!18/d7d62/4

我的问题：

我能不能以某种方式修剪已经访问过的分支，这样 recursive-CTE 就不会产生重复的行，并且不需要最后的 distinct
递归 CTE 是解决此问题的正确方法吗？

Answer 1

在 PostgreSQL 上，您可以通过将 UNION ALL 替换为 UNION 来实现。所以查询看起来像这样：

WITH RECURSIVE cte_org AS (
    select per.id, per.name, par.parentPersonId
    from Person per left join Parent par 
    on per.id = par.id
    UNION 
    SELECT 
        o.id, 
        o.name,
        rec.parentPersonId
    FROM 
        Parent rec
        INNER JOIN cte_org o 
            ON o.parentPersonId = rec.id
        where rec.parentPersonId is not null
)
SELECT *
FROM cte_org
ORDER BY id, parentPersonId;

http://sqlfiddle.com/#!17/225cf4/4

递归cte查询是否可以进行分支修剪

Is branch pruning possible for recursive cte query

sql

tsql

sql-server

recursive-query

common-table-expression