Мы ускорили JOIN в ClickHouse… в 100 раз

Недавно мы представили два пул-реквеста в ClickHouse, которые значительно повышают производительность JOIN’ов в распространенных сценариях.

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

Пул-реквест №1: Проталкивание предикатов JOIN с применением классов эквивалентности

Проталкивание предикатов (predicate pushdown) — это техника оптимизации запросов, используемая в системах управления базами данных для значительного сокращения объема данных, обрабатываемых запросом.

В ClickHouse, как и в большинстве других баз данных SQL, выполнение запроса делится на несколько этапов:

1. Парсинг запроса.

2. Анализ запроса.

3. Построение логического плана запроса.

4. Оптимизация логического плана запроса.

5. Построение физического плана запроса.

6. Оптимизация физического плана запроса.

7. Выполнение физического плана запроса.

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

Шаги плана запроса удобно представлять в терминах реляционной алгебры. Реляционная алгебра и ее операторы хорошо изучены, и существует множество известных оптимизаций.

Одной из таких оптимизаций является проталкивание предикатов.

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

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

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

Вот пример:

CREATE TABLE test_table_1 (id UInt64, value String) ENGINE=MergeTree ORDER BY id; CREATE TABLE test_table_2 (id UInt64, value String) ENGINE=MergeTree ORDER BY id;  INSERT INTO test_table_1 SELECT number, number FROM numbers(150000000); INSERT INTO test_table_2 SELECT number, number FROM numbers(150000000);

SELECT * FROM test_table_1 AS lhs  INNER JOIN test_table_2 AS rhs ON lhs.id = rhs.id  WHERE test_table_1.id = 5;   Elapsed: 22.130 sec.  Processed 150.01 million rows, 3.79 GB (6.78 million rows/s., 171.21 MB/s.) Peak memory usage: 18.41 GiB.

Давайте посмотрим на логический план запроса ClickHouse для этого запроса:

EXPLAIN SELECT * FROM test_table_1 AS lhs  INNER JOIN test_table_2 AS rhs ON lhs.id = rhs.id  WHERE test_table_1.id = 5 SETTINGS optimize_move_to_prewhere = 0  ┌─explain──────────────────────────────────────────────────────────────────────┐ │ Expression ((Project names + (Projection + )))                               │ │   Join (JOIN FillRightFirst)                                                 │ │     Filter (( + (JOIN actions + Change column names to column identifiers))) │ │       ReadFromMergeTree (default.test_table_1)                               │ │     Expression ((JOIN actions + Change column names to column identifiers))  │ │       ReadFromMergeTree (default.test_table_2)                               │ └──────────────────────────────────────────────────────────────────────────────┘

В этом примере предикат перемещается на ЛЕВУЮ сторону JOIN. Обратите внимание, что я добавил SETTINGS optimize_move_to_prewhere = 0, потому что иначе этот шаг фильтрации был бы преобразован в PREWHERE для левой таблицы.

До ClickHouse 24.4 для JOIN использовалась простая версия оптимизации проталкиванием предикатов. Примечательно, что она не учитывала классы эквивалентности объединенных столбцов (то есть эквивалентные столбцы после выполнения JOIN).

В PR #61216 мы представили более сложный анализ предикатов, который использует классы эквивалентности и может преобразовывать предикаты, применяемые к одной стороне JOIN, в предикаты, которые могут быть применены к другой стороне JOIN. Кроме того, предикат будет разделен на части, и при необходимости только безопасные части будут перенесены вниз.

Рассмотрим пример:

SELECT * FROM test_table_1 AS lhs  INNER JOIN test_table_2 AS rhs ON lhs.id = rhs.id  WHERE test_table_1.id = 5;

В этом примере мы знаем, что столбец id из test_table_1 эквивалентен столбцу id из test_table_2, и мы можем преобразовать предикат test_table_1.id = 5 в test_table_2.id = 5 и перенести его в правую таблицу.

Оптимизация путем проталкивания фильтра для разных типов JOIN’ов имеет разную логику:

1. Для INNER JOIN мы можем переносить все предикаты на обе стороны JOIN. Мы также можем преобразовать предикаты, использующие только эквивалентные столбцы, с левой стороны в правую и наоборот.

2. Для LEFT/RIGHT JOIN мы можем перенести условия, использующие только столбцы из таблицы LEFT/RIGHT, на сторону LEFT/RIGHT JOIN. Мы также можем преобразовать предикаты, использующие только эквивалентные столбцы с левой стороны в правую для LEFT JOIN’ов и с правой стороны в левую для RIGHT JOIN’ов.

Давайте посмотрим на план запроса после внедрения этой оптимизации:

EXPLAIN SELECT * FROM test_table_1 AS lhs INNER JOIN test_table_2 AS rhs ON lhs.id = rhs.id WHERE test_table_1.id = 5 SETTINGS optimize_move_to_prewhere = 0  ┌─explain──────────────────────────────────────────────────────────────────────┐ │ Expression ((Project names + (Projection + )))                               │ │   Join (JOIN FillRightFirst)                                                 │ │     Filter (( + (JOIN actions + Change column names to column identifiers))) │ │       ReadFromMergeTree (default.test_table_1)                               │ │     Filter (( + (JOIN actions + Change column names to column identifiers))) │ │       ReadFromMergeTree (default.test_table_2)                               │ └──────────────────────────────────────────────────────────────────────────────┘

Теперь предикат переносится как на левую, так и на правую сторону JOIN’а. Мы также можем увидеть улучшение производительности запросов с INNER, LEFT и RIGHT JOIN на реальных цифрах:

inner join до и после SELECT * FROM test_table_1 AS lhs INNER JOIN test_table_2 AS rhs ON lhs.id = rhs.id WHERE lhs.id = 5  До:  Времени затрачено: 22.130 с Обработано 150.01 млн строк, 3.79 ГБ (6.78 млн строк/с, 171.21 МБ/с) Пиковое использование памяти: 18.41 ГБ  После:  Времени затрачено: 0.005 с Обработано 16.38 тыс. строк, 131.19 КБ (3.21 млн строк/с, 25.73 МБ/с) Пиковое использование памяти: 579.28 КБ

left join до и после SELECT * FROM test_table_1 AS lhs LEFT JOIN test_table_2 AS rhs ON lhs.id = rhs.id WHERE lhs.id = 5;  До:  Времени затрачено: 22.680 с Обработано 150.01 млн строк, 3.79 ГБ (6.61 млн строк/с, 167.06 МБ/с) Пиковое использование памяти: 18.42 ГБ  После:  Времени затрачено: 0.005 с Обработано 16.38 тыс. строк, 131.19 КБ (3.30 млн строк/с, 26,45 МБ/с) Пиковое использование памяти: 579.28 КБ

Вот полные результаты тестов производительности ClickHouse, а ниже вы можете увидеть основные моменты.

Эти изменения повысили скорость работы INNER и LEFT JOIN’ов более чем в 180 раз.

Эта оптимизация дополнительно решает несколько связанных, ранее существовавших проблем в ClickHouse. Вот несколько примеров:

1. #10913

2. #45242

3. #55054

4. #55058

5. #26268

Пул-реквест №2: Автоматическое преобразование OUTER JOIN в INNER JOIN

Мы внесли еще одно изменение, которое позволяет ClickHouse автоматически преобразовывать OUTER JOIN в INNER JOIN, если предикат после JOIN фильтрует все не объединенные строки (non-joined rows) со значениями по умолчанию.

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

Используя таблицу из демонстрации предыдущей оптимизации…

запрос SELECT * FROM test_table_1 AS lhs LEFT JOIN test_table_2 AS rhs ON lhs.id = rhs.id WHERE test_table_2.id = 5   Времени затрачено: 27.680 с Обработано 300.00 млн строк, 7.58 ГБ (10.84 млн строк/с, 273.77 МБ/с) Пиковое использование памяти: 18.46 ГБ

Вот логический план запроса ClickHouse:

план запроса EXPLAIN actions = 1 SELECT * FROM test_table_1 AS lhs  LEFT JOIN test_table_2 AS rhs ON lhs.id = rhs.id  WHERE test_table_2.id = 5   ┌─explain─────────────────────────────────────────────┐ │ Expression ((Project names + Projection))           │ │   Filter ((WHERE + DROP unused columns after JOIN)) │ │     Join (JOIN FillRightFirst)                      │ │     Type: LEFT                                      │ │     Strictness: ALL                                 │ │     Algorithm: HashJoin                             │ │     Clauses: [(__table1.id) = (__table2.id)]        │ │     ...                                             │ └─────────────────────────────────────────────────────┘

Примечание

При actions = 1 мы можем увидеть больше деталей плана запроса, таких как тип JOIN, конкретные действия, которые будут выполнены, и другие детали. Обратите внимание, что я сохранил только ключевую часть плана запроса, чтобы мы могли удостовериться, что это LEFT JOIN.

В этом примере мы знаем, что предикат test_table_2.id = 5 всегда будет фильтровать неохваченные строки из LEFT JOIN со значениями по умолчанию.

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

Для этого мы пытаемся выполнить константное сворачивание предиката, который выполняется после OUTER JOIN, где мы заменяем все столбцы правой/левой стороны для LEFT/RIGHT JOIN на столбцы с константными значениями по умолчанию. Если результатом константного сворачивания предиката является константа False или NULL, мы можем преобразовать OUTER JOIN в INNER JOIN.

Вот план запроса после внедрения этой оптимизации:

план запроса после оптимизации EXPLAIN actions = 1 SELECT * FROM test_table_1 AS lhs LEFT JOIN test_table_2 AS rhs ON lhs.id = rhs.id WHERE test_table_2.id = 5   ┌─explain────────────────────────────────────────┐ │ Expression ((Project names + (Projection + ))) │ │   Join (JOIN FillRightFirst)                   │ │   Type: INNER                                  │ │   Strictness: ALL                              │ │   Algorithm: HashJoin                          │ │   Clauses: [(__table1.id) = (__table2.id)]     │ │   ...                                          │ └────────────────────────────────────────────────┘

Здесь LEFT JOIN уже заменен на INNER JOIN. Мы видим, что шаг Filter сдвинут вниз, потому что для INNER JOIN можно безопасно переместить test_table_2.id = 5 на обе стороны JOIN.

Мы также видим улучшение производительности исходных запросов после применения оптимизации:

производительность до и после SELECT * FROM test_table_1 AS lhs  LEFT JOIN test_table_2 AS rhs ON lhs.id = rhs.id  WHERE test_table_2.id = 5  До:   Времени затрачено: 27.680 с  Обработано 300.00 млн строк, 7.58 ГБ (10.84 млн строк/с, 273.77 МБ/с) Пиковое использование памяти: 18.46 ГБ  После:   Времени затрачено: 0.004 сек.  Обработано 16.38 тыс. строк, 131.19 КБ (3.96 млн строк/с, 31.74 МБ/с) Пиковое использование памяти: 578.27 КБ

В результатах тестирования производительности ClickHouse мы видим огромные улучшения для INNER, LEFT и RIGHT JOIN:

Эти изменения значительно повысили производительность ClickHouse JOIN, в некоторых случаях на несколько порядков.

Заключение

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

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

Всё о работе с ClickHouse (от установки и настройки до продовых решений) можно изучить на курсе «ClickHouse для инженеров и архитекторов БД».

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