Порядок соединений, GEQO и кеш плана

Соединение трёх таблиц A, B, C можно собрать в разном порядке: (A⋈B)⋈C, (A⋈C)⋈B, (B⋈C)⋈A и так далее. Для каждого порядка ещё выбирается алгоритм (nested loop / hash / merge) и метод доступа к каждой таблице. Число комбинаций растёт быстрее факториала от числа таблиц.

таблиц:   2     3     4      5       ...    10

порядков: 1     3     15     105     ...    ~17 млн

На 4-5 таблицах перебрать всё ещё реально. На 10 - уже миллионы вариантов, и честный перебор каждого занял бы дольше, чем само выполнение запроса. Планировщик должен где-то остановиться.

Пока таблиц немного, планировщик ищет лучший порядок почти полным перебором, но умно - динамическим программированием: лучший план для пары таблиц переиспользуется при построении планов для троек, и так далее. Это резко сокращает работу по сравнению с наивным перебором.

Сколько таблиц «немного», задаёт join_collapse_limit (по умолчанию 8). Он управляет тем, насколько планировщик волен менять порядок явных JOIN. Если число таблиц в одном уровне FROM превышает лимит, планировщик перестаёт переставлять их и берёт порядок, как написано в запросе.

SHOW join_collapse_limit;   -- 8

SHOW from_collapse_limit;   -- 8 (то же для подзапросов)

Практическое следствие: на запросе с десятком таблиц порядок, в котором ты написал JOIN, начинает влиять на план. Иногда это используют намеренно - выставляют join_collapse_limit = 1, чтобы зафиксировать порядок соединений вручную.

Когда таблиц очень много, даже динамическое программирование становится дорогим. На этот случай есть GEQO - genetic query optimization. Вместо перебора он ищет хороший порядок генетическим алгоритмом: берёт несколько случайных порядков, «скрещивает» лучшие, вносит мутации, отбирает по стоимости - несколько поколений, и достаточно хороший порядок найден.

Включается GEQO, когда число таблиц в соединении достигает geqo_threshold (по умолчанию 12). Важная особенность: GEQO не гарантирует оптимальный план и недетерминирован - на одном и том же запросе он может выдать чуть разные порядки. Это сознательный размен: на 15 таблицах лучше быстро найти хороший план, чем долго искать идеальный.

SHOW geqo_threshold;   -- 12

Планирование - это работа, и на сложных запросах она заметна. Увидеть её можно двумя способами:

EXPLAIN ANALYZE SELECT ...;   -- внизу строка Planning Time

EXPLAIN (MEMORY) SELECT ...;  -- сколько памяти ушло на планирование

Planning Time против Execution Time показывает баланс: если запрос выполняется за 2 мс, а планируется за 20 - планирование доминирует, и его стоит кешировать. Меняя join_collapse_limit и geqo_threshold, можно наблюдать, как растёт Planning Time с числом рассмотренных порядков. Это и есть мотивация кеша плана: запланировать один раз, выполнять много.

Подготовленное выражение (PREPARE) разбирается и анализируется один раз, а выполняется много с разными параметрами. Сначала PostgreSQL для каждого вызова строит custom plan - план под конкретные значения параметров. Это точно, но каждый раз тратит время на планирование.

PREPARE q(int) AS SELECT * FROM tickets WHERE flight_id = $1;

EXECUTE q(7);

EXECUTE q(8);

После нескольких выполнений (порядка пяти) планировщик прикидывает: а нельзя ли построить один generic plan - план без привязки к значению параметра, который годится для любого $1? Если средняя стоимость custom-планов не выгоднее generic, он переключается на generic и перестаёт планировать на каждый вызов.

Разница принципиальная. Custom plan видит конкретное значение и оценивает селективность точно: flight_id = 7 - редкое значение, возьмём индекс. Generic plan значения не видит и берёт усреднённую селективность - что хорошо для «обычного» параметра, но плохо для перекошенных данных.

SELECT name, generic_plans, custom_plans

FROM pg_prepared_statements;

Управлять выбором можно вручную:

SET plan_cache_mode = force_custom_plan;   -- всегда планировать заново

SET plan_cache_mode = force_generic_plan;  -- всегда один план

SET plan_cache_mode = auto;                -- решает сам (по умолчанию)

Беда приходит, когда значения параметра сильно различаются по селективности. Пусть status = 'done' встречается у 99% строк, а status = 'error' - у 0.01%. Для 'error' нужен индекс, для 'done' - Seq Scan.

Generic plan усреднит и выберет что-то одно - и будет плохим для половины вызовов. Симптом: после нескольких выполнений подготовленное выражение «вдруг» замедлилось (переключилось на generic), хотя текст и параметры те же. Видно по росту generic_plans в pg_prepared_statements.

Лечение - plan_cache_mode = force_custom_plan для таких запросов: пусть планирует каждый раз, зато под реальное значение. Платишь временем планирования, выигрываешь правильный план. Подробнее про кеш и порядок - в join-order-geqo.