Пример самосоединения в SQL: самый быстрый перелёт с пересадкой

Q: Как найти стыковочные рейсы в SQL?

Соедините таблицу рейсов саму с собой: первая копия - первое плечо, вторая - второе. Соединяйте по условию «аэропорт прилёта первого плеча равен аэропорту вылета второго» и требуйте, чтобы второй вылет был позже первого прилёта.

Q: Как вычислить время между двумя timestamp в PostgreSQL?

Вычтите одно из другого: scheduled_arrival - scheduled_departure возвращает interval. В MySQL используйте TIMESTAMPDIFF(MINUTE, start_time, end_time).

Q: Как найти маршруты с двумя и более пересадками?

Добавьте ещё одно самосоединение на каждое дополнительное плечо или используйте рекурсивный CTE, который продлевает маршрут по одному рейсу (урок 6.6).

Урок 12.1 · Время чтения: ~6 мин · Задачи для практики ↓

В этом уроке разобрано решение SQL-задачи Самый быстрый перелёт на базе данных Bookings (PostgreSQL). Вы увидите, как самосоединение превращает одну таблицу flights в два плеча маршрута с пересадкой, как убедиться, что пересадка возможна, и как выбрать самый быстрый вариант.

Задача: найти самый быстрый способ долететь из аэропорта Пулково в Санкт-Петербурге (LED) в Брянск (BZK) 16 августа 2017 года ровно с одной пересадкой. Для каждого варианта нужны номера рейсов, аэропорт пересадки, длительность каждого перелёта, время ожидания и общее время в пути. Время считается по полям scheduled_departure и scheduled_arrival.

Сначала попробуйте решить задачу сами; полный запрос спрятан в конце урока.

Главная идея: маршрут - это две строки

Маршрут с одной пересадкой - это не один рейс, а два:

Плечо 1: из LED в некоторый аэропорт X.
Плечо 2: из того же аэропорта X в BZK.

Оба плеча - строки одной и той же таблицы flights. Чтобы поставить их рядом в одной строке результата, соедините таблицу саму с собой и дайте каждой копии свой псевдоним: first_leg и second_leg. Это самосоединение (self-join, см. урок 5.7).

Решение по шагам

1. Выбор подходящих рейсов

Первое плечо вылетает из LED, второе прилетает в BZK, и оба вылетают 16 августа:

SELECT COUNT(*) AS flights_from_led
FROM flights
WHERE departure_airport = 'LED'
  AND scheduled_departure BETWEEN '2017-08-16' AND '2017-08-17';

Результат: в этот день из LED вылетают 33 рейса; любой из них может быть первым плечом.

2. Соединение плеч

Плечи должны встречаться в одном аэропорту, а второй рейс должен вылетать после приземления первого:

SELECT
    first_leg.flight_no,
    first_leg.arrival_airport AS connection_airport,
    second_leg.flight_no,
    second_leg.scheduled_departure - first_leg.scheduled_arrival AS connection_time,
    second_leg.scheduled_arrival - first_leg.scheduled_departure AS total_trip_time
FROM flights AS first_leg
JOIN flights AS second_leg
    ON first_leg.arrival_airport = second_leg.departure_airport
   AND second_leg.arrival_airport = 'BZK'
   AND second_leg.scheduled_departure > first_leg.scheduled_arrival
WHERE first_leg.departure_airport = 'LED'
  AND first_leg.scheduled_departure BETWEEN '2017-08-16' AND '2017-08-17'
  AND second_leg.scheduled_departure BETWEEN '2017-08-16' AND '2017-08-17'
ORDER BY total_trip_time;

Результат: 18 вариантов через 3 аэропорта пересадки; самый быстрый идёт через московское Шереметьево (SVO) и занимает 1 час 25 минут.

first_leg.arrival_airport = second_leg.departure_airport - точка пересадки.
second_leg.scheduled_departure > first_leg.scheduled_arrival отбрасывает варианты, где второй самолёт улетает раньше, чем приземлится первый. Без этого условия запрос вернул бы невозможные маршруты.

3. Расчёт длительностей

В PostgreSQL разность двух значений timestamp даёт interval, например 01:25:00:

первый перелёт: first_leg.scheduled_arrival - first_leg.scheduled_departure;
ожидание: second_leg.scheduled_departure - first_leg.scheduled_arrival;
вся поездка: second_leg.scheduled_arrival - first_leg.scheduled_departure, от первого вылета до последнего прилёта.

4. Самый быстрый вариант

Отсортируйте по общему времени в пути и оставьте первую строку с помощью LIMIT 1. Если несколько вариантов могут иметь одинаковое время, LIMIT 1 вернёт один из них; чтобы показать все, сравнивайте с минимумом, например через RANK() (урок 7.2).

На что обратить внимание

Пересадка - всего 5 минут. В самом быстром варианте второй рейс вылетает из SVO через пять минут после посадки первого. Задача требует только, чтобы второй рейс вылетал позже; реальная система бронирования потребовала бы минимальное время пересадки, например second_leg.scheduled_departure >= first_leg.scheduled_arrival + INTERVAL '1 hour'.
Фильтруйте по дате оба плеча. Без условия на дату для second_leg запрос соединял бы и с рейсами следующих дней.
BETWEEN включает обе границы. BETWEEN '2017-08-16' AND '2017-08-17' включает и рейс ровно в полночь 17 августа. Для целых суток точнее >= '2017-08-16' AND < '2017-08-17'.

Спойлер: SQL-запрос с решением спрятан ниже. Нажмите, чтобы открыть.


select
    first_leg.flight_no flight1_no,
    first_leg.departure_airport,
    first_leg.arrival_airport connection_airport,
    first_leg.scheduled_arrival - first_leg.scheduled_departure flight1_time,
    second_leg.scheduled_departure - first_leg.scheduled_arrival connection_time,
    second_leg.flight_no flight2_no,
    second_leg.arrival_airport,
    second_leg.scheduled_arrival - second_leg.scheduled_departure flight2_time,
    second_leg.scheduled_arrival - first_leg.scheduled_departure total_trip_time
from flights first_leg
join flights second_leg on first_leg.arrival_airport = second_leg.departure_airport
    and second_leg.arrival_airport = 'BZK'
    and second_leg.scheduled_departure > first_leg.scheduled_arrival
where first_leg.departure_airport = 'LED'
    and first_leg.scheduled_departure between '2017-08-16' and '2017-08-17'
    and second_leg.scheduled_departure between '2017-08-16' and '2017-08-17'
order by total_trip_time
limit 1;

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

Маршрут с одной пересадкой - это две строки одной таблицы, соединённые самосоединением с двумя псевдонимами.
Условие пересадки: first_leg.arrival_airport = second_leg.departure_airport.
Второй рейс должен вылетать после прилёта первого, иначе маршрут невозможен.
Разность значений timestamp в PostgreSQL даёт interval, который можно сравнивать и сортировать.
ORDER BY ... LIMIT 1 возвращает лучший вариант; чтобы сохранить равные варианты, используйте RANK().

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

Как найти стыковочные рейсы в SQL?