3

I have a PostgreSQL table with id and clusters like this:

CREATE TABLE w (id bigint, clst int);
INSERT INTO w (id,clst)
VALUES 
  (1,0),
  (1,4),
  (2,1),
  (2,2),
  (2,3),
  (3,2),
  (4,2),
  (5,4),
  (6,5);

If you aggregate clusters grouped by id, you can see that there are overlapping values in the cluster arrays:

select id, array_agg(clst) clst from w group by id order by id;
 id |  clst
----+---------
  1 | {0,4}
  2 | {1,2,3}
  3 | {2}
  4 | {2}
  5 | {4}
  6 | {5}

i.e. cluster 4 covers id 1 and 5, cluster 2 covers id 2, 3 and 4, whereas cluster 5 corresponds only to one id.

How can I now aggregate ids grouped by cluster arrays overlapping? i.e. the expected result is:

 id      | clst
---------+-------
 {1,5}   | {0,4,4}
 {2,3,4} | {1,2,3,2,2}
 {6}     | {5}

I don't care much about the cluster column just need ids properly aggregated.

There is no restriction on number of possible overlappings. Number of clusters per id is not restricted either (it can be hundreds or even more). Clusters are assined to ids not sequenctially.

There are millions of rows in the table!!!

Using PostgreSQL 11.

  • The logic of how to do the grouping is missing. So is your DDL. – Michael Kutz Apr 20 at 22:39
  • I've edited the question to explain the desired logic. – yaugenka Apr 20 at 23:25
  • Why should 1,2 exist at all? Why should it (1,2) be grouped with 1,2,3? Why is 3 grouped with only 4? – Michael Kutz Apr 21 at 0:57
  • @MichaelKutz sorry for unclarity. I have rewritten the question completely this time. – yaugenka Apr 21 at 8:47
  • What's the max. possible length of chains like [1,2], [2,3], [3,4] etc? Any restriction at all? If not, this is very hard on set-based solutions. Anything else you can tell us about cluster arrays? Are numbers arbitrary or ranges without gaps like your example seems to suggest? Cardinality? Range of possible IDs and cluster-numbers? Min/max/median/avg number of clusters per array. Any meta-information is crucial to keep performance in check here. Start with your version of Postgres and your actual table definition (CREATE TABLE statement) clarifying data types and constraints. – Erwin Brandstetter Apr 21 at 23:02
3

I don't care much about the cluster column just need ids properly aggregated.

In that case we can make use of the uniq and sort functions in the intarray extension:

with recursive a as (
  select id, array_agg(distinct clst) clst from w group by id)
, t(id,pid,clst) as (
  select id,id,clst from a
  union all
  select t.id,a.id,t.clst|a.clst
  from t join a on a.id<>t.pid and t.clst&&a.clst and not t.clst@>a.clst)
, d as (
  select distinct on(id) id, clst from t order by id, cardinality(clst) desc)
select array_agg(id), clst from d group by clst;
array_agg | clst   
:-------- | :------
{6}       | {5}    
{2,3,4}   | {1,2,3}
{1,5}     | {0,4}  

db<>fiddle here

Bear in mind that this is unlikely to perform well on millions of rows.

  • You can replace uniq(sort(t.clst||a.clst)) with t.clst | a.clst for better performance. | being the custom "union" operator provided by intarray that returns sorted arrays implicitly. – Erwin Brandstetter Apr 23 at 10:09
  • @Erwin thanks, that's a handy tip :) The intarray documentation could be a bit clearer on what the union operators do, ie whether they guarantee a sorted output. – Jack Douglas Apr 23 at 21:09
  • 1
    @JackDouglas: Sadly, no guarantees in the manual. I looked up the source code here and here, and it definitely returns a sorted list of unique elements. Still just an implementation detail. If that's too vague, the sure way would be sort(t.cls | a.clst). Still faster than before and at least uniqueness is guaranteed from the union operator. – Erwin Brandstetter Apr 23 at 23:36
  • 1
    Thanks @Erwin — at the end of the day performance is likely to be the killer without some other kind of 'constraint', as you said, still it's a fun problem :) – Jack Douglas Apr 24 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.