Физические JOIN: Nested Loop, Hash Join, Merge Join

JOIN в тексте запроса один, а способов его выполнить у базы три. Планировщик выбирает между ними по объёму таблиц, наличию индексов и статистике. Понимать эти три алгоритма нужно не для того, чтобы выбирать их вручную, а чтобы читать план и видеть, почему запрос работает час.

В этом уроке песочница разворачивает большую базу: 80 тысяч заказов и 180 тысяч позиций. На маленькой планировщик почти всегда выбирает один алгоритм, и разницы не видно.

Nested Loop: цикл в цикле

Для каждой строки внешней таблицы найти подходящие строки во внутренней. Без индекса это полный перебор: N строк снаружи умножить на M строк внутри. С индексом по ключу соединения внутренний поиск становится дешёвым, и алгоритм превращается в лучший выбор для маленького внешнего набора.

EXPLAIN
SELECT o.order_id
FROM orders o
JOIN customers c USING (customer_id)
WHERE c.customer_id = 42;

Nested Loop
  ->  Index Only Scan using customers_pkey on customers c
        Index Cond: (customer_id = 42)
  ->  Bitmap Heap Scan on orders o
        Recheck Cond: (customer_id = 42)
        ->  Bitmap Index Scan on ix_orders_customer
              Index Cond: (customer_id = 42)

Снаружи одна строка, внутри поиск по индексу. Это план для точечных запросов: один клиент, один заказ, одна дата. Как только внешний набор вырастает до десятков тысяч строк, Nested Loop становится самым медленным вариантом: для каждой строки отдельный поиск, и суммарно это дороже, чем прочитать таблицу целиком один раз.

Hash Join: хеш-таблица в памяти

Меньшую таблицу целиком прочитать и построить по ключу хеш-таблицу в памяти. Затем пройти большую таблицу один раз и для каждой строки заглянуть в хеш. Обе таблицы читаются ровно по разу, индексы не нужны.

EXPLAIN
SELECT c.city, sum(o.total_amount)
FROM orders o
JOIN customers c USING (customer_id)
GROUP BY 1;

HashAggregate
  ->  Hash Join
        Hash Cond: (o.customer_id = c.customer_id)
        ->  Seq Scan on orders o
        ->  Hash
              ->  Seq Scan on customers c

Хеш строится по customers, потому что она меньше: 15 тысяч строк против 80. Это рабочая лошадь аналитических запросов. Ограничение одно: хеш-таблица должна помещаться в память, лимит задаёт настройка work_mem. Если не помещается, база делит данные на партии и пишет их на диск, в плане появляется Batches: 2 и больше, и запрос замедляется в разы. Hash Join работает только для соединения по равенству.

Merge Join: два отсортированных потока

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

EXPLAIN
SELECT o.order_id, i.line_no
FROM orders o
JOIN order_items i USING (order_id)
ORDER BY o.order_id;

Merge Join
  Merge Cond: (o.order_id = i.order_id)
  ->  Index Only Scan using orders_pkey on orders o
  ->  Index Scan using ix_items_order on order_items i

Здесь оба входа уже отсортированы индексами, и ORDER BY сверху достался бесплатно. Merge Join выгоден для двух больших таблиц, когда сортировка есть или нужна по другой причине, и он не требует памяти под хеш. Если данные не отсортированы, добавляется узел Sort, и выгода часто исчезает.

Как планировщик выбирает

Сводка, к которой вы будете возвращаться:

Выбор зависит от оценки числа строк. Планировщик оценивает, сколько строк вернёт каждый узел, и опирается на статистику: сколько уникальных значений в колонке, как они распределены. Статистика собирается командой ANALYZE и устаревает после больших загрузок. Ошибка оценки в сто раз означает Nested Loop там, где нужен Hash Join, и запрос на час вместо секунды. В блоке про производительность разберём, как это увидеть в EXPLAIN ANALYZE.

Сравните на большой базе:

SET enable_hashjoin = off; SET enable_mergejoin = off;
EXPLAIN SELECT count(*) FROM orders o JOIN order_items i USING (order_id);

Планировщику остался Nested Loop, и он всё ещё использует индекс, но 180 тысяч раз. На этой машине это в три раза медленнее Hash Join. На таблицах в сотни миллионов строк разница измеряется часами.

Перекос и функции над ключом

Два способа сломать хороший план.

Перекос данных. У клиента 1 в базе сотни заказов, у большинства единицы. Hash Join к перекосу устойчив, а вот в распределённых системах перекос по ключу означает, что один узел получает всю работу. Об этом ниже.

Функция над колонкой в условии. Стоит написать o.customer_id::text = c.customer_id::text или lower(email) = lower(email), и индекс по колонке становится бесполезным: база не может искать в индексе по значению, которого там нет. Планировщик возвращается к полному перебору. Приводите типы на этапе загрузки, а не в условии соединения.

Что меняется в MPP: Greenplum, ClickHouse, Spark

В распределённой базе таблицы лежат на десятках узлов, разрезанные по ключу распределения. Соединить две таблицы можно только если строки с одинаковым ключом находятся на одном узле. Если ключ соединения совпадает с ключом распределения обеих таблиц, каждый узел соединяет свою часть локально, это самый дешёвый случай.

Если не совпадает, у планировщика два способа: разослать маленькую таблицу целиком на все узлы, broadcast, или перераспределить большую по ключу соединения через сеть, redistribute. Оба видны в плане Greenplum как Broadcast Motion и Redistribute Motion, и именно они, а не сам JOIN, обычно съедают время. Перекос по ключу здесь особенно опасен: узел, которому достался клиент 1, будет работать, пока остальные ждут.

Поэтому в MPP правила соединения дополняются: ключ распределения выбирается под самые частые JOIN, справочники делают маленькими и реплицируемыми, а перекошенные ключи разбирают отдельно. Подробно это разбирает модуль Greenplum, а здесь важно знать, что план JOIN в распределённой системе начинается с вопроса «где лежат данные».

Практика

База в этом уроке большая: первый запуск занимает 15–20 секунд и около 100 МБ памяти. В окружении заранее созданы индексы ix_orders_customer и ix_items_order. Задачи проверяются по тексту плана: нужный алгоритм должен появиться в выводе EXPLAIN.