• <menu id="gyiem"><menu id="gyiem"></menu></menu>
  • <menu id="gyiem"><code id="gyiem"></code></menu>

    SQL優化(二) 快速計算Distinct Count

    原創文章,轉載請務必將下面這段話置于文章開頭處(保留超鏈接)。
    本文轉發自技術世界原文鏈接 http://www.luozeyang.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如下

    1
    2
    3
    4
    select 
    count(distinct mac_macaddr)
    from
    testmac

      count group by SQL如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    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。

    1
    2
    3
    4
    5
    6
    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 l
    oops=1)

      而當結果集較大時,無法通過在內存中維護Hash表的方式使用HashAggregation,planner會使用GroupAggregation,并會用到排序,而且因為目標數據集太大,無法在內存中使用Quick Sort,而要在外存中使用Merge Sort,而這就極大的增加了I/O開銷。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    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 loo
    ps=1)

    dinstinct count高效近似算法

      由于distinct count的需求非常普遍(如互聯網中計算UV),而該計算的代價又相比較高,很難適應實時性要求較高的場景,如流計算,因此有很多相關研究試圖解決該問題。比較著名的算法有daptive sampling AlgorithmDistinct Counting with a Self-Learning BitmapHyperLogLogLogLogProbabilistic 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
    2
    3
    4
    5
    6
    7
    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類型的字段中。

    1
    2
    3
    4
    5
    6
    7
    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%。

    1
    2
    3
    4
    5
    6
    7
    8
    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 AlgorithmDistinct Counting with a Self-Learning BitmapHyperLogLogLogLogProbabilistic Counting Algorithms等近似算法。另外,對于data warehouse這種存儲數據量隨著時間不斷超增加且最終數據總量非常巨大的應用場景,可以使用hll這種支持合并dintinct count結果的數據類型,并周期性的(比如daily/weekly/monthly)計算部分數據的distinct值,然后通過合并部分結果的方式得到總結果的方式來快速響應查詢請求。

    SQL優化系列

    郭俊 Jason wechat
    歡迎關注作者微信公眾號【大數據架構】
    您的贊賞將支持作者繼續原創分享
    速赢彩app 贵州贵阳 | 昭通 | 泸州 | 山西太原 | 枣庄 | 石嘴山 | 克孜勒苏 | 吴忠 | 柳州 | 连云港 | 赵县 | 南安 | 荣成 | 铜陵 | 廊坊 | 丹东 | 仙桃 | 肥城 | 曲靖 | 三亚 | 龙岩 | 内江 | 江门 | 梅州 | 台湾台湾 | 池州 | 泰州 | 淮南 | 安庆 | 福建福州 | 陕西西安 | 吴忠 | 娄底 | 泸州 | 柳州 | 广安 | 眉山 | 安顺 | 宣城 | 禹州 | 黔西南 | 安顺 | 燕郊 | 巢湖 | 安吉 | 铜陵 | 三亚 | 柳州 | 中山 | 本溪 | 文山 | 衢州 | 昆山 | 山南 | 武安 | 邹城 | 蚌埠 | 秦皇岛 | 四川成都 | 凉山 | 石河子 | 瑞安 | 项城 | 乌海 | 深圳 | 上饶 | 建湖 | 石河子 | 香港香港 | 衡阳 | 吉林长春 | 黄冈 | 澳门澳门 | 曹县 | 正定 | 大理 | 昌吉 | 博尔塔拉 | 龙岩 | 克孜勒苏 | 岳阳 | 建湖 | 沭阳 | 宁德 | 内蒙古呼和浩特 | 运城 | 顺德 | 三河 | 曲靖 | 广元 | 山东青岛 | 聊城 | 大连 | 邢台 | 仁怀 | 九江 | 果洛 | 宁波 | 平潭 | 忻州 | 宣城 | 东方 | 阳泉 | 台南 | 澄迈 | 哈密 | 泸州 | 桂林 | 霍邱 | 株洲 | 白沙 | 益阳 | 白沙 |