Компания Citus Data, развивающая распределённую СУБД CitusDB, опубликовала исходные тексты TopN, расширения для PotgreSQL, позволяющего эффективно рассчитывать выборки наиболее популярных значений в записях. Код расширения поставляется под лицензией AGPLv3.

При большом объёме данных формирование выборок, рассчитывающих популярные значения в разрезе времени (например, вывод самых популярных страниц из лога запросов web-сервера в разрезе по дням или группировка популярных товаров по дням/категориям) является достаточно ресурсоёмкой задачей. Для ускорения построения подобных выборок TopN использует алгоритм приближённой оценки результата и предварительное агрегирование записей в компактный хэш со счётчиками наиболее популярных значений, сохраняемый в отдельной таблице с использованием типа JSONB. Агрегированные данные можно инкрементально обновлять для приведения к актуальному состоянию. Произвольные выборки над агрегированными данными производятся при помощи функции topn() и выполняются почти мгновенно, независимо от фактического размера исходных данных для анализа.

Например:

— создадим таблицу с агрегированными данными для расчёта рейтинга в разрезе “дата – имя”
# create table aggregated_topns (day date, topn jsonb);
CREATE TABLE
Time: 9.593 ms

— выполняем один раз ресурсоёмкую операцию агрегирования данных и заносим
— в ранее созданную таблицу сведения о частоте 1000 самых популярных элементов.
# insert into aggregated_topns select date_trunc(‘day’, created_at), topn_add_agg((repo::json)->> ‘name’) as topn from github_events group by 1;
INSERT 0 7
Time: 34904.259 ms (00:34.904)

— формируем top 10 за 2 и 3 января.
postgres=# select (topn(topn_union_agg(topn), 10)).* from aggregated_topns where day IN (‘2018-01-02’, ‘2018-01-03’);
item | frequency
————————————————+———–
dipper-github-fra-sin-syd-nrt/test-ruby-sample | 12489
wangshub/wechat_jump_game | 6402
shenzhouzd/update | 6170
SCons/scons | 4593
TheDimPause/thedimpause.github.io | 3964
nicopeters/sigrhtest | 3740
curtclifton/curtclifton.github.io | 3345
CreatorB/hackerdroid | 3206
dipper-github-icn-bom-cdg/test-ruby-sample | 3126
dotclear/dotclear | 2992
(10 rows)

Time: 7.750 ms

— формируем раздельные top 2 за 1,2 и 3 января.
postgres=# select day, (topn(topn, 2)).* from aggregated_topns where day IN (‘2018-01-01’, ‘2018-01-02’, ‘2018-01-03’);
day | item | frequency
————+————————————————+———–
2018-01-01 | dipper-github-fra-sin-syd-nrt/test-ruby-sample | 9179
2018-01-01 | shenzhouzd/update | 4543
2018-01-02 | dipper-github-fra-sin-syd-nrt/test-ruby-sample | 7151
2018-01-02 | SCons/scons | 4593
2018-01-03 | dipper-github-fra-sin-syd-nrt/test-ruby-sample | 5338
2018-01-03 | CreatorB/hackerdroid | 3206
(6 rows)

Time: 4.037 ms