Когда в запросе три JOIN’а — оптимизатор может выбирать порядок из десятка вариантов. Когда десять — из миллиона. Когда двадцать — из астрономического числа. Эта задача NP-hard, но оптимизатор Postgres решает её каждый раз, когда ты выполняешь сложный SELECT. Понимание как именно он это делает — ключ к диагностике планов, которые «вдруг стали медленными».

Почему порядок JOIN важен

Два эквивалентных по результату плана могут различаться по скорости в 100-1000 раз. Простой пример: соединяем три таблицы A, B, C. После фильтра в A осталось 10 строк, в B — 10M, в C — 10K. Сравним два порядка:

• (A JOIN B) JOIN C: сначала Nested Loop A × B (10 × 10M = 100M операций, если нет индекса по join-ключу), потом результат с C.
• (A JOIN C) JOIN B: сначала A × C (10 × 10K = 100K), получаем ~10 строк, потом NL с B (10 × log 10M = 230). Итого 100K + 230.

Разница — в миллион раз. И заметь: это не «лучший выбор индекса» — это именно порядок соединения. Оптимизатор должен это сообразить до того, как запрос пойдёт в executor.

Дерево соединения: left-deep vs bushy

Любой план соединения N таблиц можно представить как бинарное дерево, листья — таблицы, узлы — операторы JOIN.

Постгрес умеет генерировать оба варианта и считает их стоимости. На N таблиц число left-deep планов — N!, число bushy — Catalan(N) × N! (катастрофически больше). Поэтому оптимизатор ограничивает search space.

Cost-based exhaustive search

При числе JOIN-таблиц до geqo_threshold (по умолчанию 12), оптимизатор делает полный перебор через динамическое программирование по подмножествам таблиц. Алгоритм:

# DP по подмножествам таблиц (System R, Selinger 1979)
best[{T}] = cost of scanning T alone, для каждой таблицы T
for size = 2 to N:
    for each subset S of size 'size':
        for each split (L, R) of S into two non-empty parts:
            cost = best[L] + best[R] + join_cost(L, R)
            if cost < best[S]: best[S] = cost; best_plan[S] = ...

Сложность — O(3^N) (число способов разбить N таблиц на два подмножества и их подмножества). На 12 таблицах это 530K вариантов — пара миллисекунд. На 13 — миллион с лишним, заметно. На 20 — миллиарды, неприемлемо.

Поэтому при числе таблиц больше или равно geqo_threshold, Postgres переключается на

Параметры, которые управляют процессом

Несколько ключевых GUC-переменных:

• geqo_threshold (default 12) — с какого числа таблиц переходить на GEQO.
• join_collapse_limit (default 8) — до какого числа явных JOIN Postgres «уплощает» их в одну группу для перебора. Если у тебя A JOIN B JOIN C JOIN D и limit = 8, оптимизатор рассмотрит все 4! = 24 порядка. Если limit = 3, он зафиксирует порядок первых JOIN’ов как написано.
• from_collapse_limit (default 8) — аналог для FROM a, b, c, d (старый синтаксис без JOIN). До этого числа таблиц подзапросы во FROM сглатываются.
• enable_geqo (default on) — выключить GEQO; на больших запросах это вернёт exhaustive search и долгие планирования.

Подсказка из практики: если у тебя 15-20 JOIN’ов и GEQO даёт плохой план, попробуй поднять geqo_threshold до 20 — exhaustive search будет занимать секунды, но даст лучший план. На запросах, которые выполняются раз в час, это терпимо.

Как оптимизатор оценивает каждый вариант

Для каждой пары (L, R) он считает:

1. Cardinality (число строк в результате JOIN) — через pg_stats, корреляции, гистограммы. Это самый шаткий момент: ошибка в оценке кардинальности подмножества каскадно убивает выбор.
2. Стоимость каждого алгоритма — Nested Loop, Hash Join, Merge Join.
3. Можно ли использовать индекс на любой стороне.
4. Можно ли параллелить — для бушевых деревьев это особенно важно.

Самая частая причина «плохого плана» — ошибка в estimate. Постгрес посчитал, что WHERE x = 5 пропустит 100 строк, а реально пропускает миллион. Кардинальность раздулась, дальше каскад: каждый следующий JOIN получает на вход неправильный размер, выбирает не тот алгоритм, не тот порядок. Лекарство — ANALYZE, CREATE STATISTICS (extended statistics), переписать запрос.

Demo: эффект join_collapse_limit

Постгрес сам решит, начинать ли с customers (где is_vip = true, малая выборка) или с orders (где status = paid, большая выборка). При малом is_vip — он почти наверняка начнёт с customers как build для Hash Join.

Теперь поставим жёсткий лимит, и заставим выполнять в порядке текста запроса:

На двух таблицах разницы не будет — это просто демонстрация механизма. Но на 5-10 таблицах принудительный порядок может ускорить или замедлить запрос в десятки раз. Иногда join_collapse_limit = 1 используют как «хак» для ручной оптимизации: переписывают FROM в нужном порядке, и принудительно его фиксируют.

Demo: видим перебор GEQO

Можно увеличить число таблиц через симуляцию, чтобы посмотреть, как GEQO начинает работать:

В EXPLAIN на простом 2-таблицу JOIN визуально ничего не изменится. Но если бы у тебя был запрос на 20 таблиц, GEQO дал бы план за миллисекунды, exhaustive — секунды или минуты. Это компромисс «качество плана vs время на планирование».

Когда оптимизатор ошибается

Типичные ловушки:

1. Коррелированные предикаты. Постгрес считает, что WHERE country = 'RU' AND city = 'Moscow' отсекает selectivity(country) × selectivity(city) = 0.2 × 0.001 = 0.0002. Реально: city=Moscow существует только для country=RU, значит отсекает 0.001. Кардинальность сильно недооценена. Решение — CREATE STATISTICS (extended statistics с зависимостями).
2. IN (...) на много значений. Селективность считается линейно, но в плане часто формируется как Hash Join по временной таблице — оценка размера выборки страдает.
3. Корелированные подзапросы. Подзапрос внутри SELECT часто планируется как Nested Loop с подплана, что бывает в 100 раз медленнее, чем перепись через CTE/JOIN.
4. OR в join-условии. Декомпозируется в UNION ALL двух планов, и порядок может быть невозможен оптимальный.

Ручное вмешательство: pg_hint_plan

Постгрес сам не имеет hint’ов (как Oracle или MySQL). Но есть расширение pg_hint_plan, которое позволяет писать комментарии вроде:

/*+ HashJoin(c o) Leading((c o)) */
SELECT ...

Это: «Использовать Hash Join для c и o; начинать соединения с (c, o)». Полезно для критичных запросов, где статистика стабильно ошибается. В коре Postgres’а такого нет — но в production-системах с этим работают регулярно.

Чек-лист

• Порядок JOIN — отдельное измерение оптимизации, может менять время в 100-1000 раз.
• Постгрес делает exhaustive cost-based search для < geqo_threshold (default 12), переключается на GEQO выше.
• join_collapse_limit (default 8) — до какого числа явных JOIN их можно переставлять. Большее значение даёт больше свободы, но и больше времени на планирование.
• Left-deep tree — линейный pipeline; bushy — позволяет параллелизм, но взрывает search space.
• Главная причина «плохого плана» — ошибка в estimate cardinality. Решение: ANALYZE, CREATE STATISTICS, переписать запрос.
• Для жёсткой фиксации порядка: SET join_collapse_limit = 1 + правильный порядок таблиц в FROM.
• pg_hint_plan позволяет инджектить hint’ы в комментариях (как в Oracle), полезно для критичных запросов.
• Запросы из 20+ таблиц — это обычно знак, что данные плохо нормализованы или запрос можно разбить на этапы.