快速計算Distinct Count

標簽

PostgreSQL , 估值計算 , PipelineDB , hll , bloom , T-D , TOP-K , SSF

背景

本文轉發自技術世界，原文鏈接　https://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，都是在保證誤差較小的情況下高效計算出結果。本文分別就這幾種算法做了兩組實驗。

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

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

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

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

https://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能計算幾百億的不同數值並且保證隻有很小的誤差。

https://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值，然後通過合並部分結果的方式得到總結果的方式來快速響應查詢請求。