递归CTE查询是否可以进行分支修剪 [英] Is branch pruning possible for recursive cte query

问题描述

这受问题的启发一个SQL语句-我想出了一个解决方案，但是我对它的效率有所怀疑。

This is inspired by question Retrieve a list of lists in one SQL statement - I have come up with a solution, but I have doubts on its efficiency.

要重述该问题：

• 我们有2个表：人和父母


• 人员包含有关每个人的基本数据


• Parent 是一个将人与其父母联系起来的联接表


• 每个人可以有多个父母


• 我们要接收每个人的数据列出所有祖先-每个祖先在自己的行中


• 如果没有祖先，则该人只有一行，其parentId为空

• we have 2 Tables: Person and Parent
• Person contains basic data about each person
• Parent is a join table relating person with its parents
• each Person can have multiple parents
• we want to receive each person data with list of all their ancestors - each ancestor in its own row
• if there are no ancestors, we have only one row for that person, with null parentId

以下是数据格式：

人员表

Id <PK>
Name

父表

Id<PK>
ParentPersonId <FK into Person >

人员具有值PK的行

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

父级包含具有值的行

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

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

So person 1 has ancestors 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查询，但是我担心它会产生过多的行，因为每个子树都可以多次输入。我需要过滤出具有唯一性的重复项，而执行计划表明，即使有了这些简单的数据，对唯一性进行排序也需要50％的时间。这是我的查询：

My solution used recursive CTE query, but my fear is that it produces too many rows, as each subtree can be entered multiple times. I needed to filter out duplicates with distinct, and execution plan shows that, even with this simple data, sorting for distinct takes 50% of the time. Here is my query:

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

我的问题 >

• 我可以以某种方式修剪已经访问过的分支，以便递归CTE不会产生重复的行，并且不需要最后的区别


• 递归CTE是解决此问题的正确方法吗？

推荐答案

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

On PostgreSQL you can acheive that by replacing UNION ALL with UNION. So the query looks like that:

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查询是否可以进行分支修剪的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！