PostgreSQL count-min sketch top-n 概率计算插件 cms_topn (结合窗口实现同比、环比、滑窗分析等) - 流计算核心功能之一
背景
概率计算是流式计算中比较重要的基础，PostgreSQL生态中的pipelinedb提供了诸多概率计算的功能模块。
《[转]流数据库 概率计算概念 - PipelineDB-Probabilistic Data Structures & Algorithms》
由于pipelinedb还没有插件化（估计快了），citusdb社区将pipelinedb中的count-min sketch部分剥离出来，提供了一个插件cms_topn。用于估算TOP-N的值，以及它对应的出现次数。
特别适合于热点分析，例如热点APP，热点店铺，特点商品等。
count-min 论文详见
[
我们可以试一下cms_topn。
部署cms_topn
git clone https://github.com/citusdata/cms_topn
cd cms_topn
git checkout pg9_6_integration
export PATH=/home/digoal/pgsql9.6/bin:$PATH
USE_PGXS=1 make
USE_PGXS=1 make install
psql
create extension cms_topn;
cms_topn用法介绍
类型
新增一个数据类型：cms_topn
这个类型中包括n行m列hash函数值（注册一个n*m的函数值矩阵），同时包含TOP N个值。
因此可以用来求TOP-N，以及它对应的出现次数。
函数接口
1、构造空cms_topn的函数
cms_topn(integer n, double precision errorBound default 0.001, double precision confidenceInterval default 0.99)
参数 n 表示这个cms_topn类型需要存多少个热点值。
概率控制：
The second parameter specifies error bound for the approximation of the frequencies and the third one specifies confidence of the error bound. Size of the sketch is determined with the given error bound and confidence interval according to formula in this paper: http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf. Such as these default values give us an error bound of 0.1% with a confidence of 99% and the created sketch has 5 rows and 2719 columns. Smaller error bound and higher confidence interval require bigger number of columns and rows, respectively. Size informaton of a created sketch can be seen with cms_topn_info function.
2、将单个值添加到cms_topn 类型中，用于单次添加。
cms_topn_add(cms_topn, value)
3、将多个值添加到cms_topn 类型中，用于批量添加。
cms_topn_add_agg(value, integer n, double precision errorBound default 0.001, double precision confidenceInterval default 0.99)
4、查询TOP-N，以及TOP-N VALUE对应的出现频次（类似 count值）。
topn(cms_topn, value)
这里用到的VALUE，是一个空值，主要用于告诉cms_topn里面存的是什么类型。
5、提取某个值的出现频次。
cms_topn_frequency(cms_topn, value)
6、输出一个cms_topn值的统计信息。
cms_topn_info(cms_topn)
例子1
1、构建测试表
create unlogged table test(id int, c1 int);
2、写入测试数据
为了便于分析TOP-N的值效果。我们这里使用高斯分布，生成c1字段的值。
详见：
vi test.sql
\set c1 random_gaussian(1,1000000,1000)
\set id random(1,100)
insert into test values (:id, :c1);
pgbench -M prepared -n -r -P 1 -f ./test.sql -c 32 -j 32 -T 120
3、创建cms_topn表
create unlogged table topn_test(id int primary key, c1_topn cms_topn);
4、生成统计值，并写入cms_topn表。
insert into topn_test select id, cms_topn_add_agg(c1,20) from test group by id;
5、查看cms_topn中的估算top-n值以及出现次数。基本与精确值一致。
select id, topn(c1_topn, null::int) from topn_test where id=1;
id | topn
----+--------------
1 | (499965,255)
1 | (500083,255)
1 | (499769,244)
1 | (500058,243)
1 | (499931,243)
1 | (500035,240)
1 | (499887,239)
1 | (500139,238)
1 | (500046,238)
1 | (499955,238)
1 | (500039,237)
1 | (500005,237)
1 | (500142,237)
1 | (499953,237)
1 | (500148,236)
1 | (499996,235)
1 | (499942,235)
1 | (499948,235)
1 | (500208,235)
1 | (500003,235)
(20 rows)
6、查看原始表的精确统计
select c1,count(*) from test where id=1 group by c1 order by count(*) desc limit 20;
c1 | count
--------+-------
500083 | 255
499965 | 255
499769 | 244
499931 | 243
500058 | 243
500035 | 240
499887 | 239
499955 | 238
500139 | 238
500046 | 238
500039 | 237
499953 | 237
500005 | 237
500142 | 237
500148 | 236
499948 | 235
500208 | 235
499996 | 235
500003 | 235
499942 | 235
(20 rows)
7、查看某个区间的topn的聚合值，（常见于滑窗分析，例如查看最近N天的TOP-N）。
《PostgreSQL SELECT 的高级用法(CTE, LATERAL, ORDINALITY, WINDOW, SKIP LOCKED, DISTINCT, GROUPING SETS, …)》
用到了 cms_topn提供的哈希聚合函数。
select topn(cms_topn_union_agg(c1_topn), null::int) from topn_test where id<=10 ;
topn
---------------
(500003,2250)
(499875,2238)
(499967,2232)
(500004,2227)
(499999,2212)
(499981,2208)
(499902,2206)
(500033,2202)
(500010,2200)
(500014,2198)
(500005,2197)
(499977,2194)
(499965,2193)
(499924,2193)
(499978,2186)
(500022,2186)
(499982,2182)
(500035,2182)
(500029,2181)
(499998,2174)
(20 rows)
对比原始数据，精确度也蛮OK的
select c1,count(*) from test where id<=10 group by c1 order by count(*) desc limit 20;
c1 | count
--------+-------
500003 | 2250
499875 | 2238
499967 | 2232
500004 | 2227
499999 | 2212
499981 | 2208
499902 | 2206
500033 | 2202
500010 | 2200
500014 | 2198
500005 | 2197
499924 | 2193
499977 | 2193
499965 | 2193
500022 | 2186
499978 | 2186
500035 | 2182
499982 | 2182
500016 | 2181
500029 | 2181
(20 rows)
8、查看某个值的出现频率
postgres=# select cms_topn_frequency(c1_topn, 500000) from topn_test where id=1;
cms_topn_frequency
--------------------
206
(1 row)
与精确值一致
postgres=# select count(*) from test where id=1 and c1=500000;
count
-------
206
(1 row)
如果输入了一个不在TOP-N中的值，返回计数0.
postgres=# select cms_topn_frequency(c1_topn, 50000) from topn_test where id=1;
cms_topn_frequency
--------------------
0
(1 row)
9、查看某个cms_topn字段的统计信息
postgres=# select cms_topn_info(c1_topn) from topn_test where id=1;
cms_topn_info
-----------------------------------------------------
Sketch depth = 5, Sketch width = 2719, Size = 106kB
(1 row)
例子2
既然我们可以批量聚合，也可以利用PostgreSQL的规则实现实时聚合，生成cms_topn的统计值。
1、在原始表上面，增加一个规则，当数据写入时，自动将值添加到topn统计表中。
create rule r1 as on insert to test
do also
insert into topn_test values (NEW.id, cms_topn_add(cms_topn(20), NEW.c1))
on conflict (id) do update
set c1_topn=cms_topn_add(topn_test.c1_topn, NEW.c1);
CREATE RULE
2、现在往原始表写入数据，就会自动将数据合并到topn了。
3、其他流式计算的方法，参考：
《PostgreSQL 流式统计 - insert on conflict 实现 流式 UV(distinct), min, max, avg, sum, count …》
《HTAP数据库 PostgreSQL 场景与性能测试之 32 - (OLTP) 高吞吐数据进出(堆存、行扫、无需索引) - 阅后即焚(JSON + 函数流式计算)》
《HTAP数据库 PostgreSQL 场景与性能测试之 31 - (OLTP) 高吞吐数据进出(堆存、行扫、无需索引) - 阅后即焚(读写大吞吐并测)》
《HTAP数据库 PostgreSQL 场景与性能测试之 27 - (OLTP) 物联网 - FEED日志, 流式处理 与 阅后即焚 (CTE)》
《(流式、lambda、触发器)实时处理大比拼 - 物联网(IoT)\金融,时序处理最佳实践》
小结
cms_topn为概率计算的一种，用于生成高频词、高频词的出现次数。
使用cms_topn，按时间区间进行统计，结合WINDOW窗口用法，可以非常快速的生成同比、环比、滑动窗口等top-n的数据。
我在另一篇文档中，提到过HLL的估值计算和滑窗分析，感兴趣的朋友可以观看：
《阿里云 PostgreSQL 产品生态；案例、开发实践、管理实践、学习资料、学习视频》
包含大量案例、开发实践。
参考
《Greenplum 最佳实践 - 估值插件hll的使用(以及hll分式聚合函数优化)》
《PostgreSQL hll (HyperLogLog) extension for “State of The Art Cardinality Estimation Algorithm” - 3》
《PostgreSQL hll (HyperLogLog) extension for “State of The Art Cardinality Estimation Algorithm” - 2》
《PostgreSQL hll (HyperLogLog) extension for “State of The Art Cardinality Estimation Algorithm” - 1》