Cumulative DISTINCT в SQL на собеседовании Data Engineer

Зачем спрашивают на собесе DE

Cumulative unique users — типичная аналитическая задача. На собесе DE: «как посчитать running DAU», «зачем HLL», «почему COUNT DISTINCT в OVER не работает».

Проблема: COUNT(DISTINCT) в окнах

Хочется: для каждой даты — total unique users (от начала до этой даты).

-- Не работает в Postgres
SELECT day,
       COUNT(DISTINCT user_id) OVER (ORDER BY day) AS cumulative_users
FROM events;
-- ERROR: DISTINCT not supported in window

Почему. Window function для cumulative нужна running aggregation. DISTINCT требует full state — несовместимо со streaming approach.

Subquery подход

Стандартный workaround:

WITH first_seen AS (
  SELECT user_id, MIN(day) AS first_day
  FROM events
  GROUP BY user_id
)
SELECT day,
       SUM(new_users) OVER (ORDER BY day) AS cumulative_users
FROM (
  SELECT first_day AS day,
         COUNT(*) AS new_users
  FROM first_seen
  GROUP BY first_day
) t;

Идея: для каждого user'а — first_day. Cumulative count = сумма «новых» по дням.

Self-join

Альтернатива (медленнее):

SELECT d.day,
       (SELECT COUNT(DISTINCT user_id)
        FROM events e
        WHERE e.day <= d.day) AS cumulative_users
FROM (SELECT DISTINCT day FROM events) d;

O(N²) — для каждого day считаем над всем датасетом. На больших данных — катастрофа.

HyperLogLog approximate

HyperLogLog (HLL) — probabilistic data structure. Estimates unique count в небольшой памяти (~1KB на miliard уникальных).

Свойства:

• Mergeable — два HLL можно объединить в один (HLL итогом).
• Точность ~1.6% relative error на дефолтных параметрах.
• Constant memory.

Postgres (extension hll):

SELECT day, hll_cardinality(hll_union_agg(hll_users)) AS cum_users
FROM (
  SELECT day,
         hll_add_agg(hll_hash_text(user_id)) AS hll_users
  FROM events
  GROUP BY day
) t;

Cumulative — через rolling union.

ClickHouse:

SELECT day, uniqHLL12(user_id) OVER (ORDER BY day) AS cum_users
FROM events;

uniq* функции в CH — все используют HLL под капотом.

BigQuery / Snowflake — встроенные APPROX_COUNT_DISTINCT.

BITMAP в ClickHouse

Для exact counts на small cardinality (< миллионы).

SELECT day, bitmapCardinality(bitmapColumn) AS users
FROM (
  SELECT day, groupBitmapState(user_id) AS bitmapColumn
  FROM events
  GROUP BY day
)

Bitmap mergeable, exact. Хорош для cohorts, retention analysis.

Частые ошибки

COUNT(DISTINCT) OVER. Не работает в Postgres / Spark. Нужен workaround.

Self-join на больших таблицах. O(N²), не масштабируется.

Не использовать HLL для approximation. Точное count бесполезно когда нужна тенденция, HLL делает быстрее.

Считать HLL exact. ~1-2% error. Не используй для compliance / billing.

Игнорировать встроенные approximate. APPROX_COUNT_DISTINCT (BQ, Snowflake) или uniq (CH) — гораздо быстрее.

Связанные темы

• LAG и LEAD на собесе DE
• Оконные функции на собесе DE
• SQL для Data Engineer
• ClickHouse MergeTree для DE
• Подготовка к собесу Data Engineer

FAQ

HLL для retention?

Можно. HLL items на каждый день / cohort, потом intersection (через inclusion-exclusion).

Это официальная информация?

Нет. Статья основана на документации Postgres HLL extension, ClickHouse, BigQuery / Snowflake.

Тренируйте Data Engineering — откройте тренажёр с 1500+ вопросами для собесов.