PostgreSQL HLL插件介紹—晟數學院

更多精彩内容：請登入：ke.sandata.com.cn

前言

HLL是 HyperLogLog資料結構的簡稱。PostgresSQL通過插件的方式引入了這種新的資料類型hll。HyperLogLog是一個具有固定大小，類似于集合結構，用于可調精度的不同值計數。例如，在1280位元組的hll資料結構中，它可以在很小的誤差範圍内估算出數百億的不同值計數。

算法

hll可以被視為層次結構的不同集合/不同值計數算法的組合，并向上移動該層次結構的規則。為了區分上述描述算法，将其命名為以下:

♠ EMPTY

表示空集的常量值

♠ EXPLICIT

集合中确定的，唯一的，排序完整的整數清單，該清單保持一個固定的基數

♠ SPARSE

HyperLogLog是基于映射的“惰性”實作，是一種基于機率集合的資料結構。僅将非零寄存器的索引和值存儲在 map中，直到非零寄存器的數量超過固定的基數。

♠ FULL

HyperLogLog是一個完全物化，基于清單的實作。它将每個寄存器的值顯式存儲在按寄存器索引排序的清單中。

PostgreSQL HLL插件介紹—晟數學院

基本概念

基數計數

用來統計一個集合中不重複的元素的個數。

基數計數實作

假設一個集合為Su,用列舉法表示{2,3,1,4,5,9},如果此時有一個新的元素Xi=3要加入到集合Su中。如果Su中包含該元素,那麼該元素将不會被加入到集合Su中，否則，加入該元素到集合中，計數值為Su，即基數值為元素的中非相同值的個數。如集合中{1,2,3,5,2}，基數為4，因為2是 DV（Distinct Value），不被計算到基數中。

該實作有兩個問題：

當集合無限增加，元素增多時，相應的存儲記憶體也會無限增長
當集合無線增加，元素增多，判斷是否包含待加入元素的成本也将增加。

實作動機

最初擴充原始HLL算法如下：

一般情況下，一個HLL占用 regwidth * 2^log2m 位存儲。
典型使用中，log2m = 11 和 regwidth = 5時，将請求需要10240位或者1280個位元組。即 5 * 2^11 = 5* 2048 = 10240
還有一種就是有很多的位元組

最初的HLL算法的第一個補充來自于實作1280個位元組需要160個64位整數的大小。是以，如果希望在低基數下獲得更高的準确性，則可以将一組明确的輸入保留為64位整數的排序清單，直到達到第161個不同的值為止。這将為提供流中不同值的真實表示，同時需要相同數量的記憶體。（這是EXPLICIT算法）。

第二個是不需要存儲值為零的寄存器。可以簡單地将一組具有非零值的寄存器表示為從索引到值的映射。該映射存儲為索引值對的清單，這些索引值對是長度為log2m + regwidth的bit-packed的“short words”。（這是SPARSE算法。）

結合這兩種增強，得到了一個“promotion hierarchy”，可以對算法進行調整以提高準确性，記憶體或性能。

初始化和存儲新的hll對象将僅配置設定一個小的小标記值，該值表示空集（EMPTY）。當添加前幾個值時，唯一整數的排序清單存儲在EXPLICIT集中。當希望停止權衡記憶體的準确性時，已排序清單中的值将“promoted”為基于SPARSE映射的HyperLogLog結構。最後，當有足夠的寄存器時，基于映射的HLL将轉換為位打包的FULL HLL結構。

自然地，EMPTY和EXPLICIT表示的基數估計是準确的，而SPARSE和FULL表示的準确性受原始HLL算法提供的保證的限制。

PostgreSQL HLL插件介紹—晟數學院

安裝和使用HLL

解壓安裝包

[postgres@pgserver plugin]$ ls
postgresql-hll-2.15.1  postgresql-hll-2.15.1.tar.gz
[postgres@pgserver plugin]$ cd postgresql-hll-2.15.1
[postgres@pgserver postgresql-hll-2.15.1]$ ls
CHANGELOG.md  expected     include  Makefile   REFERENCE.md  src
DEVELOPER.md  hll.control  LICENSE  README.md  sql           update

編譯安裝

[postgres@pgserver postgresql-hll-2.15.1]$ make -j24 && make install

測試

[postgres@pgserver postgresql-hll-2.15.1]$ psql -d postgres
psql (13.2)
Type "help" for help.

postgres=# CREATE EXTENSION hll;
CREATE EXTENSION
postgres=#

建構資料

CREATE TABLE helloworld
  (
    id integer,
    set hll
  )
;
--- Insert an empty HLL
INSERT INTO helloworld
  (id,
    set
  )
  VALUES
  (1,
    hll_empty()
  )
;

--- Add a hashed integer to the HLL
UPDATE
  helloworld
SET
set = hll_add(set, hll_hash_integer(12345))
WHERE
  id = 1
;

--- Or add a hashed string to the HLL
UPDATE
  helloworld
SET
set = hll_add(set, hll_hash_text('hello world'))
WHERE
  id = 1
;

--- Get the cardinality of the HLL
SELECT
  hll_cardinality(set)
FROM
  helloworld
WHERE
  id = 1
;
postgres=# SELECT
postgres-#   hll_cardinality(set)
postgres-# FROM
postgres-#   helloworld
postgres-# WHERE
postgres-#   id = 1
postgres-# ;
 hll_cardinality 
-----------------
               2
(1 row)

postgres=# SELECT * FROM helloworld ;
 id |                   set                    
----+------------------------------------------
  1 | \x128b7faaebcf97601e5541533f6046eb7f610e

從上面的示例中得到，首先建構了一個空的hll集合，然後向該集合中添加了兩個值，那麼得到的該hll的基數計數就是2。

PostgreSQL HLL插件介紹—晟數學院

接下來看一個更加實用的用例：

建立網站通路事實表和使用者日通路表

CREATE TABLE facts (
    date            date,
    user_id         integer,
    activity_type   smallint,
    referrer        varchar(255)
);


CREATE TABLE daily_uniques (
    date            date UNIQUE,
    users           hll
);

然後給網站通路表中插入過去1000天的通路資料(此處由于沒有實際的資料，隻能模拟過去1000天的資料)

檢視表

postgres=# SELECT count(*) FROM facts ;
  count   
----------
 50000000

5000萬資料

然後根據日期，對user_id進行hash處理，聚合每天使用者通路網站的資料到 hll結構中。

INSERT INTO daily_uniques(date, users)
    SELECT date, hll_add_agg(hll_hash_integer(user_id))
    FROM facts
    GROUP BY 1;

檢視表資料

postgres=# SELECT count(*) FROM daily_uniques ;
 count 
-------
  1000
(1 row)

隻有1000行資料

現在查找一下每天hll的基數計數值

postgres=# SELECT date, hll_cardinality(users) FROM daily_uniques LIMIT 10;
    date    |  hll_cardinality  
------------+-------------------
 2021-02-06 | 9725.852733707077
 2021-02-21 | 9725.852733707077
 2021-02-02 | 9725.852733707077
 2021-02-08 | 9725.852733707077
 2021-02-10 | 9725.852733707077
 2021-02-03 | 9725.852733707077
 2021-02-14 | 9725.852733707077
 2021-02-22 | 9725.852733707077
 2021-02-11 | 9725.852733707077
 2021-02-20 | 9725.852733707077

此刻，可能會想，可以用 COUNT DISTINCT做到基數統計。但是這裡隻能看到每天多少個唯一身份的使用者通路了網站。

PostgreSQL HLL插件介紹—晟數學院

倘若想要檢視每一周的唯一值呢？

HLL可以這樣處理

postgres=# SELECT hll_cardinality(hll_union_agg(users)) FROM daily_uniques WHERE date >= '2018-10-02'::date AND date <= '2018-10-08'::date;
  hll_cardinality  
-------------------
 9725.852733707077
(1 row)

或者檢視一年中的每個月通路情況

postgres=# SELECT EXTRACT(MONTH FROM date) AS month, hll_cardinality(hll_union_agg(users))
postgres-# FROM daily_uniques
postgres-# WHERE date >= '2019-01-01' AND
postgres-#       date <  '2020-01-01'
postgres-# GROUP BY 1;
 month |  hll_cardinality  
-------+-------------------
     3 | 9725.852733707077
     7 | 9725.852733707077
     8 | 9725.852733707077
    12 | 9725.852733707077
     5 | 9725.852733707077
    10 | 9725.852733707077
    11 | 9725.852733707077
     9 | 9725.852733707077
     4 | 9725.852733707077
     1 | 9725.852733707077
     2 | 9725.852733707077
     6 | 9725.852733707077

等等。是以，可以得到hll可以很好的來計算DV值，并且很快。

關于更多内容，大家可以去通路github網站來擷取。

PostgreSQL HLL插件介紹—晟數學院

PostgreSQL HLL插件介紹—晟數學院

前言

算法

基本概念

實作動機

安裝和使用HLL

繼續閱讀

set define off關閉替代變量功能

報錯：'mysql' 不是内部或外部指令，也不是可運作的程式或批處理檔案。

Linxu常用指令技巧彙總

ERROR 1 (HY000): Can't create/write to file '/tmp/#sql_4188_1.MYI' (Errcode: 28)

艱難安裝LDAP,SSL認證

《Linux指令行與Shell腳本程式設計大全第2版.布盧姆》pdf

MySQL的4種隔離級别？出現問題

XX系統實施過程問題總結

無元件上傳圖檔到資料庫中，最完整解決方案

【MySQL資料庫】資料庫索引事務1.索引2.事務

neo4j之cypher使用文檔

NOSQL安全攻擊

mybatis_入門程式Mybatis入門

登入plsql 報錯 the account is locked --使用者被鎖

sqlServer根據經緯查距離

SequoiaDB巨杉資料庫C++驅動概述