6 JOIN-алгоритмов

ClickHouse не имеет одного “JOIN-движка”. Вместо этого — 6 алгоритмов, каждый оптимизированный для своего сценария. Выбор правильного алгоритма может ускорить запрос в 25 раз или предотвратить Out Of Memory.

По умолчанию ClickHouse использует hash join. Но hash join загружает правую таблицу целиком в RAM — для таблицы в 100 ГБ при 16 ГБ RAM это катастрофа. Знание всех шести алгоритмов позволяет выбрать оптимальный для каждой ситуации.

Обзор алгоритмов

Hash Join (по умолчанию)

Загружает правую таблицу целиком в hash table в RAM. Затем для каждой строки левой таблицы — lookup в hash table по join key.

SET join_algorithm = 'hash';

SELECT l.*, r.country_name
FROM events l
JOIN countries r ON l.country_code = r.code

Когда использовать: правая таблица помещается в RAM. Для большинства аналитических JOIN — это дефолт.

Потребление памяти: примерно равно размеру правой таблицы в несжатом виде. Настройка max_bytes_in_join ограничивает максимальный размер hash table (при превышении — ошибка или переключение на другой алгоритм, если join_algorithm = 'auto').

Parallel Hash Join

Параллельное построение hash table по бакетам (по умолчанию 16). Несколько потоков строят hash table одновременно.

SET join_algorithm = 'parallel_hash';

SELECT l.*, r.region
FROM large_events l
JOIN large_regions r ON l.region_id = r.id

Когда использовать: правая таблица большая (десятки ГБ), RAM достаточно, и hash join становится bottleneck на этапе построения hash table.

Отличие от hash: hash строит hash table в одном потоке. parallel_hash — в нескольких. Lookup фаза одинаково параллельна в обоих.

Grace Hash Join

Разбивает обе таблицы на бакеты по hash от join key. Обрабатывает по одному бакету: строит hash table только для текущего бакета правой таблицы, проходит соответствующий бакет левой. Данные, не помещающиеся в RAM, спиллятся на диск.

SET join_algorithm = 'grace_hash';
SET grace_hash_join_initial_buckets = 16;

SELECT l.*, r.details
FROM huge_events l
JOIN huge_dimensions r ON l.dim_id = r.id

Когда использовать: правая таблица не помещается в RAM. grace_hash позволяет выполнить JOIN без OOM, ценой использования диска.

Настройки:

• grace_hash_join_initial_buckets — начальное количество бакетов (больше = меньше памяти, но больше I/O)
• Бакеты могут автоматически расщепляться (adaptive bucketing)

Full Sorting Merge Join

Сортирует обе таблицы по join key, затем выполняет merge (как merge sort). Если данные уже физически отсортированы по join key (совпадает с ORDER BY таблицы) — сортировка пропускается.

SET join_algorithm = 'full_sorting_merge';

-- Оптимально если обе таблицы ORDER BY user_id
SELECT l.*, r.profile
FROM events l        -- ORDER BY (user_id, event_date)
JOIN profiles r      -- ORDER BY user_id
ON l.user_id = r.user_id

Когда использовать: обе таблицы уже отсортированы по join key. В этом случае merge выполняется без дополнительной сортировки и конкурирует по скорости с hash join при значительно меньшем потреблении памяти.

DESCRIBE TABLE events FORMAT Vertical
-- ORDER BY: (user_id, event_date) → user_id = join key ✓

Partial Merge Join

Полная сортировка правой таблицы на диск. Поблочная сортировка левой таблицы (не целиком). Минимальное потребление RAM.

SET join_algorithm = 'partial_merge';

Когда использовать: экстремальный дефицит памяти. partial_merge — самый медленный, но самый экономный по RAM.

Ограничения: поддерживает только RIGHT и FULL JOIN с ALL strictness. Для LEFT JOIN используйте grace_hash.

Direct Join

Key-value lookup в Dictionary, Join engine или EmbeddedRocksDB engine правой таблицы. Данные правой таблицы уже в памяти (Dictionary) или на быстром key-value хранилище.

SET join_algorithm = 'direct';

-- Правая таблица = Dictionary
SELECT l.*, dictGet('country_dict', 'name', l.country_code) AS name
FROM events l;

-- Или через JOIN с Dictionary engine table
SELECT l.*, r.name
FROM events l
LEFT ANY JOIN countries_dict r ON l.country_code = r.code

Когда использовать: правая таблица — это справочник (Dictionary, Join engine). Direct join до 25x быстрее hash join, потому что Dictionary уже в памяти и не требует построения hash table.

Ограничения: только LEFT ANY JOIN. Не поддерживает INNER, RIGHT, FULL JOIN.

Фреймворк выбора алгоритма

Настройка join_algorithm

-- Указать конкретный алгоритм
SET join_algorithm = 'hash';                -- по умолчанию
SET join_algorithm = 'grace_hash';          -- спилл на диск
SET join_algorithm = 'full_sorting_merge';  -- для отсортированных данных
SET join_algorithm = 'direct';              -- для Dictionary

-- Автоматический выбор
SET join_algorithm = 'auto';
-- ClickHouse пробует hash → при OOM переключается на grace_hash

join_algorithm = 'auto' — безопасный вариант: начинает с hash, при превышении max_bytes_in_join автоматически переключается на grace_hash. Подходит для production, когда размер данных непредсказуем.

Сравнение производительности

Ключевые выводы

1. 6 алгоритмов, каждый для своего сценария. Нет “лучшего” — есть подходящий для конкретных данных и ресурсов.
2. hash — дефолт, быстрый, но загружает правую таблицу в RAM целиком.
3. direct — самый быстрый (до 25x), но только для Dictionary/Join engine и только LEFT ANY JOIN.
4. grace_hash — спасение при нехватке RAM: спиллит на диск, контролируется через бакеты.
5. full_sorting_merge — конкурент hash при отсортированных данных и значительно меньшем потреблении памяти.
6. join_algorithm = ‘auto’ — безопасный production-вариант: hash с автоматическим fallback на grace_hash.