在postgres中选择/过滤树结构

Question

我正在为遗留系统开发一项新功能。该系统使用两个表来保存“文档”并保存文档之间的关系（“关系”）。这个“关系”表创建了类似树结构的东西。

我们需要列出所有被归类为有效类型并且没有任何其他有效类型文档作为其祖先的文档。

文档（约 5 亿条记录正在生成）

---

id:   |  type
1   invalid_type
2   valid_type_a
3   invalid_type
4   valid_type_a
5   invalid_type
6   valid_type_b
7   invalid_type
8   valid_type_b
9   invalid_type
10  valid_type_a
11  valid_type_a
12  invalid_type
13  invalid_type
14  invalid_type
15  valid_type_b

关系（约 5 亿条生产记录）

---

relationId | parentDocumentId | childDocumentId
1       1       2
2       1       3
3       2       4
4       2       5
5       3       6
6       6       7
7       8       9
8       9       10
9       12      13
10      13      14
11      13      15

在这些表中，我需要列出有效类型的所有文档，并且没有任何有效类型（任何级别）的祖先文档。

预期结果是：2,6,8,11,15

4 是一个有效文档，但有 2 作为其父文档。

10 是有效文档，但其祖先为 8。

---

虽然我最终可以更改此结构，甚至可能将其迁移到另一个数据库（nosql ...），但现在的重点是使用当前模型开发新功能。

我一直在玩递归查询，但还无法将所有事情放在一起。 我还可以在某种程度上选择和过滤记录，然后在我的代码中应用其余规则。

非常感谢任何指向任何方向的帮助或提示。

CREATE TABLE IF NOT EXISTS document
(
    id int not null,
    type varchar not null,
    CONSTRAINT document_pk PRIMARY KEY (id)
);

CREATE TABLE IF NOT EXISTS relation
(
    id int not null,
    parent_id int not null,
    child_id int not null,
    CONSTRAINT relation_pk PRIMARY KEY (id),
    CONSTRAINT parent_fk FOREIGN KEY (parent_id)
        REFERENCES document (id),
    CONSTRAINT child_fk FOREIGN KEY (child_id)
        REFERENCES document (id)
);


INSERT INTO document (id, type)
    VALUES 
        (1, 'invalid_type'), 
        (2, 'valid_type_a'), 
        (3, 'invalid_type'), 
        (4, 'valid_type_a'), 
        (5, 'invalid_type'), 
        (6, 'valid_type_b'), 
        (7, 'invalid_type'), 
        (8, 'valid_type_b'), 
        (9, 'invalid_type'), 
        (10, 'valid_type_a'), 
        (11, 'valid_type_a'), 
        (12, 'invalid_type'), 
        (13, 'invalid_type'), 
        (14, 'invalid_type'), 
        (15, 'valid_type_b');


INSERT INTO relation (id, parent_id, child_id)
    VALUES 
        (1, 1, 2), 
        (2, 1, 3),
        (3, 2, 4),
        (4, 3, 5),
        (5, 3, 6),
        (6, 6, 7),
        (7, 8, 9),
        (8, 9, 10),
        (9, 12, 13),
        (10, 13, 14),
                (11, 13, 15);

Answer 1

从每个候选节点，您可以向上遍历树并查找是否存在有效的祖先。例如：

with recursive
n (id, lvl, cid, burned) as (
  select id, 1, id, false from document where type like 'v%'
 union all
  select n.id, n.lvl + 1, d.id, d.type like 'v%'
  from n
  join relation r on r.childDocumentId = n.cid and not n.burned
  join document d on d.id = r.parentDocumentId
)
select *
from (
  select distinct on (id) * from n order by id, lvl desc
) x
where not burned;

结果：

 id  lvl  cid  burned 
 --- ---- ---- ------ 
 2   2    1    f      
 6   3    1    f      
 8   1    8    f      
 11  1    11   f      
 15  3    12   f      

请参阅 db<>fiddle 处的运行示例。

注意：假设没有循环引用。

以下索引有助于提高性能：

create index ix1 on relation (childDocumentId, parentDocumentId);

create index ix2 on document (id);