Периодически сталкиваюсь с однотипными задачами вида "показать TOP-N позиций на каждом из вложенных интервалов некоторого периода".
Это может быть "5 лучших по успеваемости студентов в каждом семестре за последний учебный год", или "помесячная динамика позиции 10 наиболее продающихся товаров", или, как у нас в сервисе визуализации PostgreSQL-планов explain.tensor.ru, "3 наиболее активных страны за каждый день":
Давайте попробуем создать эффективный, но компактный запрос для PostgreSQL, который сможет решить такую задачу - например, за последний месяц.
Для начала нам понадобится сама таблица первичных "фактов", по которой мы будем вычислять свои "топы" - сгенерируем в ней миллион каких-то случайных записей "за последний год":
CREATE TABLE fact4agg AS
SELECT
now()::date - (random() * 365)::integer dt -- дата "факта"
, chr(ascii('a') + (random() * 26)::integer) code -- код агрегации
FROM
generate_series(1, 1e6);Раз выборку мы будем делать "за период", то индекс по дате нам точно пригодится:
CREATE INDEX ON fact4agg(dt);Генерация субинтервалов
При первом подходе к задаче может показаться, что достаточно посчитать и вывести группировку по "фактам" в разрезе каждого дня. Но это будет ошибкой, поскольку в некоторых днях может не оказаться ни одного факта.
Конечно, подобные пропуски можно будет устранить и на бизнес-логике, но она для этого все-таки приспособлена не слишком хорошо, поэтому сделаем это сразу на БД с помощью функции generate_series, получив серию дат:
WITH params(dtb, dte) AS (
VALUES(now()::date - 30, now()::date)
)
SELECT
dt::date
FROM
params
, generate_series(dtb, dte, '1 day') dt;Небольшой нюанс здесь заключается лишь в том, что эта функция выдает timestamp, а нам необходим тип date. Если вам требуется другой интервал - например, неделя или месяц - просто задайте другой шаг: '1 week' или '1 month'.
Первичный отбор данных
Ничего сильно хитрее, чем "прямо взять и посчитать", для вычисления агрегатов (если мы их нигде не храним в отдельной таблице, как это описано в серии статей про агрегаты в БД) применить не выйдет:
WITH params(dtb, dte) AS (
VALUES(now()::date - 30, now()::date)
)
SELECT
dt
, code
, count(*) qty
FROM
params
, fact4agg
WHERE
dt BETWEEN dtb AND dte
GROUP BY
1, 2;К счастью, наличие индекса позволяет нам отобрать и сгруппировать все необходимые данные достаточно быстро - всего за 65ms:
Но если мы поменяем наш индекс на более подходящий для Index Only Scan, тот же запрос окажется вдвое быстрее и в 200 раз более эффективным по объему вычитываемых данных!
DROP INDEX fact4agg_dt_idx;
CREATE INDEX ON fact4agg(dt)
INCLUDE(code);
Отбираем TOP-3
Поскольку мы условились, что делать на бизнес-логике несвойственные ей операции мы не хотим, то договоримся, что 3 "лидирующих" записи за каждый день мы отдадим одним json.
И самый простой приходящий на ум вариант выглядит как "так давайте пронумеруем нужные с помощью оконных функций и отберем только их". Правда, это приведет нас к не очень красивому "трехэтажному" запросу:
WITH params(dtb, dte) AS (
VALUES(now()::date - 30, now()::date)
)
SELECT
dt
, json_agg(
json_build_object('code', code, 'qty', qty)
ORDER BY qty DESC -- "сворачиваем" в json[] с нужной сортировкой
)
FROM
(
SELECT
*
, row_number() OVER(PARTITION BY dt ORDER BY qty DESC) rn -- нумеруем в нужном порядке
FROM
(
SELECT
dt
, code
, count(*) qty
FROM
params
, fact4agg
WHERE
dt BETWEEN dtb AND dte
GROUP BY
1, 2
) T
) T
WHERE
rn <= 3 -- отбираем только 3 первых
GROUP BY
1;Но давайте обратим внимание, что мы сортировали данные тут, минимум, дважды - сначала при нумерации, а потом - при свертке в json. Нельзя ли этого избежать?..
Оказывается, можно, если сразу все "сворачивать в массив", и уже от него брать 3 первых элемента. Но не все так просто...
ERROR: cannot subscript type json because it does not support subscriptingНельзя просто так взять сегмент из json-массива, зато из массива json'ов - можно:
WITH params(dtb, dte) AS (
VALUES(now()::date - 30, now()::date)
)
SELECT
dt
, to_json(
(
array_agg(
to_jsonb(T) - 'dt' -- свернули всю строку в jsonb и удалили лишний ключ
ORDER BY qty DESC -- сортируем в нужном порядке
) -- свернули в jsonb[]
)[:3] -- взяли 3 первых элемента
) json -- сконвертировали в "обычный" json
FROM
(
SELECT
dt
, code
, count(*) qty
FROM
params
, fact4agg
WHERE
dt BETWEEN dtb AND dte
GROUP BY
1, 2
) T
GROUP BY
1;Тут мы вместо перечисления всех полей в результирующем json просто "свернули" всю строку в jsonb и удалили в нем избыточный ключ dt.
Затем "свернули" все в jsonb[], взяли от него первые 3 элемента и превратили в "обычный" json-массив.
Итоговый запрос
Остается лишь собрать генерацию субинтервалов и агрегаты в единый запрос:
WITH params(dtb, dte) AS (
VALUES(now()::date - 30, now()::date)
)
SELECT
*
FROM
(
SELECT
dt::date
FROM
params
, generate_series(dtb, dte, '1 day') dt
) X
LEFT JOIN
(
SELECT
dt
, to_json(
(
array_agg(
to_jsonb(T) - 'dt'
ORDER BY qty DESC
)
)[:3]
) json
FROM
(
SELECT
dt
, code
, count(*) qty
FROM
params
, fact4agg
WHERE
dt BETWEEN dtb AND dte
GROUP BY
1, 2
) T
GROUP BY
1
) Y
USING(dt)
ORDER BY
dt;Убедимся фактическим планом, что мы своими агрегатами ничего сильно не попортили:
Всего 42ms (даже меньше, чем весь отбор данных при Index Scan!), да и план не слишком страшный получился.
Комментарии (14)
ptr128
28.11.2023 09:13+1В случае, когда code всего 27, а записей - миллионы, эффективней идти полностью по индексу. Пример сделал на 10 миллионах, так как на миллионе он не столь явно различается:
DROP TABLE IF EXISTS fact4agg; CREATE TABLE fact4agg AS SELECT now()::date - (random() * 365)::integer dt -- дата "факта" , chr(ascii('a') + (random() * 26)::integer) code -- код агрегации FROM generate_series(1, 1e7); CREATE INDEX fact4agg_dt_code_Idx ON fact4agg(dt) INCLUDE(code); CREATE INDEX fact4agg_code_dt_Idx ON fact4agg(code, dt);Сначала Ваш запрос:
DROP TABLE IF EXISTS tmp_tmp; EXPLAIN ANALYZE CREATE TEMP TABLE tmp_tmp AS WITH params(dtb, dte) AS ( VALUES(now()::date - 30, now()::date) ) SELECT dt , code , count(*) qty FROM params , fact4agg WHERE dt BETWEEN dtb AND dte GROUP BY 1, 2; HashAggregate (cost=25677.39..25776.21 rows=9882 width=14) (actual time=219.549..219.739 rows=837 loops=1) Group Key: fact4agg.dt, fact4agg.code Batches: 1 Memory Usage: 529kB -> Index Only Scan using fact4agg_dt_code_idx on fact4agg (cost=0.45..19367.89 rows=841267 width=6) (actual time=0.025..89.172 rows=836228 loops=1) Index Cond: ((dt >= ((now())::date - 30)) AND (dt <= (now())::date)) Heap Fetches: 0 Planning Time: 0.128 ms Execution Time: 221.081 msА теперь через code:
DROP TABLE IF EXISTS tmp_tmp; EXPLAIN ANALYZE CREATE TEMP TABLE tmp_tmp AS WITH Codes AS ( SELECT chr(ascii('a') + V.n) AS code FROM generate_series(0, 26) V(n) ), params(dtb, dte) AS ( VALUES(now()::date - 30, now()::date) ) SELECT Q.dt, C.code, Q.qty FROM Codes C CROSS JOIN params P CROSS JOIN LATERAL ( SELECT F.dt, COUNT(1) AS qty FROM fact4agg F WHERE F.code=C.code AND F.dt BETWEEN P.dtb AND P.dte GROUP BY F.dt ) Q; Nested Loop (cost=0.46..24324.77 rows=9882 width=44) (actual time=0.114..98.558 rows=837 loops=1) -> Function Scan on generate_series v (cost=0.00..0.27 rows=27 width=4) (actual time=0.005..0.010 rows=27 loops=1) -> GroupAggregate (cost=0.45..891.76 rows=366 width=12) (actual time=0.129..3.644 rows=31 loops=27) Group Key: f.dt -> Index Only Scan using fact4agg_code_dt_idx on fact4agg f (cost=0.45..732.31 rows=31158 width=4) (actual time=0.008..1.876 rows=30971 loops=27) Index Cond: ((code = chr((97 + v.n))) AND (dt >= ((now())::date - 30)) AND (dt <= (now())::date)) Heap Fetches: 0 Planning Time: 0.193 ms Execution Time: 99.835 ms
Kilor Автор
28.11.2023 09:13+1Вполне правильный подход при заведомо малом количестве вариантов - чем-то напоминает "рекурсивный DISTINCT", хотя в общем случае закладываться на такое не выйдет.
ptr128
28.11.2023 09:13Ну я и начал с того, что это эффективно именно при относительно небольшом количестве различных кодов на большом количестве записей.
На практике такой подход хорошо работает даже для 100 тыс. полувагонов и полутора миллиардах событий для них. То есть, при отношении 1/10000 этот подход еще остается эффективным.
Все же, с точки зрения БД, один уровень группировки из двух ей преподносится уже готовым - не требуется считать хеши для HashAggregate.
в общем случае закладываться на такое не выйдет
В общем случае лучше ни на что не закладываться. "Золотого молотка" не бывает )
ptr128
28.11.2023 09:13Обратил внимание, что у Вас не честные TOP 3. Если у каких-то двух code одинаковый qty в какой-то день и оба на третьем месте, то Вы случайным образом одного из них выкидываете. В реальной жизни люди так могут и обидеться.
Корректней выводить с учётом того, что какое-то место могут поделить. То есть делать выборку через DENSE_RANK():
WITH Codes AS ( SELECT chr(ascii('a') + V.n) AS code FROM generate_series(0, 26) V(n) ), params(dtb, dte) AS ( VALUES(now()::date - 30, now()::date) ), Aggregated AS ( SELECT Q.dt, C.code, Q.qty, DENSE_RANK() OVER (PARTITION BY Q.dt ORDER BY Q.qty DESC) AS dr FROM Codes C CROSS JOIN params P CROSS JOIN LATERAL ( SELECT F.dt, COUNT(1) AS qty FROM fact4agg F WHERE F.code=C.code AND F.dt BETWEEN P.dtb AND P.dte GROUP BY F.dt ) Q ) SELECT A.dt, json_agg( json_build_object('rank', A.dr, 'code', A.code, 'qty', A.qty) ORDER BY A.qty DESC ) json FROM Aggregated A WHERE A.dr<=3 GROUP BY A.dt;Но давайте обратим внимание, что мы сортировали данные тут, минимум, дважды - сначала при нумерации, а потом - при свертке в json. Нельзя ли этого избежать?..
Эту проблему PostgreSQL решил самостоятельно:
GroupAggregate (cost=24931.06..25353.55 rows=200 width=36) (actual time=98.812..99.057 rows=31 loops=1) Group Key: f.dt -> WindowAgg (cost=24931.06..25178.11 rows=9882 width=52) (actual time=98.774..98.913 rows=96 loops=1) Run Condition: (dense_rank() OVER (?) <= 3) -> Sort (cost=24931.06..24955.77 rows=9882 width=16) (actual time=98.761..98.799 rows=837 loops=1) Sort Key: f.dt, (count(1)) DESC Sort Method: quicksort Memory: 77kB -> Nested Loop (cost=0.46..24275.36 rows=9882 width=16) (actual time=0.122..98.513 rows=837 loops=1) -> Function Scan on generate_series v (cost=0.00..0.27 rows=27 width=4) (actual time=0.006..0.011 rows=27 loops=1) -> GroupAggregate (cost=0.45..891.76 rows=366 width=12) (actual time=0.133..3.645 rows=31 loops=27) Group Key: f.dt -> Index Only Scan using fact4agg_code_dt_idx on fact4agg f (cost=0.45..732.31 rows=31158 width=4) (actual time=0.011..1.881 rows=30971 loops=27) Index Cond: ((code = chr((97 + v.n))) AND (dt >= ((now())::date - 30)) AND (dt <= (now())::date)) Heap Fetches: 0 Planning Time: 0.284 ms Execution Time: 99.110 msЭто я опять на 10 миллионах развлекался.
Kilor Автор
28.11.2023 09:13Таки да, поэтому в реальности для обеспечения стабильности порядка сортировки приходится сортировать по ФИО, коду страны, дополнительным очкам... но если очень хочется "не обидеть", можно использовать
FETCH WITH TIES.ptr128
28.11.2023 09:13можно использовать
FETCH WITH TIESМожно. Но лучше все же не выбирать в БД записи, которые потом точно не собираетесь фетчить. DENSE_RANK() у меня даже стабильно несколько миллисекунд выигрывал, относительно Вашего решения через массив.
Kilor Автор
28.11.2023 09:13Они фетчатся уже в узле Index Only Scan, если мы считаем агрегаты динамически, а не храним. А если храним - то вычитаем лишь на 1 запись больше указанного лимита.
ptr128
28.11.2023 09:13Посмотрите внимательней на мой запрос. Даже первое место могут поделить не только двое, но и трое, и четверо. Аналогично и со вторым местом. А WITH TIES добавит дубли только одного последнего в выборке места. Что получится, если у Вас первое место поделили четверо? А DENSE_RANK() это отрабатывает честно.
Kilor Автор
28.11.2023 09:13В этом смысле есть разные прикладные задачи.
"10 дипломов первой степени, 20 - второй и 30 - третьей" - это как раз про dense_rank.
"Иванов и Петров поделили 1/2 место, а Сидоров с Васечкиным - 3/4" - про WITH TIES.
ptr128
28.11.2023 09:13Ну так речь именно про дипломы. Второй вариант я очень редко где-то встречал, так как он все равно не позволяет зафиксировать количество лидеров.
Kilor Автор
28.11.2023 09:13Первый вариант - это что-то типа олимпиады по информатике: "кто решил максимум задач - диплом первой степени, на одну меньше - второй".
А второй вариант - это спортивные соревнования "за место" обычно.
ptr128
28.11.2023 09:13А второй вариант - это спортивные соревнования "за место" обычно.
Обычно, так не делается. Например, в легкой атлетике:
Если два (или более) участника показали одинаковый результат, то рассматривается второй результат, независимо от попытки, если и он одинаков, то — третий результат и так до выявления преимущества одного из участников. Если все показатели у них одинаковы, то им дается дополнительная попытка для выявления победителя.
Akina
Если Вы хотите показать пути решения задачи и его оптимизации, то сначала надо как минимум зафиксировать исходные данные и конечный результат. Причём для конечного результата следует зафиксировать и набор полей, и типы данных. Произвольно "договариваться" на середине пути о смене формата вывода - неправильно.
Kilor Автор
Если мы "рулим" обеими сторонами взаимодействия
BL <--> DB, то "договориться" можем в любой момент.Можно ли не сворачивать в json? Конечно, и "отсыпать" TOP-3 за одну дату несколькими записями. Но тогда "агрегировать" в рамках дня придется уже на стороне бизнес-логики, а оно там надо?..