本文共 5592 字，大约阅读时间需要 18 分钟。
PostgreSQL , 概率计算 , pipelinedb , cms_topn , count-min sketch top-n
概率计算是流式计算中比较重要的基础，PostgreSQL生态中的pipelinedb提供了诸多概率计算的功能模块。
由于pipelinedb还没有插件化（估计快了），citusdb社区将pipelinedb中的count-min sketch部分剥离出来，提供了一个插件cms_topn。用于估算TOP-N的值，以及它对应的出现次数。
特别适合于热点分析，例如热点APP，热点店铺，特点商品等。
count-min 论文详见
我们可以试一下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
这个类型中包括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: . 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、构建测试表
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）。
用到了 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)
既然我们可以批量聚合，也可以利用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、其他流式计算的方法，参考：
cms_topn为概率计算的一种，用于生成高频词、高频词的出现次数。
使用cms_topn，按时间区间进行统计，结合WINDOW窗口用法，可以非常快速的生成同比、环比、滑动窗口等top-n的数据。
我在另一篇文档中，提到过HLL的估值计算和滑窗分析，感兴趣的朋友可以观看：
包含大量案例、开发实践。
转载地址：http://aofll.baihongyu.com/