Алгоритмы JOIN: Nested Loop, Hash, Merge

JOIN двух таблиц по 10 миллионов строк каждая. Nested Loop: 5 часов. Hash Join: 3 минуты. Merge Join: 45 секунд (если индексы есть). Один и тот же результат, разница в 400 раз - только из-за выбора алгоритма.

• **Airbnb** при аналитике booking-events JOIN с user_attributes (обе таблицы > 500M строк) настроил work_mem=2GB для reporting-сессий и принудительно включил Parallel Hash Join через max_parallel_workers_per_gather=8 - запрос с 45 минут упал до 4 минут.
• **Stripe** обнаружил, что планировщик выбирал Nested Loop для join payments * customers из-за неточных statistics на customers (много дублей в customer_type). Extended statistics устранили ошибку estimates - планировщик переключился на Hash Join, latency с 12s до 0.8s.
• **GitLab** в ci_builds * ci_jobs join (крупнейшие таблицы в схеме) использует Merge Join через составные индексы - оба входа отсортированы по (pipeline_id, id), сортировка бесплатна, что даёт выигрыш над Hash Join при work_mem ограничениях.
• **Notion** при репликации blocks между workspace-ами столкнулся с деградацией Hash Join из-за Batches:16 - work_mem был 4MB на OLTP-сервере. Решение: отдельный pool connection с work_mem=512MB для bulk-операций.

Nested Loop Join

**Nested Loop** - самый простой алгоритм JOIN: для каждой строки внешней (outer) таблицы выполняется поиск совпадений во внутренней (inner). Если inner имеет индекс по join-колонке, поиск стоит O(log N) - это делает Nested Loop оптимальным для небольших наборов данных с высокоселективными join conditions.

Nested Loop становится опасным при больших outer наборах без индекса на inner: вырождается в O(M*N). Планировщик избегает его при больших оценках строк - выбирает Hash Join. Если планировщик ошибается в оценках и выбирает Nested Loop для 100k * 100k - это катастрофа по времени.

Hash Join

**Hash Join** строит хеш-таблицу из меньшей (build) стороны JOIN, затем сканирует большую (probe) сторону, проверяя каждую строку через хеш. Сложность O(M+N) - линейная, без индексов. Это делает Hash Join основным алгоритмом для объединения больших таблиц.

Критический параметр: `Batches`. Если `Batches > 1` - хеш-таблица не поместилась в `work_mem` и разлилась на диск (grace hash join). Каждый дополнительный batch требует повторного чтения probe-таблицы. `Batches: 8` означает probe-таблица читается 8 раз - потенциально огромный performance hit.

Merge Join

**Merge Join** требует, чтобы обе стороны JOIN были отсортированы по join-ключу. Затем два указателя двигаются синхронно - O(M+N) как Hash Join, но без хеш-таблицы. Преимущество: если данные уже отсортированы (индекс), сортировка бесплатна.

work_mem и производительность JOIN

`work_mem` определяет сколько RAM доступно для каждой операции сортировки или хеш-таблицы. Критически важно: это limit **на операцию**, не на запрос. Сложный запрос с 5 hash joins и 3 sorts может использовать до `work_mem * 8` памяти одновременно. При 100 concurrent connections = `work_mem * 8 * 100` в худшем случае.

Рекомендация для production: global work_mem держать 4-16MB, для аналитических запросов устанавливать через `SET work_mem` в начале сессии. GitLab использует `statement_timeout` + отдельный connection pool с large work_mem для reporting queries, чтобы аналитика не конкурировала с OLTP.

Параллельные JOIN

PostgreSQL может распараллелить Hash Join и Merge Join (но не Nested Loop по inner) при наличии достаточных ресурсов. Параллелизм включается когда estimated rows превышает `min_parallel_table_scan_size` (по умолчанию 8MB) и запрос не запущен внутри функции или транзакции с определёнными constraints.

Параллельный Hash Join (PG11+) использует shared hash table между воркерами - это эффективнее, чем каждый воркер строит свою копию. До PG11 параллельный hash join каждый воркер строил хеш-таблицу отдельно, что не давало пропорционального ускорения.

Ключевые идеи

• **Nested Loop** - O(M * log N) с индексом; идеален для маленьких наборов, катастрофа без индексов при большом outer.
• **Hash Join** - O(M+N); стандарт для больших таблиц, но требует work_mem; Batches > 1 означает disk spill и повторное чтение probe-стороны.
• **Merge Join** - O(M+N); выгоден когда входы уже отсортированы (индексы), иначе платит за Sort узлы.
• **work_mem** - per-operation limit; увеличение глобально опасно при many concurrent connections; используй SET LOCAL для аналитических запросов.

Связанные темы

Алгоритмы JOIN тесно связаны с несколькими другими аспектами PostgreSQL:

• EXPLAIN ANALYZE — Единственный способ увидеть какой алгоритм выбран и были ли Batches > 1 (disk spill)
• Планировщик и статистика — Выбор алгоритма JOIN зависит от cardinality estimates - ошибки в статистике приводят к неоптимальным планам
• Типы индексов — Индексы на join-ключах делают Nested Loop и Merge Join эффективными; без них Hash Join часто единственный разумный выбор

Вопросы для размышления

• Какой алгоритм JOIN чаще всего появляется в планах самых медленных запросов вашего приложения, и соответствует ли это ожиданиям?
• Есть ли в вашей схеме таблицы с частыми JOIN, где добавление индекса на join-ключ могло бы переключить алгоритм с Hash Join на Nested Loop?
• Как работа с work_mem организована в вашем проекте - один глобальный лимит или разные пулы для OLTP и аналитики?

Связанные уроки

• alg-10-binary-search