Gaps and islands: последовательности дат

Определение непрерывных последовательностей календарных дат

В аналитических задачах часто требуется сгруппировать события пользователя в непрерывные периоды активности: серии ежедневных тренировок, непрерывные дни заходов на платформу или периоды аренды оборудования. Такой класс задач называют задачей об островах и разрывах (gaps and islands).

Островом (island) называют непрерывную последовательность календарных дней, в которой каждая следующая активность происходит строго на следующий календарный день: разница между соседними днями равна ровно 1 дню. Разрыв (gap) возникает в тот момент, когда между соседними днями активности пользователя проходит больше одного календарного дня.

Подготовим таблицу activity_log, содержащую записи действий двух пользователей:

CREATE TABLE activity_log (
  log_id INTEGER PRIMARY KEY,
  user_id INTEGER NOT NULL,
  activity_date TEXT NOT NULL
);

INSERT INTO activity_log (log_id, user_id, activity_date) VALUES
(1, 101, '2024-03-01'),
(2, 101, '2024-03-01'),
(3, 101, '2024-03-02'),
(4, 101, '2024-03-05'),
(5, 101, '2024-03-06'),
(6, 102, '2024-03-10'),
(7, 102, '2024-03-12'),
(8, 102, '2024-03-13');

Посмотрим на записи пользователя 101:

SELECT log_id, user_id, activity_date
FROM activity_log
WHERE user_id = 101
ORDER BY activity_date, log_id;

log_id	user_id	activity_date
1	101	2024-03-01
2	101	2024-03-01
3	101	2024-03-02
4	101	2024-03-05
5	101	2024-03-06

В хронологии пользователя 101 видно две серии:

• Первая серия: 2024-03-01 и 2024-03-02. Дни идут подряд.
• Разрыв: между 2024-03-02 и 2024-03-05 прошло 3 дня, непрерывность прервана.
• Вторая серия: 2024-03-05 и 2024-03-06. Дни снова идут подряд.

Правило островов требует строго соблюдать единицу измерения: разрыв рассчитывается по целым календарным дням формата YYYY-MM-DD, а не по часам или минутам. Если разрыв превышает 1 календарный день, предыдущая серия завершается и начинается новая.

Дедупликация до уровня суток и ловушка повторных событий

В реальных логах один пользователь может совершить несколько действий за один и тот же день. В таблице activity_log для пользователя 101 присутствуют строки с log_id = 1 и log_id = 2, обе от 2024-03-01.

Попробуем сразу применить функцию LAG(), чтобы вычислить разницу в днях между строками:

SELECT
  log_id,
  user_id,
  activity_date,
  LAG(activity_date) OVER (PARTITION BY user_id ORDER BY activity_date, log_id) AS prev_date,
  CAST(julianday(activity_date) - julianday(LAG(activity_date) OVER (PARTITION BY user_id ORDER BY activity_date, log_id)) AS INTEGER) AS diff_days
FROM activity_log
WHERE user_id = 101
ORDER BY activity_date, log_id;

log_id	user_id	activity_date	prev_date	diff_days
1	101	2024-03-01	NULL	NULL
2	101	2024-03-01	2024-03-01	0
3	101	2024-03-02	2024-03-01	1
4	101	2024-03-05	2024-03-02	3
5	101	2024-03-06	2024-03-05	1

В строке с log_id = 2 предыдущей датой становится 2024-03-01, а разница diff_days оказывается равной 0. Если алгоритм проверяет непрерывность условием diff_days = 1, то второй лог за тот же день ошибочно распознается как разрыв и разорвет непрерывный остров на две неверные части.

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

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

WITH dedup AS (
  SELECT DISTINCT user_id, activity_date
  FROM activity_log
)
SELECT user_id, activity_date
FROM dedup
ORDER BY user_id, activity_date;

Схлопывание через DISTINCT (или GROUP BY user_id, activity_date) гарантирует, что каждая дата для каждого пользователя встречается ровно один раз, исключая появление нулевых шагов diff_days = 0.

Шаблон LAG, разметка разрывов и нарастающая сумма серий

После приведения данных к одной строке на (user_id, activity_date) разметка серий строится по многоэтапной схеме:

1. Найти предыдущую активную дату пользователя с помощью LAG(activity_date) OVER (PARTITION BY user_id ORDER BY activity_date).
2. Выставить бинарный маркер is_new_series: флаг равен 1, если предыдущей даты нет (prev_date IS NULL) или разница между датами строго больше 1 дня (diff > 1). В противном случае шаг равен ровно 1 дню, разрыва нет, и флаг равен 0.
3. Сформировать идентификатор серии series_id как нарастающую сумму маркеров: SUM(is_new_series) OVER (PARTITION BY user_id ORDER BY activity_date ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW).

В SQLite оконное выражение нельзя сразу подставить в WHERE или использовать его псевдоним на том же уровне SELECT. Кроме того, оконную функцию нельзя вложить в другую оконную функцию: нельзя вычислить SUM(CASE WHEN LAG(...) ...) внутри одного блока. Поэтому каждый этап выносится в отдельное общее табличное выражение (CTE).

Посмотрим на вычисление маркера is_new_series:

WITH dedup AS (
  SELECT DISTINCT user_id, activity_date
  FROM activity_log
),
lagged AS (
  SELECT
    user_id,
    activity_date,
    LAG(activity_date) OVER (PARTITION BY user_id ORDER BY activity_date) AS prev_date
  FROM dedup
)
SELECT
  user_id,
  activity_date,
  prev_date,
  CASE
    WHEN prev_date IS NULL OR CAST(julianday(activity_date) - julianday(prev_date) AS INTEGER) > 1 THEN 1
    ELSE 0
  END AS is_new_series
FROM lagged
ORDER BY user_id, activity_date;

user_id	activity_date	prev_date	is_new_series
101	2024-03-01	NULL	1
101	2024-03-02	2024-03-01	0
101	2024-03-05	2024-03-02	1
101	2024-03-06	2024-03-05	0
102	2024-03-10	NULL	1
102	2024-03-12	2024-03-10	1
102	2024-03-13	2024-03-12	0

Разность дат рассчитывается через CAST(julianday(activity_date) - julianday(prev_date) AS INTEGER). Значение julianday() переводит строковую дату ISO-8601 в непрерывную шкалу юлианских дней, а разность двух таких чисел возвращает количество суток между ними.

Теперь сложим маркеры нарастающим итогом. Каждая единица в маркере увеличивает сумму на 1, а каждый ноль оставляет сумму прежней. В результате все дни одной непрерывной цепочки получают одно и то же число series_id:

WITH dedup AS (
  SELECT DISTINCT user_id, activity_date
  FROM activity_log
),
lagged AS (
  SELECT
    user_id,
    activity_date,
    LAG(activity_date) OVER (PARTITION BY user_id ORDER BY activity_date) AS prev_date
  FROM dedup
),
marked AS (
  SELECT
    user_id,
    activity_date,
    CASE
      WHEN prev_date IS NULL OR CAST(julianday(activity_date) - julianday(prev_date) AS INTEGER) > 1 THEN 1
      ELSE 0
    END AS is_new_series
  FROM lagged
)
SELECT
  user_id,
  activity_date,
  is_new_series,
  SUM(is_new_series) OVER (
    PARTITION BY user_id
    ORDER BY activity_date
    ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
  ) AS series_id
FROM marked
ORDER BY user_id, activity_date;

user_id	activity_date	is_new_series	series_id
101	2024-03-01	1	1
101	2024-03-02	0	1
101	2024-03-05	1	2
101	2024-03-06	0	2
102	2024-03-10	1	1
102	2024-03-12	1	2
102	2024-03-13	0	2

В оконной функции обязательно задана явная физическая рамка ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW. Она складывает физические строки строго по текущую позицию, изолируя расчет каждого пользователя внутри окна PARTITION BY user_id.

Агрегация серий и пошаговый контроль границ

Когда каждой строке присвоен series_id, задача сводится к обычной группировке GROUP BY user_id, series_id. Для каждой серии вычисляются границы и длина:

• Дата начала серии: MIN(activity_date).
• Дата окончания серии: MAX(activity_date).
• Длина серии в днях: COUNT(*).

Выполним полный запрос для всех пользователей таблицы:

WITH dedup AS (
  SELECT DISTINCT user_id, activity_date
  FROM activity_log
),
lagged AS (
  SELECT
    user_id,
    activity_date,
    LAG(activity_date) OVER (PARTITION BY user_id ORDER BY activity_date) AS prev_date
  FROM dedup
),
marked AS (
  SELECT
    user_id,
    activity_date,
    CASE
      WHEN prev_date IS NULL OR CAST(julianday(activity_date) - julianday(prev_date) AS INTEGER) > 1 THEN 1
      ELSE 0
    END AS is_new_series
  FROM lagged
),
grouped_series AS (
  SELECT
    user_id,
    activity_date,
    SUM(is_new_series) OVER (
      PARTITION BY user_id
      ORDER BY activity_date
      ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
    ) AS series_id
  FROM marked
)
SELECT
  user_id,
  series_id,
  MIN(activity_date) AS start_date,
  MAX(activity_date) AS end_date,
  COUNT(*) AS days_count
FROM grouped_series
GROUP BY user_id, series_id
ORDER BY user_id, start_date;

user_id	series_id	start_date	end_date	days_count
101	1	2024-03-01	2024-03-02	2
101	2	2024-03-05	2024-03-06	2
102	1	2024-03-10	2024-03-10	1
102	2	2024-03-12	2024-03-13	2

Разберем полученный результат по пользователям:

• Пользователь 101: даты 2024-03-01 (дубль схлопнут) и 2024-03-02 сформировали серию 1 длиной 2 дня. Затем разрыв в 3 дня сменил маркер на 1, образовав серию 2 для дат 2024-03-05 и 2024-03-06 длиной 2 дня.
• Пользователь 102: дата 2024-03-10 стоит изолированно. Следующая активность зафиксирована только 2024-03-12. Одиночный день 2024-03-10 образует валидную серию 1 длиной days_count = 1, где start_date и end_date совпадают. Дни 2024-03-12 и 2024-03-13 объединяются в серию 2 длительностью 2 дня.

Длину серии рассчитывает COUNT(*). Использовать для длины вычитание дат MAX(activity_date) - MIN(activity_date) нельзя: для одиночного дня 2024-03-10 разность дат вернула бы 0, тогда как пользователь был активен ровно 1 день.