koanse Oct 20 2024 at 03:19

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

7 min

2.5K

SQL*Data Mining*

Case

Comments 6

sshikov Oct 20 2024 at 08:46

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

На практике это означает фуллскан, а значит в реальных условиях больших таблиц эти идеи могут оказаться неприменимы. Если бы это движок СУБД скажем умел бы вычислять в процессе сбора статистик... замедляя саму процедуру сбора :)

koanse Oct 20 2024 at 16:04

Если рассмотреть

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

то видно, что как раз решается проблема расчета кардинальности набора выбранных полей m

$column_1, column_2, column_3, ..., column_m,m\leqslant n$

за счет оценки кардинальности набора m полей (а не более точного вычисления кардинальности) без дополнительных SQL запросов и на основе существующих значений

Проблема задачи в том, что на примере 10 полей в таблице

$column_1, column_2, column_3, ..., column_{10}$

и количества полей для оценки кардинальности в 3 поля

получаем разное число сочетаний из 10 по 3:

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

Т.е. при проверке кардинальности "в лоб" на основе дополнительных SQL запросов для проверки кардинальности 3 полей из 10 полей таблицы уже потенциально есть 120 вариантов и 120 запросов.

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

Akina Oct 20 2024 at 21:49

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

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

Хотя нет... начните-ка вы просто с точного формулирования определения. Что это вообще такое - кардинальность?

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

Кардинальность отдельных разрядов в строковом представлении целого числового значения? вы серьёзно?

koanse Oct 21 2024 at 03:48

Имеются две формулы расчета кардинальности, которые применяются в СУБД.

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 записями.

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

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

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

т.е. при значении кардинальности для поля (полей) от 0 до 0.1 такое поле (поля) является низкокардинальным и добавление такого поля (полей) в GROUP BY снизит время выполнения запроса

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

Кардинальность отдельных разрядов в строковом представлении целого числового значения? вы серьёзно?

Среди данных для двух полей одной таблицы

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

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

Это словесное описание таблицы такого вида

Кардинальность отдельных разрядов в строковом представлении целого числового значения? вы серьёзно?

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

Пример далее не имеет особого отношения к теме статьи и просто как иллюстрация.

Например, у Пети 5 пальцев, и он хранит их состояние (0 - палец согнут и 1 - палец разогнут) в 5 разных битах одного двоичного числа из 5 бит, каждый бит соответствует одному пальцу (младший бит - мизинец и т.д.). Петя назагибал пальцы 10 раз и получил 10 двоичных чисел: 00000, 11111, 00001, 11111, 00001, 11111, 00001, 11111, 00001, 11111.

Видно, вероятность появления 1 в младшем бите равна 9/10=0.9 (например, Петя после первого разгиба мизинца его сломал и больше не двигал).

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

Также можно посчитать кардинальность состояния каждого пальца Пети и кардинальность каждого бита, соответствующего состоянию пальцу Пети, в смысле отношения кардинального числа к числу записей, и получим 2 / 10 = 0.2.

Далее, если для 10 наблюдений разложить пять бит пальцев Пети по пяти столбцам одной таблицы, то получим реляционного Петю, для которого будут те же самые кардинальности (причем двух видов: в смысле кардинального числа и в смысле отношения кардинального числа к числу записей), как и для побитового Пети, с учетом маппинга пальцев, бит и столбцов :)

Akina Oct 21 2024 at 08:04

Очень жаль, что всё вот это размещено в комментарии, а не вошло в текст статьи. Потому как меняется смысл многих утверждений статьи. Любой читатель домысливает несказанное и неописанное по своему разумению - и в результате вместо вполне приличного текста порой получается ну такая ерунда... Может, имеет смысл переработать статью, добавить отсутствующие уточнения и разъяснения и убрать все недосказанности и умолчания?

koanse Oct 21 2024 at 14:06

Спасибо, да, хорошая идея