Привет, Хабр!

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

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

В этой статье рассмотрим, как реализован HLL в PostgreSQL.

Установим

Установим HyperLogLog в БД PostgreSQL с помощью команды:

CREATE EXTENSION hll;

Команда добавит необходимые функции и типы данных в систему.

После установки расширения вы можно начать использовать функции HyperLogLog.

Основные функции HLL

hll_add() принимает элемент и HLL скетч, добавляет элемент в скетч и возвращает обновленный HLL скетч:

SELECT hll_add(hll_hash_integer(user_id)) FROM users;

hll_cardinality() возвращает аппроксимированное количество уникальных элементов в HLL скетче:

SELECT hll_cardinality(hll) FROM some_table;

hll_hash_text(), hll_hash_integer() генерируют хеш-значение из текста или целого числа соответственно для дальнейшего использования в HLL скетчах.

hll_union_agg() агрегатная функция, которая объединяет несколько HLL скетчей в один. Юзается для получения общего количества уникальных элементов из нескольких скетчей. Пример:

SELECT hll_union_agg(hll) FROM multiple_sketches;

hll_empty() создает пустой HLL скетч.

hll_size() возвращает размер в байтах HLL скетча.

hll_add_agg() агрегатная функция, аналогичная hll_union_agg, но она также добавляет новые элементы к HLL скетчу по мере их обработки.

hll_union() объединяет два или более HLL скетча в один.

hll_compact() оптимизирует хранение HLL скетча, минимизируя его размер без потери точности.

hll_decompress() преобразует сжатый HLL скетч обратно в его обычное состояние.

hyperloglog_init() инициализирует новый HLL скетч с определенной степенью ошибки и предполагаемым количеством уникальных элементов.

hyperloglog_reset() сбрасывает HLL скетч к исходному состоянию, удаляя все добавленные элементы.

hyperloglog_merge() объединяет два HLL скетча в один, сохраняя аппроксимированное количество уникальных элементов из обоих скетчей.

Примеры применений

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

SELECT
    created_at,
    event_type,
    hll_cardinality(distinct_user_id_count) AS distinct_count
FROM
    github_events_rollup_minute
WHERE
    created_at BETWEEN '2024-12-01 05:00:00' AND '2024-12-01 06:00:00';

Для оценки количества уникальных адресов электронной почты в БД можно использовать следующий запрос:

SELECT hll_cardinality(hll_sketch) AS estimated_distinct_count
FROM (
    SELECT hll_add(hll_hash_text(email)) AS hll_sketch
    FROM users
) AS subquery;

Создание таблицы для ежедневного подсчета уникальных посетителей, используя HLL для учета уникальности:

CREATE TABLE daily_uniques (
    date DATE UNIQUE,
    users hll
);
UPDATE daily_uniques
SET users = hll_add(users, hll_hash_text('visitor_ip'))
WHERE date = current_date;

HLL также поддерживает оценку уникальности для комбинаций нескольких столбцов, например, для идентификации уникальных комбинаций юзеров и продуктов:

SELECT hll_cardinality(hll_sketch) AS estimated_distinct_count
FROM (
    SELECT hll_add(hll_hash_any(ARRAY[user_id, product_id])) AS hll_sketch
    FROM orders
) AS subquery;

Можно юзать HLL в системах, где необходима высокая производительность запросов на больших объемах данных, например, для агрегации уникальных посетителей с различными характеристиками:

SELECT hll_cardinality(hll_union_agg(unique_visitors))
FROM daily_unique_visitors
WHERE ts >= '2019-07-01' AND ts < '2019-08-01' AND customer_id = 'A' AND location = 'US';

HLL предлагает аппроксимацию количества уникальных элементов с типичной относительной точностью (стандартной ошибкой) около 2%, при этом используя всего около 1.5 КБ памяти. Т.е HLL хорош для приложений, где необходимо обрабатывать большие объемы данных с приемлемой точностью, но не требуется абсолютная точность.

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

Материал подготовлен в преддверии старта продвинутой обучающей программы по PostgreSQL.