есть запрос для построения маршрутов из рейсов
WITH RECURSIVE tree AS (
SELECT f0.id::text AS flights,
'/'||origin_id||'/'||destination_id||'/' AS route,
'/'||airline||'/' AS airlines,
'/'||invisible||'/' AS invisible,
origin_id, destination_id,
std AS departure,
sta AS arrival,
0 as hops,
(sta - std)::INTERVAL AS total_time,
'00:00'::INTERVAL AS waiting_time,
available AS available
FROM flights f0
INNER JOIN airports a
ON f0.origin_id = a.id
AND NOT a.cargo_accepted = false
WHERE origin_id = '13'
AND airline IN ('LH', 'OK', 'QS', 'U6')
AND std >= '2017-06-02 06:11:02 UTC'
AND NOT f0.available = false
UNION ALL
SELECT s.flights || '-->' || f1.id::text AS flights,
s.route||f1.destination_id||'/',
s.airlines||f1.airline||'/',
s.invisible||f1.invisible||'/',
s.origin_id, f1.destination_id,
s.departure AS departure,
f1.sta AS arrival,
s.hops + 1 AS hops,
s.total_time + (f1.sta - f1.std)::INTERVAL AS total_time,
s.waiting_time + (f1.std - s.arrival)::INTERVAL AS waiting_time,
s.available
FROM tree s
JOIN flights f1
INNER JOIN airports a1
ON f1.origin_id = a1.id
AND NOT a1.cargo_accepted = false
AND NOT a1.transit = false
ON f1.origin_id = s.destination_id
AND f1.std >= s.arrival + '8 hour'
AND f1.std <= s.arrival + '7 day'
AND NOT s.route LIKE '%/'||f1.destination_id||'/%'
AND s.hops < 4
AND NOT s.available = false
AND NOT f1.available = false
AND f1.airline IN ('LH', 'OK', 'QS', 'U6')
)
SELECT *
FROM tree
INNER JOIN airports a3
ON destination_id = a3.id
AND NOT a3.cargo_accepted = false
WHERE destination_id = '112'
AND waiting_time < '25 day'
AND arrival <= '2017-06-27 06:00:28 UTC'
AND airlines LIKE '%U6%'
ORDER BY arrival, departure, waiting_time
количество рейсов растет и запрос начинает все дольше и дольше думать
на данный момент в базе 64105 рейсов, как бы это мелочи для DB но запрос проходит примерно за 12-16 секунд.
Помогите разобраться, что не так?
делал анализ
https://gist.github.com/sanyco86/26f07fbf567e09639cc75ac7b557e660
ну и собственно, если кто-то захочет вникнуть в проблему
тестовые данные
http://beta.u6-cargo.com/assets/Postgtes_backup.sql
Ответ
Основная проблема данного запроса в быстром размножении количества обрабатываемых записей в рекурсии. Основным и практически единственным способом борьбы с этим является как можно большее ограничение подбираемых внутри рекурсии записей. А одна лишняя запись на первом шаге рекурсии может породить за собой тысячи записей к 4 шагу...
Первое, что бросается в глаза: запрос внутри рекурсивной части выбирает все рейсы начиная с конкретной даты, но никак не ограничивая максимально возможную дату. При этом после рекурсии все рейсы с датой посадки больше определенной отбрасываются. Добавление условий на максимальную дату в обе части рекурсивного CTE сокращают время работы с 12 секунд до 2.5.
Второе, что можно сделать - это оптимизировать работу с индексами. На таблице создано много индексов, но по одиночным полям. А использование сразу нескольких индексов по одной таблице в запросе хоть и возможно, но не сильно увеличивает производительность, а иногда ее и снижает. Весь вопрос в селективности того или иного индекса. Если по условию индекса отбирается слишком много записей, то работа по нему лишь замедляет выборку. Для того что бы повысить селективность стоит делать составные индексы из нескольких полей подбирающие по условию в запросе как можно меньше записей. В вашем случае необходимо сделать следующее:
DROP INDEX "index_flights_on_available";
CREATE INDEX "index_dep_std" ON "flights"
USING "btree" ("origin_id", "std", "sta", "destination_id", "available");
Индекс по бинарному полю available обладает очень низкой селективностю, отбирая по одному ключу сразу половину всей таблицы. В нем нет смысла. А в данном случае оптимизатор все таки его использовал объединяя результаты с выбором по другому индексу, но это несколько замедляло запрос, затраты на объединение были выше, чем давала фильтрация по нему. Создаваемый же индекс максимально покрывает потребности данного запроса, так как поиск рейсов начинается с определенного АП вылета по интервалу дат, поэтому мы включаем эти поля первыми, сначала проверяемое на точное равенство, потом те, что на диапазон. Включение АП назначения и available позволяет проверить практически все условия из запроса двигаясь по дереву индекса. Данная операция сокращает запрос до 1 секунды.
И наконец еще одно предложение, самое сложное по реализации ... В настоящее время запрос перебирает все возможные сочетания аэропортов из всей маршрутой сети, но очевидно, что полеты через некоторые АП проверять бесполезно. Если нам надо попасть из Москвы в Сочи то лететь первым делом в Мирный, который мягко говоря не в той стороне и главное, у которого весьма специфичная сеть своих рейсов, заведомо проигрышный вариант. Однако рекурсия рассматривает и такие варианты и порождает за одним перелетом в Мирный еще ворох рейсов, следующих из него. Для фильтрации таких ситуаций можно заранее рассчитать достижимость каких либо АП при пролете через другие и в рекурсии не заходить в ветви, по которым требуемый АП назначения заведомо не достижим за оставшиеся N перелетов. Создадим таблицу достижимости АП из других:
create table approach(
orig integer not null, -- Аэропорт вылета
dest integer not null, -- Аэропорт назначения
hop integer not null, -- Минимальное количество перелетов для достижения
constraint approach_pkey primary key(dest,orig)
);
Теперь ее надо заполнить, это самая интересная и сложная часть. Дело в том, что содержимое данной таблицы надо будет всегда поддерживать в актуальном состоянии, как только появляется рейс связывающий аэропорты, между которыми до этого не было прямого сообщения - нам надо пересчитать всю сеть. Изменяются поля cargo_accepted и transit в справочнике аэропортов - опять пересчитать. И что бы таблица отвечала текущей ситуации дополнительно надо ее пересчитывать например раз в сутки. Пересчет выполняется следующим запросом:
WITH RECURSIVE Q(o,d,transit) as(
select origin_id o, destination_id d, a.transit -- Список пар АП из рейсов
from flights f, airports a
where std >= localtimestamp - interval '1 day'
-- and std <= localtimestamp + interval '60 day'
and a.id=f.origin_id and NOT a.cargo_accepted = false
group by origin_id, destination_id, a.transit
),
Tree(orig, dest, hop, transit, route) as(
select o, d, 1, transit, -- Затравка рекурсивной части
'/'||o||'/'||d||'/' AS route
from Q
union all -- Рекурсия
select T.orig, Q.d, T.hop+1, T.transit, T.route||Q.d||'/'
from Tree T, Q
where Q.o=T.dest and not Q.transit=false
and T.route not like '%/'||Q.d||'/%' and T.hop<4
),
New(orig,dest,hop) as( -- Таким должно быть содержимое таблицы
select orig, dest, min(hop) hop
from Tree
group by orig, dest
union select distinct o,o,0 -- Записи из АП в него самого за 0 перелетов нужны поиску
from Q
),
Upd(orig,dest) as( -- Обновляем существующие записи
update approach a
set hop=n.hop
from New n
where a.orig=n.orig and a.dest=n.dest
returning a.orig, a.dest
),
Ins(orig, dest) as( -- Вставляем недостающие
insert into approach(orig,dest,hop)
select orig, dest, hop
from New n
where (n.orig,n.dest) not in(select orig,dest from Upd)
returning orig,dest
) -- И удаляем устаревшие
delete from approach where (orig,dest) not in(select orig,dest from New)
Особое внимание обратите на условия в самом начале. В данном случае берутся все рейсы, начиная со вчерашнего дня, поэтому использовать таблицу можно будет только при поиске будущих рейсов. Если надо искать, что было в прошлом (надеюсь все таки не надо), придется либо менять это условие, что понизит точность в текущий момент, либо не пользоваться ей при поиске в истории. Так же, если например системе никогда не надо искать рейсы, которые вылетят через два месяца, можете раскоментарить ограничение на максимальную дату.
Еще раз напоминаю, что таблицу надо поддерживать в актуальном состоянии. Для этого рекомендую сделать хранимую процедуру с данным запросом и вызывать ее раз в день, в триггере на справочник аэропортов и в триггере на добавление рейсов (что бы это не было слишком частым, вызывать ее только если в таблице approach нет записи с парой аэропортов из добавляемого рейса с полем hop равным 1 (прямой перелет)). В принципе, на текущей сети рейсов она выполняется 80 ms.
И наконец итоговая версия запроса поиска:
WITH RECURSIVE tree AS (
SELECT f0.id::text AS flights,
'/'||origin_id||'/'||destination_id||'/' AS route,
'/'||airline||'/' AS airlines,
'/'||invisible||'/' AS invisible,
origin_id, destination_id,
std AS departure,
sta AS arrival,
0 as hops,
(sta - std)::INTERVAL AS total_time,
'00:00'::INTERVAL AS waiting_time,
available AS available
FROM flights f0
INNER JOIN airports a
ON f0.origin_id = a.id
AND NOT a.cargo_accepted = false
WHERE origin_id = 13
AND airline IN ('LH', 'OK', 'QS', 'U6')
AND std >= '2017-06-02 06:11:02 UTC'
and sta <= '2017-06-27 06:00:28 UTC'
AND NOT f0.available = false
UNION ALL
SELECT s.flights || '-->' || f1.id::text AS flights,
s.route||f1.destination_id||'/',
s.airlines||f1.airline||'/',
s.invisible||f1.invisible||'/',
s.origin_id, f1.destination_id,
s.departure AS departure,
f1.sta AS arrival,
s.hops + 1 AS hops,
s.total_time + (f1.sta - f1.std)::INTERVAL AS total_time,
s.waiting_time + (f1.std - s.arrival)::INTERVAL AS waiting_time,
s.available
FROM tree s
JOIN airports a1
ON s.destination_id = a1.id AND NOT a1.cargo_accepted = false AND NOT a1.transit = false
JOIN flights f1
ON f1.origin_id = s.destination_id
AND f1.std >= s.arrival + '8 hour'
AND f1.std <= s.arrival + '7 day'
AND NOT f1.available = false
JOIN approach app
ON app.dest=49 -- <-- Заменить на требуемый АП назначения
and app.hop<4-1-s.hops -- <-- 4 - та же, что в условии s.hops<4
and f1.destination_id=app.orig
WHERE NOT s.route LIKE '%/'||f1.destination_id||'/%'
AND s.hops < 4
AND NOT s.available = false
AND f1.airline IN ('LH', 'OK', 'QS', 'U6')
and f1.sta <= '2017-06-27 06:00:28 UTC'
)
SELECT *
FROM tree
INNER JOIN airports a3
ON destination_id = a3.id
AND NOT a3.cargo_accepted = false
WHERE destination_id = 49
AND waiting_time < '25 day'
AND arrival <= '2017-06-27 06:00:28 UTC'
AND airlines LIKE '%U6%'
ORDER BY arrival, departure, waiting_time
К сожалению, на маршрутах, действительно требующих нескольких перелетов, скорость уменьшилась только до 500-600ms (вроде 13-49 в примере). Зато на рейсе 13-112 время выполнения уменьшилось до 11 ms (т.е. в 1000 раз по сравнению с вариантом из вопроса). Рекомендую посравнивать на всякий случай результаты после выполнения реальных запросов без использования approach и с ней. В принципе разницы в количестве записей на нескольких тестовых направлениях я не заметил.
