有效合并包含重叠值的数组

Question

给定一个包含整数数组的 table，应合并这些数组，以便所有具有重叠条目的数组最终成为一个数组。

鉴于 table arrays

     a      
------------
 {1,2,3}
 {1,4,7}
 {4,7,9}
 {15,17,18}
 {18,16,15}
 {20}

结果应该是这样的

{1,2,3,4,7,9}
{15,17,18,16}
{20}

如您所见，合并后的数组中的重复值可能会被删除，结果条目在数组中的顺序并不重要。这些数组是整数数组，因此可以使用 intarray 模块中的函数。

这将在相当大的 table 上完成，因此性能至关重要。

我第一个天真的方法是在 && 运算符上自加入 table。像这样：

SELECT DISTINCT uniq(sort(t1.a || t2.a))
FROM arrays t1
JOIN arrays t2 ON t1.a && t2.a

这留下了两个问题：

它不是递归的（它最多合并 2 个数组）。
这可能可以通过递归 CTE 来解决。
输出中再次出现合并数组。

非常欢迎任何意见。

Answer 1

do $$
declare
    arr int[];
    arr_id int := 0;
    tmp_id int;
begin
    create temporary table tmp (v int primary key, id int not null);
    for arr in select a from t loop
        select id into tmp_id from tmp where v = any(arr) limit 1;
        if tmp_id is NULL then
            tmp_id = arr_id;
            arr_id = arr_id+1;
        end if;
        insert into tmp
            select unnest(arr), tmp_id
            on conflict do nothing;
    end loop;
end
$$;
select array_agg(v) from tmp group by id;

Answer 2

纯SQL版本：

WITH RECURSIVE x (a) AS (VALUES ('{1,2,3}'::int2[]),
 ('{1,4,7}'),
 ('{4,7,9}'),
 ('{15,17,18}'),
 ('{18,16,15}'),
 ('{20}')
), y AS (
    SELECT 1::int AS lvl,
           ARRAY [ a::text ] AS a,
           a AS res
      FROM x
     UNION ALL
    SELECT lvl + 1,
           t1.a || ARRAY [ t2.a::text ],
           (SELECT array_agg(DISTINCT unnest ORDER BY unnest)
              FROM (SELECT unnest(t1.res) UNION SELECT unnest(t2.a)) AS a) 
      FROM y AS t1
      JOIN x AS t2 ON (t2.a && t1.res) AND NOT t2.a::text = ANY(t1.a)
     WHERE lvl < 10
)
SELECT DISTINCT res
  FROM x
  JOIN LATERAL (SELECT res FROM y WHERE x.a && y.res ORDER BY lvl DESC LIMIT 1) AS z ON true

有效合并包含重叠值的数组

efficient merge of arrays that contain overlapping values

postgresql

postgresql-9.6