🏝️ Решаем очень сложную SQL-задачу об островах и проливах
Пошаговый разбор решения SQL-задачи об островах и проливах на примере базы данных Sakila с использованием оконных функций и CTE.
Задача об островах и проливах – это классическая задача в SQL, часто используемая для оценки навыков программиста в работе с базами данных. Суть задачи заключается в том, чтобы в таблице, содержащей данные о событиях и их временных интервалах, объединить отдельные записи в непрерывные интервалы, представляющие собой «острова» (периоды, когда происходили события) и «проливы» (промежутки между ними).
Пример задачи
Рассмотрим задачу на примере задания с сайта SQLTest.online. Все задания на сайте ранжированы по сложности на основе оценок зарегистрированных пользователей, и эта задача в числе немногих имеет оценку «Очень сложно».
Условия задачи
Имеется таблица rental, в которой хранятся записи о фильмах, взятых напрокат пользователями сервиса Sakila. Для решения задачи нам понадобятся только три колонки из этой таблицы:
customer_idrental_datereturn_date
Задача
Задача состоит в следующем:
Для клиента MARY SMITH (customer_id = 1) найдите все периоды, когда у нее был хотя бы один взятый напрокат фильм.
Статья по теме
Решение
1. Извлечение записей по заданному клиенту
Начнем с простого – напишем запрос для извлечения всех записей по данному клиенту:
select
customer_id,
rental_date as start_date,
return_date as finish_date
from rental
where customer_id = 1
Этот запрос вернет нам 32 записи о фильмах, арендованных MARY SMITH.
2. Нумерация строк и определение «проливов»
Воспользуемся оконной функцией row_number(),
Еще одна оконная функция – lag()return_date
select
customer_id,
row_number() over(order by return_date, rental_date) as row_num,
rental_date as start_date,
return_date as finish_date,
lag(return_date, 1) over (order by return_date, rental_date) as prev_return_date
from rental
where customer_id = 1
order by row_num;
Итак, если вы выполните этот запрос здесь, то получите следующий результат:
|-------------|---------|---------------------|---------------------|---------------------| | customer_id | row_num | start_date | finish_date | prev_return_date | |-------------|---------|---------------------|---------------------|---------------------| | 1 | 1 | 2005-05-28 10:35:23 | 2005-06-03 06:32:23 | [null] | | 1 | 2 | 2005-05-25 11:30:37 | 2005-06-03 12:00:37 | 2005-06-03 06:32:23 | | 1 | 3 | 2005-06-16 15:18:57 | 2005-06-17 21:05:57 | 2005-06-03 12:00:37 | | 1 | 4 | 2005-06-15 18:02:53 | 2005-06-19 15:54:53 | 2005-06-17 21:05:57 | | 1 | 5 | 2005-06-18 13:33:59 | 2005-06-19 17:40:59 | 2005-06-19 15:54:53 | | 1 | 6 | 2005-06-18 08:41:48 | 2005-06-22 03:36:48 | 2005-06-19 17:40:59 | | 1 | 7 | 2005-06-15 00:54:12 | 2005-06-23 02:42:12 | 2005-06-22 03:36:48 | | 1 | 8 | 2005-06-15 21:08:46 | 2005-06-25 02:26:46 | 2005-06-23 02:42:12 | | 1 | 9 | 2005-06-21 06:24:45 | 2005-06-28 03:28:45 | 2005-06-25 02:26:46 | | 1 | 10 | 2005-07-08 07:33:56 | 2005-07-12 13:25:56 | 2005-06-28 03:28:45 | | 1 | 11 | 2005-07-09 16:38:01 | 2005-07-13 18:02:01 | 2005-07-12 13:25:56 | | 1 | 12 | 2005-07-08 03:17:05 | 2005-07-14 01:19:05 | 2005-07-13 18:02:01 | | 1 | 13 | 2005-07-09 13:24:07 | 2005-07-14 14:01:07 | 2005-07-14 01:19:05 | | 1 | 14 | 2005-07-11 10:13:46 | 2005-07-19 13:15:46 | 2005-07-14 14:01:07 | | 1 | 15 | 2005-07-28 17:33:39 | 2005-07-29 20:17:39 | 2005-07-19 13:15:46 | | 1 | 16 | 2005-07-28 19:20:07 | 2005-07-29 22:54:07 | 2005-07-29 20:17:39 | | 1 | 17 | 2005-07-28 09:04:45 | 2005-07-30 12:37:45 | 2005-07-29 22:54:07 | | 1 | 18 | 2005-07-28 16:18:23 | 2005-07-30 17:56:23 | 2005-07-30 12:37:45 | | 1 | 19 | 2005-07-27 11:31:22 | 2005-07-31 06:50:22 | 2005-07-30 17:56:23 | | 1 | 20 | 2005-07-29 03:58:49 | 2005-08-01 05:16:49 | 2005-07-31 06:50:22 | | 1 | 21 | 2005-07-31 02:42:18 | 2005-08-02 23:26:18 | 2005-08-01 05:16:49 | | 1 | 22 | 2005-08-02 18:01:38 | 2005-08-04 13:19:38 | 2005-08-02 23:26:18 | | 1 | 23 | 2005-08-01 08:51:04 | 2005-08-10 12:12:04 | 2005-08-04 13:19:38 | | 1 | 24 | 2005-08-02 15:36:52 | 2005-08-10 16:40:52 | 2005-08-10 12:12:04 | | 1 | 25 | 2005-08-17 12:37:54 | 2005-08-19 10:11:54 | 2005-08-10 16:40:52 | | 1 | 26 | 2005-08-19 09:55:16 | 2005-08-20 14:44:16 | 2005-08-19 10:11:54 | | 1 | 27 | 2005-08-18 03:57:29 | 2005-08-22 23:05:29 | 2005-08-20 14:44:16 | | 1 | 28 | 2005-08-21 23:33:57 | 2005-08-23 01:30:57 | 2005-08-22 23:05:29 | | 1 | 29 | 2005-08-19 13:56:54 | 2005-08-23 08:50:54 | 2005-08-23 01:30:57 | | 1 | 30 | 2005-08-22 01:27:57 | 2005-08-27 07:01:57 | 2005-08-23 08:50:54 | | 1 | 31 | 2005-08-22 19:41:37 | 2005-08-28 22:49:37 | 2005-08-27 07:01:57 | | 1 | 32 | 2005-08-22 20:03:46 | 2005-08-30 01:51:46 | 2005-08-28 22:49:37 |
3. Определение начала новых периодов
Из этой таблицы мы можем установить, является ли каждая следующая запись непрерывным продолжением предыдущей. Для этого нужно убедиться, что дата в колонке prev_return_date больше или равна start_date. Для удобства записи, воспользуемся CTE (Common Table Expression):
with d as (
select
customer_id,
row_number() over(order by return_date, rental_date) as row_num,
rental_date as start_date,
return_date as finish_date,
lag(return_date, 1) over (order by return_date, rental_date) as prev_return_date
from rental
where customer_id = 1
order by row_num
) select
*,
case when d.prev_return_date >= start_date then 0 else 1 end new_period
from d;
В результате этого запроса мы получим дополнительную колонку new_period
|-------------|---------|---------------------|---------------------|---------------------|------------| | customer_id | row_num | start_date | finish_date | prev_return_date | new_period | |-------------|---------|---------------------|---------------------|---------------------|------------| | 1 | 1 | 2005-05-28 10:35:23 | 2005-06-03 06:32:23 | [null] | 1 | | 1 | 2 | 2005-05-25 11:30:37 | 2005-06-03 12:00:37 | 2005-06-03 06:32:23 | 0 | | 1 | 3 | 2005-06-16 15:18:57 | 2005-06-17 21:05:57 | 2005-06-03 12:00:37 | 1 | | 1 | 4 | 2005-06-15 18:02:53 | 2005-06-19 15:54:53 | 2005-06-17 21:05:57 | 0 | | 1 | 5 | 2005-06-18 13:33:59 | 2005-06-19 17:40:59 | 2005-06-19 15:54:53 | 0 | | 1 | 6 | 2005-06-18 08:41:48 | 2005-06-22 03:36:48 | 2005-06-19 17:40:59 | 0 | | 1 | 7 | 2005-06-15 00:54:12 | 2005-06-23 02:42:12 | 2005-06-22 03:36:48 | 0 | | 1 | 8 | 2005-06-15 21:08:46 | 2005-06-25 02:26:46 | 2005-06-23 02:42:12 | 0 | | 1 | 9 | 2005-06-21 06:24:45 | 2005-06-28 03:28:45 | 2005-06-25 02:26:46 | 0 | | 1 | 10 | 2005-07-08 07:33:56 | 2005-07-12 13:25:56 | 2005-06-28 03:28:45 | 1 | | 1 | 11 | 2005-07-09 16:38:01 | 2005-07-13 18:02:01 | 2005-07-12 13:25:56 | 0 | | 1 | 12 | 2005-07-08 03:17:05 | 2005-07-14 01:19:05 | 2005-07-13 18:02:01 | 0 | | 1 | 13 | 2005-07-09 13:24:07 | 2005-07-14 14:01:07 | 2005-07-14 01:19:05 | 0 | | 1 | 14 | 2005-07-11 10:13:46 | 2005-07-19 13:15:46 | 2005-07-14 14:01:07 | 0 | | 1 | 15 | 2005-07-28 17:33:39 | 2005-07-29 20:17:39 | 2005-07-19 13:15:46 | 1 | | 1 | 16 | 2005-07-28 19:20:07 | 2005-07-29 22:54:07 | 2005-07-29 20:17:39 | 0 | | 1 | 17 | 2005-07-28 09:04:45 | 2005-07-30 12:37:45 | 2005-07-29 22:54:07 | 0 | | 1 | 18 | 2005-07-28 16:18:23 | 2005-07-30 17:56:23 | 2005-07-30 12:37:45 | 0 | | 1 | 19 | 2005-07-27 11:31:22 | 2005-07-31 06:50:22 | 2005-07-30 17:56:23 | 0 | | 1 | 20 | 2005-07-29 03:58:49 | 2005-08-01 05:16:49 | 2005-07-31 06:50:22 | 0 | | 1 | 21 | 2005-07-31 02:42:18 | 2005-08-02 23:26:18 | 2005-08-01 05:16:49 | 0 | | 1 | 22 | 2005-08-02 18:01:38 | 2005-08-04 13:19:38 | 2005-08-02 23:26:18 | 0 | | 1 | 23 | 2005-08-01 08:51:04 | 2005-08-10 12:12:04 | 2005-08-04 13:19:38 | 0 | | 1 | 24 | 2005-08-02 15:36:52 | 2005-08-10 16:40:52 | 2005-08-10 12:12:04 | 0 | | 1 | 25 | 2005-08-17 12:37:54 | 2005-08-19 10:11:54 | 2005-08-10 16:40:52 | 1 | | 1 | 26 | 2005-08-19 09:55:16 | 2005-08-20 14:44:16 | 2005-08-19 10:11:54 | 0 | | 1 | 27 | 2005-08-18 03:57:29 | 2005-08-22 23:05:29 | 2005-08-20 14:44:16 | 0 | | 1 | 28 | 2005-08-21 23:33:57 | 2005-08-23 01:30:57 | 2005-08-22 23:05:29 | 0 | | 1 | 29 | 2005-08-19 13:56:54 | 2005-08-23 08:50:54 | 2005-08-23 01:30:57 | 0 | | 1 | 30 | 2005-08-22 01:27:57 | 2005-08-27 07:01:57 | 2005-08-23 08:50:54 | 0 | | 1 | 31 | 2005-08-22 19:41:37 | 2005-08-28 22:49:37 | 2005-08-27 07:01:57 | 0 | | 1 | 32 | 2005-08-22 20:03:46 | 2005-08-30 01:51:46 | 2005-08-28 22:49:37 | 0 |
💻 Библиотека программиста
Больше полезных материалов вы найдете на нашем телеграм-канале «Библиотека программиста»
4. Нумерация «островов»
Воспользуемся оконной функцией sum(), чтобы превратить последовательность нулей и единиц в номера периодов («островов»):
with d as (
select
customer_id,
row_number() over(order by return_date, rental_date) as row_num,
rental_date as start_date,
return_date as finish_date,
lag(return_date, 1) over (order by return_date, rental_date) as prev_return_date
from rental
where customer_id = 1
order by row_num
) select
*,
sum(case when d.prev_return_date >= start_date then 0 else 1 end) over (order by row_num) island_id
from d;
И немедленно получим результат:
|-------------|---------|---------------------|---------------------|---------------------|-----------| | customer_id | row_num | start_date | finish_date | prev_return_date | island_id | |-------------|---------|---------------------|---------------------|---------------------|-----------| | 1 | 1 | 2005-05-28 10:35:23 | 2005-06-03 06:32:23 | [null] | 1 | | 1 | 2 | 2005-05-25 11:30:37 | 2005-06-03 12:00:37 | 2005-06-03 06:32:23 | 1 | | 1 | 3 | 2005-06-16 15:18:57 | 2005-06-17 21:05:57 | 2005-06-03 12:00:37 | 2 | | 1 | 4 | 2005-06-15 18:02:53 | 2005-06-19 15:54:53 | 2005-06-17 21:05:57 | 2 | | 1 | 5 | 2005-06-18 13:33:59 | 2005-06-19 17:40:59 | 2005-06-19 15:54:53 | 2 | | 1 | 6 | 2005-06-18 08:41:48 | 2005-06-22 03:36:48 | 2005-06-19 17:40:59 | 2 | | 1 | 7 | 2005-06-15 00:54:12 | 2005-06-23 02:42:12 | 2005-06-22 03:36:48 | 2 | | 1 | 8 | 2005-06-15 21:08:46 | 2005-06-25 02:26:46 | 2005-06-23 02:42:12 | 2 | | 1 | 9 | 2005-06-21 06:24:45 | 2005-06-28 03:28:45 | 2005-06-25 02:26:46 | 2 | | 1 | 10 | 2005-07-08 07:33:56 | 2005-07-12 13:25:56 | 2005-06-28 03:28:45 | 3 | | 1 | 11 | 2005-07-09 16:38:01 | 2005-07-13 18:02:01 | 2005-07-12 13:25:56 | 3 | | 1 | 12 | 2005-07-08 03:17:05 | 2005-07-14 01:19:05 | 2005-07-13 18:02:01 | 3 | | 1 | 13 | 2005-07-09 13:24:07 | 2005-07-14 14:01:07 | 2005-07-14 01:19:05 | 3 | | 1 | 14 | 2005-07-11 10:13:46 | 2005-07-19 13:15:46 | 2005-07-14 14:01:07 | 3 | | 1 | 15 | 2005-07-28 17:33:39 | 2005-07-29 20:17:39 | 2005-07-19 13:15:46 | 4 | | 1 | 16 | 2005-07-28 19:20:07 | 2005-07-29 22:54:07 | 2005-07-29 20:17:39 | 4 | | 1 | 17 | 2005-07-28 09:04:45 | 2005-07-30 12:37:45 | 2005-07-29 22:54:07 | 4 | | 1 | 18 | 2005-07-28 16:18:23 | 2005-07-30 17:56:23 | 2005-07-30 12:37:45 | 4 | | 1 | 19 | 2005-07-27 11:31:22 | 2005-07-31 06:50:22 | 2005-07-30 17:56:23 | 4 | | 1 | 20 | 2005-07-29 03:58:49 | 2005-08-01 05:16:49 | 2005-07-31 06:50:22 | 4 | | 1 | 21 | 2005-07-31 02:42:18 | 2005-08-02 23:26:18 | 2005-08-01 05:16:49 | 4 | | 1 | 22 | 2005-08-02 18:01:38 | 2005-08-04 13:19:38 | 2005-08-02 23:26:18 | 4 | | 1 | 23 | 2005-08-01 08:51:04 | 2005-08-10 12:12:04 | 2005-08-04 13:19:38 | 4 | | 1 | 24 | 2005-08-02 15:36:52 | 2005-08-10 16:40:52 | 2005-08-10 12:12:04 | 4 | | 1 | 25 | 2005-08-17 12:37:54 | 2005-08-19 10:11:54 | 2005-08-10 16:40:52 | 5 | | 1 | 26 | 2005-08-19 09:55:16 | 2005-08-20 14:44:16 | 2005-08-19 10:11:54 | 5 | | 1 | 27 | 2005-08-18 03:57:29 | 2005-08-22 23:05:29 | 2005-08-20 14:44:16 | 5 | | 1 | 28 | 2005-08-21 23:33:57 | 2005-08-23 01:30:57 | 2005-08-22 23:05:29 | 5 | | 1 | 29 | 2005-08-19 13:56:54 | 2005-08-23 08:50:54 | 2005-08-23 01:30:57 | 5 | | 1 | 30 | 2005-08-22 01:27:57 | 2005-08-27 07:01:57 | 2005-08-23 08:50:54 | 5 | | 1 | 31 | 2005-08-22 19:41:37 | 2005-08-28 22:49:37 | 2005-08-27 07:01:57 | 5 | | 1 | 32 | 2005-08-22 20:03:46 | 2005-08-30 01:51:46 | 2005-08-28 22:49:37 | 5 |
5. Группировка и вывод результата
Финальным шагом будет группировка полученного результата по номеру «острова» и извлечение минимальной даты начала (start_datefinish_date
with d as (
select
customer_id,
row_number() over(order by return_date, rental_date) as row_num,
rental_date as start_date,
return_date as finish_date,
lag(return_date, 1) over (order by return_date, rental_date) as prev_return_date
from rental
where customer_id = 1
order by row_num
),
islands as (
select
*,
sum(case when d.prev_return_date >= start_date then 0 else 1 end) over (order by row_num) island_id
from d
)
select
island_id,
min(start_date) start_date,
max(finish_date) finish_date
from islands
group by island_id;
Сгруппировав строки, мы получим искомую таблицу:
|-----------|---------------------|---------------------| | island_id | start_date | finish_date | |-----------|---------------------|---------------------| | 1 | 2005-05-25 11:30:37 | 2005-06-03 12:00:37 | | 2 | 2005-06-15 00:54:12 | 2005-06-28 03:28:45 | | 3 | 2005-07-08 03:17:05 | 2005-07-19 13:15:46 | | 4 | 2005-07-27 11:31:22 | 2005-08-10 16:40:52 | | 5 | 2005-08-17 12:37:54 | 2005-08-30 01:51:46 |
Таким образом, мы установили, что MARY SMITH имела в своем распоряжении арендованные диски в течение пяти непрерывных периодов. Вы можете убедиться в этом, выполнив проверку задачи на сайте SQLTest.online
Заключение:
- В статье использованы CTE (Common Table Expressions) для разделения сложных запросов на более мелкие и понятные части.
- Применялись оконные функции
row_number()иlag()для нумерации строк и получения значений из предыдущих записей. - Функция
sum()использовалась для преобразования последовательности нулей и единиц в номера периодов («островов»). - Группировка по номеру «острова» позволила получить информацию о начале и конце каждого периода непрерывной аренды.