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不是随机的，它是其元素的最小值。

Answer 2

根据@klin 修改

create table public.foo (
id numeric,
lt numeric,
rt numeric
);
insert into public.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, grp) as (
    select 
        id, lt, rt, 
        id -- rightmost id for grouping
    from public.foo
    where rt is null -- Get the rightmost objects
    union all
    select 
        r.id, r.lt, r.rt, 
        grp -- kept constant from rightmost object on the list
    from public.foo r
    join find f on r.id = f.lt -- Traverse list from right to left
    -- Recursion will stop when all left ids are null
    )
select id, grp from find
order by grp, id;

• 拿最右边的物体
• 从右向左遍历
• 最右边的id保持不变以进行分组