概述

在實際的業務場景中，隨著業務數據量的不斷增加，數據去重的壓力也隨之增大。當數據規模達到一定程度時，采用精準去重的成本也隨之增加。在業務可接受的情況下，通過近似算法來快速去重，降低計算壓力，是一種非常有效的方式。

針對這種場景，SelectDB提供了近似去重算法HyperLogLog（簡稱 HLL）。HLL的特點是具有非常優異的空間復雜度O(log(logn))和時間復雜度O(n)，并且計算結果的誤差可控制在1%~2%左右（誤差與數據集大小以及所采用的哈希函數有關）。

HyperLogLog原理

近似去重算法HyperLogLog是LogLog算法的升級版，作用是能夠提供不精確的去重計數，其數學基礎為伯努利試驗。

數學基礎

在伯努利試驗中，假設硬幣擁有正反兩面，一次拋硬幣中最終出現正反面的概率都是50%。若將“一直拋硬幣，直到它出現正面為止”記錄為一次完整的試驗，那么對于n次伯努利試驗，就意味著出現了n次的正面。

假設每次伯努利試驗所經歷了的拋擲次數為k，第一次伯努利試驗的次數設為k1，第n次對應的是kn，以此類推。那么在這之中，對于這n次伯努利試驗，必然會有一個最大的拋擲次數k，意味著拋了k次才出現正面，稱這個次數為k_max，代表拋了最多的次數。那么，伯努利試驗容易得出有以下結論：

• n次伯努利過程的投擲次數都不大于k_max。

• n次伯努利過程，至少有一次投擲次數等于k_max。

結合極大似然估算的方法，發現在n和k_max中存在估算關聯：n = 2 ^ k_max。當我們只記錄了k_max時，即可估算總共有多少條數據，也就是基數。

估算誤差

假設試驗結果如下：

• 第1次試驗：拋了3次才出現正面，此時 k=3，n=1。

• 第2次試驗：拋了2次才出現正面，此時 k=2，n=2。

• 第3次試驗：拋了6次才出現正面，此時 k=6，n=3。

• ...

• 第n次試驗：拋了12次才出現正面，此時我們估算n = 2^12。

取上面例子中前三組試驗，那么k_max = 6，最終n=3。我們放進估算公式中去，明顯3 ≠ 2^6 。也即是說，當試驗次數很小的時候，這種估算方法的誤差是很大的。

這三組試驗，稱為一輪的估算。如果只是進行一輪的話，當n足夠大的時候，估算的誤差率會相對減少，但仍然不夠小。

SelectDB HLL函數

HLL是基于HyperLogLog算法的工程實現，用于保存HyperLogLog計算過程的中間結果，它只能作為表的Value列類型、通過聚合來不斷的減少數據量，以此來實現加快查詢的目的?；谒玫降氖且粋€估算結果，誤差大概在1%左右。HLL列是通過其它列或者導入數據里面的數據生成的，導入的時候通過hll_hash函數來指定數據中哪一列用于生成HLL列。它常用于替代count distinct，與ROLLUP結合在業務上用于快速計算獨立訪客UV（Unique Visitor）等。

HLL函數有以下幾個。

• HLL_UNION_AGG(hll)

  此函數為聚合函數，用于計算滿足條件的所有數據的基數估算。

• HLL_CARDINALITY(hll)

  此函數用于計算單條HLL列的基數估算。

• HLL_HASH(column_name)

  生成HLL列類型，用于Insert或導入數據時，導入的使用請參見使用示例。

使用示例

1. 創建一張含有HLL列的表

   CREATE TABLE test_hll(
       dt date,
       id int,
       name char(10),
       province char(10),
       os char(10),
       pv hll hll_union
   )
   Aggregate KEY (dt,id,name,province,os)
   distributed by hash(id) buckets 10
   PROPERTIES(
       "replication_num" = "1",
       "in_memory"="false"
   );

   重要

   使用HLL需要注意以下問題。

   • 使用HLL去重的時候，需要在建表語句中將目標列類型設置成HLL，聚合函數設置成HLL_UNION。

   • HLL類型的列不能作為Key列使用。

   • 不需要指定長度及默認值，長度根據數據聚合程度在系統內控制。

2. 導入數據

   示例數據如下（test_hll.csv）。

   2022-05-05,10001,測試01,北京,windows
   2022-05-05,10002,測試01,北京,linux
   2022-05-05,10003,測試01,北京,macos
   2022-05-05,10004,測試01,河北,windows
   2022-05-06,10001,測試01,上海,windows
   2022-05-06,10002,測試01,上海,linux
   2022-05-06,10003,測試01,江蘇,macos
   2022-05-06,10004,測試01,陜西,windows

   使用不同的導入方式如下。

   • 使用Stream Load導入，示例如下。

     # curl --location-trusted -u root: -H "label:label_test_hll_load" -H "column_separator:," -H "columns:dt,id,name,province,os,pv=hll_hash(id)" -T test_hll.csv http://127.0.0.1:8030/api/demo/test_hll/_stream_load
     
     {
         "TxnId": 693,
         "Label": "label_test_hll_load",
         "TwoPhaseCommit": "false",
         "Status": "Success",
         "Message": "OK",
         "NumberTotalRows": 8,
         "NumberLoadedRows": 8,
         "NumberFilteredRows": 0,
         "NumberUnselectedRows": 0,
         "LoadBytes": 320,
         "LoadTimeMs": 23,
         "BeginTxnTimeMs": 0,
         "StreamLoadPutTimeMs": 1,
         "ReadDataTimeMs": 0,
         "WriteDataTimeMs": 9,
         "CommitAndPublishTimeMs": 11
     }

   • 使用Broker Load導入，示例如下。

     LOAD LABEL demo.test_hlllabel
      (
         DATA INFILE("hdfs://hdfs_host:hdfs_port/user/doris_test_hll/data/input/file")
         INTO TABLE `test_hll`
         COLUMNS TERMINATED BY ","
         (dt,id,name,province,os)
         SET (
           pv = HLL_HASH(id)
         )
      );

3. 查詢數據

   HLL列不允許直接查詢原始值，只能通過HLL的聚合函數進行查詢。

   • 求總的PV，示例如下。

     SELECT HLL_UNION_AGG(pv) FROM test_hll;
     +---------------------+
     | hll_union_agg(`pv`) |
     +---------------------+
     |                   4 |
     +---------------------+
     1 row in set (0.00 sec)

     等價于使用(DISTINCT pv)查詢。

     SELECT COUNT(DISTINCT pv) FROM test_hll;
     +----------------------+
     | count(DISTINCT `pv`) |
     +----------------------+
     |                    4 |
     +----------------------+
     1 row in set (0.01 sec)

   • 求每一天的PV，示例如下。

     SELECT HLL_UNION_AGG(pv) FROM test_hll GROUP BY dt;
     +---------------------+
     | hll_union_agg(`pv`) |
     +---------------------+
     |                   4 |
     |                   4 |
     +---------------------+
     2 rows in set (0.01 sec)