[转] 快速计算Distinct Count

2 minute read

背景

本文转发自技术世界，原文链接　http://www.jasongj.com/2015/03/15/count_distinct/

正文

UV vs. PV

在互联网中，经常需要计算UV和PV。所谓PV即Page View，网页被打开多少次（YouTube等视频网站非常重视视频的点击率，即被播放多少次，也即PV）。而UV即Unique Visitor（微信朋友圈或者微信公众号中的文章则统计有多少人看过该文章，也即UV。虽然微信上显示是指明该值是PV，但经笔者测试，实为UV）。这两个概念非常重要，比如淘宝卖家在做活动时，他往往需要统计宝贝被看了多少次，有多少个不同的人看过该活动介绍。至于如何在互联网上唯一标识一个自然人，也是一个难点，目前还没有一个非常准确的方法，常用的方法是用户名加cookie，这里不作深究。

count distinct vs. count group by

很多情景下，尤其对于文本类型的字段，直接使用count distinct的查询效率是非常低的，而先做group by更count往往能提升查询效率。但实验表明，对于不同的字段，count distinct与count group by的性能并不一样，而且其效率也与目标数据集的数据重复度相关。

本节通过几组实验说明了不同场景下不同query的不同效率，同时分析性能差异的原因。 （本文所有实验皆基于PostgreSQL 9.3.5平台）

分别使用count distinct 和 count group by对 bigint, macaddr, text三种类型的字段做查询。

首先创建如下结构的表

Column Type Modifiers
mac_bigint bigint -
mac_macaddr macaddr -
mac_text text -

并插入1000万条记录，并保证mac_bigint为mac_macaddr去掉冒号后的16进制转换而成的10进制bigint，而mac_text为mac_macaddr的文本形式，从而保证在这三个字段上查询的结果，并且复杂度相同。

count distinct SQL如下

select   
    count(distinct mac_macaddr)   
from   
    testmac

count group by SQL如下

select  
    count(*)  
from  
    (select  
        mac_macaddr  
    from  
        testmac  
    group by  
        1) foo

对于不同记录数较大的情景（1000万条记录中，有300多万条不同记录），查询时间（单位毫秒）如下表所示。

query/字段类型 macaddr bigint text
count distinct 24668.023 13890.051 149048.911
count group by 32152.808 25929.555 159212.700

对于不同记录数较小的情景（1000万条记录中，只有1万条不同记录），查询时间（单位毫秒）如下表所示。

query/字段类型 macaddr bigint text
count distinct 20006.681 9984.763 225208.133
count group by 2529.420 2554.720 3701.869

从上面两组实验可看出，在不同记录数较小时，count group by性能普遍高于count distinct，尤其对于text类型表现的更明显。而对于不同记录数较大的场景，count group by性能反而低于直接count distinct。为什么会造成这种差异呢，我们以macaddr类型为例来对比不同结果集下count group by的query plan。

当结果集较小时，planner会使用HashAggregation。

explain analyze select count(*) from (select mac_macaddr from testmac_small group by 1) foo;  
                                        QUERY PLAN  
 Aggregate  (cost=668465.04..668465.05 rows=1 width=0) (actual time=9166.486..9166.486 rows=1 loops=1)  
   ->  HashAggregate  (cost=668296.74..668371.54 rows=7480 width=6) (actual time=9161.796..9164.393 rows=10001 loops=1)  
         ->  Seq Scan on testmac_small  (cost=0.00..572898.79 rows=38159179 width=6) (actual time=323.338..5091.112 rows=10000000 loops=1)

而当结果集较大时，无法通过在内存中维护Hash表的方式使用HashAggregation，planner会使用GroupAggregation，并会用到排序，而且因为目标数据集太大，无法在内存中使用Quick Sort，而要在外存中使用Merge Sort，而这就极大的增加了I/O开销。

explain analyze select count(*) from (select mac_macaddr from testmac group by 1) foo;  
                                        QUERY PLAN  
 Aggregate  (cost=1881542.62..1881542.63 rows=1 width=0) (actual time=34288.232..34288.232 rows=1 loops=1)  
   ->  Group  (cost=1794262.09..1844329.41 rows=2977057 width=6) (actual time=25291.372..33481.228 rows=3671797 loops=1)  
         ->  Sort  (cost=1794262.09..1819295.75 rows=10013464 width=6) (actual time=25291.366..29907.351 rows=10000000 loops=1)  
               Sort Key: testmac.mac_macaddr  
               Sort Method: external merge  Disk: 156440kB  
               ->  Seq Scan on testmac  (cost=0.00..219206.64 rows=10013464 width=6) (actual time=0.082..4312.053 rows=10000000 loops=1)

dinstinct count高效近似算法

由于distinct count的需求非常普遍（如互联网中计算UV），而该计算的代价又相比较高，很难适应实时性要求较高的场景，如流计算，因此有很多相关研究试图解决该问题。比较著名的算法有daptive sampling Algorithm，Distinct Counting with a Self-Learning Bitmap，HyperLogLog，LogLog，Probabilistic Counting Algorithms。这些算法都不能精确计算distinct count，都是在保证误差较小的情况下高效计算出结果。本文分别就这几种算法做了两组实验。

http://en.wikipedia.org/wiki/Adaptive_sampling

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4812493&tag=1

http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf

http://algo.inria.fr/flajolet/Publications/DuFl03-LNCS.pdf

http://www.mathcs.emory.edu/~cheung/papers/StreamDB/Probab/1985-Flajolet-Probabilistic-counting.pdf

数据集100万条，每条记录均不相同，几种算法耗时及内存使用如下。

algorithm result error time(ms) memory (B)
count(distinct) 1000000 0% 14026 ？
Adaptive Sampling 1008128 0.8% 8653 57627
Self-learning Bitmap 991651 0.9% 1151 65571
Bloom filter 788052 22% 2400 1198164
Probalilistic Counting 1139925 14% 3613 95
PCSA 841735 16% 842 495

数据集100万条，只有100条不同记录，几种近似算法耗时及内存使用如下。

algorithm| result| error| time(ms)| memory (B)
—|—|—|—|—
count(distinct)| 100| 0%| 75306| ？
Adaptive Sampling| 100| 0%| 1491| 57627
Self-learning Bitmap| 101| 1%| 1031| 65571
Bloom filter| 100| 0%| 1675| 1198164
Probalilistic Counting| 95| 5%| 3613| 95
PCSA| 98| 2%| 852| 495
　　
从上面两组实验可看出，大部分的近似算法工作得都很好，其速度都比简单的count distinct要快很多，而且它们对内存的使用并不多而结果去非常好，尤其是Adaptive Sampling和Self-learning Bitmap，误差一般不超过1%，性能却比简单的count distinct高十几倍乃至几十倍。 　　

distinct count结果合并

如上几种近似算法可以极大提高distinct count的效率，但对于data warehouse来说，数据量非常大，可能存储了几年的数据，为了提高查询速度，对于sum及avg这些aggregation一般会创建一些aggregation table。比如如果要算过去三年的总营业额，那可以创建一张daily/monthly aggregation table，基于daily/monthly表去计算三年的营业额。但对于distinct count，即使创建了daily/monthly aggregation table，也没办法通过其计算三年的数值。这里有种新的数据类型hll，这是一种HyperLogLog数据结构。一个1280字节的hll能计算几百亿的不同数值并且保证只有很小的误差。

http://research.neustar.biz/2012/10/25/sketch-of-the-day-hyperloglog-cornerstone-of-a-big-data-infrastructure/

首先创建一张表(fact)，结构如下

Column Type Modifiers
day date -
user_id integer -
sales numeric -

插入三年的数据，并保证总共有10万个不同的user_id，总数据量为1亿条（一天10万条左右）。

insert into fact  
select  
    current_date - (random()*1095)::integer * '1 day'::interval,  
    (random()*100000)::integer + 1,  
    random() * 10000 + 500  
from  
    generate_series(1, 100000000, 1);

直接从fact表中查询不同用户的总数，耗时115143.217 ms。

利用hll，创建daily_unique_user_hll表，将每天的不同用户信息存于hll类型的字段中。

create table daily_unique_user_hll   
as select  
    day,   
    hll_add_agg(hll_hash_integer(user_id))  
from   
    fact  
group by 1;

通过上面的daily aggregation table可计算任意日期范围内的unique user count。如计算整个三年的不同用户数，耗时17.485 ms，查询结果为101044，误差为(101044-100000)/100000=1.044%。

explain analyze select hll_cardinality(hll_union_agg(hll_add_agg)) from daily_unique_user_hll;  
                                   QUERY PLAN  
 Aggregate  (cost=196.70..196.72 rows=1 width=32) (actual time=16.772..16.772 rows=1 loops=1)  
   ->  Seq Scan on daily_unique_user_hll  (cost=0.00..193.96 rows=1096 width=32) (actual time=0.298..3.251 rows=1096 loops=1)  
 Planning time: 0.081 ms  
 Execution time: 16.851 ms  
 Time: 17.485 ms

而如果直接使用count distinct基于fact表计算该值，则耗时长达 127807.105 ms。
　　
从上面的实验中可以看到，hll类型实现了distinct count的合并，并可以通过hll存储各个部分数据集上的distinct count值，并可通过合并这些hll值来快速计算整个数据集上的distinct count值，耗时只有直接使用count distinct在原始数据上计算的1/7308，并且误差非常小，1%左右。 　　

总结

如果必须要计算精确的distinct count，可以针对不同的情况使用count distinct或者count group by来实现较好的效率，同时对于数据的存储类型，能使用macaddr/intger/bigint的，尽量不要使用text。
　　
另外不必要精确计算，只需要保证误差在可接受的范围之内，或者计算效率更重要时，可以采用本文所介绍的daptive sampling Algorithm，Distinct Counting with a Self-Learning Bitmap，HyperLogLog，LogLog，Probabilistic Counting Algorithms等近似算法。另外，对于data warehouse这种存储数据量随着时间不断超增加且最终数据总量非常巨大的应用场景，可以使用hll这种支持合并dintinct count结果的数据类型，并周期性的（比如daily/weekly/monthly）计算部分数据的distinct值，然后通过合并部分结果的方式得到总结果的方式来快速响应查询请求。

SQL优化系列

SQL优化（一） Merge Join vs. Hash Join vs. Nested Loop

http://www.jasongj.com/2015/03/07/Join1/

SQL优化（二） 快速计算Distinct Count

http://www.jasongj.com/2015/03/15/count_distinct/

SQL优化（三） PostgreSQL Table Partitioning

http://www.jasongj.com/2015/12/13/SQL3_partition/

SQL优化（四） Postgre Sql存储过程

http://www.jasongj.com/2015/12/27/SQL4_%E5%AD%98%E5%82%A8%E8%BF%87%E7%A8%8B_Store%20Procedure/

SQL优化（五） PostgreSQL （递归）CTE 通用表表达式

http://www.jasongj.com/sql/cte/

参考

http://docs.pipelinedb.com/builtin.html#t-digest-functions

https://github.com/aggregateknowledge/postgresql-hll

https://www.citusdata.com/blog/2017/04/04/distributed_count_distinct_with_postgresql/

https://github.com/conversant/postgres_hyperloglog

Flag Counter

digoal’s 大量PostgreSQL文章入口

You May Also Enjoy

PostgreSQL(PPAS 兼容Oracle) 从零开始入门手册 - 珍藏版

17 minute read

背景 云数据库PPAS版，是阿里云与EnterpriseDB公司(简称EDB)合作基于PostgreSQL高度兼容Oracle语法的数据库服务，为用户提供易于操作的迁移工具，兼容范围涵盖：PL/SQL、数据类型、高级函数、表分区等。 用户可以直接在阿里云购买PPAS进行使用。 如果在购买PPAS前，想试用一下...

PostgreSQL pipelinedb 流计算插件 - IoT应用 - 实时轨迹聚合

1 minute read

背景 IoT场景，车联网场景，共享单车场景，人的行为位点等，终端实时上报的是孤立的位点，我们需要将其补齐成轨迹。 例如共享单车，下单，开锁，生成订单，骑行，关闭订单，关锁。这个过程有一个唯一的订单号，每次上报的位点会包含时间，订单号，位置。 根据订单号，将点聚合为轨迹。 使用pipelinedb插件，可以实...

PostgreSQL datediff 日期间隔（单位转换）兼容SQL用法

2 minute read

背景 使用datediff，对时间或日期相减，得到的间隔，转换为目标单位(日、月、季度、年、小时、秒。。。等)的数值。 DATEDIFF ( datepart, {date|timestamp}, {date|timestamp} ) 周 select datediff(week,'2009-01-0...