Знакомая боль: пользователи опечатываются при регистрации, а база данных медленно, но верно превращается в хаос. На одном из проектов в поддержку артистов мы столкнулись с этим лицом к лицу.
Раньше карточки артистов создавались автоматически прямо из заявок на выступления. В итоге мы получали гору дубликатов с одинаковыми почтами и телефонами. Администрировать такую базу и координировать выступления стало безумно сложно.
Конечно, правильнее всего - пресекать появление дублей еще на входе, но нам нужно было оперативно перебирать систему на ходу и работать с тем, что уже накопилось в проде.
Что мы придумали:
Решили провести «склейку» профилей. Но просто удалить лишнее было нельзя - за каждым дублем тянулся шлейф из бронирований площадок и блокировок. Наша задача была перенести всю эту историю на одного, «главного» артиста в группе.
Правило склейки сделали простым, но учли важную деталь - связи могут тянуться цепочкой. Например, если у первого и второго артиста совпал телефон, а у второго и третьего - почта, то вся троица объединяется в одну группу. Дальше мы определяем одного "главного" и аккуратно переносим все бронирования на него
В процессе разработки решения было опробовано два алгоритма поиска этих самых дублей:
🔂 Рекурсивный обход неориентированного графа
↪️ Итеративные изменения временных групп
Рекурсивный обход неориентированного графа реализуется следующим образом:
Соединяем таблицу пользователей по какому-либо признаку:
Скрытый текст
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 … )
Обход графа
Скрытый текст
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
)
Получение групп
Скрытый текст
SELECT child_id, MIN(master_id) AS group_id FROM connected
GROUP BY group_id
Итеративные изменения временных групп же реализуются следующим образом:
Создаем временную таблицу, с id, целевыми характеристиками для склейки и с полем group_id, которая на 0-ой итерации будет равно id объекта:
Скрытый текст
CREATE TEMP TABLE tmp AS
SELECT id, … ,id AS group_id FROM table
Временная таблица нужна для избежание блокировок базы.
И соединяем и таблицу по каждому целевому для склейки признаку:
Скрытый текст
И так далее с каждой характеристикой.
Повторяем шаг 3, пока количество измененных строк не станет равным нулю.
Выбор алгоритма полностью зависит от того, как именно ваши дубли «сцепились» друг с другом в базе. Мы сравнили два подхода и делимся выводами, чтобы вы не тратили время на лишние тесты.
Сценарий 1: Много мелких групп (короткие цепочки связей типа А - Б)
Что лучше: итеративный подход со временными группами. Он за один проход обрабатывает сразу по одной связи во всех группах - это быстро и эффективно.
Что хуже: рекурсивный обход графа. Тут он будет буксовать, потому что его сила в поиске глубоких связей, которых здесь просто нет.
Сценарий 2: Мало групп, но они огромные (длинные цепочки типа А - Б - В - Г...)
Что лучше: рекурсивный обход неориентированного графа. За счет рекурсии он быстро и красиво собирает одну сложную группу целиком.
Что хуже: итеративный подход. Он захлебнется на массовых изменениях внутри огромных групп.
Как мы проверяли это на практике
Когда мы работали над проектом, мы не знали заранее, какой именно хаос ждет нас на проде. Гадать не стали - просто написали оба алгоритма и протестировали их на реальных данных.
Для нашей структуры данных победителем вышел итеративный подход - он сработал быстрее и стабильнее.
А вы сталкивались с подобным выбором? Расскажите в комментариях, какой алгоритм обычно вытягивает ваши проекты?
Автор статьи: Евгений Гришагин, бэкенд-разработчик в “Исходном Коде”
