Три способа посчитать COUNT(DISTINCT) в ClickHouse

Все замеры — на одном single-host кластере Yandex Managed ClickHouse (c3-c4-m8, 4 vCPU, 8 GB RAM, ClickHouse 25.8.22.28-yc.2). Кластер создаётся под эксперимент и удаляется в конце; общая стоимость вычислений — меньше 200 ₽.

Входные значения генерируются на лету функцией numbers_mt(N), которая возвращает ровно N различных целых без записи на диск. То есть истинное число различных значений известно и равно N по построению — это и есть «правда», с которой мы сравниваем оценки.

Запросы выполняются по нативному протоколу ClickHouse через clickhouse-driver на порту 9440 (TLS), все запросы по одному персистентному соединению. На сторонe Yandex Managed ClickHouse с публичным IP HTTPS-интерфейс (8443) на Windows-клиенте даёт зависания на TLS-renegotiation — для воспроизводимости лучше native TCP.

Каждый запрос — отдельная строка в results/raw.csv со всеми параметрами (функция, N, соль, серверное время, абсолютная и относительная ошибка, число попыток). Сводные таблицы ниже выведены из этих строк.

По одному запросу на каждую пару (N, функция). Фиксируем серверное время (из last_query.elapsed драйвера) и сверяем результат с истинным N — так и виден overflow у uniq() на 10¹¹. uniqExact запускался только до N=10⁹, где сервер уже отдаёт OOM-ошибку и закрывает соединение.

SELECT uniq(number)            FROM numbers_mt(N);
SELECT uniqCombined64(number)  FROM numbers_mt(N);
SELECT uniqExact(number)       FROM numbers_mt(N);

scripts/run-experiment.py — единый Python-скрипт всего прогона. results/raw.csv — все строки (фильтр experiment=A_unsalted для этой таблицы, experiment=A_exact для uniqExact).

Чтобы получить распределение ошибки, оборачиваем вход в солёный хеш: uniq(cityHash64(number, salt)) с salt = 1…m(N). Каждая соль даёт независимую оценку для одной и той же истинной мощности N. По m запускам считаем mean, stderr, квантили.

SELECT uniq(cityHash64(number, 42))           FROM numbers_mt(N);
SELECT uniqCombined64(cityHash64(number, 42)) FROM numbers_mt(N);

m уменьшается с ростом N, чтобы прогон укладывался в разумное время. Для uniq: 100, 100, 100, 100, 100, 30, 5. Для uniqCombined64: 100, 100, 100, 100, 30, 10, 5.

scripts/run-experiment.py — тот же скрипт. results/raw.csv — все строки (фильтр experiment=B_salted).

Алгоритмы внутри разные. uniq — по официальной документации ClickHouse «adaptive sampling», хранит до 65536 сэмплированных hash-значений (KMV-подобный оценщик; документация не называет его K-min-values). Ожидаемый масштаб случайной ошибки грубо порядка 1/√65536 ≈ 0.39% — это эвристическая оценка, а не официальный bound ClickHouse. uniqCombined64 — HyperLogLog с precision=17 по умолчанию (2¹⁷=131072 ячеек) → теоретический stderr ≈ 1.04/√131072 ≈ 0.29%. Поэтому uniqCombined64 «по бумаге» должен быть точнее uniq — и наши данные это подтверждают. uniqHLL12 — отдельная функция, использует HLL12 (2¹²=4096 ячеек) → теоретический stderr ≈ 1.625%, поэтому она и не используется в качестве дефолта.

uniq() возвращает 18 446 743 978 444 128 518 (= 2⁶⁴ − 95 265 423 098) для любого входа. Не зависит ни от хеш-сида, ни от повторного запуска, ни от того, прехешируем ли мы вход. Похоже на overflow беззнакового счётчика при слиянии партиальных состояний агрегации между потоками, которые порождает numbers_mt. Известный баг ClickHouse: issue #6078 «Avoid overflow in aggregate function uniq» (открыт с июля 2019, без фикса на момент замера).

У 32-битных «братьев» — другой режим отказа: они не переполняются, а упираются в потолок. uniqHLL12 и uniqCombined (32-битная версия) выходят на насыщение ~6.2 млрд — это практический потолок 32-битного (2³²) хеш-пространства, когда все ячейки заполнены.

Практический вывод: для колонок, где число различных значений может реально превысить ~10⁹, безопасный выбор по умолчанию — uniqCombined64(). Все 32-битные оценщики начинают врать выше миллиарда, но только uniq ломается катастрофически и молча.