CS Notes

join-order

7 min read

Порядок соединения таблиц (Join Ordering)

Предпосылки: планировщик запросов (cost model, методы доступа, алгоритмы соединения — nested loop, hash join, merge join), динамическое программирование (идея «лучшее решение через лучшие подзадачи»), JOIN (виды соединений, семантика).

← Планировщик запросов | Подзапросы и CTE →

Планировщик выбирает метод доступа к каждой таблице и алгоритм соединения для каждой пары. Но когда в запросе несколько JOIN, появляется ещё одно измерение выбора: в каком порядке строить дерево соединений. Количество вариантов растёт взрывным образом:

ТаблицПорядков соединения
312
51 680
817 297 280
1017 643 225 600
1228 158 588 057 600

Здесь считаются возможные бинарные деревья соединений (bushy trees) для N таблиц, если между таблицами есть условия соединения и их можно комбинировать разными способами. В реальных запросах вариантов обычно меньше (из-за структуры join graph), но даже тогда пространство поиска быстро становится слишком большим для полного перебора.

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

Стоимость плана определяется размером промежуточных результатов. Рассмотрим запрос:

SELECT *
FROM orders o          -- 10 000 000 строк
JOIN users u ON o.user_id = u.id    -- 1 000 000 строк
JOIN products p ON o.product_id = p.id  -- 50 000 строк
WHERE u.country = 'Japan';  -- фильтр оставляет 10 000 пользователей

При порядке (orders ⋈ products) ⋈ users сначала соединяются 10M заказов с 50K товаров — промежуточный результат огромен, а фильтр по стране применяется только в конце. При порядке (users ⋈ orders) ⋈ products фильтрация country = 'Japan' сокращает users до 10 000 строк, соединение с orders даёт ~100 000 заказов, и только этот компактный набор соединяется с products. Разница в объёме промежуточных данных — два порядка величины, а значит и разница во времени выполнения: секунды против миллисекунд.

Принцип: соединение выгодно начинать с таблицы, которая после фильтрации даёт наименьший результат. Чем раньше данные «сужаются», тем меньше работы на каждом следующем шаге.

Динамическое программирование

Для небольшого числа таблиц PostgreSQL находит оптимальный порядок соединения через динамическое программирование — восходящий перебор подмножеств.

На первом шаге планировщик оценивает стоимость доступа к каждой таблице отдельно, с учётом фильтров WHERE. Это базовые планы — одноэлементные подмножества {A}, {B}, {C}.

На втором шаге перебираются все пары таблиц, между которыми есть условие соединения. Для каждой пары планировщик пробует все три алгоритма (nested loop, hash join, merge join) и сохраняет лучший план. Получаются двухэлементные подмножества {A,B}, {A,C}, {B,C}.

На третьем шаге — тройки. Подмножество {A,B,C} можно получить тремя способами: {A,B} ⋈ C, {A,C} ⋈ B, {B,C} ⋈ A. Для каждого варианта планировщик берёт уже найденный лучший план для пары и рассчитывает cost соединения с оставшейся таблицей. Побеждает вариант с минимальным cost.

Шаг 1: {A}, {B}, {C} — базовые планы доступа

Шаг 2: {A,B}, {A,C}, {B,C} — лучшие планы для пар

Шаг 3: {A,B,C} — лучший из:
  {A,B} ⋈ C
  {A,C} ⋈ B
  {B,C} ⋈ A

И так далее до полного набора таблиц. Ключевая идея здесь в том, что планировщик переиспользует уже найденные лучшие планы для подмножеств и не пересчитывает одно и то же с нуля. При 10 таблицах подмножеств всего 2^10 = 1 024, но для каждого подмножества всё равно нужно рассмотреть разные способы разбиения (и несколько интересных порядков результата, см. ниже) — поэтому время планирования растёт экспоненциально и у полного перебора есть естественный предел.

Interesting orders

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

Допустим, для подмножества {A,B} нашлись два плана: hash join с cost = 1000 (результат не отсортирован) и merge join с cost = 1200 (результат отсортирован по ключу соединения). По простому правилу планировщик оставляет hash join — он дешевле. Но при добавлении таблицы C, если соединение с C тоже выполняется merge join, результат hash join потребует дополнительной сортировки (допустим, +500), а результат merge join — уже отсортирован, и merge join с C обойдётся без неё. Итого: hash join путь стоит 1000 + 500 + X, а merge join путь — 1200 + X. Merge join мог дать лучший итоговый план, но был отброшен на предыдущем шаге.

Планировщик решает эту проблему, сохраняя несколько планов для каждого подмножества — по одному для каждого «интересного порядка» (interesting order). Порядок считается интересным, если он может пригодиться на следующих шагах: для merge join с другой таблицей, для ORDER BY в финальном запросе или для GROUP BY. Это увеличивает объём работы планировщика, но позволяет находить глобально оптимальные планы, где дешёвый промежуточный шаг окупается экономией на последующих.

Какой алгоритм соединения какой порядок даёт:

АлгоритмПорядок результата
Hash JoinНе определён — хеш-функция «перемешивает» значения, близкие ключи попадают в разные бакеты
Merge JoinОтсортирован по ключу соединения — алгоритм требует отсортированных входов и обходит их последовательно
Nested LoopПорядок внешней таблицы — внутренняя сканируется заново для каждой строки внешней

Merge join — единственный алгоритм, гарантирующий отсортированный результат, что делает его кандидатом для interesting orders даже при чуть большем cost.

GEQO — генетический оптимизатор

Динамическое программирование с 2^N подмножествами работает до определённого предела. При 12 таблицах подмножеств уже больше 4 000, а с учётом interesting orders и трёх алгоритмов на каждое соединение объём вычислений становится ощутимым. Когда число таблиц в запросе превышает порог geqo_threshold (по умолчанию 12), PostgreSQL переключается на GEQO — Genetic Query Optimizer.

GEQO работает по принципу генетического алгоритма. Начальная популяция — набор случайных порядков соединения. Для каждого порядка вычисляется cost (fitness). Планы с лучшим cost с большей вероятностью «выживают» и передают свои гены — фрагменты порядка — в следующее поколение через скрещивание. Случайные мутации вносят разнообразие. После нескольких поколений популяция сходится к хорошему (но не гарантированно оптимальному) плану.

Практическое следствие: GEQO недетерминирован. Два вызова EXPLAIN для одного и того же запроса могут показать разные планы, потому что начальная популяция генерируется случайно. Это затрудняет отладку и делает записи pg_stat_statements менее стабильными.

Управление порядком соединения

Когда планировщик выбирает неоптимальный порядок — из-за неточной статистики или ограничений GEQO — есть несколько способов повлиять на его решение.

join_collapse_limit и явный JOIN

PostgreSQL обычно «разворачивает» все JOIN в плоский список таблиц и ищет оптимальный порядок через dynamic programming. Параметр join_collapse_limit (по умолчанию 8) определяет, до скольких таблиц планировщик будет переупорядочивать JOIN. При значении 1 планировщик сохраняет порядок как написано в запросе:

SET join_collapse_limit = 1;
 
SELECT * FROM A
JOIN B ON A.id = B.a_id
JOIN C ON B.id = C.b_id;

Планировщик выполнит соединения строго в порядке (A ⋈ B) ⋈ C. Это максимально жёсткий контроль: оптимизатор не будет переставлять JOIN, и качество плана будет зависеть от этого порядка.

Синтаксис FROM A, B, C WHERE ... не задаёт порядок — это просто три таблицы, которые планировщик соединит в любой последовательности. Для контроля нужен именно явный JOIN.

from_collapse_limit и подзапросы в FROM

Параметр from_collapse_limit (по умолчанию 8) контролирует, до скольких таблиц планировщик будет разворачивать подзапросы в FROM:

SELECT * FROM (
  SELECT * FROM A JOIN B ON A.id = B.a_id
) ab
JOIN C ON ab.id = C.ab_id;

По умолчанию планировщик может развернуть подзапрос и переупорядочить все три таблицы. При from_collapse_limit = 1 подзапрос остаётся отдельной единицей планирования: сначала оптимизируется внутренний запрос (A ⋈ B), потом результат соединяется с C. Условия могут «проталкиваться» внутрь подзапроса, поэтому контроль мягче, чем join_collapse_limit = 1.

CTE с MATERIALIZED

WITH small_set AS MATERIALIZED (
  SELECT * FROM big_table WHERE very_selective_condition
)
SELECT * FROM small_set JOIN other_table ON ...;

MATERIALIZED гарантирует, что подзапрос выполнится отдельно, результат сохранится во временном хранилище, и только потом произойдёт соединение. Это полностью изолирует CTE от join ordering основного запроса. Подробнее о поведении CTE — в подзапросах и CTE.

Увеличение geqo_threshold

SET geqo_threshold = 14;

Заставляет планировщик использовать полный перебор (dynamic programming) для большего числа таблиц. Время планирования растёт, но план может оказаться лучше, чем результат GEQO. Имеет смысл, когда GEQO стабильно выбирает плохие планы для конкретного запроса.

Сравнение способов

СпособЖёсткостьКогда применять
join_collapse_limit = 1 + явный JOINМаксимальнаяПорядок соединения фиксируется вручную
from_collapse_limit = 1 + подзапросыСредняяЧастичный контроль, условия могут проталкиваться
CTE с MATERIALIZEDВысокаяНужно зафиксировать промежуточный результат
Увеличить geqo_thresholdКосвеннаяGEQO выбирает плохие планы

Все эти механизмы контролируют пространство поиска для соединений. Но не все части запроса — соединения: подзапросы и CTE создают отдельные единицы планирования, которые планировщик может развернуть в общий join tree или оставить изолированными — подзапросы и CTE.

Sources

← Планировщик запросов | Подзапросы и CTE →

Graph View

Backlinks