Для систем управления бизнесом часто приходится решать очень похожий класс задач по вычислению количества уникальных объектов на произвольном временном интервале. В контексте CRM это могут быть "пользователи, обращавшиеся на горячую линию на прошлой неделе", "контрагенты, оплатившие за последние 30 дней" или "потенциальные клиенты, с кем был контакт в этом квартале".
Искать в большом количестве фактов «уники» — всегда сложно и долго, если их достаточно много. Если интервалы фиксированы (календарные месяц/квартал/год), можно материализовывать такие агрегаты заранее. А если интервал — произвольный, как тогда эффективно найти ответ?
Сначала смоделируем ситуацию, как она выглядит для нас, в масштабах «Тензора» — 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]:
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]:
Итак, в сегодняшнем забеге упаковка в массив позволяет получить наиболее сбалансированный по объему и скорости результат.
А еще быстрее - можно? Да, но это уже материал для хаба "ненормальное программирование".
Основные затраты времени у нас шли на объединение массивов/объектов. То есть чем меньше записей с "пакетами" нам необходимо обработать - тем лучше.
Для этого все даты можно покрыть отрезками длиной 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;Если интересно - потренируйтесь на досуге.
Комментарии (21)
Hashbash
20.01.2022 00:34Мне кажется, вы слишком усложняете себе задачу, а потом ее зачем-то решаете...
... CREATE INDEX tbl_fact_idx ON tbl_fact (clientid); vacuum analyze tbl_fact; -- 10 s 72 ms public> select count(distinct clientid) from tbl_fact [2022-01-20 00:32:34] 1 row retrieved starting from 1 in 10 s 72 ms (execution: 10 s 31 ms, fetching: 41 ms) --3 s 712 ms public> select count(*) from (select clientid from tbl_fact group by clientid) q [2022-01-20 00:33:45] 1 row retrieved starting from 1 in 3 s 712 ms (execution: 3 s 672 ms, fetching: 40 ms)
Kilor Автор
20.01.2022 09:26+1Бессмысленно обсуждать производительность запросов без их планов. А в них надо обязательно смотреть buffers - а то вполне можем попасть на ситуацию описанную в "наивном" варианте - когда приходится читать 180MB, если не повезет - с диска.
Hashbash
20.01.2022 12:38Хотел показать, что есть более простые варианты считать уников. В данном случае, вариант, в котором нет необходимости в сортировке значений. Для вашего распределения числа уникальных записей должно быть быстрее.
Kilor Автор
20.01.2022 12:48вариант, в котором нет необходимости в сортировке значений
Который из них? Оба приведенных варианта запроса не учитывают задаваемый пользователем интервал. А если его просто добавить в запрос - перестанет нормально помогать индекс
(clientid).Hashbash
20.01.2022 13:50Второй не сортирует. По поводу даты, разумеется, или индекс по дате или составной с датой должен быть. При этом разница между этими индексами тоже будет сильной.
Kilor Автор
20.01.2022 13:58Если имелось в виду в том смысле, что не сортирует дополнительно отдельно от других узлов плана, поскольку из индекса получает уже отсортированный набор - то да:
Aggregate (actual time=4633.054..4633.056 rows=1 loops=1) Buffers: shared hit=10783998 read=30552 -> Group (actual time=0.076..4370.153 rows=4889090 loops=1) Group Key: tbl_fact.clientid Buffers: shared hit=10783998 read=30552 -> Index Only Scan using tbl_fact_idx on tbl_fact (actual time=0.072..3056.843 rows=19036668 loops=1) Heap Fetches: 0 Buffers: shared hit=10783998 read=30552 Planning: Buffers: shared hit=17 read=1 Planning Time: 0.960 ms Execution Time: 4633.278 msНо наличие даты в условии сразу все ломает.
Hashbash
20.01.2022 14:23Не ломает
create index tbl_fact_idx2 on tbl_fact(clientid, dt); explain analyze select count(*) from (select clientid from tbl_fact where dt between '2021-01-01' and '2021-12-01' group by clientid) q;Aggregate (cost=641207.12..641207.13 rows=1 width=8) (actual time=5522.464..5522.466 rows=1 loops=1) -> Group (cost=0.44..594183.54 rows=3761887 width=4) (actual time=55.265..5263.736 rows=4817602 loops=1) Group Key: tbl_fact.clientid -> Index Only Scan using tbl_fact_idx2 on tbl_fact (cost=0.44..552706.71 rows=16590731 width=4) (actual time=0.095..3838.740 rows=16545711 loops=1) Index Cond: ((dt >= '2021-01-01'::date) AND (dt <= '2021-12-01'::date)) Heap Fetches: 0Kilor Автор
20.01.2022 14:42Без buffers ненаглядно, но - стало медленнее, 5 сек вместо 3 сек?
Это вполне соотносится с "плохим" использованием индекса "без начала": https://habr.com/ru/company/tensor/blog/488104/
Hashbash
20.01.2022 14:58Нет, выполнение те же 3 секунды
public> select count(*) from (select clientid from tbl_fact where dt between '2021-01-01' and '2021-12-01' group by clientid) q [2022-01-20 14:57:33] 1 row retrieved starting from 1 in 3 s 322 ms (execution: 3 s 302 ms, fetching: 20 ms)Kilor Автор
20.01.2022 15:16В приведенном выше плане общее время 5522.466 - и вот как раз так может играть чтение из кэша/с диска.
vasyakolobok77
20.01.2022 12:58Вполне может быть, что после первого запроса все страницы памяти попали с диска в shared_buffers, и второй запрос просто читал их оттуда.
Hashbash
20.01.2022 13:53Тогда бы и первый стал бы работать быстрее при повторных запусках, а этого не происходит. Ну плюс план разный, первый seq скан, второй index scan only. + сортировка перед каунтом.
miksoft
20.01.2022 00:37А если построить предагрегат для всех возможных диапазонов дат?
Это не так уж много — за 10 лет всего 6,66 млн. записей.
Тогда всего одну запись дернуть по индексу — может оказаться меньше миллисекунды, если индекс в кэше.Kilor Автор
20.01.2022 09:24Вариант вполне реализуемый, но каждая такая запись будет хранить массив примерно от 100K (в день) до 5M (за все время) идентификаторов.
Если прикинуть просто по среднему, получится 6.66M (записей) x 2.5M (идентификаторов) x 4 (байта) ~= 66.6TB, даже без учета индексов.
Ivan22
20.01.2022 16:33Неплохо, но в нашей реаьности у юзеров перед глазами дашборды в PowerBI и они само собой не в DirectQuery работают а в своем кеше загруженном и там считает DAX дистинкт каунты, а не sql постгресовый
hungry_forester
Буквально написано - списки, а не количества :)
Вот кстати, это такое бест практис или просто "а че DISTINCT, есть такая опция, значит, она хорошая?" Нету базы с 1.5М фактов чтобы потестить. Больше есть :)
В целом, так загоняться ради 0.7 сек... Такое. С другой стороны, по-моему, оно и считать должно на такой таблице уники побыстрее... Без извращений, только с грамотной индексацией.
Kilor Автор
Собственно, списки мы тоже имеем этим способом.
Ну как бы именно
count(DISTINCT column)дает количество уникальных значений столбца, аcount(column). даст просто колчичество неNULLовых.Теперь предположим, что где-то в интерфейсе на дашборде у каждого из 5K сотрудников висит "метер", который считает уников по первому наивному способу...
baldr
Статья хорошая, но вот с этим вашим комментарием - не согласен категорически. Плохой пример. Если у 5К сотрудников висит "метер", который из базы периодически тянет этот показатель GET-запросом, то тут не исправить оптимизацией запроса. Тут надо либо аггрегировать предварительно для всех и рассылать push-запросом, либо где-нибудь в Redis вести отдельный счетчик, либо как-то еще решать это архитектурно.
На мой взгляд операции с базой (удаленной) - слишком дорогие чтобы такими запросами баловаться. Если база обслуживает 5К юзеров, то у нее уже наверняка есть более важные и тяжелые операции.
Я понимаю что вы придумали этот пример "на бегу" и наверняка сами понимаете его условность, но объяснить должен кто-то :)
Kilor Автор
Понятно, что давать этим 5K юзеров дергать из базы один и тот же набор данных - сильно неоптимально. Но и данные у них могут быть свои у каждого (по своим сделкам), и решения с выносом операций обсчета "наружу" - в Redis, отдельный воркер, который только тем и занимается, что считает да рассылает - не всегда будет архитектурно оптимально. Баланс тут очень тонок и зависит от дополнительных факторов за рамками статьи.
MrGrey13
Кейс в статье вырван из контекста, конечно. Обычно это как раз преднастроенные дашборды на витринах с известной структурой, типичный хранилищный кейс. Колоночная база - и вашему сеньору не придется делать сравнение полдюжины способов расчета "количества уникальных" чтобы выиграть какие-то миллисекунды. Вместо этого он может пойти порешать действительно интересные и важные таски.
Kilor Автор
Например, такие таски как написание синхронизирующих эти две базы воркеров, устранение рассогласований в них или внедрение протоколов двухфазного коммита...