我怎样才能在 postgres 中通过数组值找到所有链接的行？

Question

我有一个 table 这样的：

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，因为我的问题是图形化的，但我不确定该怎么做。

其他信息和背景：

Table 有 ~2500000 行。

实际上我尝试解决的问题有更多的领域和条件：

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

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

----编辑-----

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

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........

这个问题有解决办法吗？

Answer 1

这是解决这个 graph-walking 问题的方法：

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

common-table-expression 遍历图形，递归地寻找当前节点的“相邻”节点，同时跟踪 already-visited 节点。然后外部查询聚合，使用每个路径的最少节点识别组，最后对组进行排名。

Demo on DB Fiddle:

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

Answer 2

您可以将其作为递归 CTE 来处理。根据公共值定义 id 之间的边。然后遍历边并聚合：

with recursive nodes as (
      select id, val
      from t cross join
           unnest(arr_val) as val
     ),
     edges as (
      select distinct n1.id as id1, n2.id as id2
      from nodes n1 join
           nodes n2
           on n1.val = n2.val
     ),
     cte as (
      select id1, id2, array[id1] as visited, 1 as lev
      from edges
      where id1 = id2
      union all
      select cte.id1, e.id2, visited || e.id2,
             lev + 1
      from cte join
           edges e
           on cte.id2 = e.id1
      where e.id2 <> all(cte.visited) 
     ),
     vals as (
      select id1, array_agg(distinct id2 order by id2) as id2s
      from cte
      group by id1
    )
select *, dense_rank() over (order by id2s) as grp
from vals;

Here 是一个 db<>fiddle.

Answer 3

虽然 Gordon Linoffs 解决方案是我发现的最快的解决方案，适用于组不是很大的少量数据，但它不适用于更大的数据集和更大的组。我改变了他的解决方案以使其工作。我将边缘移动到索引 table：创建 table 条边 ( id1 整数不为空， id2 整数不为空，约束 staffel_group_nodes_pk 主键（id1，id2） );

insert into edges(id1, id2) with
nodes(id, arr_val) as (
    select id, arr_val
    from my_table
)
    select n1.id as id1, n2.id as id2
    from nodes n1
             join
         nodes n2
         on n1.arr_val && n2.arr_val ;

只有 Tha 没有帮助。我也改变了他的递归部分：

with recursive
    cte as (
        select id1, array [id1] as visited
        from edges
        where id1 = id2
        union all
        select unnested.id1, array_agg(distinct unnested.vis) as visited
        from (
                 select cte.id1,
                        unnest(cte.visited || e.id2) as vis
                 from cte
                          join
                      staffel_group_edges e
                      on e.id1 = any (cte.visited)
                          and e.id2 <> all (cte.visited)) as unnested
        group by unnested.id1
    ),
    vals as (
        select id1, array_agg(distinct vis) as id2s
        from (
                 select cte.id1,
                        unnest(cte.visited) as vis
                 from cte) as unnested

        group by unnested.id1
    )
select id1,id2s, dense_rank() over (order by id2s) as grp
from vals;

每一步我都会根据起点对所有搜索进行分组。这大大减少了平行行走路径的数量，并且工作速度出奇地快。

我怎样才能在 postgres 中通过数组值找到所有链接的行？

How can i find all linked rows by array values in postgres?

sql

postgresql

graph-theory

recursive-query

postgresql-12