Postgres 组链表查询

Question

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

我想要一种方法，通过按查询分组将 link 的所有对象分组在一起。每个组的 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 保持不变以进行分组

Postgres 组链表查询

Postgres Group Linked List Query

postgresql

recursive-query

common-table-expression