SQL HowTo: считаем «уников» на интервале19.01.2022 17:47

Для систем управления бизнесом часто приходится решать очень похожий класс задач по вычислению количества уникальных объектов на произвольном временном интервале. В контексте CRM это могут быть »пользователи, обращавшиеся на горячую линию на прошлой неделе»,»контрагенты, оплатившие за последние 30 дней» или »потенциальные клиенты, с кем был контакт в этом квартале».

Искать в большом количестве фактов «уники» — всегда сложно и долго, если их достаточно много. Если интервалы фиксированы (календарные месяц/квартал/год), можно материализовывать такие агрегаты заранее. А если интервал — произвольный, как тогда эффективно найти ответ?

image-loader.svg

Сначала смоделируем ситуацию, как она выглядит для нас, в масштабах «Тензора» — 5000 наших сотрудников до 100 000 раз за сутки общаются с потенциальными клиентами или с кем-то из уже работающих с нами 5 миллионов пользователей: 

CREATE TABLE tbl_fact(
  id
    serial
      PRIMARY KEY
, dt
    date
, clientid
    integer
);
CREATE INDEX ON tbl_fact(clientid, dt DESC);
CREATE INDEX ON tbl_fact(dt, clientid);

INSERT INTO tbl_fact(dt, clientid)
SELECT
  dt
, unnest(ARRAY(
    SELECT
      (random() * 5e6)::integer -- 5M уникальных клиентов
    FROM
      generate_series(1, qty)
  )) clientid
FROM
  (
    SELECT
      dt::date
    , (random() * 1e5)::integer qty -- до 100K контактов в день с ними
    FROM
      generate_series('2021-01-01'::timestamp, '2021-12-31'::timestamp, '1 day'::interval) dt
  ) T;
-- Query returned successfully: 19036668 rows affected, 03:15 minutes execution time.

А теперь попробуем ответить на простой вопрос — сколько было уникальных клиентов в декабре?

Понятно, что если вся «первичка» уже лежит в PostgreSQL, то для реализации одной лишь этой функции выгружать данные во внешнюю СУБД с колоночным хранением данных вроде ClickHouse, которая подошла бы именно для этой задачи лучше, не особо оправданно с точки зрения эксплуатации разнородной архитектуры.

SELECT
  count(DISTINCT clientid)
FROM
  tbl_fact
WHERE
  dt BETWEEN '2021-12-01' AND '2021-12-31';
-- 1364826

Получилось чуть больше 1364K «уников» из 1594K «фактов», но считалось это как-то слишком долго — 717 мс [explain.tensor.ru]:

«Наивный» подсчет по первичным данным

Но самое печальное — это объем данных, который нам приходится прочитать — почти 23K страниц, то есть примерно 180MB. И если любая из них окажется не в кэше, и ее придется вычитывать с диска — тормоза нам обеспечены.

ARRAY

Но мы можем попробовать заранее «упаковать» имеющиеся у нас данные, чтобы в момент запроса читать самый минимум — использовать массив уникальных идентификаторов за каждый день (ведь нам заранее неизвестен интервал, который захочет запросить пользователь): 

CREATE TABLE tbl_pack_array AS
SELECT
  dt
, array_agg(DISTINCT clientid) pack
FROM
  tbl_fact
GROUP BY
  1;
CREATE INDEX ON tbl_pack_array(dt);

Тогда нам останется лишь прочитать записи за нужный интервал дней, «развернуть» все идентификаторы и посчитать количество уникальных: 

SELECT
  count(DISTINCT clientid)
FROM
  (
    SELECT
      unnest(pack) clientid
    FROM
      tbl_pack_array
    WHERE
      dt BETWEEN '2021-12-01' AND '2021-12-31'
  ) T;

Читать приходится в 26 раз меньше — всего 888 страниц, да и по времени отыграли 10% — до 642 мс [explain.tensor.ru]:

Группировка массивовГруппировка массивов

hstore

Но в варианте с массивом нам пришлось каждый из них unnest'ить и уникализировать самостоятельно? Но ведь есть способ отдать уникализацию самому серверу — использовать сложение hstore с одноименными ключами: 

SELECT 'a=>1,b=>2'::hstore || 'b=>3,c=>4'::hstore;
-- "a"=>"1", "b"=>"3", "c"=>"4"

Не забываем, что сначала необходимо установить это расширение в свою базу: 

CREATE EXTENSION hstore;

И только после этого пакуем, не забывая, что все ключи должны быть текстовыми: 

CREATE TABLE tbl_pack_hstore AS
SELECT
  dt
, hstore(
    array_agg(DISTINCT clientid)::text[] -- ключи - только текстовые
  , NULL                                 -- значения нам неважны
  ) pack
FROM
  tbl_fact
GROUP BY
  1;
CREATE INDEX ON tbl_pack_hstore(dt);

Теперь нам необходимо «сложить» hstore-объекты в нужных строках, но соответствующей агрегатной функции hstore_agg не существует. Не беда — создадим ее сами: 

CREATE AGGREGATE hstore_agg(hstore) (
  sfunc = hs_concat -- это функция, уже реализующая hstore || hstore
, stype = hstore
, parallel = safe
);

Воспользуемся функцией akeys, которая вернет нам массив ключей собранного объекта: 

SELECT
  array_length(akeys(hstore_agg(pack)), 1)
FROM
  tbl_pack_hstore
WHERE
  dt BETWEEN '2021-12-01' AND '2021-12-31';

Читать теперь приходится в 2.5 раза больше — 3049 страниц, зато по времени — еще минус 5% — 612 мс [explain.tensor.ru]:

Группировка hstoreГруппировка hstore

jsonb

Но ведь есть «нативный» тип, который самостоятельно делает уникализацию ключей — json[b]: 

SELECT '{"a":1,"b":2}'::jsonb || '{"b":3,"c":4}'::jsonb;
-- {"a": 1, "b": 3, "c": 4}

Давайте обойдемся без всех этих дополнительно устанавливаемых расширений: 

CREATE TABLE tbl_pack_jsonb AS
SELECT
  dt
, jsonb_object_agg(clientid, NULL) pack
FROM
  tbl_fact
GROUP BY
  1;
CREATE INDEX ON tbl_pack_jsonb(dt);

Правда, агрегатную функцию снова придется делать самим: 

CREATE AGGREGATE jsonb_agg(jsonb) (
  sfunc = jsonb_concat -- это функция, уже реализующая jsonb || jsonb
, stype = jsonb
, parallel = safe
);

И даже не будем пробовать извлекать ключи — достаточно уже агрегации…

SELECT
  jsonb_agg(pack)
FROM
  tbl_pack_jsonb
WHERE
  dt BETWEEN '2021-12-01' AND '2021-12-31';

… чтобы понять, что хоть jsonb и гораздо компактнее hstore (читать приходится лишь чуть больше, чем для массивов — 963 страницы), но это не окупает адских тормозов при агрегации почти на 13 секунд! [explain.tensor.ru]:

Группировка jsonbГруппировка jsonb

Итак, в сегодняшнем забеге упаковка в массив позволяет получить наиболее сбалансированный по объему и скорости результат.

А еще быстрее — можно? Да, но это уже материал для хаба «ненормальное программирование».

Основные затраты времени у нас шли на объединение массивов/объектов. То есть чем меньше записей с «пакетами» нам необходимо обработать — тем лучше.

Для этого все даты можно покрыть отрезками длиной 2^N:

Сегментация датСегментация дат

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

Разбиение интервала на сегментыРазбиение интервала на сегменты

Ну, а каскадное добавление ID клиента во все такие отрезки можно с помощью несложной функции: 

CREATE OR REPLACE FUNCTION uniq_set(_pow integer, _ord integer, clientid integer) RETURNS void AS $$
DECLARE
  _row tbl_uniq%ROWTYPE;
BEGIN
  INSERT INTO tbl_uniq(
    pow
  , ord
  , uniq
  )
  VALUES(
    _pow
  , _ord
  , ARRAY[clientid]
  )
  ON CONFLICT(pow, ord)
    DO UPDATE
    SET
      uniq = tbl_uniq.uniq || excluded.uniq -- включаем значение в массив...
    WHERE
      NOT tbl_uniq.uniq @> excluded.uniq -- ... если его там еще не было
  RETURNING
    * INTO _row;
  IF FOUND AND _pow < 9 THEN
    PERFORM uniq_set(_pow + 1, _ord >> 1, clientid);
  END IF;
END $$ LANGUAGE plpgsql;

Если интересно — потренируйтесь на досуге.

© Habrahabr.ru