В предыдущих уроках мы говорили о JOIN’е как о логической операции — σ_p(A × B). Декартово произведение + фильтр. С точки зрения семантики это всё, что нужно знать. С точки зрения времени выполнения — нет.

В этом уроке мы посмотрим, как СУБД физически исполняет JOIN. Без деталей оптимизатора (это материал отдельного курса по internals). Цель — дать интуицию, чтобы понимать: «почему этот запрос работает 50 мс, а тот же — на похожих данных — 50 секунд».

Три алгоритма соединения

Реляционные СУБД умеют исполнять JOIN тремя основными способами. У каждого свой профиль: где он силён, где беспомощен.

Nested Loop — самый простой

Двойной цикл: для каждой строки A пройди по всем строкам B, проверь предикат, если истинно — выведи пару.

для каждой строки a в A:
    для каждой строки b в B:
        если p(a, b):  выведи (a, b)

Сложность — O(m × n) в худшем случае. Если m=1000, n=1000, то миллион проверок. Если m=1M, n=1M — триллион проверок. Катастрофа.

Но: если на B есть индекс по колонке предиката — внутренний цикл превращается из «пройди все n» в «найди по индексу за O(log n) или O(1)». Тогда сложность падает до O(m × log n). Для m=1000 и индексированной B размером 1M — это всего ~30 000 операций. Очень быстро.

Когда выбирается: внешняя таблица маленькая, внутренняя — большая, но с индексом по join-колонке. Также — для non-equi-join’ов (где предикат вроде <, >, BETWEEN): hash и merge их не умеют, остаётся только nested loop.

Без индекса — катастрофа. CROSS JOIN без WHERE на двух таблицах по 100k — это 10 миллиардов комбинаций.

Hash Join — для equi-join’ов

Идея: построить hash-таблицу по одной из таблиц (обычно меньшей — «build side»), потом «прокачать» через неё вторую (большую — «probe side»).

построй hash от B по B.key       -- O(n), требует памяти ~ n
для каждой строки a в A:
    найди в hash значение a.key   -- O(1) в среднем
    если есть — выведи пару

Сложность — O(m + n). Линейная. Намного быстрее nested loop без индекса.

Цена — память. Hash-таблицу нужно где-то держать. Если она не помещается в work_mem (параметр PostgreSQL), СУБД переходит на hybrid hash join с диском — это резко тормозит.

Когда выбирается: equi-join на крупных таблицах без полезного индекса. Memory-bound.

Маленькая таблица — слева (или: на build side). Если ты можешь выбирать порядок — кладёт меньшую таблицу как первую (PostgreSQL обычно сам определяет, но иногда ошибается на сложных запросах). Hash-таблица из 1000 элементов помещается легко; из 100M — уже проблема.

Только для equi-join’ов. Hash считается от значения; неравенство «прохешировать» нельзя.

Merge Join — для отсортированных

Если обе таблицы уже отсортированы по join-колонке, то их можно соединить за O(m + n) простой проход слиянием — как при сортировке слиянием.

курсоры a → A, b → B
пока оба не закончились:
    если a.key < b.key: a++
    если a.key > b.key: b++
    если a.key == b.key: выведи (a, b), сдвинь дубликаты

Сложность — O(m + n), если сортировка уже сделана. Если нет — добавляется O(m log m + n log n) на сортировку.

Когда выбирается: обе таблицы можно прочитать уже отсортированными (например, через индекс или результат предыдущего шага плана). Часто это лучший вариант для очень больших таблиц без подходящих хешируемых ключей или когда work_mem мал.

Equi-join vs non-equi: огромная разница

Equi-join (предикат =) могут исполнять все три алгоритма. Non-equi-join (<, >, <>, BETWEEN) — только nested loop. Hash и merge построены на равенстве ключей, неравенство им не подходит.

В выводе EXPLAIN первый запрос покажет Hash Join или Merge Join. Второй — Nested Loop, потенциально с большим cost. На маленьких таблицах разница незаметна. На таблицах в миллион строк — это «10 секунд» vs «несколько часов».

Практическая мораль: если ты можешь переписать non-equi-join через equi-join (например, разбив диапазон на дискретные ключи) — это часто даёт x100 ускорения. Это не всегда возможно, но если возможно — стоит.

Несколько эмпирических правил

Без углубления в оптимизатор, эти правила покрывают 80% случаев:

1. Маленькая таблица слева для hash join (а точнее — build side). PostgreSQL обычно сам это решает, но если видишь странный план — попробуй поменять порядок.
2. Индексируй FK-колонки. orders.customer_id без индекса — это потенциальный nested loop через seq scan, и беда. Большинство СУБД (включая PostgreSQL) не создают индекс на FK автоматически — это ручная работа.
3. Equi-join по возможности. Замени WHERE date_trunc('day', x) = '2025-01-01' на WHERE x >= '2025-01-01' AND x < '2025-01-02' — только в реверс. Первый вариант не индексируется напрямую; второй — да.
4. Селективность раньше. Если у тебя цепочка JOIN’ов и одна таблица сильно фильтруется по WHERE — оптимизатор обычно её обработает первой. Но если он промахнулся — можно подсказать через CTE или порядок JOIN’ов.
5. EXPLAIN ANALYZE — твой друг. Не гадай — измеряй.

Hash join не справляется с памятью — что происходит

work_mem в PostgreSQL по умолчанию — 4 MB. Если hash-таблица не помещается, начинается batch-hash: данные разбиваются на куски, каждый обрабатывается отдельно с временным файлом на диске. Это резко замедляет запрос — диск медленнее RAM в сотни раз.

Симптомы: запрос «вдруг» начал работать в 50 раз дольше после роста данных. Решение: увеличить work_mem (per-session или глобально), уменьшить размер hashable таблицы фильтрацией перед JOIN, или добавить индекс, чтобы оптимизатор выбрал nested loop с index lookup.

На таких маленьких таблицах PostgreSQL может выбрать nested loop (потому что построение hash дороже окупится). На больших — почти всегда hash или merge. EXPLAIN покажет конкретный алгоритм и оценку строк.

Чек-лист

• Три алгоритма JOIN: nested loop, hash join, merge join.
• Nested loop: O(m × n) без индекса, O(m × log n) с индексом. Только этот алгоритм исполняет non-equi-join’ы.
• Hash join: O(m + n), линейный, но требует памяти. Только для equi-join’ов.
• Merge join: O(m + n), если данные уже отсортированы. Иначе плюс сортировка.
• Equi-join намного быстрее non-equi (последний всегда nested loop).
• Индексируй FK-колонки вручную — большинство СУБД не делают это автоматически.
• EXPLAIN ANALYZE показывает реальный план и реальное время. Используй его для диагностики, а не интуицию.