Меньше JOIN’ов — больше скорость! Или несколько примеров оптимизаций DAX и SQL

Все мы любим ClickHouse, но прекрасно знаем, что у этой СУБД есть свои особенности и ограничения. В этой статье мы поговорим о том, почему нужно избавляться от лишних операторов JOIN, если вы работаете с большими нагрузками, а также оценим, какой эффект дает исключение JOINов, поднятие их на уровень выше, перестановка таблиц местами и некоторые другие хитрые трюки на уровне кода SQL. Всех, кто работает с ClickHouse, а также тех, кто не хочет работать с ClickHouse, но подумывает получить все готовенькое от Visiology, приглашаю под кат!

Привет, дорогой читатель! Меня зовут Руслан Халиуллин, я работаю в команде разработки аналитического движка Visiology 3 ДанКо. На летней конференции HighLoad++ наш архитектор Никита Ильин уже рассказывал о движке, модели данных и применяемых оптимизациях. И сегодня мы подробнее поговорим о том, как происходит процесс работы с ClickHouse “под капотом”, когда пользователи видят красивый DAX и получают быстрые результаты. 

При всей нашей искренней любви к ClickHouse, которая естественна для всех российских вендоров BI, на самом деле весь секрет высокой производительности и удобства Visiology 3 заключается не в самом ClickHouse, а в том, что “над ним”. Весь секрет — в ДанКо. Это наш движок, который основывается на базе ClickHouse 23.3.4.17 для хранения данных и выполнения пользовательских запросов и PostgreSQL 15 для работы с метаданными.

Основные задачи, которые решает наш движок:

- загрузка данных из разных источников

- управление метаданными TOM (Tabular Object Model)

- управление доступом к данным (RLS)

- обеспечение масштабируемости и отказоустойчивости движка

- поддержка выполнения DAX (такого же как в PowerBI).

Последний пункт, хоть и не является единственной “обязанностью” ДанКо, но обычно вызывает наибольший интерес. Если разобрать работу с DAX по этапам, то она будет выглядеть следующим образом:

1. Клиент отправляет DAX-запрос

2. Строится дерево DAX

3. Применяется алгоритм преобразования DAX в SQL

4. Оптимизатор SQL улучшает запрос

5. Запрос выполняется в ClickHouse

6. Результат передается клиенту

ДанКо-магия

И тут я предлагаю обратить пристальное внимание на “пункт №4”. Оптимизация очень важна! И если кто-то думает, что можно легко передать любой запрос в ClickHouse в виде SQL…то он, конечно прав. Но для этого существует миллион способов. Как уже писал мой коллега Антон Кондауров, можно сгенерировать и послать  огромные многоуровневые SQL-запросы. Отправить такой запрос в ClickHouse напрямую возможно, но это может привести к нежелательным последствиям:

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

Конечно, нам хотелось бы сразу построить оптимальный SQL, чтобы для каждого оператора DAX была своя выверенная рабочая схема. Однако на практике такой подход оказался неэффективным. В первой версии нашего алгоритма, зашитого в движок ДанКо, мы уже пробовали применить такой подход. И изначально разработка шла хорошо, а поддержка функций без многоуровневых вложенностей развивалась достаточно быстро. Например, первая версия движка уже поддерживала подобную формулу:

EVALUATE
SUMMARIZECOLUMNS (
	'product'[classname],
	'product'[colorname],
	"result",
    	CALCULATE (
        	SUM ( 'facts'[unitprice] ),
        	REMOVEFILTERS ( 'product' ),
        	SUMMARIZE ( 'product', 'product'[classname] ),
        	FILTER ( 'product', 'product'[classname] IN { "Economy" } )
    	)
)

Такой запрос возвращает таблицу, где для каждого класса и цвета товара отображается сумма цен по товарам класса 'Economy', при этом игнорируются любые другие фильтры, наложенные на таблицу 'product'.

Но по мере усложнения задач выяснилось, что для реальной работы нужен не выверенный алгоритм, а методы оптимизации, которые помогают адаптироваться к разным ситуациям. Помню, как мы столкнулись с проблемой, когда продуктовая команда поставила задачу реализовать поддержку сценариев накопленного итога (Year-to-Date, YTD). 

То есть запрос выглядел примерно так:

EVALUATE
SUMMARIZECOLUMNS (
    ‘date’[year],
    'date'[month],
    "Sales",
        CALCULATE (
            SUM ( 'facts'[unitprice] ),
            FILTER (
                ALL ( ‘date’ ),
                AND(
                    ‘date’[datekey] >= DATE(YEAR(MAXX(‘date’, ‘date’[datekey])), 1, 1),
                    ‘date’[datekey] <= MAXX ( ‘date’, ‘date’[datekey] )
                )
            )
        )
)

С этого момента мы поняли, что пора заняться существенной переработкой функционала. Дело было в том, что код, написанный "на if-чиках" стало очень тяжело нести дальше.. Да, при этом строился сразу максимально простой и оптимальный SQL - сопровождение такого решения была крайне ресурсоемкой. Чтобы добавить новый функционал нужно было перерабатывать очень много кода. Также в случае возникновения багов возникали бы сложности с поддержки.

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

Оптимизации движка

Итак, много месяцев назад мы пошли путем оптимизаций движка и достигли хороших результатов. Например, в последнем релизе Visiology 3.10 удалось повысить скорость доступа к данным до 13 раз по сравнению с 3.9! Паттерн Visitor, который мы используем для разработки оптимизаций, позволяет обрабатывать различные элементы дерева SQL-запросов. На момент написания статьи у нас уже реализовано несколько десятков SQL-оптимизаций, среди которых rule-based и эвристические подходы, учитывающие специфику работы ClickHouse.

Удаление избыточных JOIN

Один из самых полезных классов оптимизаций SQL в Visiology 3 — это борьба с операторами JOIN, которые очень не любит СУБД ClickHouse. Избыточные JOIN могут генерироваться в процессе работы алгоритма преобразования DAX в SQL. И если мы избавляемся от них, то делаем наш движок быстрее. В качестве примера для оптимизации рассмотрим простой кейс: сумма продаж товаров в разбиение по брендам.

Примерный DAX будет выглядеть следующим образом:

EVALUATE SUMMARIZECOLUMNS(
‘products’[brandname],
“Result”,
SUM(‘facts’[unitprice])
)

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

'product'[colorname] IN {"Red","Blue"}

На самом деле здесь приведен сильно упрощенный DAX.

DEFINE
    VAR __DS0Core =
        SUMMARIZECOLUMNS (
            'product'[brandname],
            "unitprice", SUM ( 'facts'[unitprice] )
        )

EVALUATE
TOPN ( 3000, __DS0Core, 'product'[brandname], ASC, [unitprice], ASC )
ORDER BY
    'product'[brandname] ASC,
    [unitprice] ASC

В результате получим следующее:

В процессе преобразования DAX -> SQL сгенерируется следующий фрагмент SQL:

SELECT
  `grouping_table_0`.`brandname` AS `brandname`,
  SUM(`main_table`.`salesamount`) AS `scalar_result`
FROM `factonlinesales` AS `main_table`
       INNER JOIN `dimproduct` AS `join_table_0`
                  ON `main_table`.`productkey` =
                     `join_table_0`.`productkey`
       INNER JOIN (SELECT brandname, productkey
                   FROM `dimproduct`
                   WHERE colorname IN ('Red', 'Blue')) AS `grouping_table_0`
                  ON `main_table`.`productkey` =
                     `grouping_table_0`.`productkey`
GROUP BY `grouping_table_0`.`brandname`

-- Elapsed: 1.061 sec. Processed 200.01 million rows, 3.60 GB (188.43 million rows/s., 3.39 GB/s.)

Если присмотреться к коду, становится видно, что у нас имеется два INNER JOIN причем на одну и ту же таблицу, и по тому одному и тому же условию. Но информация о связях хранится в модели данных (признак ключевого поля), а модель данных Visiology аналогична PowerBI (Tabular Object Model)

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

SELECT `join_table_0`.`brandname` AS `brandname`,
     SUM(`main_table`.`salesamount`) AS `scalar_result`
FROM `factonlinesales` AS `main_table`
       INNER JOIN (SELECT brandname, productkey
                   FROM `dimproduct`
                   WHERE colorname IN ('Red', 'Blue')) AS `join_table_0`
                  ON `main_table`.`productkey` =
                     `join_table_0`.`productkey`
GROUP BY `join_table_0`.`brandname`

-- Elapsed: 0.508 sec. Processed 200.00 million rows, 3.60 GB (393.72 million rows/s., 7.09 GB/s.)

Время выполнения такого SQL уже практически в 2 раза меньше, чем у  неоптимизированного!

Перенос CROSS JOIN на уровень выше (CROSS JOIN lift up)

Еще одна оптимизация, направленная на “зачистку” JOIN’ов. Ее суть заключается в том, что агрегирование большего объема данных в неоптимизированном запросе не дает преимуществ, и подзапрос в CROSS JOIN можно поднять на уровень выше, что не влияет на результат агрегации, но значительно уменьшает количество обрабатываемых данных.

Пример запроса до оптимизации:

SELECT
  brandname AS brandname,
  gender AS gender,
  sum(unitprice) AS scalar_result
FROM
(
  SELECT
      grid_grouping_table_0.brandname_IntKey AS brandname,
      grouping_table_0.dimcustomer_gender_IntKey AS gender,
      tableRef.unitprice AS unitprice
  FROM `factonlinesales` AS tableRef
  INNER JOIN `dimcustomer` AS grouping_table_0 ON tableRef.customerkey = grouping_table_0.dimcustomer_customerkey
  CROSS JOIN
  (
      SELECT grouping_table_0.brandname_IntKey AS brandname_IntKey
      FROM `dimproduct` AS grouping_table_0
      GROUP BY grouping_table_0.brandname_IntKey
  ) AS grid_grouping_table_0
) AS expression_result
GROUP BY
  brandname,
  gender

-- Elapsed: 6.209 sec. Processed 205.00 million rows, 4.03 GB (33.02 million rows/s., 648.27 MB/s.)

Пример запроса после оптимизации:

SELECT
  grid_grouping_table_0.brandname_IntKey AS brandname,
  gender AS gender,
  scalar_result AS scalar_result
FROM
(
  SELECT
      gender AS gender,
      sum(unitprice) AS scalar_result
  FROM
  (
      SELECT
          grouping_table_0.dimcustomer_gender_IntKey AS gender,
          tableRef.unitprice AS unitprice
      FROM `factonlinesales` AS tableRef
      INNER JOIN `dimcustomer` AS grouping_table_0 ON tableRef.customerkey = grouping_table_0.dimcustomer_customerkey
  ) AS expression_result
  GROUP BY gender
) AS q1
CROSS JOIN
(
  SELECT grouping_table_0.brandname_IntKey AS brandname_IntKey
  FROM `dimproduct` AS grouping_table_0
  GROUP BY grouping_table_0.brandname_IntKey
) AS grid_grouping_table_0

-- Elapsed: 2.528 sec. Processed 205.00 million rows, 4.03 GB (81.10 million rows/s., 1.59 GB/s.)

Как видно, после оптимизации время выполнения запроса сократилось более чем в два раза.

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

1b92661c477a :) set send_logs_level='trace'

Полный trace-log нам не нужен, и сегодня в статье далее ограничимся лишь...

ClickHouse запустил параллельный процесс выполнения агрегации после оптимизации на 16 потоков. При этом если до оптимизации в каждом потоке было по 135  млн строк, то после оптимизации стало по 12 млн. Хорошее сокращение!

Разворачиваем таблицу в подзапрос (для включения ClickHouse оптимизации с PREWHERE)

Оператор PREWHERE в ClickHouse ограничивает количество прочитанных данных до того, как будут прочитаны ненужные для фильтрации столбцы. Иными словами сначала применяется фильтрация на уровне минимального набора столбцов и только после этого считаются остальные столбцы, участвующие в запросе. 

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

Рассмотрим пример запроса до применения оптимизации:

SELECT
   dimproduct.classname AS classname,
   sum(factonlinesales.unitprice) AS scalar_result
FROM `factonlinesales` AS factonlinesales
INNER JOIN `dimproduct` AS dimproduct ON dimproduct.productkey = factonlinesales.productkey
INNER JOIN `dimcustomer` AS dimcustomer ON dimcustomer.customerkey = factonlinesales.customerkey
WHERE (dimcustomer.gender = 'F') AND (dimproduct.brandname = 'Contoso')
GROUP BY dimproduct.classname

-- Elapsed: 4.421 sec. Processed 205.00 million rows, 4.47 GB (46.37 million rows/s., 1.01 GB/s.)

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

Теперь применим оптимизацию и посмотрим что изменится:

SELECT
   dimproduct.classname AS classname,
   sum(factonlinesales.unitprice) AS scalar_result
FROM `factonlinesales` AS factonlinesales
INNER JOIN
(
   SELECT
       transformedTableToSubQuery.brandname AS brandname,
       transformedTableToSubQuery.classname AS classname,
       transformedTableToSubQuery.productkey AS productkey
   FROM `dimproduct` AS transformedTableToSubQuery
) AS dimproduct ON dimproduct.productkey = factonlinesales.productkey
INNER JOIN
(
   SELECT
       transformedTableToSubQuery.gender AS gender,
       transformedTableToSubQuery.customerkey AS customerkey
   FROM `dimcustomer` AS transformedTableToSubQuery
) AS dimcustomer ON dimcustomer.customerkey = factonlinesales.customerkey
WHERE (dimproduct.brandname = 'Contoso') AND (dimcustomer.gender = 'F')
GROUP BY dimproduct.classname

-- Elapsed: 1.725 sec. Processed 202.49 million rows, 4.44 GB (117.41 million rows/s., 2.57 GB/s.

В случае первого запроса видим:

[a2a868d5d579] 2024.09.05 12:24:32.198817 [ 48 ] {c455f7a5-39de-4041-877a-cb4c5e25e403} <Debug> QueryPlanOptimizations: Pushed down filter equals(brandname, 'Contoso') to the Left side of join

Но строк все равно было прочитало суммарно: 202.49 million rows

Теперь смотрим трассировку оптимизированного запроса и видим что-то новенькое:

[a2a868d5d579] 2024.09.05 12:25:15.522413 [ 48 ] {9612130d-7464-439d-938e-df7be2451174} <Trace> MergeTreeBaseSelectProcessor: PREWHERE condition was split into 1 steps: "equals(brandname, 'Contoso')"

Благодаря такой трансформации запроса нам удалось включить дополнительную оптимизацию со стороны ClickHouse.

Перенос местами таблиц при JOIN

Если нужно JOINить две таблицы друг с другом, нужно сначала подумать, кого на ком JOINить. :) Такая особенность связана с тем, что ClickHouse поднимает в памяти хэш-таблицу. Т.е. чем больше строк в таблице справа (которая присоединяется), тем больше оперативной памяти будет занято.

Эта проблема уже описана в документации:

Currently, ClickHouse does not reorder joins. Always ensure the smallest table is on the right-hand side of the Join. This will be held in memory for most join algorithms and will ensure the lowest memory overhead for the query.

Итак, что мы можем сделать? Поменяем таблицы местами. И наш пример до оптимизации выглядит так:

SELECT sum(t2.unitprice)
FROM (SELECT brandname, productkey
    FROM `dimproduct`
    WHERE brandname IN ('Contoso')
) AS t1
LEFT OUTER JOIN `factonlinesales` AS t2 ON t1.productkey = t2.productkey
GROUP BY brandname

-- Elapsed: 12.765 sec. Processed 200.00 million rows, 3.60 GB (15.67 million rows/s., 282.03 MB/s.)

В трассировочных логах видим, что пик использования оперативной памяти составил 10Гб.

[1b92661c477a] 2024.09.06 08:10:26.049867 [ 49 ] {c5431d66-1324-43cc-b35e-24bf75f1d476} <Debug> MemoryTracker: Peak memory usage (for query): 10.01 GiB.

А после оптимизации он выглядит вот так:

SELECT sum(t2.unitprice)
FROM `factonlinesales` AS t2
RIGHT OUTER JOIN (
  SELECT brandname, productkey
  FROM `dimproduct`
  WHERE brandname IN ('Contoso')
) AS t1 ON t1.productkey = t2.productkey
GROUP BY brandname

-- Elapsed: 0.871 sec. Processed 200.00 million rows, 3.60 GB (229.73 million rows/s., 4.14 GB/s.)

Картина изменилась:

[1b92661c477a] 2024.09.06 08:11:08.319432 [ 49 ] {7446d3e1-3beb-445a-9b89-46563327c465} <Debug> MemoryTracker: Peak memory usage (for query): 26.29 MiB.

Оптимизация на уровне DAX-дерева

Как следует из названия, эта оптимизация применяется на этапе построения DAX-дерева, перед генерацией окончательного SQL-запроса. Ранее я упомянул, что алгоритмы могут генерировать многоуровневые SQL-запросы, где каждая DAX-функция превращается в отдельный подзапрос. Чтобы уменьшить сложность и повысить эффективность обработки запросов, мы реализовали оптимизации, которые сокращают SQL до более простого вида уже на этапе генерации, вместо того чтобы полагаться только на последующую SQL-оптимизацию.

Пример типичного DAX-выражения для фильтрации данных по диапазону дат:

FILTER (
  ‘date’ ,
  AND(
     ‘date’[datekey] >= DATE(2021,1,1)
     ‘date’[datekey] <= DATE(2022,12,31)
  )
)

Без оптимизаций, это выражение может быть преобразовано в несколько вложенных подзапросов, как в примере ниже:

SELECT l.datekey
FROM
  (SELECT datekey
   FROM `dimdate`
   WHERE `datekey` >= toDate(concat(toString(2021), '-', toString(1), '-', toString(1)))
  ) AS l
JOIN
  (SELECT datekey
   FROM `dimdate`
   WHERE `datekey` <= toDate(concat(toString(2022), '-', toString(12), '-', toString(31)))
  ) AS r
ON l.datekey = r.datekey

Однако наша оптимизация позволяет избежать ненужных подзапросов и объединений (JOIN), генерируя гораздо более простой SQL-запрос:

SELECT datekey
FROM `dimdate`
WHERE if((`datekey` >= toDate(concat(toString(2021), '-', toString(1), '-', toString(1)))) AND
        (`datekey` <= toDate(concat(toString(2022), '-', toString(12), '-', toString(31)))), true,
        false)

Заключение

В этой статье мы затронули лишь несколько оптимизаций, используемых в аналитическом движке Visiology 3 ДанКо. Эти улучшения позволяют эффективно преобразовывать DAX-выражения в оптимизированные SQL-запросы, снижая нагрузку на базу данных и повышая общую производительность системы, что мы видим фактически от релиза к релизу Visiology 3.

Если вы работаете с ClickHouse как с аналитической СУБД, вы можете самостоятельно реализовать подобные оптимизации при повышении нагрузки, увеличении объемов данных или количества пользователей. Однако практика нашей разработки показала, что все это — большие и трудоемкие задачи. Но зато пользователи Visiology получают десятки уже готовых оптимизаций, которые позволяют движку ДанКо работать с ClickHouse намного быстрее даже при больших объемах данных и сложных запросах.