sql - 如何在 postgres 中按数组值查找所有链接的行？

Question

我有一张这样的桌子：

id | arr_val  | grp
-----------------
1  | {10,20}  | -
2  | {20,30}  | -
3  | {50,5}   | -
4  | {30,60}  | -
5  | {1,5}    | -
6  | {7,6}    | -

我想找出哪些行在一个组中。在这个例子中，1,2,4 是一个组，因为 1 和 2 有一个共同的元素，而 2 和 4。3 和 5 形成一个组，因为它们有一个共同的元素。6 与其他人没有共同点。所以它为自己形成了一个群体。结果应如下所示：

id | arr_val  | grp
-----------------
1  | {10,20}  | 1
2  | {20,30}  | 1
3  | {50,5}   | 2
4  | {30,60}  | 1
5  | {1,5}    | 2
6  | {7,6}    | 3

我认为我需要递归 cte，因为我的问题是类似图形的，但我不知道该怎么做。

附加信息和背景：

该表有 ~2500000 行。

实际上，我试图解决的问题有更多的领域和条件来寻找一个群体：

id | arr_val  | date | val | grp
---------------------------------
1  | {10,20}  | -
2  | {20,30}  | -

不仅组的元素需要通过 arr_val 中的公共元素链接。它们都需要在 val 中具有相同的值，并且需要通过日期的时间跨度（间隙和岛屿）链接。我解决了另外两个，但现在我的问题的条件被添加了。如果有一种简单的方法可以在一个查询中同时完成这三个操作，那将是很棒的，但没有必要。

- - 编辑 - - -

虽然这两个答案都适用于五行的示例，但它们不适用于包含更多行的表。两个答案都存在递归部分中的行数爆炸并且最后只减少它们的问题。解决方案也应该适用于这样的数据：

id | arr_val  | grp
-----------------
1  | {1}      | -
2  | {1}      | -
3  | {1}      | -
4  | {1}      | -
5  | {1}      | -
6  | {1}      | -
7  | {1}      | -
8  | {1}      | -
9  | {1}      | -
10 | {1}      | -
11 | {1}      | -
more rows........

有没有办法解决这个问题？

标签： sqlpostgresqlgraph-theoryrecursive-querypostgresql-12

Answer 1

这是解决此图行走问题的一种方法：

with recursive cte as (
    select id, arr_val, array[id] path from mytable
    union all
    select t.id, t.arr_val, c.path || t.id
    from cte c
    inner join mytable t on t.arr_val && c.arr_val and not t.id = any(c.path)
)
select c.id, c.arr_val, dense_rank() over(order by min(x.id)) grp
from cte c
cross join lateral unnest(c.path) as x(id)
group by c.id, c.arr_val
order by c.id

公共表表达式遍历图，递归地寻找与当前节点“相邻”的节点，同时跟踪已经访问过的节点。然后外部查询聚合，使用每条路径的最少节点识别组，最后对组进行排名。

DB Fiddle 上的演示：

编号 | arr_val | grp
-: | :-------- | --:
 1 | {10,20} | 1
 2 | {20,30} | 1
 3 | {50,5} | 2
 4 | {30,60} | 1
 5 | {1,5} | 2
 6 | {7,6} | 3