UDN-企业互联网技术人气社区

板块导航

浏览  : 993
回复  : 1

[讨论交流] SQL优化(二) 快速计算Distinct Count

[复制链接]
cat77的头像 楼主
发表于 2016-8-5 08:00:03 | 显示全部楼层 |阅读模式
本帖最后由 cat77 于 2016-8-6 11:10 编辑

  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如下
复制代码

  count group by SQL如下
  1. select
  2.     count(*)
  3. from
  4.     (select
  5.         mac_macaddr
  6.     from
  7.         testmac
  8.     group by
  9.         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。
  1. explain analyze select count(*) from (select mac_macaddr from testmac_small group by 1) foo;
  2.                                         QUERY PLAN
  3. Aggregate  (cost=668465.04..668465.05 rows=1 width=0) (actual time=9166.486..9166.486 rows=1 loops=1)
  4.    ->  HashAggregate  (cost=668296.74..668371.54 rows=7480 width=6) (actual time=9161.796..9164.393 rows=10001 loops=1)
  5.          ->  Seq Scan on testmac_small  (cost=0.00..572898.79 rows=38159179 width=6) (actual time=323.338..5091.112 rows=10000000 l
  6. oops=1)
复制代码

  而当结果集较大时,无法通过在内存中维护Hash表的方式使用HashAggregation,planner会使用GroupAggregation,并会用到排序,而且因为目标数据集太大,无法在内存中使用Quick Sort,而要在外存中使用Merge Sort,而这就极大的增加了I/O开销。
  1. explain analyze select count(*) from (select mac_macaddr from testmac group by 1) foo;
  2.                                         QUERY PLAN
  3. Aggregate  (cost=1881542.62..1881542.63 rows=1 width=0) (actual time=34288.232..34288.232 rows=1 loops=1)
  4.    ->  Group  (cost=1794262.09..1844329.41 rows=2977057 width=6) (actual time=25291.372..33481.228 rows=3671797 loops=1)
  5.          ->  Sort  (cost=1794262.09..1819295.75 rows=10013464 width=6) (actual time=25291.366..29907.351 rows=10000000 loops=1)
  6.                Sort Key: testmac.mac_macaddr
  7.                Sort Method: external merge  Disk: 156440kB
  8.                ->  Seq Scan on testmac  (cost=0.00..219206.64 rows=10013464 width=6) (actual time=0.082..4312.053 rows=10000000 loo
  9. ps=1)
复制代码

  dinstinct count高效近似算法

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

  • 数据集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能计算几百亿的不同数值并且保证只有很小的误差。

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

Column
Type
Modifiers
day
date

user_id
integer

sales
numeric

  插入三年的数据,并保证总共有10万个不同的user_id,总数据量为1亿条(一天10万条左右)。
  1. insert into fact
  2. select
  3.     current_date - (random()*1095)::integer * '1 day'::interval,
  4.     (random()*100000)::integer + 1,
  5.     random() * 10000 + 500
  6. from
  7.     generate_series(1, 100000000, 1);
复制代码

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

  利用hll,创建daily_unique_user_hll表,将每天的不同用户信息存于hll类型的字段中。
  1. create table daily_unique_user_hll
  2. as select
  3.     day,
  4.     hll_add_agg(hll_hash_integer(user_id))
  5. from
  6.     fact
  7. group by 1;
复制代码

  通过上面的daily aggregation table可计算任意日期范围内的unique user count。如计算整个三年的不同用户数,耗时17.485 ms,查询结果为101044,误差为(101044-100000)/100000=1.044%。
  1. explain analyze select hll_cardinality(hll_union_agg(hll_add_agg)) from daily_unique_user_hll;
  2.                                    QUERY PLAN
  3. Aggregate  (cost=196.70..196.72 rows=1 width=32) (actual time=16.772..16.772 rows=1 loops=1)
  4.    ->  Seq Scan on daily_unique_user_hll  (cost=0.00..193.96 rows=1096 width=32) (actual time=0.298..3.251 rows=
  5. 1096 loops=1)
  6. Planning time: 0.081 ms
  7. Execution time: 16.851 ms
  8. 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优化系列

相关帖子

发表于 2016-8-5 13:54:24 | 显示全部楼层
在互联网中,经常需要计算UV和PV。所谓PV即Page View,网页被打开多少次(YouTube等视频网站非常重视视频的点击率,即被播放多少次,也即PV)。
使用道具 举报

回复

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部