Типы Join в ClickHouse. Как работает LEFT RIGHT INNER FULL CROSS JOIN?

В ClickHouse поддерживаются все основные типы соединений, известные из стандартного SQL:

• INNER JOIN возвращает только строки, которые совпадают по ключам соединения.
• LEFT OUTER JOIN возвращает все строки из левой таблицы, дополняя их совпадающими строками из правой таблицы. Если совпадений нет, строки из левой таблицы всё равно включаются.
• RIGHT OUTER JOIN аналогично LEFT JOIN, но приоритет отдаётся правой таблице (возвращает все строки из правой таблицы, дополняя их совпадающими строками из левой таблицы. Если совпадений нет, строки из правой таблицы возвращаются в полном объеме).
• FULL OUTER JOIN возвращает все строки из обеих таблиц, добавляя строки без совпадений с обеих сторон (не совпадающие строки из обеих таблиц возвращаются в дополнение к совпадающим строкам).
• CROSS JOIN создаёт декартово произведение таблиц, соединяя каждую строку одной таблицы с каждой строкой другой. Ключи соединения при этом не указываются.

Если тип соединения не указан, по умолчанию используется INNER JOIN. Слово OUTER в LEFT OUTER JOIN и RIGHT OUTER JOIN можно опустить. Для CROSS JOIN существует альтернативный синтаксис — перечисление таблиц через запятую в секции FROM.

Кроме того, в ClickHouse доступны дополнительные типы соединений:

• LEFT SEMI JOIN и RIGHT SEMI JOIN — возвращают строки, удовлетворяющие условиям соединения, не создавая при этом декартово произведение (белый список по ключам соединения).
• LEFT ANTI JOIN и RIGHT ANTI JOIN — исключают строки, соответствующие условиям соединения, также без декартова произведения (черный список по ключам соединения).
• LEFT ANY JOIN, RIGHT ANY JOIN и INNER ANY JOIN — частично или полностью отключают создание декартова произведения для стандартных видов соединений.
• ASOF JOIN и LEFT ASOF JOIN — используются для соединения последовательностей с нечетким совпадением по ключам.

Операции JOIN ClickHouse выполняются иначе, чем в традиционных базах данных SQL, в первую очередь из-за его столбчатой ​​архитектуры хранения и возможностей распределенной обработки данных. Понимание того, как JOIN работают внутри ClickHouse, включает рассмотрение типов JOIN, которые он поддерживает, и механизмов, которые он использует для эффективного выполнения этих операций.

Внутренняя работа ClickHouse при выполнении JOIN

1. Выбор алгоритма join

ClickHouse в основном использует два алгоритма для операций JOIN: Hash Join и Merge Join.

• Hash Join: используется по умолчанию и чаще всего. Эффективен для неравных размеров наборов данных (один маленький, один большой). Меньший набор данных используется для создания хэш-таблицы в памяти, которая затем используется для поиска строк из большей таблицы.
• Merge Join: используется для equi-JOIN на упорядоченных данных. Он менее требователен к памяти, но требует сортировки обоих наборов данных по ключу JOIN.

2. Распределенная обработка

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

3. Управление памятью

Для Hash Joins ClickHouse пытается вместить хэш-таблицу для меньшей таблицы в доступную память. Если она не вмещается, ClickHouse использует внешнюю память (диск) для переполнения, что может повлиять на производительность.
В ClickHouse есть несколько настроек для управления использованием памяти во время JOIN, например max_memory_usage и join_use_nulls.

4. Обработка столбцов

ClickHouse обрабатывает данные столбчатым способом, то есть извлекает только те столбцы, которые требуются для операции JOIN. Это повышает производительность, особенно при работе с широкими таблицами, где в JOIN задействовано всего несколько столбцов.

5. Работа с различными двигателями таблиц

Поведение ClickHouse JOIN также может различаться в зависимости от задействованных движков таблиц. Например, объединение двух таблиц MergeTree может быть более эффективным, чем объединение таблицы MergeTree с таблицей Memory.

Процесс Join можно представить упрощенно в виде схемы:

INNER JOIN

INNER JOIN возвращает для каждой строки из двух таблиц, совпадающих по ключам JOIN, значения столбцов строки из левой таблицы, объединенные со значениями столбцов строки из правой таблицы. Если строка имеет более одного соответствия, то возвращаются все соответствия (это означает, что декартово произведение создается для строк с совпадающими ключами JOIN).

OUTER JOIN

Ключевое слово OUTER можно опустить.

LEFT OUTER JOIN сначала выполняет операцию INNER JOIN. Затем каждая строка левой таблицы, которая не вошла в результат INNER JOIN, добавляется к результату LEFT OUTER JOIN со значениями по умолчанию для соответствующих типов данных в столбцах правой таблицы. Таким образом, в объединенной таблице всегда есть по крайней мере одна строка для каждой строки левой таблицы.

RIGHT OUTER JOIN работает аналогичным образом, но добавляет к результату INNER JOIN строки из правой таблицы, которые не вошли в результат INNER JOIN, со значениями по умолчанию в столбцах левой таблицы. В объединенной таблице всегда есть по крайней мере одна строка для каждой строки правой таблицы.

FULL OUTER JOIN комбинирует LEFT OUTER JOIN и RIGHT OUTER JOIN — то есть возвращает результат INNER JOIN, а также значения несовпадающих строк обеих таблиц, заполняя пустые ячейки значениями по умолчанию.

Чтобы вместо значений по умолчанию в пустых ячейках использовать значения NULL (как в стандартном SQL), нужно изменить значение настройки join_use_nulls.

CROSS JOIN

CROSS JOIN производит полное декартово произведение двух таблиц без учета ключей соединения. Каждая строка из левой таблицы объединяется с каждой строкой из правой таблицы.

Альтернативный синтаксис для CROSS JOIN — указать несколько таблиц в предложении FROM через запятую.

ClickHouse переписывает CROSS JOIN в INNER JOIN, если в WHERE запроса есть выражения соединения.

SEMI JOIN

Запрос LEFT SEMI JOIN возвращает значения столбцов для каждой строки из левой таблицы, которая имеет хотя бы одно совпадение ключа соединения в правой таблице. Возвращается только первое найденное совпадение (декартово произведение отключено).

Запрос RIGHT SEMI JOIN аналогичен и возвращает значения для всех строк из правой таблицы, имеющих хотя бы одно совпадение в левой таблице, но возвращается только первое найденное совпадение (декартово произведение отключено).

ANTI JOIN

LEFT ANTI JOIN возвращает значения столбцов для всех несовпадающих строк из левой таблицы.

Аналогично, RIGHT ANTI JOIN возвращает значения столбцов для всех несовпадающих правых строк таблицы.

ANY JOIN

LEFT ANY JOIN — это комбинация LEFT OUTER JOIN + LEFT SEMI JOIN, что означает, что ClickHouse возвращает значения столбцов для каждой строки из левой таблицы, либо объединенные со значениями столбцов соответствующей строки из правой таблицы, либо объединенные со значениями столбцов по умолчанию для правой таблицы, в случае отсутствия совпадений. Если строка из левой таблицы имеет более одного совпадения в правой таблице, ClickHouse возвращает только объединенные значения столбцов из первого найденного совпадения (декартово произведение отключено).

Аналогично, RIGHT ANY JOIN представляет собой комбинацию RIGHT OUTER JOIN + RIGHT SEMI JOIN.

А INNER ANY JOIN — это INNER JOIN с отключенным декартовым произведением.

ASOF JOIN

ASOF JOIN, реализованный для ClickHouse в 2019 году Мартейном Баккером и Артемом Зуйковым, обеспечивает возможности неточного соответствия. Если строка из левой таблицы не имеет точного соответствия в правой таблице, то вместо этого в качестве соответствия используется ближайшая соответствующая строка из правой таблицы.

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

Для работы алгоритма необходим специальный столбец в таблицах:

• Должен содержать упорядоченную последовательность.
• Может быть одного из следующих типов: Int, UInt, Float, Date, DateTime, Decimal.
• Не может быть единственным столбцом в секции JOIN.

Синтаксис ASOF JOIN ... ON:

Можно использовать произвольное количество условий равенства и одно условие на ближайшее совпадение. Например:

Условия, поддержанные для проверки на ближайшее совпадение:
>, >=, <, <=

Алгоритмы JOIN

На текущий момент для ClickHouse разработано 6 следующих алгоритмов JOIN:

• Direct join
• Hash join — Хэш-соединение
• Parallel hash join — Параллельное хэш-соединение
• Grace hash join
• Full sorting merge join — Полная сортировка слиянием
• Partial merge join — Частичное слияние

Эти алгоритмы определяют способ планирования и выполнения запроса на join.

По умолчанию ClickHouse использует Direct join или Hash join алгоритм на основе используемого join type, strictness и движка (engine) соединяемых таблиц.

В качестве альтернативы ClickHouse можно настроить на адаптивный выбор и динамическое изменение алгоритма соединения для использования во время выполнения в зависимости от доступности и использования ресурсов:

Когда join_algorithm установлен в auto, ClickHouse сначала пробует hash join алгоритм, и если предел памяти этого алгоритма нарушен, алгоритм переключается на лету на partial merge join.
Вы можете наблюдать, какой алгоритм был выбран, с помощью журнала трассировки (trace logging).

Клиент будет получать журналы трассировки, даже если на сервере установлен уровень журнала ‘info‘.

ClickHouse также позволяет пользователям самостоятельно указывать желаемый алгоритм соединения.

Обзор JOIN алгоритмов ClickHouse на основе их относительного потребления памяти и времени выполнения:

Выбор алгоритма Join происходит по следующей схеме:

Query Pipeline ClickHouse (Конвейер запросов)

Конвейер запросов ClickHouse разработан так, чтобы быть быстрым.

Запросы в ClickHouse обрабатываются в высокопараллельном режиме, используя все необходимые ресурсы, доступные на текущем сервере, и во многих случаях оборудование используется до его теоретических пределов. Чем больше ядер ЦП и основной памяти у сервера, тем больше выигрыша в производительности от параллельного выполнения запроса.

Query Pipeline определяет уровень параллелизма для каждого этапа выполнения запроса.

На следующей диаграмме показано, как ClickHouse Query Pipeline обрабатывает запрос на сервере с 4 ядрами ЦП:

Запрашиваемые табличные данные динамически распределяются между 4 отдельными и параллельными потоковыми этапами, которые передают данные поблочно в ClickHouse. Поскольку сервер имеет 4 ядра ЦП, большинство этапов обработки запросов из конвейера запросов выполняются 4 потоками параллельно.

Количество используемых потоков зависит от параметра max_threads, который по умолчанию равен количеству ядер ЦП, которые ClickHouse видит на машине, на которой он работает.

Для всех запросов, включая join, конвейер запросов обеспечивает высокопараллельную и масштабируемую обработку данных таблицы.

Как работает Direct Join в ClickHouse?

Алгоритм Direct Join может быть применен, когда базовое хранилище для таблицы с правой стороны поддерживает запросы ключ-значение с низкой задержкой (low latency key-value requests). ClickHouse имеет три движка таблиц, обеспечивающих это:

• Join (по сути, это предварительно вычисленная хэш-таблица),
• EmbeddedRocksDB и
• Dictionary.

Следующее описание механики алгоритма Direct Join на основе Dictionary, одинаково применимо для всех трех движков.

Словари (Dictionary) — это ключевая функция ClickHouse, обеспечивающая представление данных в памяти по принципу «ключ-значение» из различных внутренних и внешних источников, оптимизированное для запросов поиска с очень низкой задержкой.

Это удобно в различных сценариях, например, для обогащения полученных данных «на лету», не замедляя процесс приема, а также для повышения производительности запросов в целом, при этом особенно полезны операции JOIN.

Cхема конвейера запросов алгоритма Direct Join:

Алгоритм Direct Join требует, чтобы правая таблица поддерживалась словарем, так что данные, которые должны быть объединены из этой таблицы, уже присутствовали в памяти в форме структуры данных ключ-значение с low-latency.

Затем все данные из левой таблицы передаются параллельно двумя потоками (потому что max_threads = 2) в механизм запросов, и строки объединяются параллельно двумя этапами соединения путем выполнения поиска в базовом словаре правой таблицы.

Поддерживаемые типы соединений для алгоритма Direct Join
Поддерживается только тип соединения LEFT ANY. Обратите внимание, что ключ соединения должен соответствовать атрибуту ключа базового хранилища ключей и значений.

Low-Latency

В ClickHouse low-latency (низкая задержка) означает, что запросы могут обрабатываться без задержек и без попыток подготовить ответ заранее, прямо в тот момент, когда загружается страница пользовательского интерфейса. Другими словами, в режиме онлайн.

Как работает Hash Join в ClickHouse?

Хеш-таблица в памяти может обслуживать 250 миллионов совершенно случайных запросов в секунду (и более миллиарда, если она помещается в CPU cache). Эта очень быстрая возможность поиска делает хеш-таблицу в памяти естественным общим выбором в ClickHouse для реализации join, когда невозможно или нецелесообразно использовать преимущества сортировки таблиц.

Алгоритм хэш-соединения является наиболее общим из доступных реализаций join в ClickHouse.

Схема работы алгоритма Hash join в Query Pipeline ClickHouse:

① Все данные из таблицы справа передаются (параллельно двумя потоками, поскольку max_threads = 2) в память, а затем ClickHouse заполняет этими данными хэш-таблицу в памяти.
② Данные из таблицы слева передаются потоком (параллельно двумя потоками, поскольку max_threads = 2) и
③ Объединяются путем выполнения поиска в хэш-таблице.

Обратите внимание, что поскольку ClickHouse берет таблицу с правой стороны и создает для нее хэш-таблицу в оперативной памяти, более эффективно размещать меньшую таблицу с правой стороны JOIN.

Также обратите внимание, что таблица Hash является ключевой структурой данных в ClickHouse. На основе каждого конкретного запроса и, в частности, для запросов join, на основе типов столбцов ключей join и строгости join ClickHouse автоматически выбирает один из 30+ вариантов.

Поддерживаемые типы соединений для алгоритма Hash Join

В настоящее время Hash Join поддерживает несколько ключей соединения, объединенных с помощью OR в предложении ON.

Рекомендации по использованию JOIN в ClickHouse

todo

Дополнительные материалы по JOINs в ClickHouse

• ClickHouse официальная документация — Секция JOIN
• Оператор JOIN в блоге Arenadata (полный раздел по Arenadata QuickMarts)