28.1 Три алгоритма, три области применения
| Алгоритм | Идея | Лучший случай | Сложность |
|---|---|---|---|
| Nested loop | для каждой внешней строки искать совпадения во внутренней | внешний вход мал, на внутреннем есть индекс | O(N × M), с индексом O(N × log M) |
| Hash join | построить хеш меньшего входа, прозондировать большим | большие входы, соединение по равенству | O(N + M) |
| Merge join | слить два отсортированных входа | входы уже отсортированы по ключу | O(N + M) после сортировки |
Планировщик не любит ни один из них «вообще» - он считает стоимость каждого для конкретных размеров входов (а размеры берёт из кардинальности, см. planner-statistics). Поэтому ошибка в оценке числа строк особенно больно бьёт именно по выбору алгоритма соединения.
28.2 Nested loop
Самый простой алгоритм: взять каждую строку внешней таблицы и для неё пройти внутреннюю в поисках совпадений.
для каждой строки o из outer:
для каждой строки i из inner:
если o.key == i.key: выдать (o, i)
В лоб это O(N × M) - убийственно для больших таблиц. Но nested loop спасает индекс на внутренней таблице: тогда внутренний цикл не проход, а точечный поиск по индексу - O(log M) вместо O(M). Получается O(N × log M), и это лучший план, когда внешний вход мал (десятки строк), а на ключе соединения внутренней есть индекс.
Nested Loop
-> Seq Scan on flights f (rows=2) ← маленький внешний вход
-> Index Scan on tickets t ← точечный поиск по индексу
Index Cond: (t.flight_id = f.flight_id)
28.3 Hash join
Когда оба входа велики, nested loop безнадёжен. Hash join меняет стратегию: один раз прочитать оба входа.
фаза build: построить хеш-таблицу по меньшему входу (ключ → строки)
фаза probe: для каждой строки большего входа найти ключ в хеше
Каждый вход читается ровно один раз - O(N + M). Цена - память:
хеш-таблица меньшего входа должна поместиться в work_mem.
Ограничение - hash join работает только для соединения по
равенству (=), потому что хеш не умеет в диапазоны.
Hash Join
Hash Cond: (t.flight_id = f.flight_id)
-> Seq Scan on tickets t ← probe большим входом
-> Hash
-> Seq Scan on flights f ← build меньшим входом
Планировщик строит хеш по меньшему из входов - так таблица занимает
меньше памяти и охотнее влезает в work_mem.
28.3.1 Подводный камень: hash join проливается на диск
Если хеш-таблица не влезает в work_mem, hash join не падает - он
делит вход на пакеты (batches) и часть выгружает во временные файлы
на диск. В EXPLAIN ANALYZE это видно:
Hash (actual ...)
Buckets: 4096 Batches: 8 Memory Usage: 4096kB
Batches: 1 - всё поместилось в память, идеально. Batches: 8 -
пришлось проливаться на диск восемь раз, и hash join стал заметно
медленнее. Симптом сопровождается ростом temp-файлов.
Лечение - либо увеличить work_mem (осторожно: он на каждый узел
сортировки/хеша каждого соединения, а не на запрос целиком, и
бездумно большой work_mem под нагрузкой съест всю память), либо
уменьшить вход (точнее условие, нужные колонки). Часто проще
добавить недостающий индекс и увести план в nested loop или merge.
28.4 Merge join
Если оба входа отсортированы по ключу соединения, их можно слить за один проход, как две упорядоченные колоды: идти по обеим одновременно, продвигая ту, где ключ меньше.
указатели на начало обоих отсортированных входов
пока оба не кончились:
если ключи равны: выдать пару, продвинуть
иначе продвинуть тот вход, где ключ меньше
Сама слияние - O(N + M). Вопрос в сортировке: если входы уже
отсортированы (например, читаются по индексу в порядке ключа),
merge join почти бесплатен. Если сортировать надо - добавляется
стоимость двух Sort, и тогда hash join обычно выгоднее. Поэтому
merge join выигрывает там, где сортировка «бесплатна»: данные уже
приходят по индексу в нужном порядке, или результат всё равно нужен
отсортированным дальше по плану.
28.5 Memoize: кеш для nested loop
У nested loop с индексным внутренним поиском есть слабость:
одинаковые ключи во внешнем входе заставляют повторять один и тот
же поиск. Если во внешней таблице ключ 7 встречается сто раз,
внутренний индексный поиск по 7 выполнится сто раз с одним и тем
же результатом.
Узел Memoize это лечит: он кеширует результат внутреннего поиска
по каждому значению ключа. Повторился ключ - ответ берётся из кеша,
без обращения к индексу.
Nested Loop
-> Seq Scan on orders ← много повторяющихся flight_id
-> Memoize
Cache Key: orders.flight_id
-> Index Scan on flights
Memoize особенно выгоден при перекошенном распределении ключей (несколько значений очень часты) и небольшом числе различных значений - тогда кеш покрывает почти все поиски.
28.6 Как заставить планировщик показать каждый
Чтобы увидеть все три алгоритма на одном запросе, есть тумблеры
enable_*. Они не запрещают алгоритм жёстко, а назначают ему
огромный штраф к стоимости, и планировщик выбирает другой.
SET enable_hashjoin = off; -- увести с hash на merge/nested
SET enable_mergejoin = off; -- ... и с merge тоже
EXPLAIN SELECT ... JOIN ...; -- остался nested loop
Это инструмент для учёбы и диагностики, не для прода: в проде нельзя глобально выключать алгоритм, потому что для других запросов он лучший. Если планировщик упорно выбирает «плохой» join, корень почти всегда в кардинальности - он считает входы не того размера. Чинить надо статистику и оценку строк, а не выключать алгоритм. К выбору порядка соединений и кешу планов перейдём в join-algorithms и следующей главе.
Уроки в sandbox
lab-28.1. Получить все три типа соединения на одном JOIN
Соединим две таблицы и тумблерами enable_* проведём план через hash, merge и nested loop. Перед каждым EXPLAIN предскажи, какой алгоритм останется.
Подготовь данные:
CREATE TABLE a AS SELECT g id FROM generate_series(1,100000) g; CREATE TABLE b AS SELECT g id FROM generate_series(1,100000) g; ANALYZE a; ANALYZE b;.По умолчанию:
EXPLAIN SELECT * FROM a JOIN b USING(id);- на больших входах без индексов ожидается Hash Join.Выключи hash:
SET enable_hashjoin = off;и повтори EXPLAIN - предскажи, что останется (merge с двумя Sort).Добавь индекс и маленький внешний вход:
CREATE INDEX ON b(id); ANALYZE b;затемEXPLAIN SELECT * FROM a JOIN b USING(id) WHERE a.id < 5;- ожидается Nested Loop с Index Scan по b.Сделай
EXPLAIN ANALYZEдля hash-варианта (верниSET enable_hashjoin = on; SET enable_mergejoin = on;) и посмотри Batches в узле Hash.Уменьши
SET work_mem = '64kB';и повтори - предскажи, вырастет ли число Batches (пролив на диск).
sandbox с автопроверкой - открыть в песочнице
Резюме
- Три алгоритма соединения: nested loop (мал внешний вход + индекс внутри), hash join (большие входы, равенство), merge join (входы уже отсортированы).
- Nested loop в лоб O(N×M), но с индексом на внутренней таблице - O(N×log M); лучший выбор, когда внешних строк мало.
- Hash join читает оба входа один раз (O(N+M)), строит хеш по меньшему входу в work_mem; работает только для соединения по равенству.
- Если хеш не влезает в work_mem, join делит вход на batches и проливается на диск; Batches > 1 в EXPLAIN ANALYZE - сигнал нехватки памяти.
- Merge join сливает два отсортированных входа за один проход; почти бесплатен, когда сортировка не нужна (данные идут по индексу).
- Memoize кеширует результаты внутреннего поиска nested loop по ключу - выгоден при повторяющихся и перекошенных ключах.
- Тумблеры enable_* штрафуют алгоритм для учёбы/диагностики, но не для прода; упорно плохой join обычно значит неверную кардинальность, а не плохой алгоритм.
Контрольные вопросы
Когда nested loop - лучший план, а когда худший?
Показать ответ
Лучший - когда внешний вход маленький (десятки строк), а на ключе соединения внутренней таблицы есть индекс. Тогда для каждой внешней строки внутренний поиск точечный (O(log M)), и весь join дёшев. Худший - когда оба входа большие и индекса нет: тогда это O(N×M), то есть для каждой из миллионов внешних строк проход по миллионам внутренних. Именно сюда обычно скатывается план, когда планировщик из-за устаревшей статистики думает, что внешних строк мало, а их много.
Почему hash join нельзя применить к соединению по `<` или `BETWEEN`?
Показать ответ
Потому что хеш-таблица отвечает только на вопрос «есть ли точно такой ключ» - она строится по равенству хешей. Диапазонные условия (
<,BETWEEN) требуют сравнивать порядок, а хеш порядок не сохраняет: близкие значения попадают в произвольные корзины. Поэтому hash join работает лишь для эквисоединений (=). Для диапазонных соединений используют nested loop (часто с индексом) или merge join по отсортированным входам.В `EXPLAIN ANALYZE` у узла Hash написано `Batches: 16`. Что это значит и плохо ли это?
Показать ответ
Это значит, что хеш-таблица не поместилась в work_mem, и hash join разбил вход на 16 пакетов, выгружая часть во временные файлы на диск.
Batches: 1- всё в памяти, идеально; больше единицы - был пролив на диск, и join стал медленнее, обычно вместе с ростом temp-файлов. Чинят увеличением work_mem (осторожно, он на каждый хеш/сортировку, а не на запрос), сужением входа или добавлением индекса, уводящего план в nested loop/merge.Что делает узел Memoize и когда он помогает?
Показать ответ
Memoize кеширует результаты внутреннего (параметризованного) поиска в nested loop по значению ключа. Если во внешнем входе ключ повторяется, повторный поиск берётся из кеша вместо обращения к индексу. Помогает при перекошенном распределении ключей (несколько значений очень частотны) и небольшом числе различных значений - тогда кеш покрывает почти все поиски и экономит много повторной работы. При уникальных ключах смысла в нём нет: кешировать нечего.
Планировщик упорно выбирает медленный hash join. Стоит ли выключить его через `enable_hashjoin = off`?
Показать ответ
В проде - нет. enable_* выключают алгоритм глобально для сессии, а для других запросов hash join может быть лучшим. Упорный выбор «плохого» соединения почти всегда значит, что планировщик неправильно оценил размеры входов - корень в кардинальности и статистике. Правильно чинить там: обновить ANALYZE, добавить расширенную статистику, поправить индексы. enable_* годятся для учёбы и разовой диагностики «а что было бы другим планом», но не как постоянное решение.