Три способа выполнить один JOIN и почему база выбирает не тот, что вы ждали

MAATRIX

Вы написали JOIN двух таблиц, посмотрели EXPLAIN и не узнали план: там, где вы ждали быстрый проход по индексу, база построила хеш-таблицу и просканировала всё целиком. Первая мысль — оптимизатор сломан. На практике почти всегда наоборот: у соединения таблиц есть три классических алгоритма выполнения, и планировщик честно выбрал тот, что показался ему дешевле по его оценке данных. Разберёмся, как устроены эти три способа и почему "неожиданный" выбор почти никогда не баг.

Три способа склеить две таблицы

Когда СУБД видит SELECT ... FROM a JOIN b ON a.id = b.a_id, у неё есть выбор из трёх базовых физических операций — вне зависимости от того, MySQL это, PostgreSQL или любая другая реляционная база с оптимизатором на основе стоимости (cost-based optimizer):

• Nested Loop Join — для каждой строки одной таблицы искать совпадения в другой.
• Hash Join — построить хеш-таблицу по одной стороне и пройтись по другой, проверяя совпадения через неё.
• Merge Join — слить два заранее отсортированных потока, как две отсортированные колоды карт.

Ни один из них не "лучше" в общем смысле — каждый выигрывает в своих условиях: при разном объёме данных, при наличии или отсутствии подходящего индекса, при доступной памяти. Планировщик оценивает стоимость каждого варианта для конкретного запроса и конкретных таблиц и берёт тот, что дешевле по его расчётам. Дальше — про каждый алгоритм отдельно, и про то, откуда берётся эта оценка.

Nested Loop Join: перебор ради простоты

Это самый прямолинейный алгоритм: берём каждую строку из внешней (driving) таблицы и для неё ищем совпадения во внутренней. Псевдокод:

for row_a in table_a:
    for row_b in table_b:
        if row_a.id == row_b.a_id:
            emit(row_a, row_b)

В таком виде это O(N × M) — квадратичная сложность, неприемлемая для сколько-нибудь крупных таблиц. Но на практике внутренний цикл почти всегда идёт не полным сканированием, а через индекс:

for row_a in table_a:
    row_b = index_lookup(table_b, key = row_a.id)
    emit(row_a, row_b)

Тогда сложность падает примерно до N × O(log M) — по числу строк внешней таблицы, умноженному на стоимость одного индексного поиска. Это делает nested loop отличным выбором, когда:

• внешняя таблица (или отфильтрованная её часть) даёт немного строк — например, после WHERE user_id = 42;
• на столбце соединения внутренней таблицы есть подходящий индекс;
• нужен ответ на первые строки быстро, а не весь результат сразу (поэтому nested loop часто встречается в планах с LIMIT).

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

EXPLAIN (ANALYZE, BUFFERS)
SELECT o.id, o.total, c.name
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.status = 'pending';

В плане nested loop обычно выглядит так: Nested Loop -> Seq Scan on orders (filter: status = 'pending') -> Index Scan using customers_pkey on customers. Внешний узел — то, что даёт мало строк после фильтра, внутренний — то, где есть индекс по ключу соединения.

Hash Join: сначала строим таблицу в памяти

Когда подходящего индекса нет или обе стороны соединения велики, перебор с поиском по индексу становится невыгодным — слишком много точечных обращений. Здесь на сцену выходит hash join, устроенный в два этапа:

1. Build-фаза. Берётся меньшая по оценке сторона (build side), и по ключу соединения строится хеш-таблица в памяти.
2. Probe-фаза. По каждой строке второй таблицы (probe side) вычисляется тот же хеш, и происходит поиск совпадения в уже построенной хеш-таблице — это O(1) в среднем, а не O(log N), как у индекса.

Итоговая сложность близка к O(N + M) — линейной по сумме размеров обеих таблиц, без квадратичного роста. Это делает hash join хорошим выбором именно для больших объёмов без подходящего индекса: не нужно сортировать данные заранее, не нужно, чтобы кто-то из участников соединения был маленьким.

Ключевое ограничение — память. Хеш-таблица строится в оперативной памяти (в PostgreSQL это ограничено параметром work_mem), и если build-сторона не помещается, база переходит к grace hash join: делит обе стороны на пакеты (batches) по хешу и обрабатывает их по очереди, частично сбрасывая данные на диск. Это работает, но заметно медленнее, чем однопроходный вариант в памяти.

-- посмотреть текущий лимит памяти на операцию сортировки/хеширования
SHOW work_mem;

-- временно увеличить для конкретной сессии/транзакции, если оптимизатор
-- уходит в multi-batch hash join там, где памяти чуть-чуть не хватает
SET work_mem = '64MB';

В плане запроса это видно как Hash Join -> Hash (тут строится таблица) -> Seq Scan on ... -> Seq Scan on ..., а при переходе на диск — как рост числа Batches в выводе EXPLAIN (ANALYZE, BUFFERS).

Merge Join: слияние двух отсортированных потоков

Третий алгоритм требует, чтобы оба входа уже были отсортированы по ключу соединения — либо потому что данные читаются через индекс, который и так упорядочен, либо потому что планировщик добавил явный шаг сортировки перед соединением. Дальше всё просто: два указателя идут по своим потокам, как при слиянии двух отсортированных списков (merge step из merge sort):

i, j = 0, 0
while i < len(a) and j < len(b):
    if a[i].key < b[j].key: i += 1
    elif a[i].key > b[j].key: j += 1
    else:
        emit(a[i], b[j])
        # обработать дубликаты по ключу с обеих сторон
        ...

Каждая строка просматривается не более пары раз, без хеш-таблицы в памяти и без точечных индексных поисков на каждую строку. Merge join особенно хорош, когда:

• оба входа и так упорядочены — например, читаются через индекс по ключу соединения или пришли из ORDER BY, совпадающего с условием JOIN;
• объёмы велики, а строить хеш-таблицу в памяти дорого или её некуда поместить;
• нужен результат в отсортированном порядке дальше по плану — например, для последующей группировки.

Минус — если данные не отсортированы заранее, планировщику приходится добавлять явный шаг Sort перед merge join, а сортировка сама по себе не бесплатна: она может занять память (work_mem) или уйти на диск во временные файлы, если данных слишком много. В этом случае hash join часто оказывается дешевле, потому что не требует полной сортировки — и планировщик учитывает это при выборе.

EXPLAIN (ANALYZE, BUFFERS)
SELECT e.id, e.amount, a.category
FROM events e
JOIN accounts a ON a.id = e.account_id
ORDER BY e.account_id;

В плане merge join выглядит как Merge Join -> Index Scan using events_account_id_idx -> Index Scan using accounts_pkey — оба узла уже дают отсортированный поток, без отдельного Sort сверху.

Как планировщик выбирает алгоритм

Оптимизатор запросов — это не набор жёстких правил вида "если строк больше миллиона, используй hash join". Это калькулятор стоимости: для каждого разумного плана он считает приблизительную "цену" в условных единицах (последовательное чтение страницы, случайное чтение, сравнение строк, обращение к процессору) и берёт план с наименьшей суммарной ценой. У соединения таблиц эта цена складывается из нескольких факторов:

Подробнее о механизме выбора плана и формулах стоимости — в статье как планировщик запросов выбирает план и где ошибается.

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

Почему "неожиданный" выбор почти всегда статистика, а не баг

Когда план кажется субъективно неверным — планировщик взял hash join там, где вы бы поставили nested loop с индексом, или наоборот, — в подавляющем большинстве случаев причина не в логике оптимизатора, а в том, что его входные оценки разошлись с реальностью. Несколько типичных источников такого расхождения:

• Устаревшая статистика. После массовой загрузки или удаления строк старая статистика может считать таблицу маленькой, хотя она уже выросла на порядок. Обновляется она автоанализом не мгновенно, а по порогу изменений — на свежих таблицах может просто не успеть.
• Коррелированные столбцы. Оптимизатор по умолчанию считает столбцы независимыми. Если WHERE city = 'Москва' AND region = 'Центральный' на деле сильно коррелируют, реальная селективность условия выше, чем произведение селективностей по отдельности, — планировщик может занизить или завысить ожидаемое число строк.
• Функции над столбцом соединения. JOIN ... ON lower(a.email) = b.email часто лишает планировщик возможности использовать индекс — если только по выражению lower(email) не создан функциональный индекс.
• Перекос распределения (skew). Если большая доля строк имеет одно и то же значение ключа соединения, а гистограмма статистики недостаточно детальна, число совпадений для "тяжёлых" значений может сильно отличаться от предполагаемого.

Конкретный случай такого расхождения разобран в статье индекс был, а планировщик его не брал из-за статистики.

Проверить это несложно: EXPLAIN ANALYZE (не просто EXPLAIN) показывает не только план, но и реальное число строк на каждом узле рядом с оценкой планировщика. Если оценка и факт расходятся на порядок и больше — вот и причина "неожиданного" плана:

EXPLAIN (ANALYZE, BUFFERS)
SELECT ...
JOIN ...;

-- в выводе ищите пары вида:
-- Hash Join (cost=... rows=1200 width=...) (actual time=... rows=48000 loops=1)
--                            ^ оценка                          ^ факт

Разница rows=1200 в оценке против rows=48000 по факту — это не ошибка hash join как алгоритма, это ошибка входных данных, на которых он был выбран. С точным прогнозом планировщик мог бы вообще предпочесть другой алгоритм — но узнать точное число строк заранее, не выполнив запрос, он не может в принципе; вся его работа строится на приближении.

Как обновить статистику и проверить гипотезу

Если план резко изменился после загрузки данных или миграции — первым делом обновите статистику вручную, не дожидаясь автоанализа:

-- PostgreSQL: пересчитать статистику по конкретной таблице
ANALYZE orders;

-- заглянуть в саму сохранённую статистику по столбцу
SELECT attname, n_distinct, correlation
FROM pg_stats
WHERE tablename = 'orders' AND attname = 'customer_id';

Сравните план "до" и "после" ANALYZE — это покажет, была ли причина именно в устаревшей оценке. Отдельно проверьте, что на столбцах соединения вообще есть индексы: без них планировщик может брать hash join не потому, что он выгоднее, а потому что альтернативы нет:

CREATE INDEX CONCURRENTLY idx_orders_customer_id ON orders (customer_id);

Чтобы проверить гипотезу "а что если бы база выбрала другой алгоритм", в PostgreSQL можно на уровне сессии отключить конкретный метод соединения и сравнить планы — это диагностический приём, а не постоянная настройка:

BEGIN;
SET LOCAL enable_hashjoin = off;
EXPLAIN (ANALYZE, BUFFERS) SELECT ...;
ROLLBACK;

Если альтернативный план оказался быстрее — это сигнал разбираться со статистикой, индексами или структурой запроса, а не "чинить планировщик". Держать методы соединения выключенными глобально — плохая идея: это лишает оптимизатор гибкости на всех будущих запросах.

Если план включает явную сортировку перед соединением, проверьте, не уходит ли она на диск из-за нехватки work_mem — механика разобрана в статье о том, как временные файлы сортировки заполнили диск за несколько минут: та же причина часто стоит за медленным merge join.

Частые вопросы