koanse 20 окт в 03:19

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

7 мин

1.6K

Кейс

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

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

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

$card\left( A \right)=\left| A \right|=M$

2.Кардинальность в смысле баз данных как отношение количества уникальных записей в поле M к общему количеству записей N в таблице: 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 можно считать параметром и менять при необходимости в зависимости от СУБД.

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

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

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

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

Кардинальность разряда десятков в смысле отношения количества уникальных значений к общему числу записей таблицы: 10 / 100 = 0.1 (соответствует порогу 0.1), кардинальность разряда единиц: 10 / 100 = 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

Кардинальность разряда десятков: 10 / 100 = 0.1 (соответствует порогу 0.1), кардинальность разряда единиц: 10 / 100 = 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 запросами с 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 < 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 - минимальная кардинальность

Публикации

Истории

Работа

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