Урок 12.8 · Время чтения: ~7 мин

Пропуски и острова (gaps and islands) — семейство задач о последовательностях: найти участки идущих подряд значений (острова) и дыры между ними (пропуски). Типичные вопросы: «самая длинная серия входов каждого пользователя», «периоды, когда датчик присылал данные», «пропущенные номера счетов». Это любимый вопрос продвинутого уровня на собеседованиях по SQL. В этом уроке вы изучите приём с ROW_NUMBER, который группирует даты подряд в острова, найдёте пропуски с помощью LEAD и посчитаете самую длинную серию каждого клиента.

Пропуски и острова в SQL

Остров — это участок значений без дыр: дни подряд, числа подряд. Пропуск — участок недостающих значений между двумя островами. Сложность в том, что SQL работает с множествами, а «подряд» — это отношение между строками. Оконные функции превращают задачу в короткий запрос.

Примеры работают на учебной базе Sakila (MySQL 8.0). Аренды в Sakila записаны недельными периодами, поэтому острова хорошо видны.

Главный приём: дата минус номер строки

Возьмите отсортированный список различных дат и пронумеруйте его. Внутри участка дней подряд дата растёт на один день, а номер строки — на единицу, поэтому дата − номер строки остаётся постоянной. Когда день пропущен, дата прыгает вперёд, а номер строки — нет, и разность меняется. Эта разность и есть ключ острова.

Посмотрим на дни аренды клиента 42 до 13 июля 2005 года:

WITH customer_days AS (
    SELECT DISTINCT DATE(rental_date) AS rental_day
    FROM rental
    WHERE customer_id = 42
      AND rental_date < '2005-07-13'
)
SELECT rental_day,
       ROW_NUMBER() OVER (ORDER BY rental_day) AS rn,
       DATE_SUB(rental_day, INTERVAL ROW_NUMBER() OVER (ORDER BY rental_day) DAY) AS island_key
FROM customer_days
ORDER BY rental_day;

Результат: 9 дней, образующих 4 острова; например, у дней с 9 по 12 июля ключ 2005-07-03.

Сам ключ ничего не означает; важно лишь, что он одинаков внутри острова и различается между островами. 8 июля пропущено, поэтому 7 июля образует отдельный остров.

Острова: периоды с арендами

Теперь сгруппируйте по ключу и возьмите первый и последний день каждого острова:

WITH rental_days AS (
    SELECT DISTINCT DATE(rental_date) AS rental_day
    FROM rental
),
grouped AS (
    SELECT rental_day,
           DATE_SUB(rental_day, INTERVAL ROW_NUMBER() OVER (ORDER BY rental_day) DAY) AS island_key
    FROM rental_days
)
SELECT MIN(rental_day) AS island_start,
       MAX(rental_day) AS island_end,
       COUNT(*) AS days
FROM grouped
GROUP BY island_key
ORDER BY island_start;

Результат: 6 островов: пять периодов по 8 дней подряд в 2005 году и один день — 14 февраля 2006 года.

DISTINCT в первом CTE обязателен. Если бы один день встретился дважды, он получил бы два номера строки, и разность разорвала бы остров. Для последовательностей целых чисел используйте value - ROW_NUMBER() точно так же.

Пропуски: периоды без аренд

Для пропусков сравните каждый день со следующим с помощью LEAD(). Если следующий день наступает позже чем через один день, между ними есть дыра:

WITH rental_days AS (
    SELECT DISTINCT DATE(rental_date) AS rental_day
    FROM rental
),
with_next AS (
    SELECT rental_day,
           LEAD(rental_day) OVER (ORDER BY rental_day) AS next_day
    FROM rental_days
)
SELECT DATE_ADD(rental_day, INTERVAL 1 DAY) AS gap_start,
       DATE_SUB(next_day, INTERVAL 1 DAY) AS gap_end,
       DATEDIFF(next_day, rental_day) - 1 AS missing_days
FROM with_next
WHERE DATEDIFF(next_day, rental_day) > 1
ORDER BY gap_start;

Результат: 5 пропусков: четыре по 13 дней между периодами 2005 года и один на 174 дня — с 24 августа 2005 года по 13 февраля 2006 года.

Тот же запрос с числами находит пропущенные id, например номера счетов: замените DATEDIFF(next_day, rental_day) на next_id - id.

Серии для каждого клиента

Вариант для собеседования: «найдите для каждого клиента самую длинную серию дней аренды подряд». Добавьте PARTITION BY customer_id, чтобы у каждого клиента была своя нумерация, затем агрегируйте дважды: острова по клиенту, а затем самый длинный остров:

WITH customer_days AS (
    SELECT DISTINCT customer_id, DATE(rental_date) AS rental_day
    FROM rental
),
grouped AS (
    SELECT customer_id, rental_day,
           DATE_SUB(rental_day, INTERVAL ROW_NUMBER() OVER (
               PARTITION BY customer_id ORDER BY rental_day) DAY) AS island_key
    FROM customer_days
),
streaks AS (
    SELECT customer_id, island_key, COUNT(*) AS streak_days
    FROM grouped
    GROUP BY customer_id, island_key
)
SELECT customer_id, MAX(streak_days) AS longest_streak
FROM streaks
GROUP BY customer_id
ORDER BY longest_streak DESC, customer_id
LIMIT 5;

Результат: клиенты 42, 181, 290, 306 и 373 брали фильмы 8 дней подряд; всего серия в 8 дней есть у 10 клиентов.

Самая длинная возможная серия здесь — 8 дней, потому что сам прокат работал периодами по 8 дней. На реальных данных об активности тот же запрос находит серии входов, рабочие дни подряд или периоды непрерывной передачи данных с датчика.

Практика

• Задача Gap & Islands

Ключевые выводы:

• Острова — участки значений подряд; пропуски — недостающие участки между ними.
• В участке дат подряд date - ROW_NUMBER() постоянна: группируйте по ней, чтобы получить острова.
• Сначала уберите повторы с помощью DISTINCT, иначе один день получит несколько номеров строк и острова разорвутся.
• LEAD() сравнивает каждое значение со следующим и находит пропуски.
• PARTITION BY даёт каждому объекту свои острова; вторая агрегация находит самую длинную серию.

Часто задаваемые вопросы

Что такое задача gaps and islands в SQL?

Это класс задач о последовательностях значений: острова — участки идущих подряд значений (дней, чисел) без дыр, пропуски — недостающие значения между ними. Примеры: серии входов, непрерывные периоды активности, пропущенные номера счетов.

Как найти дни подряд в SQL?

Пронумеруйте различные даты с помощью ROW_NUMBER() OVER (ORDER BY day) и вычтите из даты это число дней. У дней подряд результат одинаковый, поэтому GROUP BY по нему с MIN(day), MAX(day) и COUNT(*) даёт каждый участок.

Как найти пропущенные даты или номера в SQL?

С помощью LEAD(value) OVER (ORDER BY value) получите следующее значение для каждой строки и оставьте строки, где разница больше одного шага. Пропуск длится от значения плюс один шаг до следующего значения минус один шаг. Чтобы перечислить каждую пропущенную дату, присоедините сгенерированный календарь (урок 6.6).

Как найти самую длинную серию для каждого пользователя?

Сгруппируйте дни подряд в острова по каждому пользователю с помощью ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY day), посчитайте дни в каждом острове и возьмите MAX этих значений по пользователю.