В этой заметке речь пойдет о том, как писать рекурсивные запросы. Тема эта поднималась не раз и не два, но обычно все ограничивается простыми «деревянными» случаями: спуститься от вершины до листьев, подняться от вершины до корня. Мы же займемся более сложным случаем произвольного графа.

Начнем с того, что повторим теорию (очень кратко, потому что с ней все ясно), а затем поговорим о том, что делать, если непонятно, как подступиться к реальной задаче, или вроде бы понятно, но запрос упорно не хочет работать.

Для упражнения будем использовать демо-базу, подробно описанную ранее, и попробуем написать в ней запрос для поиска кратчайшего пути из одного аэропорта в другой.

Немного теории

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

Так вот рекурсивный запрос — это такой способ устроить цикл прямо внутри SQL. Не то, чтобы это было нужно очень часто, но иногда все-таки приходится. И тут начинаются сложности, поскольку рекурсивный запрос не очень похож ни на обычный запрос, ни тем более на обычный цикл.

Общая схема рекурсивного запроса такова:

WITH RECURSIVE t AS (
  нерекурсивная часть      (1)
  UNION ALL
  рекурсивная часть        (2)
)
SELECT * FROM t;           (3)


Сначала выполняется нерекурсивная часть (1). Затем рекурсивная часть (2) выполняется до тех пор, пока она возвращает какие-либо строки. Рекурсивная часть называется так потому, что она может обращаться к результату выполнения предыдущей итерации, который доступен ей под именем t.

Попутно результат выполнения каждой итерации складывается в результирующую таблицу, которая будет доступна под тем же именем t после того, как весь запрос отработает (3). Если вместо UNION ALL написать UNION, то на каждой итерации будут устраняться дубликаты строк.

В виде псевдокода это можно изобразить примерно так:

res < EMPTY;
t < (нерекурсивная часть);
WHILE t IS NOT EMPTY LOOP
    res < res UNION ALL t;
    aux < (рекурсивная часть);
    t < aux;
END LOOP;
t < res;


Простой пример:

demo=# WITH RECURSIVE t(n,factorial) AS (
  VALUES (0,1)
  UNION ALL
  SELECT t.n+1, t.factorial*(t.n+1) FROM t WHERE t.n < 5
)
SELECT * FROM t;

 n | factorial
---+-----------
 0 |         1
 1 |         1
 2 |         2
 3 |         6
 4 |        24
 5 |       120
(6 строк)


Ну и достаточно, чтобы вспомнить. Если уже на этом этапе не все понятно, самое время почитать документацию.

Практика

Вооружившись теорией, мы теперь можем (теоретически) взять и написать запрос, о котором говорилось выше: поиск кратчайшего пути из, скажем, Усть-Кута (UKX) в Нерюнгри (CNN).

Из всей демо-базы нам потребуются две таблицы: аэропорты (airports) и маршруты (routes). Формально маршруты — материализованное представление, но об этом можно не думать. (Если вы еще не знакомы со структурой демонстрационной базы, посмотрите ее описание.)

Выглядеть запрос может примерно так:

WITH RECURSIVE p(last_arrival, destination, hops, flights, found) AS (
  SELECT a_from.airport_code,
         a_to.airport_code,
         ARRAY[a_from.airport_code],
         ARRAY[]::char(6)[],
         a_from.airport_code = a_to.airport_code
  FROM   airports a_from, airports a_to
  WHERE  a_from.airport_code = 'UKX'
  AND    a_to.airport_code = 'CNN'
  UNION ALL
  SELECT r.arrival_airport,
         p.destination,
         (p.hops || r.arrival_airport)::char(3)[],
         (p.flights || r.flight_no)::char(6)[],
         bool_or(r.arrival_airport = p.destination) OVER ()
  FROM   routes r, p
  WHERE  r.departure_airport = p.last_arrival
  AND    NOT r.arrival_airport = ANY(p.hops)
  AND    NOT p.found
)
SELECT hops,
       flights
FROM   p
WHERE  p.last_arrival = p.destination;


Это, конечно, здорово, да только как до этого дойти, когда на экране еще ничего нет, кроме мигающего курсора?

В этом месте кассеты ему всегда кажется, что он случайно поставил пиво на кнопку перемотки: танцоры перестают злобно пародировать самого Рэнди и внезапно начинают двигаться совершенно профессионально. Вроде бы движения все те же, что и раньше, но будь он проклят, если может различить их в творческом исполнении. Нет никакого плавного перехода, вот что бесит и всегда бесило Рэнди в этих видеоуроках. Любой идиот может разучить основные шаги за полчаса. Но когда полчаса истекают, тренер почему-то ждет, что ты начнешь порхать по сцене, как будто промелькнули титры «прошло несколько лет». Наверное, то же чувствуют гуманитарии на уроках математики, думает Рэнди. Вот учитель пишет на доске пару простых уравнений, а спустя десять минут из них уже выведена скорость света в вакууме.

— Нил Стивенсон, «Криптономикон» (перевод мой)

Я, например, не могу написать такой запрос из головы. Поэтому будем двигаться последовательно.

Итак, нам нужно получить путь. Путь из пункта А в пункт Б — это последовательность рейсов. Первый рейс вылетает из А куда-то, следующий — из этого куда-та еще куда-то и так далее, пока последний рейс не завершится в искомом пункте Б. Вот такую цепочку рейсов с фиксированным началом, фиксированным концом и неизвестной серединой нам и надо найти.

Как представить такую цепочку? С реляционной точки зрения ей бы логично быть таблицей со столбцами номер по порядку и аэропорт. Но нам надо работать с цепочкой как с одним объектом, так что самое удобное — представить ее массивом: [аэропорт, аэропорт, ...]. (Если с этим сложности, то почитайте про массивы и функции для работы с ними.)

С чего начинать итерацию, понятно: с аэропорта в Усть-Куте.

demo=# SELECT ARRAY[airport_code] FROM airports WHERE airport_code = 'UKX';

 array
-------
 {UKX}
(1 строка)


Почему не просто ARRAY['UKX']? Полезно немного подстраховаться: если вдруг опечатаемся в коде аэропорта, запрос ничего не вернет.

Теперь представим себе, что результат этой начальной итерации лежит в таблице, а нам надо сделать вторую итерацию. Можно так и поступить: создать и заполнить таблицу и писать с ней запросы. Но проще воспользоваться WITH:

demo=# WITH p(last_arrival, hops) AS (
  SELECT airport_code,
         ARRAY[airport_code]
  FROM   airports
  WHERE  airport_code = 'UKX'
)
SELECT * FROM p;

 last_arrival | hops  
--------------+-------
 UKX          | {UKX}
(1 строка)


Мы назвали столбец hops, чтобы не запутаться. Кроме того, добавили еще один (last_arrival) для последнего пункта в нашей будущей цепочке. Вместо этого можно было бы вычислять последний элемент массива (p.hops[cardinality(p.hops)]), но это не так наглядно.

Теперь вторая итерация:

demo=# WITH p(last_arrival, hops) AS (
  SELECT airport_code,
         ARRAY[airport_code]
  FROM   airports
  WHERE  airport_code = 'UKX'
)
SELECT r.arrival_airport AS last_arrival,
       p.hops || ARRAY[r.arrival_airport] AS hops
FROM   routes r, p
WHERE  r.departure_airport = p.last_arrival;

 last_arrival |   hops    
--------------+-----------
 KJA          | {UKX,KJA}
(1 строка)


Что мы сделали? Мы взяли первую итерацию (таблица p) и соединили ее с маршрутами. В качестве аэропорта вылета мы указали последний аэропорт из нашей цепочки, а аэропорт прибытия дописали к цепочке справа. Оказывается, из Усть-Кута можно улететь в один только Красноярск.

Теперь более или менее понятно, как собрать рекурсивный запрос. Добавляем волшебное слово RESURSIVE, а запрос объединяем с первой итерацией с помощью UNION ALL. И в основном запросе отбираем цепочку, которая в конечном итоге привела в аэропорт назначения (CNN).

Примерно так?

demo=# WITH RECURSIVE p(last_arrival, hops) AS (
  SELECT airport_code,
         ARRAY[airport_code]
  FROM   airports
  WHERE  airport_code = 'UKX'
  UNION ALL
  SELECT r.arrival_airport,
         p.hops || r.arrival_airport
  FROM   routes r, p
  WHERE  r.departure_airport = p.last_arrival
)
SELECT *
FROM   p
WHERE  p.last_arrival = (
         SELECT airport_code FROM airports WHERE airport_code = 'CNN'
);

ОШИБКА:  в рекурсивном запросе "p" столбец 2 имеет тип character(3)[] в не рекурсивной части, но в результате тип bpchar[]
СТРОКА 3:          ARRAY[airport_code]
                   ^
ПОДСКАЗКА:  Приведите результат не рекурсивной части к правильному типу.


Хм. Постгрес расстроен тем, что второй столбец имеет тип character(3)[] в нерекурсивной части (non-recursive term), но в целом тип получается bpchar[]. Тип bpchar (blank-padded char) — это внутреннее имя для типа char; к сожалению, конкатенация массивов не сохраняет тип элементов, поэтому требуется явное приведение типов.

demo=# WITH RECURSIVE p(last_arrival, hops) AS (
  SELECT airport_code,
         ARRAY[airport_code]
  FROM   airports
  WHERE  airport_code = 'UKX'
  UNION ALL
  SELECT r.arrival_airport,
         (p.hops || r.arrival_airport)::char(3)[]
  FROM   routes r, p
  WHERE  r.departure_airport = p.last_arrival
)
SELECT *
FROM   p
WHERE  p.last_arrival = (
         SELECT airport_code FROM airports WHERE airport_code = 'CNN'
);


Ошибки больше нет, но увы — запрос повис. И что теперь делать?

Будем разбираться. Попробуем выполнить наш запрос «по шагам» и посмотреть, что происходит на каждой итерации.

Понятно, что можно повторить фокус с запихиванием первой итерации в таблицу и постепенным присоединением новых итераций, но это уж очень муторно, да и ошибиться легко. Но есть способ лучше.

Давайте добавим в наш запрос еще один столбец с номером итерации (назовем его level). В первой итерации он будет равен единице, а потом будем увеличивать его. Само по себе это не поможет, но теперь мы можем остановить выполнение запроса в любом месте. Первые две итерации мы видели, поглядим на третью:

demo=# WITH RECURSIVE p(last_arrival, hops, level) AS (
  SELECT airport_code,
         ARRAY[airport_code],
         1
  FROM   airports
  WHERE airport_code = 'UKX'
  UNION ALL
  SELECT r.arrival_airport,
         (p.hops || r.arrival_airport)::char(3)[],
         p.level + 1
  FROM   routes r, p
  WHERE  r.departure_airport = p.last_arrival
  AND    p.level < 3
)
SELECT * FROM p;

 last_arrival |     hops      | level
--------------+---------------+-------
 UKX          | {UKX}         |     1
 KJA          | {UKX,KJA}     |     2
 UKX          | {UKX,KJA,UKX} |     3
 OVB          | {UKX,KJA,OVB} |     3
 OVB          | {UKX,KJA,OVB} |     3
 NOZ          | {UKX,KJA,NOZ} |     3
 NOZ          | {UKX,KJA,NOZ} |     3
 AER          | {UKX,KJA,AER} |     3
 SVO          | {UKX,KJA,SVO} |     3
 NUX          | {UKX,KJA,NUX} |     3
 UIK          | {UKX,KJA,UIK} |     3
 UIK          | {UKX,KJA,UIK} |     3
 BAX          | {UKX,KJA,BAX} |     3
 KRO          | {UKX,KJA,KRO} |     3
 OVS          | {UKX,KJA,OVS} |     3
(15 строк)


Что-то неожиданное.

Во-первых, некоторые строки дублируются (например, {UKX,KJA,OVB}). Это, на самом деле, правильно, потому что есть два разных рейса из Красноярска (KJA) в Новосибирск (OVB):

demo=# SELECT flight_no
FROM   routes
WHERE  departure_airport = 'KJA'
AND    arrival_airport = 'OVB';

 flight_no
-----------
 PG0206
 PG0207
(2 строки)


Добавим номер рейса в запрос, чтобы отличать строки; он нам все равно нужен.

demo=# WITH RECURSIVE p(last_arrival, hops, flights, level) AS (
  SELECT airport_code,
         ARRAY[airport_code],
         ARRAY[]::char(6)[],
         1
  FROM   airports
  WHERE  airport_code = 'UKX'
  UNION ALL
  SELECT r.arrival_airport,
         (p.hops || r.arrival_airport)::char(3)[],
         (p.flights || r.flight_no)::char(6)[],
         p.level + 1
  FROM   routes r, p
  WHERE  r.departure_airport = p.last_arrival
  AND    p.level < 3
)
SELECT * FROM p;

 last_arrival |     hops      |     flights     | level
--------------+---------------+-----------------+-------
 UKX          | {UKX}         | {}              |     1
 KJA          | {UKX,KJA}     | {PG0022}        |     2
 UKX          | {UKX,KJA,UKX} | {PG0022,PG0021} |     3
 OVB          | {UKX,KJA,OVB} | {PG0022,PG0206} |     3
 OVB          | {UKX,KJA,OVB} | {PG0022,PG0207} |     3
 NOZ          | {UKX,KJA,NOZ} | {PG0022,PG0351} |     3
 NOZ          | {UKX,KJA,NOZ} | {PG0022,PG0352} |     3
 AER          | {UKX,KJA,AER} | {PG0022,PG0501} |     3
 SVO          | {UKX,KJA,SVO} | {PG0022,PG0548} |     3
 NUX          | {UKX,KJA,NUX} | {PG0022,PG0623} |     3
 UIK          | {UKX,KJA,UIK} | {PG0022,PG0625} |     3
 UIK          | {UKX,KJA,UIK} | {PG0022,PG0626} |     3
 BAX          | {UKX,KJA,BAX} | {PG0022,PG0653} |     3
 KRO          | {UKX,KJA,KRO} | {PG0022,PG0673} |     3
 OVS          | {UKX,KJA,OVS} | {PG0022,PG0689} |     3
(15 строк)


А вот другая странность хуже. Одна из строк показывает, что мы можем прилететь обратно: {UKX,KJA,UKX}. И это означает, что мы будем летать по кругу бесконечно, запрос не остановится. Вот и разгадка зависания.

Что с этим делать? Надо добавить условие, что каждый аэропорт можно посетить не более одного раза (в таком случае маршрут все равно не будет оптимальным).

demo=# WITH RECURSIVE p(last_arrival, hops, flights, level) AS (
  SELECT airport_code,
         ARRAY[airport_code],
         ARRAY[]::char(6)[],
         1
  FROM   airports
  WHERE  airport_code = 'UKX'
  UNION ALL
  SELECT r.arrival_airport,
         (p.hops || r.arrival_airport)::char(3)[],
         (p.flights || r.flight_no)::char(6)[],
         p.level + 1
  FROM   routes r, p
  WHERE  r.departure_airport = p.last_arrival
  AND    NOT r.arrival_airport = ANY(p.hops)
  AND    p.level < 3
)
SELECT * FROM p;

 last_arrival |     hops      |     flights     | level
--------------+---------------+-----------------+-------
 UKX          | {UKX}         | {}              |     1
 KJA          | {UKX,KJA}     | {PG0022}        |     2
 OVB          | {UKX,KJA,OVB} | {PG0022,PG0206} |     3
 OVB          | {UKX,KJA,OVB} | {PG0022,PG0207} |     3
 NOZ          | {UKX,KJA,NOZ} | {PG0022,PG0351} |     3
 NOZ          | {UKX,KJA,NOZ} | {PG0022,PG0352} |     3
 AER          | {UKX,KJA,AER} | {PG0022,PG0501} |     3
 SVO          | {UKX,KJA,SVO} | {PG0022,PG0548} |     3
 NUX          | {UKX,KJA,NUX} | {PG0022,PG0623} |     3
 UIK          | {UKX,KJA,UIK} | {PG0022,PG0625} |     3
 UIK          | {UKX,KJA,UIK} | {PG0022,PG0626} |     3
 BAX          | {UKX,KJA,BAX} | {PG0022,PG0653} |     3
 KRO          | {UKX,KJA,KRO} | {PG0022,PG0673} |     3
 OVS          | {UKX,KJA,OVS} | {PG0022,PG0689} |     3
(14 строк)


Кажется, теперь порядок. Запускаем без ограничений?

demo=# WITH RECURSIVE p(last_arrival, hops, flights, level) AS (
  SELECT airport_code,
         ARRAY[airport_code],
         ARRAY[]::char(6)[],
         1
  FROM   airports
  WHERE  airport_code = 'UKX'
  UNION ALL
  SELECT r.arrival_airport,
         (p.hops || r.arrival_airport)::char(3)[],
         (p.flights || r.flight_no)::char(6)[],
         p.level + 1
  FROM   routes r, p
  WHERE  r.departure_airport = p.last_arrival
  AND    NOT r.arrival_airport = ANY(p.hops)
--  AND    p.level < 3
)
SELECT *
FROM   p
WHERE  p.last_arrival = (
         SELECT airport_code FROM airports WHERE airport_code = 'CNN'
);


Формально теперь все должно получиться… но запрос опять виснет, а если набраться терпения, то может упасть с ошибкой «закончилось место для временных файлов».

Почему так? А потому что нам приходится строить все возможные пути произвольной длины из пункта А, и лишь в самом конце мы отбираем из них те, которые заканчиваются в пункте Б. Это, мягко говоря, не самый эффективный алгоритм. Чтобы понять масштаб бедствия, можно посмотреть, сколько строк получается на каждом шаге, меняя ограничение на level:

1	1
2	2
3	14
4	165
5	1978
6	22322
7	249942
8	2316063

Ну и так далее, и каждый следующий запрос работает ощутимо медленнее предыдущего.
Давайте задумаемся, какое число мы ожидаем увидеть в ответе? Если бы у нас были крупные города, то, скорее всего, 2 (с пересадкой в Москве). В нашем случае ожидаемо будет добавить еще как минимум пару на региональные рейсы, чтобы долететь до крупного города. То есть где-то 4 или 5, ну может быть 6. Однако запрос не собирается останавливаться и на восьми: он дойдет (если хватит сил и здоровья) примерно до сотни, пока не сможет продлить ни одну из цепочек!

При этом алгоритм работает «в ширину»: сначала мы добавляем все пути длиной 1, потом все пути длиной 2 и так далее. То есть как только мы найдем хоть какой-нибудь первый попавшийся путь из А в Б, этот путь и будет самым коротким (по числу пересадок). Вопрос теперь только в том, как вовремя остановить перебор.

Идея в том, чтобы на каждом шаге устанавливать признак «путь найден», если хотя бы один из только что построенных путей заканчивается в пункте назначения. Тогда мы сможем записать и условие остановки.

Начнем с добавления пункта назначения в сам запрос (до этого он появлялся только в самом конце, когда дело доходило до фильтрации всех найденных результатов). Вычислим его в самом начале, а в рекурсивной части запроса просто оставим без изменений:

demo=# WITH RECURSIVE p(last_arrival, destination, hops, flights, level) AS (
  SELECT a_from.airport_code,
         a_to.airport_code,
         ARRAY[a_from.airport_code],
         ARRAY[]::char(6)[],
         1
  FROM   airports a_from, airports a_to
  WHERE  a_from.airport_code = 'UKX'
  AND    a_to.airport_code = 'CNN'
  UNION ALL
  SELECT r.arrival_airport,
         p.destination,
         (p.hops || r.arrival_airport)::char(3)[],
         (p.flights || r.flight_no)::char(6)[],
         p.level + 1
  FROM   routes r, p
  WHERE  r.departure_airport = p.hops[cardinality(p.hops)]
  AND    NOT r.arrival_airport = ANY(p.hops)
  AND    p.level < 3
)
SELECT * FROM p;

 last_arrival | destination |     hops      |     flights     | level
--------------+-------------+---------------+-----------------+-------
 UKX          | CNN         | {UKX}         | {}              |     1
 KJA          | CNN         | {UKX,KJA}     | {PG0022}        |     2
 OVB          | CNN         | {UKX,KJA,OVB} | {PG0022,PG0206} |     3
 OVB          | CNN         | {UKX,KJA,OVB} | {PG0022,PG0207} |     3
 NOZ          | CNN         | {UKX,KJA,NOZ} | {PG0022,PG0351} |     3
 NOZ          | CNN         | {UKX,KJA,NOZ} | {PG0022,PG0352} |     3
 AER          | CNN         | {UKX,KJA,AER} | {PG0022,PG0501} |     3
 SVO          | CNN         | {UKX,KJA,SVO} | {PG0022,PG0548} |     3
 NUX          | CNN         | {UKX,KJA,NUX} | {PG0022,PG0623} |     3
 UIK          | CNN         | {UKX,KJA,UIK} | {PG0022,PG0625} |     3
 UIK          | CNN         | {UKX,KJA,UIK} | {PG0022,PG0626} |     3
 BAX          | CNN         | {UKX,KJA,BAX} | {PG0022,PG0653} |     3
 KRO          | CNN         | {UKX,KJA,KRO} | {PG0022,PG0673} |     3
 OVS          | CNN         | {UKX,KJA,OVS} | {PG0022,PG0689} |     3
(14 строк)


Теперь признак найденного пути вычислить легко: он должен быть установлен, если последний пункт пути совпадает с пунктом назначения хотя бы для одной строки. Для этого нам пригодится оконная функция bool_or (если оконные функции — нечто новое для вас, начните с введения, в конце которого есть и ссылки на более подробное описание).

demo=# WITH RECURSIVE p(last_arrival, destination, hops, flights, found, level) AS (
  SELECT a_from.airport_code,
         a_to.airport_code,
         ARRAY[a_from.airport_code],
         ARRAY[]::char(6)[],
         a_from.airport_code = a_to.airport_code,
         1
  FROM   airports a_from, airports a_to
  WHERE  a_from.airport_code = 'UKX'
  AND    a_to.airport_code = 'OVB' -- CNN
  UNION ALL
  SELECT r.arrival_airport,
         p.destination,
         (p.hops || r.arrival_airport)::char(3)[],
         (p.flights || r.flight_no)::char(6)[],
         bool_or(r.arrival_airport = p.destination) OVER (),
         p.level + 1
  FROM   routes r, p
  WHERE  r.departure_airport = p.last_arrival
  AND    NOT r.arrival_airport = ANY(p.hops)
  AND    p.level < 3
)
SELECT * FROM p;

 last_arrival | destination |     hops      |     flights     | found | level
--------------+-------------+---------------+-----------------+-------+-------
 UKX          | OVB         | {UKX}         | {}              | f     |     1
 KJA          | OVB         | {UKX,KJA}     | {PG0022}        | f     |     2
 OVB          | OVB         | {UKX,KJA,OVB} | {PG0022,PG0206} | t     |     3
 OVB          | OVB         | {UKX,KJA,OVB} | {PG0022,PG0207} | t     |     3
 NOZ          | OVB         | {UKX,KJA,NOZ} | {PG0022,PG0351} | t     |     3
 NOZ          | OVB         | {UKX,KJA,NOZ} | {PG0022,PG0352} | t     |     3
 AER          | OVB         | {UKX,KJA,AER} | {PG0022,PG0501} | t     |     3
 SVO          | OVB         | {UKX,KJA,SVO} | {PG0022,PG0548} | t     |     3
 NUX          | OVB         | {UKX,KJA,NUX} | {PG0022,PG0623} | t     |     3
 UIK          | OVB         | {UKX,KJA,UIK} | {PG0022,PG0625} | t     |     3
 UIK          | OVB         | {UKX,KJA,UIK} | {PG0022,PG0626} | t     |     3
 BAX          | OVB         | {UKX,KJA,BAX} | {PG0022,PG0653} | t     |     3
 KRO          | OVB         | {UKX,KJA,KRO} | {PG0022,PG0673} | t     |     3
 OVS          | OVB         | {UKX,KJA,OVS} | {PG0022,PG0689} | t     |     3
(14 строк)


Тут мы проверили, как запрос будет работать для пути из Усть-Кута (UKX) в Новосибирск (OVB), который, как мы уже знаем, имеет длину 3. (Для этого, кстати, пришлось поменять CNN на OVB только в одном месте — мелочь, а приятно.) Все работает!

Признак мы вычисляем и в нерекурсивной части запроса. Можно было бы просто написать false, но так запрос будет более универсальным и корректно определит число пересадок из А в сам же А.

Осталось добавить условие останова и можно запускать:

demo=# WITH RECURSIVE p(last_arrival, destination, hops, flights, found, level) AS (
  SELECT a_from.airport_code,
         a_to.airport_code,
         ARRAY[a_from.airport_code],
         ARRAY[]::char(6)[],
         a_from.airport_code = a_to.airport_code,
         1
  FROM   airports a_from, airports a_to
  WHERE  a_from.airport_code = 'UKX'
  AND    a_to.airport_code = 'CNN'
  UNION ALL
  SELECT r.arrival_airport,
         p.destination,
         (p.hops || r.arrival_airport)::char(3)[],
         (p.flights || r.flight_no)::char(6)[],
         bool_or(r.arrival_airport = p.destination) OVER (),
         p.level + 1
  FROM   routes r, p
  WHERE  r.departure_airport = p.last_arrival
  AND    NOT r.arrival_airport = ANY(p.hops)
  AND    NOT p.found
--  AND    p.level < 3
)
SELECT hops, flights
FROM   p
WHERE  p.last_arrival = p.destination;

         hops          |            flights            
-----------------------+-------------------------------
 {UKX,KJA,OVB,MJZ,CNN} | {PG0022,PG0206,PG0390,PG0035}
 {UKX,KJA,OVB,MJZ,CNN} | {PG0022,PG0207,PG0390,PG0035}
 {UKX,KJA,SVO,MJZ,CNN} | {PG0022,PG0548,PG0120,PG0035}
 {UKX,KJA,OVB,MJZ,CNN} | {PG0022,PG0206,PG0390,PG0036}
 {UKX,KJA,OVB,MJZ,CNN} | {PG0022,PG0207,PG0390,PG0036}
 {UKX,KJA,SVO,MJZ,CNN} | {PG0022,PG0548,PG0120,PG0036}
 {UKX,KJA,OVS,LED,CNN} | {PG0022,PG0689,PG0686,PG0245}
 {UKX,KJA,SVO,LED,CNN} | {PG0022,PG0548,PG0472,PG0245}
 {UKX,KJA,SVO,LED,CNN} | {PG0022,PG0548,PG0471,PG0245}
 {UKX,KJA,SVO,LED,CNN} | {PG0022,PG0548,PG0470,PG0245}
 {UKX,KJA,SVO,LED,CNN} | {PG0022,PG0548,PG0469,PG0245}
 {UKX,KJA,SVO,LED,CNN} | {PG0022,PG0548,PG0468,PG0245}
 {UKX,KJA,OVB,PEE,CNN} | {PG0022,PG0206,PG0186,PG0394}
 {UKX,KJA,OVB,PEE,CNN} | {PG0022,PG0207,PG0186,PG0394}
 {UKX,KJA,BAX,ASF,CNN} | {PG0022,PG0653,PG0595,PG0427}
 {UKX,KJA,SVO,ASF,CNN} | {PG0022,PG0548,PG0128,PG0427}
 {UKX,KJA,OVS,DME,CNN} | {PG0022,PG0689,PG0544,PG0709}
 {UKX,KJA,OVS,DME,CNN} | {PG0022,PG0689,PG0543,PG0709}
 {UKX,KJA,KRO,DME,CNN} | {PG0022,PG0673,PG0371,PG0709}
 {UKX,KJA,OVB,DME,CNN} | {PG0022,PG0206,PG0223,PG0709}
 {UKX,KJA,OVB,DME,CNN} | {PG0022,PG0207,PG0223,PG0709}
 {UKX,KJA,NUX,DME,CNN} | {PG0022,PG0623,PG0165,PG0709}
 {UKX,KJA,BAX,DME,CNN} | {PG0022,PG0653,PG0117,PG0709}
(23 строки)


Вот, собственно, и все. Мы пришли к запросу из начала статьи, и отрабатывает он мгновенно. Теперь можно убрать «отладочный» level… а можно и оставить.

Подытожим полезные приемы:

• Представление «пути» в виде массива помогает во многих случаях. Вместо этого можно конкатенировать строки, но это менее удобно.
• Предотвращение зацикливания (с помощью того же массива).
• Отладка ограничением числа итераций.
• Иногда для улучшения производительности нужен способ вовремя остановиться.
• Использование оконных функций позволяет творить чудеса.

В качестве упражнений

Чтобы закрепить навык, можно выполнить несколько вариаций на ту же тему.

1. Какое максимальное число пересадок потребуется, чтобы добраться из любого аэропорта в любой другой?
   Подсказка 1: первая часть запроса должна содержать все пары аэропортов вылета и прибытия.
   Подсказка 2: признак найденного пути надо считать отдельно для каждой пары аэропортов.
   
   
2. Найдите путь (из UKX в CNN), оптимальный по суммарной длительности перелетов (без учета ожидания пересадок).
   Подсказка 1: может оказаться, что такой путь не оптимален по числу пересадок.
   Подсказка 2: надо придумать признак того, что дальнейший перебор бесполезен.
   
   
3. Найдите путь (из UKX в CNN), оптимальный по суммарной длительности перелетов с учетом времени ожидания пересадок. Считайте, что к первому вылету мы готовы в момент времени bookings.now() - interval '20 days'.
   

Когда справитесь с третьим заданием — поделитесь своим успехом с нами (edu@postgrespro.ru). А авторам понравившихся решений мы будем рады подарить приглашение на PgConf.Russia 2017.