postgresql - Postgres 组链表查询

Question

我想将我的对象 Foo 分组，它有一个属性 left 和 right 可以是 null 或包含 另一个 Foo 对象的 pid。

我想要一种方法来对通过查询分组链接在一起的所有对象进行分组。每个组的 id 可以是随机的，但必须是不同的。

示例输入

╔═════╦══════════╦════╦════╦
║ FO  ║ left     ║  right  ║
╠═════╬══════════╬═════════╬
║  1  ║     3    ║   2     ║
║  2  ║     1    ║         ║
║  3  ║          ║   1     ║
║  4  ║     5    ║   6     ║
║  5  ║          ║   4     ║
║  6  ║     4    ║         ║
╚═════╩══════════╩════╩════╩

输出:

╔═════╦══════════╦════╦════╦
║ FO  ║ group    ║         ║
╠═════╬══════════╬═════════╬
║  1  ║     1    ║         ║
║  2  ║     1    ║         ║
║  3  ║     1    ║         ║
║  4  ║     2    ║         ║
║  5  ║     2    ║         ║
║  6  ║     2    ║         ║
╚═════╩══════════╩════╩════╩

Answer 1

递归数据结构需要递归查询。示例数据:

create table foo(id int, lt int, rt int);
insert into foo values
(1, 3, 2),
(2, 1, null),
(3, null, 1),
(4, 5, 6),
(5, null, 4),
(6, 4, null);

查询:

with recursive find (id, lt, rt, ids) as (
    select id, lt, rt, array[id]
    from foo
union all
    select 
        r.id, f.lt, f.rt, 
        case when ids[1] < f.id then ids || f.id else f.id || ids end
    from find r
    join foo f on f.id = r.lt or f.id = r.rt
    where f.id <> all(ids)
    )
select distinct on (id) id, ids[1] as group
from find
order by id, array_length(ids, 1) desc;

 id | group 
----+-------
  1 |     1
  2 |     1
  3 |     1
  4 |     4
  5 |     4
  6 |     4
(6 rows)    

组的 Id 不是随机的，它是其元素的 min(id)。