Три алгоритма
| Алгоритм | Лучший случай | Сложность |
|---|---|---|
| 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), а не плохой алгоритм.
Тумблеры enable_* - для диагностики, не для прода. Выбор порядка
соединений - в join-order-geqo.