Привет, Хабр! Существуют разные задачи в IT, многие решаются алгоритмически или условно за счет архитектурных решений. Среди всего многообразия задач также интересны задачи, решаемые с применением статистических методов.

Одной из таких задач является приближенный расчет количества уникальных значений в поле таблицы (или кардинальности). Казалось бы, практическая польза от быстрого расчета количества уникальных значений поля без больших затрат памяти невелика, однако это позволяет, например, построить оптимальный с точки зрения производительности SQL запрос с этим полем, или использовать это поле в UI (например, элемент с бесконечной прокруткой или элемент с поиском при значительном количестве уникальных значений, а не отображение конечного списка) и т.д. Задача может быть эффективно решена в СУБД, обладающей соответствующими инструментами, поэтому будет рассмотрен ClickHouse.

Интересно решение задачи расчета количества уникальных значений столбца в ClickHouse? Добро пожаловать :)

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

В качестве иллюстрации возможностей статистических методов интересно вспомнить, например, ГОСТы, ISO, относящиеся к выборочному контролю качества.

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

Так, в примере из ГОСТ приложения Г.1 Контроль поставщика делается выборочный контроль качества партии часов из 2120 штук. Не вдаваясь в детали, для контроля на стороне поставщика достаточно проверить качество по признаку на выборке из n=239 часов (из всей партии 2120 штук), причем для приемки партии нужно, чтобы количество часов с отклонениями не превышало A=3 с вероятностью приемки P=0,9503 и уровнем несоответствий q_α=0.6%. Иными словами, при A=3 единицах часов с отклонениями в выборке n=239 часов из партии в 2120 штук с вероятностью P=0,9503 можно утверждать, что во всей партии количество бракованных часов будет q_α=0.6%. К слову, в примере приложения Г.2 Контроль потребителя из партии 2120 достаточно проверить n=73 единицы с приемочным числом A=4 для решения о приемке или возврате партии часов с уровнем несоответствий q_β=8,0% и вероятностью не менее 1-β=0.80. Эти примеры показывают, что даже на малых выборках, в несколько раз меньше исследуемой партии, можно успешно решать важные задачи (в данном случае, контроля качества) с заданной точностью и вероятностями.

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

Создается впечатление, что в задаче расчета приближенного количества уникальных элементов в ClickHouse есть смысл использовать условие SAMPLE, чтобы взять, например, 10% строк таблицы при помощи SQL вида FROM table SAMPLE 0.1, оценить наблюдаемое значение некоторого статистического критерия, определить доверительный интервал при заданной вероятности с использованием теоретического значения критерия и т.д.

К счастью, приближенное определение количества уникальных значений в ClickHouse уже реализовано в функции uniqTheta. Стоит отметить, что в ClickHouse есть и другие функции для подсчета уникальных значений, например, uniq, uniqHLL12, но uniqTheta дает результат с точки зрения статистического подхода. Например, для размера таблицы 4096 при доверительной вероятности 0.95 относительная ошибка составляет 3.125%, что приведено в документации и теоретической таблице ошибок, что радует и говорит о статистическом подходе к решению задачи. Причем с ростом размера таблицы относительная ошибка только уменьшается, что видно из таблицы ошибок, что ещё раз подтверждает, что для получения относительно точного результата совершенно нет необходимости просматривать весь миллиард записей таблицы.

Под капотом uniqTheta использует KVM (или k^th Minimum Value).

Схема алгоритма KWM при k=3 с https://datasketches.apache.org/docs/Theta/KMVbetterEst.html

Видно, что используется хеш функция, возвращающее равномерное распределение Uniform Random Hash от 0 до 1. Она рассчитается для всех значений поля таблицы. Полученные хеш значения сортируются. Далее оценку числа уникальных значений получаем через расстояние от 0 до k хеш значений (также приведен пример для k=3 и расстояния d=0.195 - соответствует рисунку):

Относительную погрешность можно взять из таблицы ошибок по количеству строк (Conf: K) и ошибке (#Std Dev: 2).

Также в документации описаны затраты памяти для uniqTheta (41 килобайт).

4096(2^12) 64-bit sketch are used. The size of the state is about 41 KB.

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

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

Надеюсь, погружение в статистические подходы было интересным, удачи в обработке Big Data :)

Подсчет уникальных значений поля в ClickHouse