# HLL数据类型
HLL（HyperLoglog）是统计数据集中唯一值个数的高效近似算法。它有着计算速度快，节省空间的特点，不需要直接存储集合本身，而是存储一种名为HLL的数据结构。每当有新数据加入进行统计时，只需要把数据经过哈希计算并插入到HLL中，最后根据HLL就可以得到结果。
HLL与其他算法的比较请参见[表1]。
 表1HLL与其他算法比较 
| 项目     | Sort算法   | Hash算法 | HLL        |
|:---|:---|:---|:---|
| 时间复杂度  | O(nlogn) | O(n)   | O(n)       |
| 空间复杂度  | O(n)     | O(n)   | 1280 bytes |
| 误差率    | 0        | 0      | ≈2%        |
| 所需存储空间 | 原始数据大小   | 原始数据大小 | 1280 bytes |
   
HLL在计算速度和所占存储空间上都占优势。在时间复杂度上，Sort算法需要排序至少O(nlogn)的时间，虽说Hash算法和HLL一样扫描一次全表O(n)的时间就可以得出结果，但是存储空间上，Sort算法和Hash算法都需要先把原始数据存起来再进行统计，会导致存储空间消耗巨大，而对HLL来说不需要存原始数据，只需要维护HLL数据结构，故占用空间始终是1280bytes常数级别。
![](https://support.huaweicloud.com/sqlreference-dws/public_sys-resources/note_3.0-zh-cn.png)
- 当前默认规格下可计算最大distinct值的数量为1.6e+12个，误差率最大仅2.3%。用户应注意如果计算结果超过当前规格下distinct最大值会导致计算结果误差率变大，或导致计算结果失败并报错。
- 用户在首次使用该特性时，应该对业务的distinct value做评估，选取适当的配置参数并做验证，以确保精度符合要求：
  - 当前默认参数下，可以计算的distinct value值为1.6e+12，如果计算得到的distinct value值为NaN，需要调整log2m和regwidth来容纳更多的distinct value。
  
  - 虽然hash算法存在极低的hash collision概率，但是建议用户在首次使用时，选取2-3个hash seed验证，如果得到的distinct value相差不大，则可以从该组seed中任选一个作为hash seed。
   
 
HLL中主要的数据结构，请参见[表2]。
 表2HyperLogLog中主要数据结构 
| 数据类型 | 功能描述                               |
|:---|:---|
| hll  | 大小为确定的1280 bytes，可直接计算得到distinct值。 |
   
#### HLL的应用场景
- 使用hll数据类型场景
  1. 创建带有hll类型的表并向表中插入空的hll。
     ```
     CREATE TABLE helloworld (id integer, col hll);
     INSERT INTO helloworld(id, col) VALUES (1, hll_empty());
     ```
     
  
  2. 把整数经过哈希计算加入到hll中。
     ```
     UPDATE helloworld SET col = hll_add(col, hll_hash_integer(12345)) WHERE id = 1;
     ```
     
  
  3. 把字符串经过哈希计算加入到hll中。
     ```
     UPDATE helloworld SET col = hll_add(col, hll_hash_text('hello world')) WHERE id = 1;
     ```
     
  
  4. 得到hll中的distinct值。
     ```
     SELECT hll_cardinality(col) FROM helloworld WHERE id = 1;
      hll_cardinality 
     -----------------
                    2
     (1 row)
     ```
     
   
- 使用hll进行网站访客统计场景
  1. 创建原始数据表facts，记录用户访问网站时间。
     ```
     CREATE TABLE facts (
              date            date,
              user_id         integer
     );
     ```
     
  
  2. 插入用户访问过网站的数据。
     ```
     INSERT INTO facts VALUES ('2019-02-20', generate_series(1,100));
     INSERT INTO facts VALUES ('2019-02-21', generate_series(1,200));
     INSERT INTO facts VALUES ('2019-02-22', generate_series(1,300));
     INSERT INTO facts VALUES ('2019-02-23', generate_series(1,400));
     INSERT INTO facts VALUES ('2019-02-24', generate_series(1,500));
     INSERT INTO facts VALUES ('2019-02-25', generate_series(1,600));
     INSERT INTO facts VALUES ('2019-02-26', generate_series(1,700));
     INSERT INTO facts VALUES ('2019-02-27', generate_series(1,800));
     ```
     
  
  3. 创建表并指定列为hll。根据日期把数据分组，并把数据插入到hll中。
     ```
     CREATE TABLE daily_uniques (
         date            date UNIQUE,
         users           hll
     );
      
     INSERT INTO daily_uniques(date, users)
         SELECT date, hll_add_agg(hll_hash_integer(user_id))
         FROM facts
         GROUP BY 1;
     ```
     
  
  4. 计算每一天访问网站不同用户数量。
     ```
     SELECT date, hll_cardinality(users) FROM daily_uniques ORDER BY date;
             date         | hll_cardinality  
     ---------------------+------------------
      2019-02-20 00:00:00 |              100
      2019-02-21 00:00:00 | 203.813355588808
      2019-02-22 00:00:00 | 308.048239950384
      2019-02-23 00:00:00 | 410.529188080374
      2019-02-24 00:00:00 | 513.263875705319
      2019-02-25 00:00:00 | 609.271181107416
      2019-02-26 00:00:00 | 702.941844662509
      2019-02-27 00:00:00 | 792.249946595237
     (8 rows)
     ```
     
  
  5. 计算在2019.02.20到2019.02.26一周中有多少不同用户访问过网站。
     ```
     SELECT hll_cardinality(hll_union_agg(users)) FROM daily_uniques WHERE date >= '2019-02-20'::date AND date <= '2019-02-26'::date;
      hll_cardinality  
     ------------------
      702.941844662509
     (1 row)
     ```
     
  
  6. 计算昨天访问过网站而今天没访问网站的用户数量。
     ```
     SELECT date,  OVER two_days) - #users AS lost_uniques FROM daily_uniques WINDOW two_days AS (ORDER BY date ASC ROWS 1 PRECEDING);                                                                                                             
             date         | lost_uniques 
     ---------------------+--------------
      2019-02-20 00:00:00 |            0
      2019-02-21 00:00:00 |            0
      2019-02-22 00:00:00 |            0
      2019-02-23 00:00:00 |            0
      2019-02-24 00:00:00 |            0
      2019-02-25 00:00:00 |            0
      2019-02-26 00:00:00 |            0
      2019-02-27 00:00:00 |            0
     (8 rows)
     ```
     
   
- 插入数据不满足hll数据结构要求时报错场景 当用户给hll类型的字段插入数据的时候，必须保证插入的数据满足hll数据结构要求，如果解析后不满足就会报错。
  例如： 插入数据'E\\\\1234'时，该数据不满足hll数据结构，不能解析成功因此失败报错。
  ```
  CREATE TABLE test(id integer, col hll);
  INSERT INTO test VALUES(1, 'E\\1234');
  ERROR:  invalid input syntax for integer: "E\\1234"
  ```