Привет, Хабр!
Меня зовут Сергей Аладышев, работаю системным аналитиком 10 лет, и в работе часто сталкиваюсь с задачами, решения для которых выглядят понятными, но не всегда оптимальными, а главное затратными по времени.
Сегодня хочу обсудить похожую задачу: «поиск разрывов истории записей», она же: «поиск разрывов истории SCD2 в SQL». С задачей сталкивался несколько раз, но статей с её разбором не нашел, поэтому решил, что тема актуальна.
В статье разберем два способа решения задачи и сравним их по производительности через Tensor. Расскажу о стандартном подходе с поиском разрывов в истории через оконные функции lead, lag и подходе с использованием типа данных daterange (datemultirange).
Дисклеймер:
Если найдете неоптимальные моменты, неточности или технические ошибки, буду рад обратной связи в комментариях. Постараюсь на все ответить 🙂
Поехали!
Основная часть
Требования от заказчика:
«Клиенты загрузили не все выписки, сделайте что-нибудь, чтобы было видно, что нужно дозагрузить».
Из требований имеем:
Таблица с выписками по счетам.
Выписки имеют периоды действия - дата начала, дата окончания.
Выписки привязаны к счетам.
Наличие выписки по счету за период говорит о наличии данных за этот период.
Для формирования отчетности за период нужна полнота данных за период отчетности.
Нужно проверить, что за период отчетности по всем счетам клиента есть выписки за каждый день. Если каких-то выписок нет, нужно запросить их у клиента.
Таблица выписок - acc_statement
create table
acc_statement (
id bigint,
account_id bigint,
date_begin date,
date_end date
)Таблица имеет 4 поля, которые потребуются для решения задачи:
id - идентификатор записи
account_id - идентификатор счета
date_begin - дата начала периода выписки
date_end - дата окончания периода выписки
На основе таблицы нужно формировать отчетность, для которой нужны полные данные за период, но в загруженных выписках имеем пропуски.
Пример пропущенных данных
id | account_id | date_begin | date_end |
1 | 1 | 2025-03-31 | 2025-04-10 |
2 | 1 | 2025-04-15 | 2025-04-17 |
3 | 1 | 2025-04-18 | 2025-04-30 |
В данном примере пропущен период с 11.04 по 14.04.
Важно понимать, что периоды, в которых пропущены данные, могут быть произвольными. Пропуски могут быть как в начале периода, так и в конце, выписки могут пересекаться, дублировать одинаковые периоды, либо вообще отсутствовать.
Пропуски нужно показать клиенту, чтобы он мог дозагрузить недостающие выписки.
Первой мыслью было использование lead, lag. Похожую задачу делал в хранилище данных, но такой подход занимает много времени и в целом не вызывает чувства восторга и внутреннего перфекционизма. Поэтому первым делом была предпринята попытка оптимизации (ничего неделания) и поиска другого варианта решения.
Date_begin/date_end - интервал дат, множество которых составляет массив, задача заключается в поиске разрывов в массиве дат.
К сожалению, поиск по Хабру и Stack Overflow не дал точных ответов, но в процессе поиска нашел то, что было очень похоже по описанию на мою задачу: «Диапазонные типы».
Диапазонные типы Range Types
PostgresPro: https://postgrespro.ru/docs/postgrespro/9.5/rangetypes
Официальная документация PostgreSQL: https://www.postgresql.org/docs/current/rangetypes.html
Можем переложить условия задачи на диапазонные типы:
[date_begin, date_end] - диапазон дат, каждая выписка имеет свой диапазон, объединение выписок формируют множество диапазонов.
Период формирования отчетности, проверки данных тоже является диапазоном, имеющим [date_begin, date_end].
Остается сравнить диапазон дат, получаемый из выписок, с диапазоном отчетности.
Следующим шагом нужно было найти функции и операторы для сравнения интервалов daterange.
Функции и операторы диапазонных типов
PostgresPro: https://postgrespro.ru/docs/postgresql/14/functions-range
Официальная документация PostgreSQL: https://www.postgresql.org/docs/9.3/functions-range.html
Для задачи необходимо объединить интервалы, чтобы сформировать диапазон выписок, загруженных по каждому счету, а также сравнить полученный массив с диапазоном периода отчетности - периода проверки данных.
Сложить интервалы можно с помощью функции union, +, но она не решает поставленной задачи.
+ | union | numrange (5,15) + numrange (10,20) | [5,20] |
Интервалов выписок могло быть произвольное количество, а значит нужно найти агрегатную функцию, позволяющая объединять интервалы.
Перебора sum, agg и похожих вариантов ничего не дал, поэтому пришлось обратиться к документации.
Была найдена функция range_agg:
range_agg ( value anyrange ) → anymultirange
range_agg ( value anymultirange ) → anymultirange
Computes the union of the non-null input values.
Функция позволяет объединить несколько интервалов в один. Из особенностей использования - результатом выполнения функции является тип multirange - мультиинтервал.
Пробуем использовать range_agg для объединения диапазонов существующих выписок:
datemultirange (range_agg (daterange (date_begin, date_end))) as account_daterangeПоскольку основная таблица была создана в БД, и изменять типы данных и делать миграции не было сильного желания, было принято решение создать вью, которая будет агрегировать периоды загруженных выписок по каждому счету:
acc_interval_view
CREATE
OR REPLACE VIEW public.acc_interval_view AS
SELECT
account_id,
range_agg(daterange(date_begin, (date_end + '1 day'::interval)::date)) AS account_daterange
FROM
acc_statement
GROUP BY
account_id;Вью построена, для получения разрывов используем запрос
SELECT
account_id
FROM
acc_interval_view
WHERE (datemultirange('{[2025-04-01, 2025-05-01)}') <@ account_daterange) is falseОписанный выше запрос является решением нашей задачи.
Для сравнения приведу ниже решение этой же задачи с использованием оконных функций lead, lag.
Метод с использованием Lead, Lag и CTE
Для понимания отличий и сравнения реализаций решил повторить реализацию с Lead, Lag, чтобы было понимание контекста.
Перед тем как решать задачу нужно понять, что из себя представляют разрывы в истории, разделить разрывы истории на группы, написать на каждую из групп соответствующие ей условия запроса.
В ходе анализа были выявлены следующие кейсы разрывов истории:
Разрыв между последовательными записями, date_end_prev + 1 != date_begin_next
id | account_id | date_begin | date_end |
1 | 1 | 2025-03-31 | 2025-04-10 |
2 | 1 | 2025-04-15 | 2025-04-17 |
Разрыв 11.04.2025 - 14.04.2025
2. Первая запись появилась внутри периода, но дата начала первой записи больше даты начала периода
id | account_id | date_begin | date_end |
1 | 1 | 2025-04-10 | 2025-04-14 |
2 | 1 | 2025-04-15 | 2025-04-17 |
Если период проверки с 01.04.2025, интервал с 01.04.2025 по 09.04.2025 пропущен, при этом проверка из п1 его не найдет.
3. Последняя запись закончилась раньше окончания периода проверки
id | account_id | date_begin | date_end |
1 | 1 | 2025-04-01 | 2025-04-14 |
2 | 1 | 2025-04-15 | 2025-04-27 |
Если период проверки до 30.04.2025, интервал с 28.04.2025 по 30.04.2025 пропущен.
При этом в пунктах 2 и 3 важно учитывать, что для первой и последней записи в периоде lead и lag будут иметь значение NULL, поэтому важно не забывать использовать coalesce.При этом при использовании coalesce важно помнить, что работаем с типом date, поэтому значение не подойдет.
Для обработки кейсов, описанных выше, получаем запрос
-- используем cte для возможности использования результатов оконных функций в условиях след запроса
WITH
cte AS (
SELECT
id,
account_id,
date_begin,
date_end,
-- получение даты начала действия следующей записи для проверки наличия разрыва с предыдущей
coalesce(
LEAD (date_begin) OVER (
PARTITION BY
account_id
ORDER BY
date_begin
),
date_end
) AS next_date_begin,
-- получение даты окончания действия предыдущей записи, для проверки наличия разрыва с предыдущей
-- coalesce(lag(date_end) OVER (PARTITION BY account_id ORDER BY date_begin),date_begin) AS prev_date_end,
-- получение минимального date_begin для проверки, что он меньше или равен дате начала периода
MIN(date_begin) over (
partition by
account_id
) as min_date_begin,
-- получение максимального date_end для проверки, что он больше или равен дате окончания периода
MAX(date_end) over (
partition by
account_id
) as max_date_end
FROM
acc_statement
)
SELECT distinct
account_id
FROM
cte
WHERE
(
-- проверка наличия разрывов между записями, п1
(date_end < (next_date_begin - interval '1 day')) -- if true is error
-- проверка наличия разрывов между записями, п1, закомментировал, можно использовать lead, можно lag, кому как удобнее.
-- OR (prev_date_end < (date_begin - interval '1 day')) -- if true is error
-- проверка, что дата начала меньше или равна началу периода, п2
OR (min_date_begin) > '2025-04-01' -- if true is error
-- проверка, что дата окончания больше или равна окончанию периода, п3
OR (max_date_end) < '2025-04-30' -- if true is error
)По сравнению с daterange сам текст запроса получается больше, но нужно проверить производительность.
Проверка производительности или перформанса запросов
1. Критерии проверки
Имеем два способа выполнения одной и той же задачи, осталось их сравнить.
Для выполнения сравнения были нагенерированы данные (найден друг DBA, у которого была развернута БД и было пару часов свободного времени на помощь в тестировании), выполнены запросы и проанализированы на производительность.
В ходе результатов тестирование нужно сравнить:
Время выполнения запросов
Использование ресурсов
Выявить особенности использования варианта с оконными функциями и типа daterange
Имеем два способа выполнения одной и той же задачи, осталось их сравнить.
Генерация данных
Для тестирования запроса нужны данные, с их создания и начнем.
Первый шаг - генерация данных.
Чтобы тестирование было объективным, набор данных было решено делать приближенным по объемам к используемым в реальном решении. Качество данных не критично, главное - получить промежутки, полностью покрываемые записями, а также промежутки, имеющие разрывы.
INSERT INTO
acc_statement
SELECT
generate_series (1, 1000000) AS id,
generate_series (1000000, 2000000) AS account_id,
now () + interval '1 day' + ((random () -0.5) * INTERVAL '30 days'),
now () + (random () * INTERVAL '30 days');
INSERT INTO
acc_statement
SELECT
generate_series (1000000, 2000000) AS id,
generate_series (1000000, 2000000) AS account_id,
now () + interval '1 day' + ((random () -0.5) * INTERVAL '30 days'),
now () + (random () * INTERVAL '30 days');При генерации часть записей получились ошибочными: date_end < date_begin. В реальных выписках таких данных нет, поэтому было принято решение их удалить. Если рассматриваем задачу с поиском разрывов в истории, в теории при ошибках ETL описанные выше кейсы возможны, их нужно учесть в запросах. В данной задаче для упрощения данные кейсы не учитываем.
--- удаляем ошибки
delete from acc_statement
where
date_begin > date_end
-- удаляем сгенерированные записи, у которых date_begin > date_endПосле удаления у нас осталось 1,7 млн записей, которых было достаточно для тестирования. Данные сгенерированы. Можно приступать к тестированию.
Тестирование
Имеем вью, таблицу с данными и два запроса, производительность которых нужно протестировать. Для тестирования будем использовать tensor.
Запрос с использованием Lead, Lag
WITH
cte AS (
SELECT
id,
account_id,
date_begin,
date_end,
coalesce(
LEAD (date_begin) OVER (
PARTITION BY
account_id
ORDER BY
date_begin
),
date_end
) AS next_date_begin,
-- coalesce(lag(date_end) OVER (PARTITION BY account_id ORDER BY date_begin),date_begin) AS prev_date_end,
MIN(date_begin) over (
partition by
account_id
) as min_date_begin,
MAX(date_end) over (
partition by
account_id
) as max_date_end
FROM
acc_statement
)
SELECT distinct
account_id
FROM
cte
WHERE
(
(date_end < (next_date_begin - interval '1 day')) -- if true is error
-- OR (prev_date_end < (date_begin - interval '1 day')) -- if true is error
OR (min_date_begin) > '2025-04-01' -- if true is error
OR (max_date_end) < '2025-04-30' -- if true is error
)Выполняем запрос в БД. Результат 2,4 сек на 1,7 млн записей.
Запрос с использованием daterange
Пришла очередь выполнения запроса с новым способом реализации.
Даже если будет медленно, по крайней мере, выглядит красивее, меньше букв - оптимизация.
SELECT
account_id
FROM
acc_interval_view
WHERE (datemultirange('{[2025-04-01, 2025-05-01)}') <@ account_daterange) is falseВыполняем запрос в БД. Результат 2,1 сек.
Для чистоты эксперимента проверим производительность запросов на большем объеме данных. Результаты зафиксировал в таблице. Результаты выполнения запросов и планы в Tensor.
Подход, количество записей | 1,7 млн | 8,6 млн | 17 млн |
view, daterange | 2,1 сек | 11 сек | 22,6 сек |
table, lead/lag | 2,4 сек | 10,5 сек | 22,9 сек |
Анализ планов запроса в Tensor
Для дальнейшего анализа планы запросов были скопированы в Tensor. В ходе анализа больших отличий между вариантами запросов выявлено не было.
В запросе с daterange меньше операций, в lead, lag больше, но в плане затрат ресурсов запросы +/- идентичны.
Оба запроса потребляют большое количество памяти, поэтому при её нехватке в процессе выполнения может быть использован жесткий диск. При большом количестве данных производительность запроса начинает зависеть от скорости записи/чтения жесткого диска.
Вывод
В статье разобрали два подхода к решению одной задачи.
Однозначно сказать, какой способ лучше, на мой взгляд, нельзя. Каждый из методов имеет свои плюсы и минусы. Используйте тот, который нравится больше.
Спасибо за уделенное время. Буду рад обратной связи в комментариях!
Ограничения
Важно понимать, что описанный выше тест не исчерпывающий. Для упрощения запросы из статьи показывают признак полноты выписок за период.
Для получения списка недостающих интервалов необходимо вместо функции сравнения использовать функцию разности интервалов, а также обрабатывать кейсы с пустым и заполненным интервалами.
При использовании lead/lag вместо группировки селекта списка счетов вернуть все записи, которые проверка посчитала ошибочными - добавить еще одну cte.
Также, возможно, исключение из запроса min, max и вынесение их в отдельную cte увеличит производительность запроса lead/lag, но это не точно. Если интересна данная тема, могу сделать более подробный разбор в следующей статье.
Также можно попробовать решить задачу с использованием операторов justify, рассчитывая количество дней/часов в интервалах:
Adjust interval, converting 30-day time periods to months
|
Adjust interval, converting 24-hour time periods to days
|
Adjust interval using
|
