Функции HyperLogLog

Trino реализует функцию approx_distinct() с использованием структуры данных HyperLogLog.

Структуры данных

Trino реализует скетчи данных HyperLogLog как набор 32-битных корзин, которые хранят максимальный хеш. Они могут храниться разреженно (как map от ID корзины к корзине) или плотно (как непрерывный блок памяти). Структура данных HyperLogLog начинается как разреженное представление и переключается на плотное, когда это становится эффективнее. Структура P4HyperLogLog инициализируется в плотном виде и остается плотной в течение всего времени жизни.

HyperLogLog неявно приводится к P4HyperLogLog, а HyperLogLog можно явно привести к P4HyperLogLog:

cast(hll AS P4HyperLogLog)

Сериализация

Скетчи данных можно сериализовать в varbinary и десериализовать из него. Это позволяет хранить их для последующего использования. В сочетании с возможностью объединять несколько скетчей это позволяет вычислять approx_distinct() для элементов отдельной части запроса, а затем для всего запроса в целом с очень небольшими затратами.

Например, вычисление HyperLogLog для ежедневных уникальных пользователей позволяет инкрементально вычислять недельных или месячных уникальных пользователей путем объединения дневных значений. Это похоже на вычисление недельной выручки суммированием дневной выручки. Использование approx_distinct() с GROUPING SETS можно преобразовать к использованию HyperLogLog. Примеры:

CREATE TABLE visit_summaries (
  visit_date date,
  hll varbinary
);

INSERT INTO visit_summaries
SELECT visit_date, cast(approx_set(user_id) AS varbinary)
FROM user_visits
GROUP BY visit_date;

SELECT cardinality(merge(cast(hll AS HyperLogLog))) AS weekly_unique_users
FROM visit_summaries
WHERE visit_date >= current_date - interval '7' day;

Функции

approx_set(x) → HyperLogLog

Возвращает скетч HyperLogLog для входного набора данных x. Этот скетч лежит в основе approx_distinct() и может быть сохранен и использован позже через вызов cardinality().

cardinality(hll) → bigint

Выполняет approx_distinct() для данных, суммаризированных в скетче данных hll HyperLogLog.

empty_approx_set() → HyperLogLog

Возвращает пустой HyperLogLog.

merge(HyperLogLog) → HyperLogLog

Возвращает HyperLogLog агрегированного объединения отдельных структур hll HyperLogLog.