# Алгоритмы соединения: nested loop, hash, merge

_Планировщик и оптимизатор · PostgreSQL Knowledge Base_

**TL;DR:** Nested loop хорош при малом внешнем входе и индексе внутри; hash join -
для больших входов по равенству (нужен work_mem); merge join - когда
входы уже отсортированы. Memoize кеширует поиски nested loop.


## Три алгоритма

| Алгоритм | Лучший случай | Сложность |
|---|---|---|
| Nested loop | мал внешний вход + индекс на внутренней | O(N×M), с индексом O(N×log M) |
| Hash join | большие входы, соединение по `=` | O(N+M) |
| Merge join | входы уже отсортированы по ключу | O(N+M) после сортировки |

**Nested loop** для каждой внешней строки ищет совпадения во
внутренней; с индексом на ключе внутренний поиск точечный. **Hash
join** строит хеш по меньшему входу в `work_mem`, зондирует большим;
только для равенства. **Merge join** сливает два отсортированных входа
за проход; почти бесплатен, если сортировка не нужна.

## work_mem и пролив на диск

Если хеш не влезает в `work_mem`, join делит вход на batches и
проливается на диск. В `EXPLAIN ANALYZE`:

```
Hash  Buckets: 4096  Batches: 8  Memory Usage: 4096kB
```

`Batches: 1` - всё в памяти; больше - был пролив, join медленнее.

## Memoize

Узел `Memoize` кеширует результаты внутреннего поиска nested loop по
ключу - выгоден при повторяющихся и перекошенных ключах.

Упорно плохой выбор алгоритма почти всегда значит неверную
кардинальность (см. [planner-statistics](/courses/postgres/kb/planner-statistics.md)), а не плохой алгоритм.
Тумблеры `enable_*` - для диагностики, не для прода. Выбор порядка
соединений - в [join-order-geqo](/courses/postgres/kb/join-order-geqo.md).


## Команды

```sql
EXPLAIN SELECT * FROM a JOIN b USING(id);
```
Посмотреть выбранный алгоритм соединения

```sql
SET enable_hashjoin = off;
```
Увести план с hash на merge/nested (для учёбы/диагностики)

```sql
SET work_mem = '64MB';
```
Больше памяти под хеш/сортировку - меньше пролива на диск


## См. также

- [Порядок соединений, GEQO и кеш плана](/courses/postgres/kb/join-order-geqo.md)
- [Методы доступа: Seq, Index, Bitmap, Index-Only](/courses/postgres/kb/access-methods.md)
- [Статистика планировщика: pg_stats](/courses/postgres/kb/planner-statistics.md)