Блог товарища Nihirash

17.04.2018

Вы все еще ищете разрывы в ID-шниках с помощью LEFT JOIN?

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

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

Моим "дембельским аккордом" на прошлой работе была как раз задача поиска необработанных событий(гарантированная доставка сообщений) - и одной из главных проблем было выявить сразу весь диапазон потерянных событий.

Что же я сделал?

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

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

Решение "в лоб" пришедшее мне - это LEFT JOIN таблицы саму на себя, и если id+1 не существует - то это потерянный элемент то его нужно обработать. Звучит просто и здорово, но разрыв может быть на 2, 10 или даже 50 событий, и чтобы получить все потерянные события нам необходимо повторять процедуру до тех пор, пока не перезапросим все элементы.

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

Итоговое решение - замечательный SQL-запрос, который позволит за указанное время найти все разрывы и перезапросить только отсутствующие события:

SELECT external_id+1 as start_interval, next_external_id-1 as finish_interval
FROM (
      SELECT external_id, LEAD(external_id) OVER (ORDER BY external_id) as next_external_id
      FROM granted_delivery where source = 1 
           and timestamp > '2018-04-10 14:40' and timestamp < '2018-04-10 14:55'
    ) T
WHERE external_id+1 <> next_external_id

Решение было создано для PostgreSQL, возможно, Ваша БД не имеет функции LEAD, однако, думаю, что подобное решение можно использовать как отправную точку и для других баз данных.