Эффективный count distinct

Выбор количества уникальных значений за определенный промежуток времени — не очень частая задача. [https://t.onthe.io/ В .io] нам нужно определять количество уникальных пользователей, заходивших на сайт за любой период времени.

Конечно, есть очень простое решение на основе обычного SQL. Достаточно сохранять в простую таблицу уникальные id пользователей и время их входа:

id | time

Тогда решение будет выглядеть так:

SELECT count(distinct(id)) FROM visits WHERE time > :start AND time < :end
Обычная выборка count distinct в Mysql

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

mysql> SELECT count(distinct(id)), count(*) FROM table WHERE time > date_sub(now(), interval 5 day);
+---------------------+----------+
| count(distinct(id)) | count(*) |
+---------------------+----------+
|               62501 |  2551500 |
+---------------------+----------+
1 row in set (1.76 sec)

Очень медленно, и это на 2.5млн записей в таблице

Суммарное количество аудитории, которое мы считаем — около 50 млн человек в сутки, поэтому нас это не устроило.

MySQL и count(distinct)

Mysql не очень хорошо подходит для решения задач. Но попробовать стоило. Чтобы все заработало быстрее, можно сделать несколько оптимизаций.

1. Правильный индекс

Mysql все равно будет сканировать все строки из запроса для определения уникальных id. Колонка времени поможет их существенно сократить. Поэтому она должна идти первой в индексе:

CREATE INDEX time_id ON visits(time, id)

2. Квант времени

В нашем случае минимальный промежуток времени для подсчета значений не может быть меньше дня. Нет смысла сохранять в один день больше, чем одну запись для каждого пользователя. Значит колонку time нужно делать типа date и ставить уникальный индекс:

CREATE UNIQUE INDEX time_id ON visits(time, id)
Колонка time имеет тип date, теперь каждый день будет только одна запись с уникальным id

Vertica и count(distinct)

Эта векторная база данных хорошо оптимизирована под агрегатные выборки. Однако подсчет количества по выбранному промежутку времени работает всего в 2-3 раза быстрее, чем Mysql.

SELECT count(distinct(id)) FROM table WHERE time > now() - interval '5 day';
 count 
-------
 60700
(1 row)

Time: First fetch (1 row): 659.064 ms. All rows formatted: 659.201 ms

Незначительно быстрее, чем Mysql

approximate_count_distinct()

Vertica поддерживает агрегатную функцию approximate_count_distinct(), которая считает количество уникальных значений приблизительно. Она работает на порядок быстрее обычного запроса, однако имеет ошибку около 1%:

SELECT approximate_count_distinct(id) FROM table WHERE time > now() - interval '5 day';

Redis и HyperLogLog

Redis имеет специальное хранилище HyperLogLog. Оно позволяет сохранять туда ключи, а затем получать количество уникальных ключей в этом хранилище. Ограничение в том, что список сохраненных ключей достать невозможно. Преимущество в том, что одно такое хранилище занимает всего 12 Кб, способно сохранять 2⁶⁴ элементов и возвращает результат с погрешностью всего 0.8%.

Устройство HyperLogLog

HyperLogLog — это вероятностный алгоритм для подсчета уникальных элементов.

Принцип алгоритма можно объяснить простым примером из жизни. Представьте, что вы некоторое время подбрасывали монетку, подсчитывая количество непрерывных последовательных выпадений решки. Если у вас получилась последовательность длиной всего в 3 решки подряд, то можно предположить, что вы подбрасывали монетку не очень долго. С другой стороны, если у вас получилось 15, то вероятно вы потратили большую часть дня.

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

HyperLogLog вычисляет хэш каждого нового элемента. Часть этого хэша (в двоичном представлении) используется для индекса регистра (разделяем множество нулей и единиц на m-число подмножеств, наши пары монета+лист бумаги). А другая часть используется для подсчета длины последовательности первых нулей и максимального значения этой последовательности (длина последовательности выпавших решек). Вероятность последовательности из n+1 нулей равна половине вероятности последовательности длиной n.

Поэтому используя значения различных регистров, которые привязаны к максимальным последовательностям нулей для данного подмножества, HyperLogLog способен обеспечить приближенную мощность множества с высокой точностью. Если имеется m-подгрупп и n-элементов, тогда в каждой группе в среднем будет n/m уникальных элементов, а среднее по всем подгруппам дает достаточно точную оценку значения log₂(n/m).

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

В самом простом случае достаточно сохранять все значения в HLL элемент:

$r->pfadd('hll', [1]);
echo $r->pfcount('hll');

Функция pfcount вернет количество уникальных значений в ключике hll, увидим 1

Тут мы сохранили в ключ “hll” 1 элемент (число 1) и вывели количество уникальных элементов. Добавим еще парочку элементов в этот же ключик:

$r->pfadd('hll', [1, 2, 3, 1, 1, 2]);
echo $r->pfcount('hll');

Теперь на экране увидим 3

Как и следовало, мы получили результат 3 (т.е. всего 3 уникальных элемента записаны в этом ключе).

И самое главное — этот подход работает на 3-4 порядка быстрее, чем аналогичное решение на основе SQL.

Временные фильтры

И все же, стандартного решения недостаточно. Нам необходимо иметь возможность выбирать период для подсчета уникальных значений. На этот случай Redis умеет делать склеивание HLL ключей прямо во время выборки:

$r->pfadd('hll1', [1, 2, 3]);
$r->pfadd('hll2', [1, 4, 5]);
echo $r->pfcount(['hll1', 'hll2']);

Выборка вернет 5 — количество уникальных элементов сразу в двух HLL ключах

Для выборки можно использовать любое количество hll ключей. А нам необходимо получать количество уникальных пользователей по дням.
Следовательно, для решения достаточно сохранять идентификатор пользователя в HLL ключ при посещении им страницы. Название ключа будет содержать суффикс — дату посещения:

$id = $_REQUEST['id']; # id посетителя (уникальное для каждого человека)
$key = 'visits' . date('Ymd'); # HLL ключ с суффиксом даты
$r->pfadd($key, [$id]);

Сохранение информации о посещение за день

Теперь нужно выбрать количества уникальных пользователей за любой промежуток времени. Для этого нужно склеить все ключи за даты внутри этого промежутка:

$dates = ['20160610', '20160611', '20160612', '20160613']; # весь промежуток с датами в формате Ymd
foreach ( $dates as $date ) $keys[] = 'visits' . $date;
echo $r->pfcount($keys);

Результатом будет количество уникальных посетителей в промежутке с 10.06 по 13.06 2016 года

Самое главное

SQL средства плохо справляются с подсчетом уникальных значений. Особенно, если необходимо фильтровать список. На небольших объемах данных достаточно использовать правильные индексы в MySQL. На объемах больше 1 млн записей следует обдумать возможность использования хранилища HyperLogLog в Redis.

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