TL;DR: Новый оптимизатор соединений (CBO) в ClickHouse основан на эффективной реализации DPsub — исчерпывающего алгоритма динамического программирования. Для запросов, содержащих до 12 таблиц, он находит самый дешевый план в рамках существующей стоимостной модели и будет включен по умолчанию в предстоящем релизе 26.10. До сих пор изменение порядка соединений работало только для внутренних соединений (inner joins), а любой другой тип соединения выступал в качестве барьера оптимизации. Новый оптимизатор также изменяет порядок левых (LEFT), правых (RIGHT) и полных (FULL) внешних соединений, а также полусоединений (SEMI) и антисоединений (ANTI). Детектор конфликтов делает этот процесс безопасным. Он допускает только те перестановки, которые сохраняют результат запроса (корректность), и находит каждый допустимый план в пространстве поиска (полнота). Оба свойства доказаны, а тестирование на более чем 90 000 деревьев соединений и 2,8 миллионах планов-кандидатов не выявило ни одного неверного или пропущенного плана.
TL;DR: Новый оптимизатор соединений (CBO) в ClickHouse основан на эффективной реализации DPsub — исчерпывающего алгоритма динамического программирования. Для запросов, содержащих до 12 таблиц, он находит самый дешевый план в рамках существующей стоимостной модели и будет включен по умолчанию в предстоящем релизе 26.10.
До сих пор изменение порядка соединений работало только для внутренних соединений (inner joins), а любой другой тип соединения выступал в качестве барьера оптимизации. Новый оптимизатор также изменяет порядок левых (LEFT), правых (RIGHT) и полных (FULL) внешних соединений, а также полусоединений (SEMI) и антисоединений (ANTI). Детектор конфликтов делает этот процесс безопасным. Он допускает только те перестановки, которые сохраняют результат запроса (корректность), и находит каждый допустимый план в пространстве поиска (полнота). Оба свойства доказаны, а тестирование на более чем 90 000 деревьев соединений и 2,8 миллионах планов-кандидатов не выявило ни одного неверного или пропущенного плана.
SQL декларативен: запрос задает желаемый результат, а не способ его вычисления. Между ними находится оптимизатор запросов. Он превращает запрос в план выполнения — дерево операторов, таких как сканирования, фильтры, соединения и агрегации, причем для любого нетривиального запроса существует множество логически эквивалентных планов, вычисляющих абсолютно тот же результат. Фильтры могут применяться до или после соединения, соединение может строить свою хэш-таблицу из любого источника, а соединения могут выполняться в разном порядке и с использованием разных алгоритмов.
Эти планы возвращают одинаковые строки, но их стоимость может отличаться на порядки, поскольку они перекачивают через конвейер совершенно разные объемы данных. Задача оптимизатора — найти дешевый план, и для этого ему необходимы три вещи:
- пространство поиска: планы, которые эквивалентны запросу;
- стоимостная модель: оценка того, насколько дорог каждый план, построенная на основе оценок количества строк, производимых каждым оператором (на основе статистики таблиц, индексов или эвристик);
- стратегия поиска: способ найти дешевый план в этом пространстве, не перебирая их все.
Ни одно решение не имеет большего значения, чем порядок соединений. Различные порядки порождают промежуточные результаты совершенно разного размера. Соединение двух самых больших таблиц в первую очередь может материализовать миллиарды строк, в то время как соединение большой таблицы с небольшой и селективной сначала может сократить объем до нескольких тысяч строк до того, как произойдет дорогостоящее соединение. Меньшие промежуточные результаты означают меньше работы и меньше потребление памяти, поэтому цель оптимизатора — минимизировать их размер.
Никакое другое решение также не обладает столь огромным пространством поиска. Соединение n таблиц друг за другом уже допускает n! вариантов порядка. Как только соединение начинает объединять два промежуточных результата (кустовидный план), количество различных деревьев соединений становится равным n! · C(n−1), где C — число Каталана, описывающее формы деревьев. Это упрощается до (2n−2)! / (n−1)!. Для 10 таблиц это 3 628 800 левосторонних порядков, но более 17,6 миллиарда деревьев соединений. Для 12 таблиц это уже около 28 триллионов.
Существует два классических способа поиска в этом пространстве.
Жадная оптимизация. Жадный оптимизатор последовательно соединяет те два входа, результат для которых обходится дешевле всего. Он работает быстро и зачастую дает приемлемый результат, но принимает решения на ранних этапах и никогда к ним не возвращается, поэтому одно локально привлекательное соединение может загнать его в тупик худшего общего плана. По умолчанию в ClickHouse использовался жадный оптимизатор.
Динамическое программирование. Оптимизатор на основе динамического программирования «снизу вверх» находит точный порядок с наименьшей стоимостью. В его основе лежит одно наблюдение: лучший план для соединения набора таблиц строится из лучших планов двух меньших непересекающихся подмножеств. Вместо перебора каждого дерева соединений, количество которых растет факториально и достигает миллиардов даже для десятка таблиц, он решает каждую подзадачу один раз и переиспользует ответ. Процедура выполняется в порядке возрастания размера подмножества:
- Базовый случай. Для каждой отдельной таблицы лучшим планом является сканирование этой таблицы с применением ее фильтров.
- Комбинация. Для каждого большего подмножества таблиц рассматривается каждый способ его разделения на две непустые непересекающиеся части. Каждое разделение дает план-кандидат: соединение лучшего плана для левой части с лучшим планом для правой части, а его стоимость оценивается на основе предполагаемого размера вывода и стоимости двух подпланов.
- Сохранение победителя. Сохраняется самый дешевый кандидат для данного подмножества. Обе части меньше самого подмножества, поэтому их лучшие планы уже сохранены.
- Завершение. Когда достигается подмножество, содержащее все таблицы, его запись становится оптимальным порядком соединений.
Перечислители в этом семействе отличаются главным образом тем, как они обходят пространство поиска. DPsub — это вариант, управляемый подмножествами. Он представляет каждое подмножество таблиц в виде битовой маски (по одному биту на таблицу), так что каждое подмножество представляет собой просто целое число от 1 до 2ⁿ−1. Перечисление всех подмножеств означает увеличение этих целых чисел в порядке возрастания. Для каждого подмножества потенциальными левыми сторонами разделения являются его собственные подподмножества, которые можно сгенерировать путем неоднократного вычитания единицы и применения побитовой маски к подмножеству — этот трюк позволяет перебрать их все, ничего не пропуская и не повторяя. Правая сторона — это то, что осталось, что вычисляется как единичная операция XOR с левой стороной.
Что делает этот подход привлекательным, так это дешевизна самого перечисления. Инкремент счетчика, вычитание единицы, применение побитового И (AND) к двум маскам, побитового ИСКЛЮЧАЮЩЕГО ИЛИ (XOR) к двум маскам и подсчет установленных битов относятся к числу простейших операций для процессора. Каждая из них обычно транслируется в единую инструкцию, выполняемую примерно за один такт, а подмножество целиком находится в регистре. Здесь нет указателей, которые нужно отслеживать, нет наборов, которые нужно выделять, и нет хэширования. Лучший план для каждого подмножества может храниться в массиве, индексируемом битовой маской, который для 12 таблиц содержит всего 4096 записей и отлично помещается в кэш процессора. Пространство поиска по-прежнему велико, так как количество разделений растет примерно как 3ⁿ (около полумиллиона для 12 таблиц), но накладные расходы на генерацию каждого разделения составляют всего несколько тактов. Именно поэтому оптимизатор может исчерпывающе исследовать каждое подмножество и каждое разделение вместо агрессивного отсечения.
У этой простоты есть своя цена. DPsub также генерирует разделения, две стороны которых не связаны каким-либо предикатом соединения, поэтому практическая реализация пропускает такие варианты во избежание декартовых произведений. А поскольку объем работы растет экспоненциально, исчерпывающее динамическое программирование практично только для ограниченного числа таблиц: DPsub в ClickHouse перебирает подмножества размером до 12 таблиц.
Callout: Новый алгоритм изменения порядка соединений (Join Reordering) в ClickHouse создан на базе эффективной реализации DPsub. Для запросов, содержащих до 10 таблиц (до 12, если увеличено значение query_plan_optimize_join_order_limit), он находит самый дешевый план в рамках существующей модели стоимости.
Callout: Новый алгоритм изменения порядка соединений (Join Reordering) в ClickHouse создан на базе эффективной реализации DPsub. Для запросов, содержащих до 10 таблиц (до 12, если увеличено значение query_plan_optimize_join_order_limit), он находит самый дешевый план в рамках существующей модели стоимости.
Давайте рассмотрим пример с использованием набора данных TPC-H и сравним размеры промежуточных результатов для двух порядков соединений в одном и том же запросе TPC-H. Вы можете видеть, что подход «сначала селективная таблица» дает промежуточные результаты примерно в 100 раз меньшего размера для этого запроса.
Однако полный перебор хорош ровно настолько, насколько велико разрешенное для него пространство поиска, и для большинства реальных запросов в этом пространстве отсутствовал целый класс соединений!
Порядок соединений может изменить время выполнения запроса на несколько порядков. Внутренние соединения (inner joins) позволяют легко этим воспользоваться: они коммутативны (A ⋈ B равносильно B ⋈ A) и ассоциативны ((A ⋈ B) ⋈ C равносильно A ⋈ (B ⋈ C)), поэтому любой порядок дает одинаковый результат, и оптимизатору нужно лишь найти самый дешевый.
Во многих реальных запросах используются и другие типы соединений, поведение которых зависит от того, какие строки не имеют соответствия с другой стороны:
Левые внешние (left outer), полусоединения (semi) и антисоединения (anti joins) не коммутативны: A LEFT JOIN B сохраняет все строки из A, в то время как B LEFT JOIN A сохраняет все строки из B. Зачастую они также не ассоциативны. Возьмем (A LEFT JOIN B) JOIN C ON B.x = C.x. Строки из A, не имеющие пары в B, получают значение NULL для B.x, поэтому внутреннее соединение с C отбрасывает их. Если же оптимизатор сначала вычислит B JOIN C, а затем выполнит левое соединение A с полученным результатом, эти строки из A сохранятся. Два плана возвращают разные результаты, поэтому второй вариант не является допустимым изменением порядка.
Чтобы вообще иметь возможность изменять порядок таких соединений, оптимизатор должен отвечать на один вопрос для каждого рассматриваемого кандидата на соединение: является ли это изменение порядка допустимым? Компонент, который отвечает на этот вопрос, называется детектором конфликтов (conflict detector). Он меняет пространство поиска в двух направлениях. По сравнению с подходом, при котором любое соединение можно свободно переупорядочивать, он делает пространство меньше: каждое недопустимое изменение порядка, которое он исключает, — это часть пространства, которую больше не нужно исследовать. По сравнению с отношением к любому не внутреннему соединению как к барьеру, как это делала ClickHouse до сих пор, он делает пространство больше: все допустимые изменения порядка, которые скрывали барьеры, становятся доступными. Оптимизатор исследует больше планов, чем раньше, и каждый из них возвращает правильный результат.
До сих пор ClickHouse оптимизировала полусоединения и антисоединения на отдельном этапе, за пределами графа внутренних соединений:
- Оптимизатор разворачивал дерево соединений в единый граф таблиц для переупорядочивания, но принимал только простые соединения: потомок semi или anti никогда не встраивался в этот граф.
- Полусоединение или антисоединение на самом верху ограничивало граф двумя таблицами: никакой реассоциации, только обмен двух его входов местами.
- Поэтому каждое полусоединение или антисоединение было барьером оптимизации. Запрос разбивался на изолированные группы внутренних соединений, каждая из которых оптимизировалась сама по себе, а полусоединения и антисоединения были закреплены там, где их написал автор запроса.
Следствие: селективное полусоединение или антисоединение не могло быть протолкнуто за питающие его внутренние соединения, поэтому план сначала строил полный промежуточный результат.
Взгляните на этот запрос:
big и mid используют одни и те же ключи соединения, поэтому big JOIN mid получается огромным; tiny содержит лишь горстку ключей, поэтому полусоединение отбрасывает почти все строки. Когда полусоединение закреплено наверху, план сначала строит big JOIN mid. Если же разрешить полусоединению участвовать в поиске порядка соединений, оптимизатор сможет сначала отфильтровать big:
Это промежуточный результат, который меньше примерно в 496 раз, при использовании того же самого энумератора соединений в обоих случаях: единственная разница заключается в том, что полусоединение участвует в поиске. Результат идентичен.
Наш детектор конфликтов основан на On the Correct and Complete Enumeration of the Core Search Space (SIGMOD 2013). В этой статье было показано, что более ранние подходы могли пропускать допустимые планы или принимать недопустимые, и был представлен детектор конфликтов, который математически доказано является одновременно корректным и полным.
В статье определяется ядро пространства поиска: каждый план, достижимый из исходного дерева соединений с помощью алгебраических преобразований, допустимых для его операторов. Детектор конфликтов генерирует ровно это пространство, не больше и не меньше. Именно этот детектор мы и реализовали, охватив внутренние (inner), левые/правые/полные внешние (left/right/full outer), а также левые/правые полусоединения и антисоединения (left/right semi and anti joins).
То, можно ли менять местами или перегруппировывать два соседних соединения без изменения результата, зависит от их типов и, в некоторых случаях, от того, отклоняют ли их предикаты значения NULL. Детектор проверяет четыре свойства, чтобы определить, какие преобразования безопасны. В выражениях ниже ∘ᵃ и ∘ᵇ обозначают операторы соединения, а e₁, e₂ и e₃ — их входы. Свойство comm описывает отдельный тип оператора; остальные три хранятся в матрицах, индексируемых парами типов операторов:
- comm: является ли оператор коммутативным? (a ⋈ b = b ⋈ a)
- assoc: (e₁ ∘ᵃ e₂) ∘ᵇ e₃ = e₁ ∘ᵃ (e₂ ∘ᵇ e₃)?
- l-asscom: (e₁ ∘ᵃ e₂) ∘ᵇ e₃ = (e₁ ∘ᵇ e₃) ∘ᵃ e₂?
- r-asscom: e₁ ∘ᵃ (e₂ ∘ᵇ e₃) = e₂ ∘ᵇ (e₁ ∘ᵃ e₃)?
Рассмотрим этот запрос по клиентам, заказам и платежам:
При join_use_nulls = 1 несоответствующие строки заполняются значениями NULL. План A ниже следует порядку соединений, указанному в запросе; План B — это предлагаемое изменение порядка, которое детектор должен отклонить. Эти упрощенные логические планы показывают соединения и сканирования, опуская финальную проекцию. Они не эквивалентны.
План A — исходный
План B — недопустимое изменение порядка для Плана A
Для клиента без заказов План A создает строку с полями заказа, заполненными NULL, а затем отбрасывает ее на внутреннем соединении, так как она не может найти соответствие среди платежей. План B сначала соединяет заказы с платежами, а затем сохраняет этого клиента при левом соединении. Детектор должен отклонить План B в качестве альтернативы Плану A, так как он меняет результат: assoc(⟕, ⋈) возвращает false.
Теперь рассмотрим другой запрос, в котором типы соединений идут в обратном порядке:
Для этого запроса План C следует исходному порядку, а План D представляет собой допустимое изменение порядка:
План C — исходный
План D — допустимое изменение порядка для Плана C
Планы C и Д оставляют только клиентов с заказами и сохраняют каждый подходящий заказ, даже если для него нет платежа: assoc(⋈, ⟕) возвращает true. Следовательно, детектор может принять План D в качестве альтернативы Плану C.
Если оба соединения являются левыми, регруппировка также безопасна при тех же условиях равенства. Отсутствующий заказ не может совпасть с платежом, поскольку orders.id = payments.order_id отбрасывает NULL. Условие, которое могло бы совпасть с заполненным NULL заказом, сделало бы эту гарантию недействительной: assoc(⟕, ⟕) выполняется только в условиях отклонения null (null rejection). Именно поэтому правила зависят как от типов соединений, так и от того, как их условия обрабатывают значения NULL.
Наша реализация сохраняет эти правила в виде статических данных — одна строка для comm и три матрицы, что позволяет детектору проверять каждое предлагаемое преобразование, а не предполагать, что любая регруппировка безопасна.
Перед началом перебора детектор обходит исходное дерево соединений запроса. Для каждого оператора он записывает левое и правое поддеревья входов, таблицы, на которые ссылается его предложение ON, и таблицы, для которых это предложение отклоняет значения NULL. Затем для каждой пары операторов, где матрицы запрещают преобразование, он регистрирует конфликт.
Каждый оператор требует с каждой стороны только те таблицы, на которые там ссылается его секция ON, и каждый конфликт записывается отдельно в виде правила «если хотя бы одна таблица из T₁ уже присоединена, то все таблицы из T₂ тоже должны быть присоединены». Например, в Плане A внутреннее соединение (inner join) получает правило «если присоединена таблица orders, то должна быть присоединена и customers», что отклоняет orders ⋈ payments в Плане B. Сохранение конфликтов в виде отдельных условных правил вместо сведения их всех в обязательные множества — это то, что делает детектор полным: он отклоняет план только тогда, когда конфликт действительно к нему применим. Проверка валидности применяется каждый раз, когда перечислитель рассматривает соединение множества таблиц S₁ с множеством S₂:
Если проверка проходит успешно, оператор, примененный на этом разделении, определяет тип и строгость итогового соединения. Проверка представляет собой несколько операций с битовыми масками, поэтому она практически не увеличивает время перечисления.
DPsub перечисляет подмножества таблиц в виде битовых масок и для каждого подмножества находит наиболее дешевый способ его построения из двух меньших связанных подмножеств. С использованием детектора все дерево соединений попадает в DPsub как единый граф таблиц: обе стороны каждого outer, semi и anti join, а также FULL join. Потребовалось еще несколько деталей:
- Декартовы произведения (cross products). CROSS JOIN не имеет условий соединения, поэтому не добавляет ребро в граф. Мы явно связываем две его стороны как соединение с селективностью 1, чтобы граф оставался связным, а DPsub мог переместить декартово произведение туда, где оно дешевле всего, при этом оно по-прежнему выполняется и отображается как CROSS JOIN.
- Сторона сборки (build side). Стоимостная модель DPsub оценивает соединение одинаково независимо от порядка его входных данных, поэтому после поиска мы помещаем меньший ввод на сторону сборки (build side) хэш-соединения, меняя внешние соединения LEFT ↔ RIGHT, но никогда не делаем этого для ANY, SEMI и ANTI joins, смысл которых зависит от стороны.
- Ограниченный поиск. DPsub с детектором планирует деревья соединений размером до 12 таблиц, включая semi, anti и outer joins. Более крупные деревья соединений передаются жадному оптимизатору.
Детектор, ошибающийся хотя бы один раз, дает неверные результаты, поэтому мы проверили его так, как описано в научной статье. Для заданного числа таблиц n тестовый стенд:
- генерирует каждое исходное дерево соединений: все формы деревьев × все назначения операторов × все бинарные предикаты равенства;
- перечисляет все основное пространство поиска для каждого дерева;
- и проверяет каждый план-кандидат тремя независимыми способами: встроенным детектором, независимой эталонной реализацией, определяющей основное пространство поиска, и выполнением на случайных базах данных с NULL.
Он подсчитывает планы, сгенерированные за пределами основного пространства поиска (недействительные, должно быть 0), основные планы, которые не удалось сгенерировать (пропущенные), и любые планы, завершившиеся ошибкой при выполнении (должно быть 0).
Inner, left outer и anti joins:
Inner, left/full outer, semi и anti joins:
(Для строк, представляющих 6 и 7 таблиц, деревья соединений сэмплировались.) Во всех экспериментах детектор сгенерировал каждый из 2,8 миллиона основных планов и ни одного недействительного, и ни один план не сбойнул при выполнении.
Фаззер генерирует случайные запросы с множественными соединениями, комбинируя INNER, LEFT, RIGHT, FULL, SEMI и ANTI joins, включая секции ON, ссылающиеся только на одну сторону, на реальных данных с NULL, дубликатами и несовпадающими ключами. Каждый запрос выполняется тремя способами и сравнивается с контрольной суммой, независящей от порядка и безопасной для NULL, вычисляемой внутри ClickHouse:
- base: порядок написания, без переупорядочивания, в качестве эталона (ground truth);
- greedy: существующий оптимизатор по умолчанию;
- DPsub: DPsub с детектором конфликтов.
1 200 запросов, содержащих до 7 таблиц: 0 расхождений.
Насколько больше пространства поиска детектор открывает для реального оптимизатора? Подсчет валидных планов, которые исследует DPsub для 1 200 сэмплированных запросов с количеством таблиц от 3 до 7:
При 7 таблицах детектор конфликтов позволяет DPsub рассматривать в 11,5 раза больше валидных планов, чем без него: чем больше соединений в запросе, тем больше хороших планов раньше скрывали барьеры.
Тесты без сохранения состояния (stateless) в CI проверяют, помимо прочего, что каждая пара типов соединений попадает в DPsub как единый граф с неизменными результатами, что сохраняется строгость ANY/SEMI/ANTI, параметр join_use_nulls, вырожденные предикаты и декартовы произведения.
Вернемся к нашему запросу с semi-join:
но теперь оценим его по сравнению с предыдущим вариантом по умолчанию, то есть жадным оптимизатором (greedy). На наборе данных с 3 миллионами строк в big и mid и 100 ключами в tiny жадный алгоритм оставляет semi join поверх big JOIN mid:
DPsub с детектором конфликтов перемещает его ниже inner join:
Фильтры соединений во время выполнения (runtime join filters) в ClickHouse, которые пробрасывают ключи хэш-таблицы вниз к сканированию другой стороны, уже компенсируют часть неоптимального порядка в этом запросе; более хороший план от них не зависит.
На запросах TPC-DS (SF1) и TPC-H (SF1/SF10) в наших тестах производительности по сравнению с жадным алгоритмом по умолчанию:
Наш новый DPsub с детектором конфликтов является оптимизатором на основе стоимости (CBO) по умолчанию для соединений начиная с релиза 26.10:
Если вы хотите сравнить с предыдущим поведением, вы можете отключить его для каждого отдельного запроса. Чтобы узнать больше подробностей и посмотреть на порядок, тип и строгость каждого соединения, выполните EXPLAIN actions = 1:
/)
