В прошлом уроке мы видели: planner перебирает physical planы для каждой equivalence class и выбирает дешёвый. Но в формуле «перебирает» прячется боль. Сколько именно physical planов он рассматривает? Для 4 таблиц это десятки. Для 10 — миллиарды. Если бы planner честно искал всё, простой SELECT мог бы планироваться часами.

Postgres использует два разных алгоритма: dynamic programming для маленьких join-сетов и GEQO (Genetic Query Optimizer) для больших.

Комбинаторика join order

Для N таблиц число различных

Стандартный поиск Postgres — System R-style dynamic programming (не полный перебор, а DP, который запоминает оптимум для каждого подмножества таблиц). Сложность ≈ O(2^N × N). На 8 таблицах — мгновенно. На 12 — заметно. На 16+ planning может занимать сравнимо или больше, чем сам запрос.

И здесь включается GEQO.

Что такое GEQO

GEQO = Genetic Query Optimizer. Идея простая: вместо честного перебора устраиваем эволюционный поиск. Каждый «индивид» — это порядок join’ов (например, (((A ⋈ C) ⋈ B) ⋈ D)). Считаем его cost. Затем:

1. Создаём начальную популяцию случайных порядков.
2. Скрещиваем (crossover) — берём кусок порядка от одного, кусок от другого.
3. Мутируем — случайно меняем местами пары.
4. Отбираем дешёвых — они дают следующее поколение.
5. Через несколько поколений лучший индивид — наш план.

GEQO не гарантирует оптимальный план — только достаточно хороший за фиксированное время. Это компромисс: planning ~50 ms против ~50 секунд DP, ценой плана, который, возможно, на 10-20% хуже оптимального.

Когда включается

Параметр geqo_threshold (по умолчанию 12) — если в запросе количество

Проверим:

Если бы pglite поддерживал большие планы и реальные временные замеры, ты бы увидел, как при разных geqo_seed план меняется — это и есть стохастичность генетического поиска.

Главная проблема: нестабильность плана

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

В продакшене это часто неприемлемо: SLA требует предсказуемости. Один день запрос летает за 50ms, другой — за 5 секунд, потому что GEQO в этот раз нашёл плохой порядок.

Лечение:

• Зафиксировать seed: SET geqo_seed = 0.5; — даёт детерминированный поиск, но всё ещё не оптимальный.
• Поднять geqo_threshold: если у тебя обычно 8-10 таблиц, поставь threshold = 15 — будет работать DP, медленнее planning, но стабильно.
• Совсем отключить: SET geqo = off — все запросы пойдут через DP. Опасно: на действительно больших запросах planning займёт минуты.
• Увеличить количество поколений/популяцию: geqo_generations, geqo_pool_size — больше шансов на оптимум, но медленнее.

Не путать с join_collapse_limit

Часто параметры GEQO путают с другим: join_collapse_limit и from_collapse_limit (оба по умолчанию 8). Они контролируют не алгоритм поиска, а уплощение JOIN-дерева. Если у тебя 15 JOIN’ов, но join_collapse_limit = 8, planner возьмёт первые 8 и оптимизирует их вместе, а остальные — в порядке написания. То есть «защита» от долгого планирования через ограничение пространства, а не через GEQO.

Иногда выгоднее поднять join_collapse_limit (например, до 12-15) и выключить GEQO — тогда DP честно ищет оптимум на чуть большем пространстве, но без рандома. Это типичная настройка под аналитические workloads.

Когда отключают GEQO

В большинстве OLTP-нагрузок GEQO не срабатывает: запросы имеют 1-5 таблиц, до threshold далеко. Он становится темой при:

• Аналитика / OLAP: сложные звёздные/снежинковые схемы с 10+ dim-таблицами. Здесь нестабильность времени запроса заметна и часто отключают geqo = off.
• ORM-сгенерированный код: некоторые ORM (особенно для multi-tenant с большим количеством join’ов на permission-фильтры) производят запросы с 15+ join’ами случайно. Тут GEQO — палка о двух концах.
• Reporting: где время planning не критично, а вот стабильное время выполнения важно.

Эмпирическое правило: если у тебя есть запросы с 12+ JOIN’ов в проде, проверь, нужен ли тебе GEQO — либо подкрути threshold/seed, либо отключи.

Чек-лист

• DP-search (System R) экспоненциален: на ~12+ таблицах становится слишком дорогим.
• GEQO = эволюционный поиск порядка JOIN’ов: популяция, crossover, mutation, fitness = cost.
• Включается автоматически при геqo_threshold = 12 и более FROM items.
• Главный недостаток — нестабильность: один и тот же запрос → разные планы между запусками.
• Лечение: фиксированный geqo_seed, поднять threshold или совсем geqo = off (с большим join_collapse_limit).
• Не путать с join_collapse_limit / from_collapse_limit — это про границу оптимизации, а не про алгоритм.
• OLTP редко затрагивается; OLAP/reporting/ORM-генерация — типичные кандидаты на ручную настройку.