# PostgreSQL count-min sketch top-n 概率计算插件 cms_topn (结合窗口实现同比、环比、滑窗分析等) - 流计算核心功能之一

## 背景

《[转]流数据库 概率计算概念 - PipelineDB-Probabilistic Data Structures & Algorithms》

count-min 论文详见

[](20180301_03_pdf_001.pdf)

## 部署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用法介绍

### 函数接口

1、构造空cms_topn的函数

``````cms_topn(integer n, double precision errorBound default 0.001, double precision confidenceInterval default 0.99)
``````

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)
``````

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、写入测试数据

《生成泊松、高斯、指数、随机分布数据 - PostgreSQL 9.5 new feature - pgbench improve, gaussian (standard normal) & exponential distribution》

``````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, …)》

``````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)
``````

``````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)
``````

``````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

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

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为概率计算的一种，用于生成高频词、高频词的出现次数。

《阿里云 PostgreSQL 产品生态；案例、开发实践、管理实践、学习资料、学习视频》

## 参考

《生成泊松、高斯、指数、随机分布数据 - PostgreSQL 9.5 new feature - pgbench improve, gaussian (standard normal) & exponential distribution》

《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》

Tags:

Updated: