Как сгруппировать строки в таблице postgresql, которые соответствуют входному значению или соответствуют значению из любой из других совпадающих строк?

Question

У меня есть таблица, которая выглядит так в моей postgresql базе данных

введите описание изображения здесь

Как я могу вернуть кластер контактов, в котором каждый контакт в кластере использует значение contact_id_a или contact_id_b (или оба) совместно с другим контактом в кластере?

В Например, на скриншоте выше, строки 1-6 будут в одном кластере, а строка 8 не будет принадлежать ни одному кластеру.

Как этого можно достичь с помощью запроса SQL или запроса SQL в сочетании с кодом Java?

Для контекста в этой таблице перечислены все потенциальные повторяющиеся контакты в списке контактов. Мы хотим предоставить владельцу списка все контакты, которые могут быть дубликатами, чтобы пользователь мог вручную управлять этими дубликатами.

Вот мой начальный код:

DuplicateCandidate firstDuplicate = db.sql("select * from duplicates where list_id = "+list_id+ " and ignore_duplicate is not true").first(DuplicateCandidate);
        String sql = "select * from duplicates where list_id = "+list_id+ "and ignore_duplicate is not true "
                + "and (contact_id_a = ? or contact_id_b = ? or contact_id_a = ? or contact_id_b = ?";
        List<DuplicateCandidate> groupOfDuplicates  = db.sql(sql, firstDuplicate.contact_id_a,firstDuplicate.contact_id_a, firstDuplicate.contact_id_b, firstDuplicate.contact_id_b).results(DuplicateCandidate.class);

Это принесет вернуть первую строку и любые другие строки, содержащие 16247096 или 16247097, но не другие важные строки, соответствующие contact_ids из результатов второго запроса.

Ура.

Answer 1

Подобная кластеризация - это итеративный процесс с неизвестным числом шагов. Я никогда не находил решения, которое можно было бы реализовать в рамках рекурсивного запроса.

Я не работал над CRM более шести лет, но следующая функция аналогична тому, как мы использовали для создания групп совпадений. Построчное выполнение этой задачи недостаточно эффективно для нашей рабочей нагрузки, и выполнение этого с помощью основного языка с использованием, например, Java HashMap() и HashSet() и инвертированной индексации создает очень беспорядочный код.

Предполагая это schema:

\d contact_info 
                 Table "public.contact_info"
      Column      |  Type   | Collation | Nullable | Default 
------------------+---------+-----------+----------+---------
 contact_id_a     | bigint  |           |          | 
 contact_id_b     | bigint  |           |          | 
 ignore_duplicate | boolean |           |          | false
 list_id          | integer |           |          | 496

select * from contact_info ;
 contact_id_a | contact_id_b | ignore_duplicate | list_id 
--------------+--------------+------------------+---------
     16247096 |     16247097 | f                |     496
     16247096 |     16247098 | f                |     496
     16247096 |     16247099 | f                |     496
     16247097 |     16247098 | f                |     496
     16247097 |     16247099 | f                |     496
     16247098 |     16247099 | f                |     496
     16247094 |     16247095 | f                |     496
(7 rows)

Эта функция создает две временные таблицы для хранения промежуточных кластеров, а затем возвращает результат, когда кластеризация становится невозможной.

create or replace function cluster_contact() 
  returns table (clust_id bigint, contact_id bigint) 
  language plpgsql as $$
declare 
  last_count bigint := 1;
  this_count bigint := 0;
begin
  create temp table contact_match (clust_id bigint, contact_id bigint) on commit drop;
  create index cm_1 on contact_match (contact_id, clust_id);
  create index cm_2 on contact_match using hash (clust_id);
  create temp table contact_hold (clust_id bigint, contact_id bigint) on commit drop;

  with dedup as (
    select distinct least(ci.contact_id_a) as clust_id,
           greatest(ci.contact_id_b) as contact_id
      from contact_info ci
     where not ci.ignore_duplicate
  )
  insert into contact_match
    select d.clust_id, d.clust_id from dedup d
    union
    select d.clust_id, d.contact_id from dedup d;

  while last_count > this_count loop

    if this_count = 0 then 
      select count(distinct cm.clust_id) into last_count from contact_match cm;
    else 
      last_count := this_count;
    end if;

    with new_cid as (
      select cm.contact_id as clust_id_old,
             min(cm.clust_id) as clust_id_new
        from contact_match cm
       group by cm.contact_id
    )
    update contact_match
       set clust_id = nc.clust_id_new
      from new_cid nc
     where contact_match.clust_id = nc.clust_id_old;

    truncate table contact_hold;
    insert into contact_hold 
      select distinct * from contact_match;
 
    truncate table contact_match;
    insert into contact_match
      select * from contact_hold;

    select count(distinct cm.clust_id) into this_count from contact_match cm;

  end loop;

  return query select * from contact_match order by clust_id, contact_id;
end $$;

Один из самых больших умственных блоков I видели лицо разработчиков, пренебрегающее включением отношения contact_id к самому себе. Это приводит к несвязному обращению и ментальной модели, излишне усложняемой левой и правой сторонами. работает на вас.

Также знайте, что Левенштейн доступен в fuzzystrmatch, и он работает хорошо.

Если вы предпочитаете последовательный clust_id, начиная с 1, измените return query в функции на это:

  return query 
    select dense_rank() over (order by cm.clust_id) as clust_id, 
           cm.contact_id 
      from contact_match cm 
     order by clust_id, contact_id;

Это даст:

select * from cluster_contact();
 clust_id | contact_id 
----------+------------
        1 |   16247094
        1 |   16247095
        2 |   16247096
        2 |   16247097
        2 |   16247098
        2 |   16247099
(6 rows)

Answer 2

Вы можете использовать рекурсивный CTE. Это обходит график, а затем назначает минимальный идентификатор в графике для каждой строки. Обратите внимание, что ваши данные не имеют уникального идентификатора для каждой строки, поэтому это начинается с его генерации:

with recursive d as (
      select row_number() over (order by contact_id_a, contact_id_b) as id, d.*
      from duplicates d
     ),
     cte (id, contact_id_a, contact_id_b, min_id, ids, lev) as (
      select id, contact_id_a, contact_id_b, id as min_id, array[id] as ids, 1 as lev
      from d
      union all
      select d.id, d.contact_id_a, d.contact_id_b, least(d.id, cte.min_id), ids || d.id, lev + 1
      from cte join
           d
           on cte.contact_id_a = d.contact_id_a or cte.contact_id_b = d.contact_id_b
      where d.id <> ALL (cte.ids)
     )
select distinct on (id) cte.*
from cte
order by id, min_id;

Столбец min_id содержит нужную вам группировку.

Здесь - скрипт db <>, иллюстрирующий код.