Nested Loop, Hash Join, Merge Join и Memoize в PostgreSQL: как исполняются и где спиллят

В плане соединения стоит Hash Batches: 8, а в строке Buffers появилось temp read=32476 written=32476: запрос на диск не ходил бы, если бы хеш-таблица уместилась в память. Как читать такой план, написано в статье про EXPLAIN ANALYZE BUFFERS, а откуда берутся cost= и почему планировщик выбирает один узел, а не другой, — в статье про модель стоимости. Здесь разберём сами алгоритмы: что делает каждый, сколько буферов стоит, как work_mem делит хеш-таблицу на batches и что измеряется на самом деле, а не ожидается.

Опыт: таблицы и три узла

Две таблицы: dim на миллион строк (id и md5-строка) и fact на 10 миллионов, где dim_id разбросан по всей dim. Третья, ev, понадобится позже: 200 000 строк при 1 000 разных ключей. Данные займут около 680 МБ.

docker run -d --name dba-join-algorithms -e POSTGRES_PASSWORD=pg postgres:18
docker exec -it dba-join-algorithms psql -U postgres

CREATE TABLE dim AS SELECT g AS id, md5(g::text) AS name FROM generate_series(1, 1000000) g;
CREATE TABLE fact AS SELECT g AS id, (g::bigint * 7919) % 1000000 + 1 AS dim_id, g % 100 AS grp
FROM generate_series(1, 10000000) g;
ALTER TABLE dim ADD PRIMARY KEY (id);
CREATE INDEX fact_dim_id ON fact (dim_id);
CREATE TABLE ev AS SELECT g AS id, (g % 1000) * 997 % 1000000 + 1 AS dim_id
FROM generate_series(1, 200000) g;
VACUUM ANALYZE dim; VACUUM ANALYZE fact; ANALYZE ev;
SET max_parallel_workers_per_gather = 0;

EXPLAIN (COSTS OFF) SELECT count(d.name) FROM fact f JOIN dim d ON d.id = f.dim_id;

Aggregate
  ->  Hash Join
        Hash Cond: (f.dim_id = d.id)
        ->  Seq Scan on fact f
        ->  Hash
              ->  Seq Scan on dim d

Для 10 миллионов проверок планировщик по умолчанию берёт Hash Join. Дальше каждый алгоритм по очереди.

Hash Join: сколько batches при каком work_mem

Hash Join читает меньшую сторону целиком и строит хеш-таблицу по ключу соединения, потом читает большую и для каждой строки заглядывает в таблицу. Размер ограничивает work_mem умноженный на hash_mem_multiplier (nodeHash.c, REL_18_6):

	mem_limit = (double) work_mem * hash_mem_multiplier * 1024.0;

	/* Clamp in case it doesn't fit in size_t */
	mem_limit = Min(mem_limit, (double) SIZE_MAX);

	return (size_t) mem_limit;

Множитель в PostgreSQL 18 равен 2 (проверено SHOW hash_mem_multiplier), поэтому при work_mem = 4MB таблица может занять 8 МБ. Если оценка не умещается, число batches считается как степень двойки (ExecChooseHashTableSize):

		/* Calculate required number of batches. */
		dbatch = ceil(inner_rel_bytes / (hash_table_bytes - bucket_bytes));
		dbatch = Min(dbatch, max_pointers);
		minbatch = (int) dbatch;
		nbatch = pg_nextpower2_32(Max(2, minbatch));

Прогоним один и тот же запрос с пятью значениями work_mem. Merge Join и Nested Loop выключены, чтобы все пять раз измерить именно хеш.

SET enable_nestloop = off; SET enable_mergejoin = off; SET work_mem = '4MB';
EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF)
SELECT count(*) FROM fact f JOIN dim d ON d.id = f.dim_id;

Aggregate (actual rows=1.00 loops=1)
  Buffers: shared hit=15688 read=56440, temp read=32476 written=32476
  ->  Hash Join (actual rows=10000000.00 loops=1)
        Hash Cond: (f.dim_id = d.id)
        Buffers: shared hit=15688 read=56440, temp read=32476 written=32476
        ->  Seq Scan on fact f (actual rows=10000000.00 loops=1)
        ->  Hash (actual rows=1000000.00 loops=1)
              Buckets: 262144  Batches: 8  Memory Usage: 6446kB
              Buffers: shared hit=256 read=8128, temp written=2560
              ->  Seq Scan on dim d (actual rows=1000000.00 loops=1)

Узел Hash записал 2 560 блоков: это строки dim из batches 1–7. Остальные 29 916 блоков из 32 476 — строки fact, которые не попали в batch 0 и ушли в свои файлы. Все пять значений:

Число batches рассчитывается по размеру внутренней стороны: при Batches: 1 таблица заняла 43 349 КБ, из них 8 192 КБ — массив из 1 048 576 указателей-корзин, который считается в тот же счётчик, остальное — 35 157 КБ строк. При лимите 8 МБ (4MB × 2) на строки остаётся меньше шести мегабайт, и степень двойки даёт 8.

Менее очевидно, что быстрее всех оказался самый тесный work_mem: 1MB с 32 batches закончился за 2,0–2,2 с, а 256MB без единого temp-блока — за 3,8 с. Направление повторилось во всех сериях на машине с нагрузкой (load average около 10) и в повторе на чистом контейнере (2,19 и 2,12 с при 1MB против 3,93 и 3,83 с при 256MB), поэтому значения сравниваются внутри одной серии. Вероятная причина — кэш процессора: dim_id в fact разбросан случайно, и каждая из 10 млн проверок попадает в случайное место хеш-таблицы. Таблица одного batch при 1MB занимает 1,6 МБ и помещается в кэш L2 и L3 процессора стенда (12 и 25 МиБ), таблица в 43 МБ — нет. Опыт эту причину не изолировал: проверь на своём железе. Для консультанта важнее другое: temp written в плане не равен «запрос медленный». Спилл надо сравнивать со временем, а не принимать за дефект.

Nested Loop и Memoize: поиск по индексу на каждую строку

Nested Loop берёт строку внешней стороны и ищет к ней пару во внутренней — с параметризованным индексом, а не полным сканированием. Выключим хеш и слияние и соединим ev с dim по первичному ключу, сначала без кэша результатов.

SET enable_hashjoin = off; SET enable_mergejoin = off; SET enable_memoize = off;
EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF)
SELECT count(d.name) FROM ev e JOIN dim d ON d.id = e.dim_id;

Aggregate (actual rows=1.00 loops=1)
  Buffers: shared hit=800896
  ->  Nested Loop (actual rows=200000.00 loops=1)
        ->  Seq Scan on ev e (actual rows=200000.00 loops=1)
        ->  Index Scan using dim_pkey on dim d (actual rows=1.00 loops=200000)
              Index Cond: (id = e.dim_id)
              Index Searches: 200000
              Buffers: shared hit=800000
Execution Time: 311.730 ms

Внутренний Index Scan выполнен 200 000 раз (loops=200000), и каждый поиск стоит ровно 4 буфера: 800 000 / 200 000. Корень dim_pkey лежит на уровне 2 (SELECT level FROM bt_metap('dim_pkey') вернул 2): три страницы индекса и страница кучи, устройство дерева — в статье про B-tree. Но в ev всего 1 000 разных ключей: 199 000 поисков повторяют уже сделанные. Для этого с PostgreSQL 14 есть Memoize: узел кэширует результат внутренней стороны по параметру. Включим его обратно (это значение по умолчанию):

SET enable_memoize = on;

        ->  Memoize (actual rows=1.00 loops=200000)
              Cache Key: e.dim_id
              Cache Mode: logical
              Hits: 199000  Misses: 1000  Evictions: 0  Overflows: 0  Memory Usage: 137kB
              Buffers: shared hit=4000
              ->  Index Scan using dim_pkey on dim d (actual rows=1.00 loops=1000)
                    Index Cond: (id = e.dim_id)
                    Index Searches: 1000
                    Buffers: shared hit=4000
Execution Time: 42.434 ms

Индекс теперь ищется 1 000 раз, по числу разных ключей, и это те же 4 буфера на промах: 4 000. Время упало с 312 до 42 мс (повтор: 337 и 47). Код узла так и считает (nodeMemoize.c):

				entry = cache_lookup(node, &found);

				if (found && entry->complete)
				{
					node->stats.cache_hits += 1;	/* stats update */

Лимит кэша Memoize задают те же work_mem и hash_mem_multiplier, что и у хеш-таблицы. Сократим его до минимума на тех же данных:

SET work_mem = '64kB'; SET hash_mem_multiplier = 1;

              Hits: 0  Misses: 200000  Evictions: 199532  Overflows: 0  Memory Usage: 65kB
              Buffers: shared hit=800000

Ключи в ev идут по кругу, 1 000 значений подряд, а кэш в 65 КБ постоянно вытесняет записи: ни одного попадания, 199 532 вытеснения, 800 000 буферов, как без Memoize. Узел остался в плане и ничего не даёт. Hits и Evictions в EXPLAIN ANALYZE показывают это сразу.

Merge Join: слияние отсортированных входов

Merge Join идёт по двум входам одновременно, и каждый обязан быть отсортирован по ключу. Если оба индекса дают порядок бесплатно, сортировки нет. Оставим только слияние:

SET enable_hashjoin = off; SET enable_nestloop = off;
EXPLAIN (ANALYZE, BUFFERS, COSTS OFF, TIMING OFF)
SELECT count(*) FROM fact f JOIN dim d ON d.id = f.dim_id;

Aggregate (actual rows=1.00 loops=1)
  ->  Merge Join (actual rows=10000000.00 loops=1)
        Merge Cond: (f.dim_id = d.id)
        ->  Index Only Scan using fact_dim_id on fact f (actual rows=10000000.00 loops=1)
              Heap Fetches: 0
        ->  Index Only Scan using dim_pkey on dim d (actual rows=1000000.00 loops=1)
              Heap Fetches: 0
Execution Time: 995.429 ms

Оба входа читаются по индексам в порядке ключа, без Sort: 995 и 1053 мс в двух запусках, быстрее всех пяти прогонов хеша выше (2036–4188 мс). Но выигрыш держится на Heap Fetches: 0 (после VACUUM карта видимости полная) и на count(*), которому не нужны остальные столбцы. Теперь отнимем индексы и заставим слияние сортировать:

SET enable_indexscan = off; SET enable_indexonlyscan = off; SET enable_bitmapscan = off;
SET work_mem = '4MB';

        ->  Sort (actual rows=10000000.00 loops=1)
              Sort Key: f.dim_id
              Sort Method: external merge  Disk: 117536kB
        ->  Sort (actual rows=1000000.00 loops=1)
              Sort Key: d.id
              Sort Method: external merge  Disk: 11768kB
Execution Time: 2794.089 ms

При work_mem = 256MB те же сортировки идут в памяти (quicksort Memory: 262144kB и 24577kB), запрос выполнился за 1940 мс. Слияние спиллит не само, а через Sort под ним: около 126 МБ на диске в первом случае. Подробно о спилле сортировок — отдельная тема; здесь важно, что порядок входов — это стоимость, которую либо платит индекс заранее, либо Sort на каждый запрос.

Что из этого следует

• Hash Join платит памятью за скорость на больших несортированных входах; temp written в нём означает batches, а не обязательную проблему. Прежде чем поднимать work_mem, сравни время: в опыте 256MB без спилла оказался медленнее 1MB с 32 batches.
• Nested Loop хорош, когда внешняя сторона мала или повторяется и во внутренней есть индекс по ключу: поиск стоит 4 буфера, но их умножает loops. Именно там планировщик ставит Memoize.
• Memoize выигрывает только на повторяющихся ключах: 199 000 попаданий дали 42 мс против 312, а при нехватке памяти 0 попаданий и 800 000 буферов. Читай Hits, Misses и Evictions, а не только наличие узла.
• Merge Join дёшев на уже отсортированных входах и дорог, если под ним Sort; его место в плане определяет индекс, а не желание планировщика.
• Если оценка rows под Hash или Memoize расходится с фактом, число batches и выбор узла считаются от неверных чисел; причину ищи в статистике, а не в SET enable_*; один из способов — расширенная статистика.

Чек-лист

1. Для спорного соединения запусти EXPLAIN (ANALYZE, BUFFERS) и выпиши Batches, Memory Usage и temp read/written у узла Hash.
2. Меняй work_mem в сессии и сравнивай время нескольких запусков подряд, а не только temp written.
3. У Nested Loop смотри loops внутренней стороны и Buffers: буферы на поиск умножаются на loops.
4. У Memoize проверяй Hits, Misses и Evictions; ноль попаданий означает, что узел можно убрать через enable_memoize = off в сессии для проверки.
5. Если Sort под Merge Join показывает external merge Disk, оцени, дешевле ли завести индекс, чем держать work_mem под сортировку.

Опыт удаляется вместе с томом данных:

docker rm -f -v dba-join-algorithms