re:re:actable
Урок 083 минуты чтения

Как найти серии и пропуски - gaps and islands

На этой странице
Кратко

Gaps and islands — класс задач про непрерывные серии («острова») и разрывы между ними: дни подряд, когда пользователь заходил (streak), периоды непрерывной работы сервиса, пропущенные номера счетов. Классический приём для островов — разность двух нумераций: значение последовательности (дата, номер) минус row_number() по тому же порядку остаётся постоянным внутри непрерывной серии и меняется при разрыве. Эта константа становится ключом группировки. Альтернатива — lag + флаг «началась новая серия» + накопительная сумма флагов. Разрывы находят через lead: если следующее значение больше текущего + 1, между ними пропуск.

Вопрос

Как найти непрерывные серии и пропуски в данных?

Пропуски в последовательности

-- пропущенные номера счетов
SELECT number + 1 AS gap_start, next_number - 1 AS gap_end
FROM (
  SELECT number, lead(number) OVER (ORDER BY number) AS next_number
  FROM invoices
) t
WHERE next_number > number + 1;
numbers: 1, 2, 3, 7, 8, 10
gap_start | gap_end
4         | 6
9         | 9

Острова: разность нумераций

-- серии дней подряд с активностью для каждого пользователя
WITH days AS (
  SELECT DISTINCT user_id, created_at::date AS day
  FROM events
),
grouped AS (
  SELECT user_id, day,
         day - (row_number() OVER (PARTITION BY user_id ORDER BY day))::int AS grp
  FROM days
)
SELECT user_id, min(day) AS streak_start, max(day) AS streak_end, count(*) AS streak_days
FROM grouped
GROUP BY user_id, grp
ORDER BY user_id, streak_start;

Почему работает:

day        | row_number | day - rn
2026-10-01 | 1          | 2026-09-30
2026-10-02 | 2          | 2026-09-30   ← серия
2026-10-03 | 3          | 2026-09-30
2026-10-07 | 4          | 2026-10-03   ← новая серия
2026-10-08 | 5          | 2026-10-03

Внутри серии и дата, и номер растут на 1, поэтому разность постоянна.

Острова: флаг начала + накопительная сумма

-- периоды, когда статус сервиса не менялся
WITH flagged AS (
  SELECT checked_at, status,
         CASE WHEN status = lag(status) OVER (ORDER BY checked_at) THEN 0 ELSE 1 END AS is_new
  FROM health_checks
),
numbered AS (
  SELECT *, sum(is_new) OVER (ORDER BY checked_at) AS island_id
  FROM flagged
)
SELECT island_id, status, min(checked_at) AS from_at, max(checked_at) AS to_at
FROM numbered
GROUP BY island_id, status
ORDER BY from_at;

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

Текущий streak

-- длина текущей серии пользователя (последняя серия, которая заканчивается сегодня или вчера)
... WHERE streak_end >= current_date - 1
ORDER BY streak_end DESC LIMIT 1;

Частые ошибки

  • Не убрать дубли дней (DISTINCT) — разность нумераций ломается.
  • Забыть PARTITION BY user_id.
  • Таймзона: «день» пользователя считать по UTC.
  • Решать задачу циклом в приложении по всей истории событий.

Что важно помнить

  • Пропуски — lead(x) > x + 1.
  • Острова с шагом 1 — x - row_number() как ключ группы.
  • Острова по значению — флаг lag + sum флагов.

Мини-шпаргалка

  • lead(n) OVER (ORDER BY n) — следующий элемент.
  • day - row_number() OVER (ORDER BY day)::int — ключ серии.
  • sum(is_new) OVER (ORDER BY t) — номер острова.
  • GROUP BY ключ → min, max, count.

Документация

PostgreSQL: Window Functions.

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

Поиск

Поиск по урокам