koanse Mar 30 at 19:56

Кардинальность при оптимизации DAX запросов в ClickHouse

7 min

1.6K

Visiology corporate blogSQL*Big Data*Data visualization*

Case

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

Сегодня мы поговорим о применении группировок GROUP BY с учетом их производительности для относительно больших таблиц, например, с миллионами записей. Таким образом, речь пойдет об оценке кардинальности одного или нескольких столбцов. Эта задача, кстати, является достаточно нетривиальной. Но если Вы можете ее решить, появляется возможность для эффективных оптимизаций SQL. О них мы и поговорим сегодня.

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

Существуют две формулы расчета кардинальности, которые применяются в базах данных.

1. Кардинальность поля в смысле теории множеств как мощность множества (или кардинальное число), количество уникальных записей в поле

2. Кардинальность в смысле баз данных как отношение количества уникальных записей в поле M к общему количеству записей N в таблице: .

Также под кардинальностью в базах данных часто понимается тип связи:

один ко многим,
один к одному,
многие ко многим.

По мотивам теории множеств

Первое определение через кардинальное число в каких-то случаях полезно. Например, при выводе данных через UI нужно знать, что у нас всего 10 уникальных записей, и они легко поместятся в дропдаун. Однако для случая оптимизации запросов характеризовать кардинальность через кардинальное число без учета общего количества записей в таблице будет неинформативно.

Например, кардинальность поля по кардинальному числу равна 1 000 000. Для 1 000 000 записей в таблице это поле с высокой кардинальностью. Для таблицы с 1 000 000 000 записями это поле «в 1000 раз менее уникально» по сравнению с полем первичного ключа с 1 000 000 000 уникальными записями, и при оптимизации запросов поле с 1 000 000 можно считать низкокардинальным для таблицы с 1 000 000 000 записями.

Соответственно, поэтому далее рассматривается второе определение кардинальности, поскольку кардинальность поля или нескольких полей рассматривается применительно к оптимизации запросов.

Кардинальность в смысле базы данных

Какое значение кардинальности является желаемым, чтобы добавление GROUP BY снижало время выполнения запроса? Это зависит от СУБД, но в общем и целом можно принять порог низкой кардинальности, например, 0.1, т.е. при значении кардинальности для поля (полей) от 0 до 0.1 такое поле (поля) является низкокардинальным и добавление такого поля (полей) в GROUP BY снизит время выполнения запроса. Конечно, 0.1 можно считать параметром и менять при необходимости в зависимости от тех данных, с которыми Вы имеете дело.

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

Для иллюстрации рассмотрим пример запроса для двух таблиц: sales c 1 млн записей и customer тоже с 1 млн записей

CREATE OR REPLACE TABLE sales
(
    order_number Int64,
    amount       Float64,
    order_date   Date,
    product_id   Int64,
    customer_id  Int64
) ENGINE = Log;

INSERT INTO sales
SELECT toString(1000000000 + number) AS order_number,
       number % 100                  AS amount,
       dateAdd(number % 700, toDate('2023-01-01')),
       number % 8 + 1                AS product_id,
       number % 20000 + 1                AS customer_id
FROM system.numbers
LIMIT 1000000;

CREATE OR REPLACE TABLE customer
(
    customer_id   Int64,
    customer_name String
) ENGINE = Log;

INSERT INTO customer
SELECT number % 20000 + 1                 AS customer_id,
       'Customer #' || number % 20000 + 1 AS customer_name
FROM system.numbers
LIMIT 1000000;

Случай 1. Низкая кардинальность = можно добавить GROUP BY

Рассмотрим запрос с примером повышения производительности на примере поля customer_id, кардинальность которого равна 20000/1000000 = 0.02 < 0.1 — низкая. Рассмотрим исходный запрос, выполняющийся около 600 мс:

-- 600 мс
SELECT customer_id, SUM(amount)
FROM sales
         INNER JOIN customer ON sales.customer_id = customer.customer_id
GROUP BY customer_id;

Из-за низкой кардинальности customer_id дополнительная группировка по customer_id во FROM оптимизирует запрос и снижает время выполнения до 400 мс:

-- 400 мс
SELECT customer_id, SUM(sumAmount)
FROM (SELECT customer_id, SUM(amount) sumAmount FROM sales GROUP BY customer_id) AS sales
         INNER JOIN customer ON sales.customer_id = customer.customer_id
GROUP BY customer_id;

Случай 2. Высокая кардинальность = нельзя добавить GROUP BY

Рассмотрим запрос с примером снижения производительности при добавлении GROUP BY. Для этого возьмем аналогичный запрос, но с высококардинальным (и даже уникальным) полем order_number. Исходный запрос выполняется примерно за 800 мс:

-- 800 мс
SELECT order_number, SUM(amount)
FROM sales
         INNER JOIN customer ON sales.customer_id = customer.customer_id
GROUP BY order_number;

Если применить аналогичные изменения (как в случае 1), но для высококардинальной колонки order_number, получим деградацию производительности и запрос станет выполняться за 1200 мс:

-- 1200 мс
SELECT order_number, SUM(sumAmount)
FROM (SELECT order_number, customer_id, SUM(amount) sumAmount
      FROM sales
      GROUP BY customer_id, order_number) AS sales
         INNER JOIN customer ON sales.customer_id = customer.customer_id
GROUP BY order_number;

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

Также стоит отметить, что кардинальность для большого количества столбцов высокая, также при увеличении количества столбцов кардинальность стремится к 1 (при условии, что в таблице нет дубликатов).

Поэтому кардинальность нескольких колонок можно рассчитать точно только дополнительной обработкой исходных данных (например, SQL запросами с DISTINCT).

Без дополнительных подсчетов на исходных данных и без SQL запросов тоже можно успешно оценить кардинальность, но не в общем случае, а в частных (что также полезно для оптимизации запросов). И таким образом Вы найдете только низкую кардинальность, которая, впрочем, как раз представляет интерес для оптимизации.

Частные случаи могут быть, например, следующими:

Мало уникальных значений в поле (например, булево значение 0 и 1, год с кардинальностью 1/365, месяц с кардинальностью 1/30).
Высокий коэффициент корреляции (близок к 1 или -1, например, 0.99) — для полей-«дубликатов» с «почти одинаковыми» данными, для линейных зависимостей (например, год в формате YY и YYYY — зависимость вида YYYY = 2000 + YY). Также это справедливо не только для случая парной корреляции, но и для множественной, например, для связи итоговой цены с НДС Price Total, размера НДС VAT Amount и цены без НДС Price, т.е. для Price Total = VAT Amount + Price.

Оценка кардинальности

Но при этом остается общий вопрос: как же оценить низкую кардинальность для заданного набора полей таблицы column₁, column₂, ..., column_n без дополнительных запросов к СУБД, и с учетом возможных корреляционных связей?

Для этого мы периодически рассчитываем корреляционную матрицу с коэффициентами парной корреляции для полей таблицы (например, в ClickHouse на основе corrMatrix). Также периодически рассчитываем приближенные значения количества уникальных записей для каждого поля column₁, column₂, ..., column_n в таблице (например, одной из функций uniq в ClickHouse, т.е., например, uniq(column1) и т.д.), обозначим их как uniq₁, uniq₂, ..., uniq_n.

Проверка, что вместе поля column₁, column₂, ..., column_n обладают низкой кардинальностью, может включать следующие шаги.

Проверить, что у всех полей низкая кардинальность и соответствует порогу 0.1, если хотя бы у одного поля — нет, то кардинальность всех полей не является низкой и прекращаем анализ.
Отсеять колонки с коэффициентами корреляции, близкими к 1 или -1 (парной корреляции и множественной) по порогу, например, 0.99, т.е. для парной корреляции — убрать одну из двух линейно зависимых колонок, для множественной корреляции — убрать все зависимые колонки, кроме одной (например, оставить одну из трех). Получим в итоге column₁, column₂, ..., column_m, причем m ≤ n.
Наконец, оценить кардинальность оставшихся колонок после удаления «дубликатов» (в смысле линейно зависимых колонок) с учетом негативного сценария (который, например, соответствует разобранному выше случаю 1), т.е. максимальной кардинальности оставшихся столбцов:
$\frac{uniq_1\cdot uniq_2\cdot ...\cdot uniq_m}{\text{количество записей в таблице}}$
Далее полученное значение сравнить с порогом низкой кардинальности 0.1.

В качестве примера можно рассчитать кардинальность колонок месяц и год для записей за 365 дней одного года: 1 ⋅ 12 / 365 = 0.03 < 01 — низкая кардинальность

Видно, что можно ещё добавить в GROUP BY столбец с полугодием, и всё ещё будет низкая кардинальность 0.03 ⋅ 2 = 0.06 < 0.1, или столбец-«дубликат» с высокой корреляцией - например, «дубликаты»-годы в разных форматах YY и YYYY — линейная зависимость между YYYY и YY: YYYY = 2000 + YY.

Также можно привести пример для месяца и номера недели, где нарушается порог низкой кардинальности: 12 ⋅ 52 / 365 = 1.7 > 0.1

Также стоит отметить особенности фильтрации колонок для расчета кардинальности на основе коэффициента множественной корреляции.

Для связей трех колонок он рассчитывается по формуле:

$r_{yx1x2}=\sqrt{\frac{r_{x1y}^{2} + r_{x2y}^{2} - 2 \cdot r_{x1y} \cdot r_{x2y} \cdot r_{x1x2}}{1 - r_{x1x2} ^{2}}}$

В общем случае он рассчитывается на основе матрицы парных коэффициентов корреляции вида:

$R=\begin{bmatrix} 1 & r_{x1x2} & r_{x1x3} & ... & r_{x1xn} \\ r_{x1x2} & 1 & r_{x2x3} & ... & r_{x2xn} \\ r_{x1x3} & r_{x2x3} & 1 & ... & r_{x3xn} \\ ... & ... & ... & ... & ... \\ r_{x1xn} & r_{x2xn} & r_{x3xn} & ... & 1 \end{bmatrix}$

Коэффициент множественной корреляции рассчитывается на основе определителя корреляционной матрицы и алгебраического дополнения R11 элемента первого элемента этой матрицы:

$r_{x1x2x3...xn}=\sqrt{1-\frac{\left| R \right|}{R_{11}}}$

Сам расчет коэффициента корреляции (парной или множественной) больших трудностей не представляет, но сложности могут возникнуть с оценкой кардинальности для относительно большого количества полей в таблице и для малого количества связанных полей в множественной корреляции (например, 3).

Так, для 10 полей и оценки множественной корреляции между 3 полями количество комбинаций трех колонок будет равно числу сочетаний из 10 по 3:

$\mathrm{C}_{10}^{3}=\frac{10!}{3!\cdot (10-3)!}=120$

Таким образом, поиск связи 3 полей среди 10 полей «в лоб» подразумевает 120 расчетов коэффициента множественной корреляции для нахождения возможной комбинации из 3 линейно зависимых колонок, что имеет смысл учитывать с точки зрения производительности.

Считать кардинальность полезно!

Кстати, учет кардинальности требуется не только для GROUP BY обычных функций агрегации, но также и для комбинаторов, например, minState / minMerge и их производных (minStateMerge), т.к. для комбинаторов справедливы те же оптимизации кардинальности GROUP BY, как и для обычных функций агрегации. Об этом Вы можете почитать здесь.

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

Желаю быстрых запросов, успешных дашбордов :-)

Tags:

Hubs: