Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Для систем управления бизнесом часто приходится решать очень похожий класс задач по вычислению количества уникальных объектов на произвольном временном интервале. В контексте CRM это могут быть "пользователи, обращавшиеся на горячую линию на прошлой неделе", "контрагенты, оплатившие за последние 30 дней" или "потенциальные клиенты, с кем был контакт в этом квартале".
Искать в большом количестве фактов «уники» — всегда сложно и долго, если их достаточно много. Если интервалы фиксированы (календарные месяц/квартал/год), можно материализовывать такие агрегаты заранее. А если интервал — произвольный, как тогда эффективно найти ответ?
![](https://habrastorage.org/getpro/habr/upload_files/991/a2c/1f0/991a2c1f0f0cde2f71fa27c0cf06d030.png)
Сначала смоделируем ситуацию, как она выглядит для нас, в масштабах «Тензора» — 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]:
!["Наивный" подсчет по первичным данным "Наивный" подсчет по первичным данным](https://habrastorage.org/getpro/habr/upload_files/563/4a9/7de/5634a97de9f964796df352db42218436.png)
Но самое печальное - это объем данных, который нам приходится прочитать - почти 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]:
![Группировка массивов Группировка массивов](https://habrastorage.org/getpro/habr/upload_files/79d/e5f/7e4/79de5f7e476a133aef5b434737f52506.png)
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](https://habrastorage.org/getpro/habr/upload_files/d05/e7f/527/d05e7f5278ecfa7e0e53477c5a0f6b50.png)
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](https://habrastorage.org/getpro/habr/upload_files/02f/0b9/a9e/02f0b9a9eb03555c4c9adf5fc2140d8a.png)
Итак, в сегодняшнем забеге упаковка в массив позволяет получить наиболее сбалансированный по объему и скорости результат.
А еще быстрее - можно? Да, но это уже материал для хаба "ненормальное программирование".
Основные затраты времени у нас шли на объединение массивов/объектов. То есть чем меньше записей с "пакетами" нам необходимо обработать - тем лучше.
Для этого все даты можно покрыть отрезками длиной 2^N
:
![Сегментация дат Сегментация дат](https://habrastorage.org/getpro/habr/upload_files/f5d/93b/f14/f5d93bf14ba61b266adc9b7e2fb53764.png)
Тогда любой из заданных пользователем интервалов можно разбить на такие непересекающиеся отрезки:
![Разбиение интервала на сегменты Разбиение интервала на сегменты](https://habrastorage.org/getpro/habr/upload_files/455/9fa/643/4559fa6433a90073da58af435237b760.png)
Ну, а каскадное добавление 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;
Если интересно - потренируйтесь на досуге.