koanse 7 часов назад

Оценка кардинальности полей таблицы

6 мин

494

Кейс

Привет, Хабр! В SQL запросах важно ориентироваться в количестве записей в таблицах и в плане выполнения запроса. Это позволяет, например, уменьшить количество записей при выполнении запроса при помощи группировки GROUP BY. В случае работы над каждым SQL запросом вручную, это можно проверить в среде разработки. Но в случае генерации SQL запросов автоматически появляется задача проверки количества уникальных записей для одного или нескольких полей таблицы, иными словами, кардинальности. В частном случае, при наличии сильных линейных связей между полями таблицы или даже "полей-дубликатов", количество уникальных записей в двух полях практически равно количеству уникальных записей в одном поле, т.е. кардинальность двух линейно зависимых полей таблицы практически равна кардинальности одного поля. В связи с этим актуально применение коэффициентов парной и множественной корреляции при расчете кардинальности нескольких полей. Интересны статистические методы при расчете кардинальности? Добро пожаловать :)

Вначале определимся с тем, как измеряется кардинальность, и какая она нужна.

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

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

Теперь, после того, как количественно определена кардинальность и её желаемое значение, удобно рассмотреть расчет кардинальности на примере двух случаев. Будем рассматривать в качестве "первого поля таблицы" разряд десятков двузначного числа (т.е., например, 1 из числа 12), в качестве "второго поля таблицы" разряд единиц двузначного числа (т.е., например, 2 из числа 12). Будем считать, что порог низкой кардинальности 0.1, и рассмотрим 100 записей (т.е. "количество записей в таблице" будет 100).

Случай 1 - максимальная кардинальность

100 комбинаций:
00
01
02
03
..
98
99

Кардинальность разряда десятков: 0.1 (соответствует порогу 0.1), кардинальность разряда единиц: 0.1 (соответствует порогу 0.1), кардинальность двух разрядов: 100 / 100 = 1 (вне порога 0.1).

При расчете кардинальности двух разрядов можно вспомнить размещения с повторениями из комбинаторики, а именно, размещения с повторениями из n по k:

$\mathrm{\overline{A}}_{n}^{k}={n}^{k}$

В нашем случае для 2 разрядов и 10 цифр количество рамещений из 10 по 2 с повторениями будут:

$\mathrm{\overline{A}}_{10}^{2}={10}^{2}=100$

Таким образом, лишний раз можно убедиться с точки зрения комбинаторики, что даже при соблюдении кардинальности 0.1 для разрядов десятков и единиц по отдельности, на представленных данных количество уникальных значений двузначных чисел максимально и равно 100, поэтому кардинальность двух разрядов равна 1.

Случай 2 - минимальная кардинальность

100 комбинаций:
00 (10 раз 00)
00
00
00
00
00
00
00
00
00
11 (10 раз 11)
11
..

99 (10 раз 99)
99

Кардинальность разряда десятков: 0.1 (соответствует порогу 0.1), кардинальность разряда единиц: 0.1 (соответствует порогу 0.1), кардинальность двух разрядов: 10 / 100 = 0.1 (соответствует порогу 0.1).

Здесь видно, что разряды десятков и единиц дублируются, есть линейная зависимость, коэффициент корреляции равен 1.

Соответственно, кардинальность двух разрядов равна кардинальности одного разряда.

Можно отметить, что в обоих случаях кардинальности разряда десятков и единиц по отдельности равны 0.1 и соответствуют порогу низкой кардинальности, однако кардинальность двузначных чисел изменяется от 0.1 (кардинальность одного разряда) во втором случае до 1 (максимально возможная кардинальность) в первом случае.

К слову, погрешность кардинальности для двух разрядов при сравнении случая 1 со случаем 2 составляет целых 1 / 0.1 = 10 = 1000%.

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

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

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

Без дополнительных подсчетов на исходных данных и без 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.

В итоге, как оценить кардинальность для заданного набора полей таблицы column1, column2, column3, ..., columnn без дополнительных запросов к СУБД, и с учетом возможных корреляционных связей?

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

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

Проверить, что у всех полей низкая кардинальность и соотвествует порогу 0.1, если хотя бы у одного поля - нет, то кардинальность всех полей не является низкой и прекращаем анализ.
Отсеять колонки с коэффициентами корреляции, близкими к 1 или -1 (парной корреляции и множественной) по порогу, например, 0.99, т.е. для парной корреляции - убрать одну из двух линейно зависимых колонок, для множественной корреляции - убрать все зависимые колонки, кроме одной (например, оставить одну из трех). Получим в итоге column₁, 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 < 0.1 - низкая кардинальность

Видно, что можно ещё добавить в 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}$

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

$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 линейно зависимых колонок, что имеет смысл учитывать с точки зрения производительности.

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

Теги:

Хабы:

Оценка кардинальности полей таблицы

Случай 1 - максимальная кардинальность

Случай 2 - минимальная кардинальность

Публикации

Истории

Работа

Ближайшие события