Если Nested Loop — старая и универсальная лошадка, то Hash Join — это специализированный спорткар для больших equi-join. Идея пришла из теории баз данных 70-х: вместо двойного перебора построить хэш-таблицу из одной стороны и сделать O(1) lookup из другой. На двух таблицах по миллиону строк это превращает триллион сравнений в линейное чтение.

С PostgreSQL 7 Hash Join — основной алгоритм для больших equi-join. Но у него есть железные ограничения, которые надо знать: он работает только для equi-join, и крайне чувствителен к work_mem.

Алгоритм: две фазы — build и probe

Hash Join состоит из двух стадий:

# build phase: строим хэш-таблицу из меньшей таблицы
hash_table = {}
for row in smaller_table:
    key = hash(row.join_key)
    hash_table.setdefault(key, []).append(row)

# probe phase: проходим по большей и для каждой строки ищем матчи
for row in larger_table:
    key = hash(row.join_key)
    for match in hash_table.get(key, []):
        emit (match, row)

Стоимость: O(N + M), где N — размер build-side, M — размер probe-side. Линейная по обеим таблицам. Это в разы лучше O(N × M) naive NL и сопоставимо с O((N + M) × log(min)) merge join, но не требует сортировки.

Build-side и probe-side: кто меньше — тот строит

Постгрес всегда стремится поместить меньшую таблицу в build-side. Причины две:

1. Хэш-таблица должна влезть в work_mem. Чем меньше build-side, тем меньше шансов, что таблица не поместится и Postgres пойдёт в дорогой batched join (см. ниже).
2. Probe-side проходим один раз, потоково. Не нужно держать в памяти; читаем и отдаём матчи. Это идеальная роль для большой таблицы.

«Меньшая» здесь — не число строк, а оценочный размер хэша: rows × avg row width × overhead. Postgres использует статистику pg_stats и оценивает кардинальность после фильтров. Если статистика плохая — он может ошибиться и положить большую таблицу в build.

work_mem и batched join

Что происходит, если хэш-таблица не помещается в work_mem? Постгрес переходит в

1. Хэш build-side разбивается на N батчей по нескольким старшим битам хэша. Каждый батч помещается в work_mem.
2. Probe-side читается, и каждая строка направляется в соответствующий батч на диск (по тем же битам).
3. Постгрес обрабатывает батчи по очереди: загружает один build-батч в память, прогоняет соответствующий probe-батч с диска.

Цена: записать на диск ~весь probe-side, прочитать обратно. Это 2x I/O минимум. На больших таблицах batched join может работать в 5-10 раз медленнее единобатчевого.

Demo: однобатчевый vs многобатчевый

В плане ищи Hash Join сверху. Под ним — Seq Scan orders (probe) и Hash → Seq Scan customers (build). Обрати внимание на строки:

Hash Cond: (o.customer_id = c.id)
->  Hash  (cost=... rows=10000 width=...)
      Buckets: 16384  Batches: 1  Memory Usage: ...kB

Batches: 1 означает однобатчевый — хорошо. Если бы было Batches: 8, мы бы платили за диск.

Теперь принудительно урежем work_mem и заставим Postgres делать batched join:

Видим в Hash-узле Batches: 8 (или другое больше 1) и в EXPLAIN ANALYZE — Disk Usage: ...kB под Hash. Время выполнения растёт. На больших данных эта разница — 5-10x.

Только equi-join

Хэш-таблица позволяет искать только строгое равенство ключа. Это значит, Hash Join работает только для JOIN ON a.x = b.y. Если условие — a.x > b.y, a.x BETWEEN b.lo AND b.hi, a.x LIKE b.pattern — Hash Join невозможен. Postgres выберет Nested Loop или Merge Join (если возможно).

В этом главное ограничение Hash Join. Зато для самого частого паттерна — соединение по primary key / foreign key — он идеален.

NULL-handling: пустое значение, которое ни с чем не равно

Особый case: NULL = NULL в SQL — это не TRUE, а NULL. Hash Join это учитывает: строки с NULL в join-ключе не образуют пары, даже друг с другом. Это правильное поведение SQL, но иногда удивляет. Если нужно объединить NULL’ы — используй IS NOT DISTINCT FROM, и тогда Hash Join не выберется (он не поддерживает этот оператор), упадём в Merge или NL.

Cost formula

Из costsize.c упрощённо:

hash_join_cost = build_cost(inner) + probe_cost(outer)
              + cpu_operator_cost × hash_chains_traversed
              + IF batched: 2 × disk_io(outer + inner)

Главные драйверы:

• Размер build-side — линейно в build_cost.
• Размер probe-side — линейно в probe_cost.
• work_mem vs hash size — если не помещается, добавляется 2x disk I/O.
• Качество хэш-функции и distinct values — при низком n_distinct получаем много коллизий, каждый probe становится дороже.

Параллельный Hash Join (PG 11+)

Постгрес 11 добавил параллельную фазу для Hash Join: build-side читают и хэшируют несколько worker’ов параллельно, потом она хранится в shared memory (а не в локальной памяти каждого worker’а). Probe тоже параллельный. Это резко ускоряет большие joins на многоядерных машинах — но об этом подробно в уроке 5.

Изучи план: HashAggregate → Hash Join → Seq Scan orders + Hash → Seq Scan customers. Это и есть «классический» паттерн аналитического запроса в Postgres.

Что делать, когда Hash Join медленный

1. Поднять work_mem в сессии: SET work_mem = '256MB'. Эффективно для отдельных тяжёлых запросов; не делай это глобально, иначе при 100 коннектах съешь всю память сервера.
2. Уменьшить build-side фильтром: если можно отсечь часть build-таблицы заранее (через WHERE или CTE), хэш-таблица становится меньше — батчей не нужно.
3. Перепроектировать запрос так, чтобы меньшая таблица оказалась build-side. Postgres почти всегда выбирает правильно, но в редких случаях ошибается из-за плохой статистики.
4. ANALYZE — устаревшая статистика часто причина того, что Postgres переоценил build-side и пошёл в batched.

Чек-лист

• Hash Join = build (меньшая) + probe (большая). Стоимость O(N + M).
• Работает только для equi-join (a.x = b.y). NULL не образует пары.
• Build-side должен помещаться в work_mem, иначе — batched join с записью на диск (медленнее в 5-10x).
• Batches: N и Disk Usage: в EXPLAIN ANALYZE — индикаторы batched join.
• work_mem — лимит на узел, не на сессию. При нескольких Hash Join’ах в одном плане суммируется.
• Параллельный Hash Join (PG 11+) использует shared memory для build-side между workers.
• Хорошая статистика (ANALYZE) — критична: ошибка в оценке размера приводит к выбору неоптимального build-side.
• Для increase work_mem на одну сессию: SET LOCAL work_mem = '256MB' внутри транзакции тяжёлого отчёта.