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

Меня зовут Илья Новиков, я технический директор компании «Исходный код».

Ранее карточки артистов создавались автоматически на основе заявок на выступления. Поначалу это казалось вполне приемлемым: артист подает заявку, система создает карточку, администраторы могут с ней работать.

На практике мы получили кучу дубликатов. В некоторых записях был один и тот же адрес электронной почты. В некоторых — один и тот же номер телефона. Некоторые были связаны и тем, и другим, но не всегда напрямую.

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

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

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

Что у нас получилось

Мы решили объединить профили артистов.

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

Наша задача заключалась в том, чтобы переложить всю эту историю на одного ведущего артиста внутри группы.

Правило слияния выглядело простым, но одна деталь имела значение: связи между дубликатами могут образовывать цепочки.

Например:

• У артиста 1 и артиста 2 один и тот же номер телефона.

• Артист 2 и артист 3 используют один и тот же адрес электронной почты.

• Артист 1 и артист 3 не совпадают напрямую.

Они по-прежнему принадлежат к одной группе.

Это означает, что мы не можем искать только прямые пары. Нам нужно найти всю связанную группу, выбрать одного основного исполнителя и перенести все бронирования и блоки в эту основную запись.

В процессе разработки мы протестировали два алгоритма для поиска таких дублирующихся групп:

• Рекурсивный обход неориентированного графа.

• Итеративные изменения временных групп.

Рекурсивный обход неориентированного графа

В этом подходе артисты рассматриваются как узлы графа.

Атрибут соответствия создает ребро между двумя узлами. Если у двух артистов один и тот же номер телефона, они связаны. Если у двух артистов один и тот же адрес электронной почты, они тоже связаны.

После этого задача сводится к классическому поиску связанных компонентов: найти все записи, которые связаны напрямую или через другие записи.

Этап 1. Объединяем таблицу пользователей по какому-нибудь признаку

Сначала мы связываем таблицу пользователей по атрибуту, используемому для слияния.

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

Концептуально, результатом является набор ребер:

Код

WITH RECURSIVE edges AS (

SELECT id AS main FROM table

JOIN table AS child ON …

UNION ALL

SELECT id AS child FROM table

JOIN table AS main ON … )

На этом этапе база данных видит уже не только строки, но и взаимосвязи между ними.

Этап 2. Обходим граф

Затем мы выполняем рекурсивный запрос.

В первой части каждая запись в траверсе рассматривается как собственная отправная точка. Рекурсивная часть следует по ребрам от текущей дочерней записи к следующей связанной записи.

Код

connected AS (

    SELECT

        id AS master_id,

        id AS child_id

    FROM table

    UNION

    SELECT

        id AS master_id,

        id AS child_id

    FROM connected

    JOIN edges ON edges.main = connected.child_id

)

Здесь важен не точный синтаксис SQL, а скорее сам процесс.

Запрос начинается с каждой записи и проходит по всем достижимым ребрам. Если запись A связана с записью B, а запись B связана с записью C, то рекурсия в конечном итоге приводит A, B и C в одно и то же связное множество.

Это именно то, что нам нужно для цепочки дубликатов.

Этап 3. Формируем окончательные группы

После обхода нам необходимо преобразовать все найденные связи в группы.

Мы берем каждый child_id и присваиваем ему наименьший master_id из подключенного компонента.

Код

SELECT

    child_id,

    MIN(master_id) AS group_id

FROM connected

GROUP BY child_id;

Минимальный идентификатор становится идентификатором группы. Это обеспечивает стабильный идентификатор для дублирующейся группы.

После этого мы сможем решить, какой исполнитель станет основным, и переместить все связанные записи к этому исполнителю.

Преимущество этого подхода очевидно: рекурсия естественным образом обрабатывает длинные цепочки.

Если дубликаты соединены последовательно в виде A - B - C - D, то обход графа следует по всей цепочке и объединяет одну группу.

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

Итеративные изменения временных групп

Второй подход работает иначе.

Вместо рекурсивного обхода графа мы создаем временные группы и постоянно обновляем их до тех пор, пока все связанные записи не получат один и тот же group_id.

Этап 1. Создаем временную таблицу

Сначала создадим временную таблицу со следующим содержимым:

• id

• целевые поля для слияния

• group_id

На нулевой итерации group_id равен идентификатору объекта.

Код

CREATE TEMP TABLE tmp AS

SELECT

    id,

    ...,

    id AS group_id

FROM table;

Мы использовали временную таблицу, чтобы избежать блокировки основных таблиц базы данных.

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

Этап 2. Объединяем временную таблицу по каждому атрибуту слияния

Затем мы объединяем временную таблицу саму с собой по каждому целевому атрибуту.

Для каждой пары совпадающих записей мы вычисляем меньший group_id и записываем его обратно в запись с большим group_id.

Код

WITH candidates_first AS (

    SELECT

        tmp.id AS child,

        LEAST(tmp.group_id, t.group_id) AS new_group_id

    FROM tmp

    JOIN tmp AS t ON ...

    WHERE tmp.group_id > t.group_id

)

UPDATE tmp

SET group_id = candidates_first.new_group_id

FROM candidates_first

WHERE tmp.id = candidates_first.child

  AND tmp.group_id > candidates_first.new_group_id;

Затем мы повторяем ту же операцию для каждой характеристики, используемой для слияния.

Например:

• Один пропуск для номера телефона.

• Один пропуск для электронной почты.

• Один проход для другого целевого поля, если оно существует.

Идея заключается в том, что group_id постепенно приближается к наименьшему значению id внутри связанной группы.

Если A и B совпадают, B может получить group_id от A. Если B и C совпадают, C может позже получить тот же group_id. Цепочка не собирается рекурсивно. Она сжимается за счет многократных обновлений.

Этап 3. Повторяем до тех пор, пока количество измененных строк не станет равным нулю

Одной итерации может быть недостаточно.

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

Мы повторяем шаг обновления до тех пор, пока количество измененных строк не станет равным нулю.

Это условие остановки.

В этот момент все связанные дублирующиеся группы объединяются в одну группу с одним идентификатором группы (group_id).

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

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

Выбор алгоритма зависит от того, как связаны дубликаты

Здесь нет однозначного победителя.

Алгоритм зависит от того, как ваши дубликаты связаны внутри базы данных.

Мы сравнили оба подхода, потому что одно и то же правило дедупликации может приводить к совершенно разным формам данных.

Сценарий 1. Много небольших групп

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

Например:

А - В

А - В

А - В

Таких пар много, но цепочки не очень длинные.

Что работает лучше?

В данном случае лучше подходит итеративный подход с использованием временных групп.

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

Базе данных не требуется рекурсивно обходить глубокие структуры, поскольку таких глубоких структур не существует.

Что работает хуже?

Рекурсивный обход графа здесь работает хуже.

Главное его преимущество — способность находить глубокие связанные цепочки. В данном сценарии это преимущество бесполезно. Алгоритм по-прежнему несет затраты на рекурсивный обход, но данные в этом не нуждаются.

Сценарий 2. Мало групп, но очень много

В данном случае все обстоит наоборот.

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

Например:

А - В - В - Г - Е - Ф

В данном случае прямого сопоставления недостаточно. Алгоритм должен объединить всю цепочку в одну группу.

Что работает лучше?

В данном случае лучше использовать рекурсивный обход неориентированного графа.

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

В базе данных группа может выглядеть сложной, но для алгоритма это по-прежнему один связный граф.

Что работает хуже?

Итеративный подход здесь работает хуже.

Алгоритм должен передавать group_id по цепочке шаг за шагом. Большие группы означают множество промежуточных обновлений. В какой-то момент алгоритм может начать «застревать» из-за большого количества изменений внутри одной огромной группы.

Заключение

Когда мы приступили к работе, мы не знали, какой хаос нас ждет на производстве.

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

Догадываться было бессмысленно.

Мы разработали оба алгоритма и протестировали их на реальных данных.

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

Главный урок, который я извлек из этой задачи, прост: дедупликация — это не только поиск строк с одинаковым адресом электронной почты или номером телефона.

Настоящая задача состоит в том, чтобы понять, как связаны между собой записи.

• Если дубликаты образуют множество коротких цепочек, временные итеративные группы могут быть лучшим выбором.

• Если же они образуют длинные связные компоненты, рекурсивный обход графа становится более эффективным.

В нашем случае алгоритм был выбран на основе формы данных.