HyperLogLog в PostgreSQL

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

HyperLogLog принадлежит к категории вероятностных структур данных, которые позволяют аппроксимировать количество уникальных элементов в больших наборах данных с удивительно низким потреблением памяти. HLL использует 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.