Чем отличаются Nested Loop, Hash Join, Merge Join? Когда какой эффективен?

Три алгоритма JOIN в PostgreSQL

PostgreSQL выбирает алгоритм JOIN на основе cost model: оценки числа строк, доступного work_mem, наличия индексов и типа условия соединения. Понять выбор планировщика можно через EXPLAIN (ANALYZE, BUFFERS).

Nested Loop Join

Для каждой строки внешней (outer) стороны ищет совпадения во внутренней (inner) стороне. Сложность O(N × M), но на практике O(N × log M) если inner side использует индекс.

-- Nested Loop эффективен: мало строк снаружи + индекс внутри
EXPLAIN (ANALYZE)
SELECT u.name, o.order_id
FROM users u
JOIN orders o ON o.user_id = u.user_id
WHERE u.user_id = 42;
-- Nested Loop
--   ->  Index Scan on users (user_id=42)      -- 1 строка снаружи
--   ->  Index Scan on orders (user_id=42)     -- быстрый поиск внутри

Когда хорош: внешняя сторона маленькая (несколько строк), внутренняя быстро ищется по индексу. Хорошо работает при LIMIT — находит первые N строк без сканирования всего набора.

Когда плох: обе стороны большие и нет индекса на inner side — деградирует до O(N×M).

Hash Join

Строит hash table из меньшей (build) стороны, затем сканирует большую (probe) сторону и ищет совпадения в hash table. Работает только для условий равенства (=).

-- Hash Join: большие таблицы без подходящего порядка
EXPLAIN (ANALYZE, BUFFERS)
SELECT u.user_id, COUNT(o.order_id)
FROM users u
JOIN orders o ON o.user_id = u.user_id
GROUP BY u.user_id;
-- Hash Join  (cost=2841.00..8934.00)
--   Hash Cond: (o.user_id = u.user_id)
--   ->  Seq Scan on orders           -- probe side (большая)
--   ->  Hash
--         ->  Seq Scan on users      -- build side (меньшая → в память)
--               Batches: 1  Memory Usage: 4096kB

Когда хорош: большие наборы данных, нет подходящего порядка или индекса, условие равенства. Амортизированная сложность O(N+M).

Когда плох: build side не помещается в work_mem — происходит spill на диск (Batches > 1), что резко замедляет выполнение.

Merge Join

Объединяет две уже отсортированные последовательности «на лету». Требует, чтобы обе стороны были отсортированы по ключу соединения. Сложность O(N+M) при наличии сортировки.

-- Merge Join: обе стороны отсортированы по индексу
EXPLAIN (ANALYZE)
SELECT a.account_id, t.amount
FROM accounts a
JOIN transactions t ON t.account_id = a.account_id
ORDER BY a.account_id;
-- Merge Join  (cost=0.86..15420.00)
--   Merge Cond: (a.account_id = t.account_id)
--   ->  Index Scan using accounts_pkey on accounts   -- уже отсортировано
--   ->  Index Scan using idx_transactions_account on transactions

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

Когда плох: данные не отсортированы и нужна явная Sort-нода — добавляет O(N log N) накладных расходов.

Как управлять выбором алгоритма

-- Посмотреть актуальный план с реальными метриками
EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT)
SELECT u.user_id, o.order_id
FROM users AS u
JOIN orders AS o ON o.user_id = u.user_id
WHERE u.country = 'DE';

-- Диагностика: отключить конкретный алгоритм
SET enable_hashjoin = off;   -- принудить к Merge или Nested Loop
SET enable_mergejoin = off;
SET enable_nestloop = off;

-- Увеличить work_mem для Hash Join без spill
SET work_mem = '256MB';

Подводные камни

• Плохая оценка числа строк → неверный алгоритм: планировщик выбрал Nested Loop «1000 строк», реально их миллион — катастрофа. Решение: ANALYZE, увеличить default_statistics_target, добавить extended statistics для коррелированных колонок.
• Hash Join spill на диск: в EXPLAIN ANALYZE видно Batches: 8 вместо Batches: 1 — hash table не влезла в work_mem. Увеличьте work_mem для сессии или перепишите запрос.
• Merge Join и implicit Sort: если Sort-нода стоит перед Merge Join, это не бесплатно — иногда Hash Join с большим work_mem быстрее.
• Декартово произведение при отсутствии условия: если PostgreSQL не нашёл join condition, он делает Nested Loop без фильтра — exponential взрыв строк.
• work_mem — per sort/hash operation: один запрос может создать несколько hash table и sort-операций; реальное потребление памяти = work_mem × число операций × число параллельных воркеров.
• Parallel Hash Join: PostgreSQL 11+ поддерживает параллельный Hash Join; если parallel_workers не настроен, параллелизм не включится даже на большом наборе данных.
• Nested Loop + функции: если inner side вызывает медленную функцию для каждой outer-строки, это не видно в cost, но в ANALYZE отображается реальное время — смотрите actual rows и actual time.

• Считать один join algorithm всегда лучшим.
• Игнорировать estimates внешней стороны.
• Не учитывать work_mem и temp files.

• Просит условия для Nested Loop.
• Проверяет hash spill.
• Уточняет роль сортировки для Merge Join.