PostgreSQL hll (HyperLogLog) extension for State of The Art Cardinality Estimation Algorithm - 3

32 minute read

背景

接下来主要讲一下hll的存储结构.

一、hll_hashval类型的长度为64bit, 可以与int, int8类型相互转化. 但是在聚合成hll时结果是有差别的.

所以最好不要直接把int或int8类型当成hll_hashval来使用.

-- 创建测试表  
digoal=> create table agg (id int primary key,userids hll);  
NOTICE:  CREATE TABLE / PRIMARY KEY will create implicit index "agg_pkey" for table "agg"  
CREATE TABLE  
  
-- 使用generate_series函数生成数值.  
digoal=> \df *.*generate_series*  
                                                               List of functions  
   Schema   |      Name       |         Result data type          |                        Argument data types                        
   |  Type    
------------+-----------------+-----------------------------------+-----------------------------------------------------------------  
---+--------  
 pg_catalog | generate_series | SETOF bigint                      | bigint, bigint                                                    
   | normal  
 pg_catalog | generate_series | SETOF bigint                      | bigint, bigint, bigint                                            
   | normal  
 pg_catalog | generate_series | SETOF integer                     | integer, integer                                                  
   | normal  
 pg_catalog | generate_series | SETOF integer                     | integer, integer, integer      
  
-- int直接转换成hll_hashval  
digoal=> insert into agg select 1,hll_add_agg(t::hll_hashval) from generate_series(-10000000::int,0::int) g(t);  
INSERT 0 1  
  
-- int8直接转换成hll_hashval  
digoal=> insert into agg select 2,hll_add_agg(t::hll_hashval) from generate_series(-10000000::int8,0::int8) g(t);  
INSERT 0 1  
  
-- 调用hll_hash_integer  
digoal=> insert into agg select 3,hll_add_agg(hll_hash_integer(t)) from generate_series(-10000000::int,0::int) g(t);  
INSERT 0 1  
  
-- 调用hll_hash_bigint  
digoal=> insert into agg select 4,hll_add_agg(hll_hash_bigint(t)) from generate_series(-10000000::int8,0::int8) g(t);  
INSERT 0 1  
  
-- 查看唯一值.  
digoal=> select id,#userids from agg;  
 id |     ?column?       
----+------------------  
  1 | 12098218.8944067  -- int::hll_hashval  
  2 | 12098218.8944067  -- int8::hll_hashval  
  3 | 10132224.7985314  -- hll_hash_integer  
  4 | 9710693.55748479  -- hll_hash_bigint  
(4 rows)  

根据文档的描述, 误差范围为±1.04/√(2log2m).

-- 本例的log2m=12.  
digoal=> select hll_log2m(userids) from agg;  
 hll_log2m   
-----------  
        12  
        12  
        12  
        12  
(4 rows)  

可以计算出误差=±0.01625

-- 真实误差如下 :   
digoal=> select id,((#userids)-10000001)/10000001 from agg;  
 id |      ?column?         
----+---------------------  
  1 |   0.209821768458491  
  2 |   0.209821768458491  
  3 |  0.0132223785308992  
  4 | -0.0289307413584472  
(4 rows)  

说明hll_hash_integer得到的hll_hashval的聚合误差在允许范围内.

直接转换以及使用hll_hash_bigint得到的hll_hashval的聚合超出误差范围.

其他 :

digoal=> delete from agg;  
DELETE 6  
digoal=> insert into agg select 6,hll_add_agg(hll_hash_text(t::text)) from generate_series(-10000000,0) g(t);  
INSERT 0 1  
digoal=> insert into agg select 7,hll_add_agg(hll_hash_bytea(byteain(int4out(t)))) from generate_series(-10000000,0) g(t);  
INSERT 0 1  

超出误差范围.

digoal=> select id,((#userids)-10000001)/10000001 from agg;  
 id |      ?column?         
----+---------------------  
  6 | -0.0193928457148722  
  7 | -0.0193928457148722  
(2 rows)  

所以最精确的还是使用hll_hash_integer得到的hll_hashval.

二、hll的存储 :

hll 直观来看就是字节流. 可以与bytea互相转换. 如下 :

digoal=> select '\xffff'::bytea;  
 bytea    
--------  
 \xffff  
(1 row)  
  
-- bytea可以转换成hll, 但是这个hll不一定合法  
digoal=> select '\xffff'::bytea::hll;  
  hll     
--------  
 \xffff  
(1 row)  
  
-- hll转换成bytea没有任何问题, 因为bytea可以存储任何字节流.  
-- 但是hll有自己的存储规范, 实际上\xffff是不合法的, 如下 :   
digoal=> select '\xffff'::hll;  
ERROR:  unknown schema version 15  
LINE 1: select '\xffff'::hll;  
               ^  
digoal=> select '\x1fff'::hll;  
ERROR:  undefined multiset type  
LINE 1: select '\x1fff'::hll;  
               ^  
digoal=> select '\x13ff'::hll;  
ERROR:  sparse multiset too small  
LINE 1: select '\x13ff'::hll;  
               ^  
digoal=> select '\x14ff'::hll;  
ERROR:  inconsistently sized compressed multiset  
LINE 1: select '\x14ff'::hll;  
               ^  
-- 这个是合法的  
digoal=> select '\x128c7f'::hll;  
   hll      
----------  
 \x128c7f  
(1 row)  
  
-- DEBUG一个合法的hll如下 :   
digoal=> select hll_print('\x128c7f'::hll);  
                                 hll_print                                   
---------------------------------------------------------------------------  
 EXPLICIT, 0 elements, nregs=4096, nbits=5, expthresh=-1(320), sparseon=1:  
(1 row)  
  
-- DEBUG一个非法hll, 报错 :   
digoal=> select hll_print('\xffff'::bytea::hll);  
ERROR:  unknown schema version 15  

三、hll的数据结构

总的来说包含五个部分的信息(data bytes不一定有, 如果是EMPTY或者无效定义则没有data bytes的数据).

1byte(version, data type), 1byte(parameter), 1byte(cutoff), data bytes;  

3.1 version和data type占用第一个字节 :

第一个字节分成了2部分信息, 如下 :

  version 指schema version , 目前为1 , 占用前4个比特位.  
  data type 占用后4个比特位.  
    // First byte is the version and type header.  
    uint8_t vers = (i_bitp[0] >> 4) & 0xf;  
    uint8_t type = i_bitp[0] & 0xf;  

3.2 parameter 占用第二个字节 :

第二个字节分成了2部分信息, 如下 :

  the highest 3 bits are used to encode the integer value "registerWidth - 1", and  
  the remaining 5 bits encode the integer value "log2(numberOfRegisters)".  
"registerWidth" may take values from 1 to 8, inclusive, and "log2(numberOfRegisters)" may take on 1 to 31, inclusive.  
For example:  
    P = xA6 = 1010 0110 = 101 00110  
thus "registerWidth - 1" = 5, 因此 "registerWidth" = 6 and "log2(numberOfRegisters)" = 6, 因此 "numberOfRegisters" = 2^6 = 64.  

3.3 cutoff 占用第三个字节 :

第三个字节分成了3部分信息, 第二个比特位表示是否允许sparse结构. 接下来的6个比特位存储cutoff的(指数-1)信息. 如下 :

The 'cutoff' byte C encodes parameters defining the EXPLICIT to SPARSE, or EXPLICIT to FULL promotions.  
  
-- 因为SPARSE到FULL不需要根据cutoff的值来判断, 当使用SPARSE存储会超过使用FULL存储时, 即转换为FULL.  
1 bit (the top bit) of padding,  
1 bit (second highest bit) indicating the boolean value sparseEnabled, and  
6 bits (lowest six bits) as a big-endian integer explicitCutoff that can take on the values 0, 63, or 1 to 31 inclusive.  

相关代码 :

// This routine is used to encode an expthresh value to be stored  
// in the typmod metadata or a hll header.  
//  
static int32 encode_expthresh(int64 expthresh)  
{  
    // This routine presumes the uncompressed value is correct and  
    // doesn't range check.  
    //  
    if (expthresh == -1)  
        return 63;  
    else if (expthresh == 0)  
        return 0;  
    else  
        return integer_log2(expthresh) + 1;  
}  
  
// If expthresh == -1 (auto select expthresh) determine  
// the expthresh to use from nbits and nregs.  
//  
// -1则自动计算cutoff的值  
static size_t  
expthresh_value(int64 expthresh, size_t nbits, size_t nregs)  
{  
    if (expthresh != -1)  
    {  
        return (size_t) expthresh;  
    }  
    else  
    {  
        // Auto is selected, choose the maximum number of explicit  
        // registers that fits in the same space as the compressed  
        // encoding.  
        size_t cmpsz = ((nbits * nregs) + 7) / 8;  
        return cmpsz / sizeof(uint64_t);  
    }  
}  
  
解码代码 :   
// The expthresh is represented in a encoded format in the  
// type modifier to save metadata bits.  This routine is used  
// when the expthresh comes from a typmod value or hll header.  
//  
static int64 decode_expthresh(int32 encoded_expthresh)  
{  
    // This routine presumes the encoded value is correct and  
    // doesn't range check.  
    //  
    if (encoded_expthresh == 63)  
        return -1LL;  
    else if (encoded_expthresh == 0)  
        return 0;  
    else  
        return 1LL << (encoded_expthresh - 1);  
}  

3.4 不同的data type对应的data bytes也不一样.

所以data bytes存储的是动态的结构, data type可能包含如下结构类型. 数值对应的是存储在HLL中的第一个字节的后4个比特位.

0 - undefined, 无效或未定义的结构, 因此没有data bytes的部分.  
1 - EMPTY, A constant value that denotes the empty set. 同样没有data bytes的部分  
2 - EXPLICIT, 连续的字节流, 每个字节存储一个hll_hashval. 并且按照hll_hashval排序存储的结构.  
3 - SPARSE, 后面再解释.  
4 - FULL, 后面再解释.  

根据第三部分的介绍, 举例来解析一下各个部分的信息 :

首先设置一下几部分的信息 :

log2m = 10  
regwidth = 1  
expthresh = 4  
sparseon = 1  
  
digoal=> select hll_set_defaults(10,1,4,1);  
  
-- 输出1个hll的字节流信息:  
digoal=> select hll_add_agg(hll_hash_integer(t)) from generate_series(1,2) g(t);  
               hll_add_agg                  
------------------------------------------  
 \x120a438895a3f5af28cafeda0ce907e4355b60  
(1 row)  

从上面这个字节流来分析头的信息 :

1. 第一个字节: 0x12

schema version是头4个比特=1  
data type是后4个比特 = 2, 对应的是EXPLICIT  

2. 第二个字节: 0x0a

前3个比特是registerWidth - 1=0, 所以registerWidth=1;

后5个比特是log2(numberOfRegisters)=10, 所以numberOfRegisters=2^10= 1024;

3. 第三个字节: 0x43

展开成2进制为: 01000011

第一个比特是为了满足8bit 对其的padding. 值是多少都忽略不计;

第二个比特是sparseEnabled的布尔逻辑, 值为1;

最后6个比特是integer_log2(expthresh) + 1, 这里我们设置了expthresh=4, 所以integer_log2(expthresh) + 1 = 3;

如果6个比特位满表示127, 但是不能取这么大的值, 因为1LL « (encoded_expthresh - 1) 最多存储64bit. 所以前面提到了最大是63.

4. 后面的是data bytes: 0x8895a3f5af28cafeda0ce907e4355b60

使用hll_print可以打印出以上解析的信息 :

digoal=> select hll_print(hll_add_agg(hll_hash_integer(t))) from generate_series(1,2) g(t);  
                              hll_print                                
---------------------------------------------------------------------  
 EXPLICIT, 2 elements, nregs=1024, nbits=1, expthresh=4, sparseon=1:+  
 0: -8604791237420463362                                            +  
 1: -2734554653617988768   
(1 row)  

将以上的data 转换成16进制 :

8895A3F5AF28CAFE  
DA0CE907E4355B60  

正好是hll值中对应的data bytes部分.

四、data type详解 :

1. EMPTY, 没有data bytes的部分, 看字节流如下 :

digoal=> select hll_empty();  
 hll_empty   
-----------  
 \x110a43  
(1 row)  
digoal=> select hll_print(hll_empty());  
                      hll_print                        
-----------------------------------------------------  
 EMPTY, nregs=1024, nbits=1, expthresh=4, sparseon=1  
(1 row)  

2. EXPLICIT, 第三部分已经讲过, 这里就不再多说了. 只是要注意2点 :

2.1 存储是针对hll_hashval排序好了的.

digoal=> select hll_set_defaults(10,1,8192,1);  
 hll_set_defaults   
------------------  
 (10,1,4,1)  
(1 row)  
digoal=> select hll_hash_integer(t) from generate_series(1,10) g(t);  
   hll_hash_integer     
----------------------  
 -8604791237420463362  
 -2734554653617988768  
 5208657608173592891  
 2072756739463403504  
 6655367218388208063  
 -5566252076597558760  
 9162408199432052219  
 8282768600195057636  
 1779292183511753683  
 3213538865073541202  
(10 rows)  
digoal=> select hll_print(hll_add_agg(hll_hash_integer(t))) from generate_series(1,10) g(t);  
                                hll_print                                  
-------------------------------------------------------------------------  
 EXPLICIT, 10 elements, nregs=1024, nbits=1, expthresh=8192, sparseon=1:+  
 0: -8604791237420463362                                                +  
 1: -5566252076597558760                                                +  
 2: -2734554653617988768                                                +  
 3:  1779292183511753683                                                +  
 4:  2072756739463403504                                                +  
 5:  3213538865073541202                                                +  
 6:  5208657608173592891                                                +  
 7:  6655367218388208063                                                +  
 8:  8282768600195057636                                                +  
 9:  9162408199432052219   
(1 row)  

2.2 如果手动设置了expthresh, 那么使用explicit存储的最大存储空间就是3 bytes + (8bytes * expthresh); 当存储的值个数超过expthresh是会转换成SPARSE或FULL存储, 占用的空间会缩小. 具体缩小到多少可以参考以下表 :

logm2	regwidth=1	regwidth=2	regwidth=3	regwidth=4	regwidth=5	regwidth=6  
10	7.4e+02   128B	3.0e+03   256B	4.7e+04   384B	1.2e+07   512B	7.9e+11   640B	3.4e+21   768B  
11	1.5e+03   256B	5.9e+03   512B	9.5e+04   768B	2.4e+07   1.0KB	1.6e+12   1.2KB	6.8e+21   1.5KB  
12	3.0e+03   512B	1.2e+04   1.0KB	1.9e+05   1.5KB	4.8e+07   2.0KB	3.2e+12   2.5KB	1.4e+22   3KB  
13	5.9e+03   1.0KB	2.4e+04   2.0KB	3.8e+05   3KB	9.7e+07   4KB	6.3e+12   5KB	2.7e+22   6KB  
14	1.2e+04   2.0KB	4.7e+04   4KB	7.6e+05   6KB	1.9e+08   8KB	1.3e+13   10KB	5.4e+22   12KB  
15	2.4e+04   4KB	9.5e+04   8KB	1.5e+06   12KB	3.9e+08   16KB	2.5e+13   20KB	1.1e+23   24KB  
16	4.7e+04   8KB	1.9e+05   16KB	3.0e+06   24KB	7.7e+08   32KB	5.1e+13   40KB	2.2e+23   48KB  
17	9.5e+04   16KB	3.8e+05   32KB	6.0e+06   48KB	1.5e+09   64KB	1.0e+14   80KB	4.4e+23   96KB  
18	1.9e+05   32KB	7.6e+05   64KB	1.2e+07   96KB	3.1e+09   128KB	2.0e+14   160KB	8.7e+23   192KB  
19	3.8e+05   64KB	1.5e+06   128KB	2.4e+07   192KB	6.2e+09   256KB	4.1e+14   320KB	1.7e+24   384KB  
20	7.6e+05   128KB	3.0e+06   256KB	4.8e+07   384KB	1.2e+10   512KB	8.1e+14   640KB	3.5e+24   768KB  

例如 :

-- logm2:10, regwidth:1对应以上表的存储空间是128 bytes, 将thresh设置成8192, 也就是说要超过8192个存储的值时才会使用sparse存储.  
digoal=> select hll_set_defaults(10,1,8192,1);  
 hll_set_defaults   
------------------  
 (10,1,8192,1)  
(1 row)  
  
-- 8192个值时, 由于使用explicit存储结构, 所以占用空间是3bytes + 8192*8 = 65539 bytes  
digoal=> select octet_length(hll_add_agg(hll_hash_integer(t))::text::bytea) from generate_series(1,8192) g(t);  
 octet_length   
--------------  
        65539  
(1 row)  
  
-- 当值增加到8193, 那么会转换成sparse存储结构, 空间降到3 bytes + 128 bytes = 131 bytes.  
digoal=> select octet_length(hll_add_agg(hll_hash_integer(t))::text::bytea) from generate_series(1,8193) g(t);  
 octet_length   
--------------  
          131  
(1 row)  
  
-- 需要注意的是,  logm2:10, regwidth:1 最多只能存储的值不到8193个, 所以转换成sparse存储后信息会丢失.  
digoal=> select #hll_add_agg(hll_hash_integer(t)) from generate_series(1,8193) g(t);  
 ?column?   
----------  
      NaN  
(1 row)  
  
-- 而8192是explicit存储的, 所以信息是完全的 :   
digoal=> select #hll_add_agg(hll_hash_integer(t)) from generate_series(1,8192) g(t);  
 ?column?   
----------  
     8192  
(1 row)  
  
-- 从hll_print的输出可以看出端倪 :   
digoal=> select hll_print(hll_add_agg(hll_hash_integer(t))) from generate_series(1,8193) g(t);  
                                               hll_print                                                  
--------------------------------------------------------------------------------------------------------  
 COMPRESSED, 1024 filled nregs=1024, nbits=1, expthresh=8192, sparseon=1:                              +  
    0:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
   32:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
   64:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
   96:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  128:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  160:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  192:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  224:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  256:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  288:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  320:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  352:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  384:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  416:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  448:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  480:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  512:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  544:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  576:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  608:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  640:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  672:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  704:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  736:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  768:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  800:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  832:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  864:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  896:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  928:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  960:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  992:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1   
(1 row)  

把cutoff调整为自动, 再看看到底log2m:10, regwidth:1 能存储多少个值.

digoal=> select hll_set_defaults(10,1,-1,1);  
 hll_set_defaults   
------------------  
 (10,1,8192,1)  
(1 row)  
  
-- 临界值是7090, 如下 :   
-- 所有的bit全是1 :   
digoal=> select hll_print(hll_add_agg(hll_hash_integer(t))) from generate_series(1,7091) g(t);  
                                               hll_print                                                  
--------------------------------------------------------------------------------------------------------  
 COMPRESSED, 1024 filled nregs=1024, nbits=1, expthresh=-1(16), sparseon=1:                            +  
    0:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
   32:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
   64:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
   96:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  128:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  160:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  192:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  224:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  256:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  288:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  320:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  352:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  384:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  416:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  448:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  480:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  512:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  544:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  576:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  608:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  640:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  672:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  704:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  736:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  768:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  800:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  832:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  864:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  896:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  928:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  960:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  992:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1   
(1 row)  
  
-- 352这行有个bit还是0  
digoal=> select hll_print(hll_add_agg(hll_hash_integer(t))) from generate_series(1,7090) g(t);  
                                               hll_print                                                  
--------------------------------------------------------------------------------------------------------  
 COMPRESSED, 1023 filled nregs=1024, nbits=1, expthresh=-1(16), sparseon=1:                            +  
    0:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
   32:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
   64:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
   96:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  128:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  160:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  192:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  224:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  256:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  288:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  320:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  352:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  0  1  1  1  1 +  
  384:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  416:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  448:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  480:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  512:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  544:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  576:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  608:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  640:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  672:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  704:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  736:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  768:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  800:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  832:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  864:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  896:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  928:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  960:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1 +  
  992:  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1   
(1 row)  
  
-- 从distinct的结果也能看出来 :   
digoal=> select #(hll_add_agg(hll_hash_integer(t))) from generate_series(1,7090) g(t);  
     ?column?       
------------------  
 7097.82712893384  
(1 row)  
digoal=> select #(hll_add_agg(hll_hash_integer(t))) from generate_series(1,7091) g(t);  
 ?column?   
----------  
      NaN  
(1 row)  
  
-- 所以log2m=10, regwidth=1存储的值并不是7.4e+02, 而是7090. 这不知道是不是文档上的BUG。  

3. SPARSE

存储的不是完整的hll_hashval, 而是short-word, 由log2(numberOfRegisters) + registerWidth这两个宽度的比特位组成.

例如log2m=10, regwidth=1, 则存储1个值消耗11个比特.

log2(numberOfRegisters) 称为 index.  
registerWidth 称为 value.  

注意这里也有对齐的问题, 如果 BITS = (registerWidth + log2(numberOfRegisters)) * numberOfRegisters 不是8的倍数, 那么末尾需要填0。

例如 :

log2m=10, regwidth=1, expthresh= -1(16): (expthresh自动计算得到).  

这种情况下 :

digoal=> select hll_add_agg(hll_hash_integer(t)) from generate_series(1,17) g(t);  
                       hll_add_agg                          
----------------------------------------------------------  
 \x130a7f05e13c528c33666d51ca776fefde18cb1bfbb07d3fc9fc20  
(1 row)  

长度27字节 :

digoal=> select octet_length(hll_add_agg(hll_hash_integer(t))::text::bytea) from generate_series(1,17) g(t);  
 octet_length   
--------------  
           27  
(1 row)  

长度计算 :

17个值占用的空间是11*17=187字节, 不能被8整除, 需要添5个0.

digoal=> select 11*17;  
 ?column?   
----------  
      187  
(1 row)  

添5个0后等于192; 因此data bytes部分占据24字节.

digoal=> select 192/8;  
 ?column?   
----------  
       24  
(1 row)  

24加上头部的3个字节正好是27字节.

-- 手册上的例子 :   
  
For example, if log2(numberOfRegisters) = 11 and registerWidth = 6, and if the register index/value pairs are (11, 6) and (1099, 19):  
  
= [(11, 6), (1099, 19), padding]                                    # as unsigned decimal-encoded pairs  
= [(0b00000001011, 0b000110), (0b10001001011, 0b010011), 0b000000]  # as two binary-encoded pairs and 6 bits of padding  
= [(0b00000001011000110), (0b10001001011010011), 0b000000]          # as binary-encoded 17-bit short words and 6 bits of padding  
= [0b00000001, 0b01100011, 0b01000100, 0b10110100, 0b11000000]      # as binary-encoded octets in array  
= [0x01, 0x63, 0x44, 0x5B, 0xC0]                                    # as byte array  
  0x0163445BC0                                                      # as hex  

4. FULL

当使用sparse存储可能超过使用full存储的空间开销时, 会转成full存储.

(或者设置了enablesparse=false,0)时超过expthresh后会从explicit直接转换成FULL.)

FULL存储结构如下 :

存储的不是完整的hll_hashval, 而是short-word, 由registerWidth的比特位组成.

例如log2m=10, regwidth=1, 则存储1个值消耗1个比特.

registerWidth 称为 value.

注意这里也有对齐的问题, 如果 BITS = registerWidth * numberOfRegisters 不是8的倍数, 那么末尾需要填0。

例如 :

digoal=> select hll_set_defaults(10,2,16,1);  
 hll_set_defaults   
------------------  
 (10,7,16,1)  
(1 row)  
  
-- 全部填满, 每个short-word是2bit, 可存储范围为0-3. 从下面的print可以看出已经全部填满.  
digoal=> select hll_print(hll_add_agg(hll_hash_bigint(t))) from generate_series(1,9999999::int8) g(t);  
                                               hll_print                                                  
--------------------------------------------------------------------------------------------------------  
 COMPRESSED, 1024 filled nregs=1024, nbits=2, expthresh=16, sparseon=1:                                +  
    0:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
   32:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
   64:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
   96:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  128:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  160:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  192:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  224:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  256:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  288:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  320:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  352:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  384:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  416:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  448:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  480:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  512:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  544:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  576:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  608:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  640:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  672:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  704:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  736:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  768:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  800:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  832:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  864:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  896:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  928:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  960:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3 +  
  992:  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3  3   
(1 row)  
  
-- 手册中的例子 :   
  
For example, if registerWidth = 5 and numberOfRegisters = 4, and if the register index/value pairs are (0, 0), (1,1), (2,2), (3,3):  
  
  [0, 1, 2, 3, padding]                        # as unsigned decimal-encoded register values  
= [0b00000, 0b00001, 0b00010, 0b00011, 0b0000] # as four 5-bit "short words" + 4 bits padding  
= [0b00000000, 0b01000100, 0b00110000]         # as binary-encoded octets in array  
= [0x00, 0x44, 0x30]                           # as hex-encoded byte array  
= 0x004430                                     # as hex  

五、数据类型转换的规则.

因为data bytes部分存储的数据结构是动态的, 类型转换的规则如下 :

Hierarchy

The hierarchy is dependent on the ‘cutoff’ byte C. When a set is promoted from one ‘type’/algorithm to another, the top nibble of the ‘version’ byte V, the ‘parameter’ byte P, and the ‘cutoff’ byte C all remain the same. The bottom nibble of V and the ‘data’ bytes B may change.

When any value is added to an EMPTY set,

if explicitCutoff = 0 and sparseEnabled = 0, then it is promoted to a FULL set containing that one value.
if explicitCutoff = 0 and sparseEnabled = 1, then it is promoted to a SPARSE set containing that one value.
if explicitCutoff > 0 but < 63, then it is promoted to an EXPLICIT set containing that one value.

When inserting an element into an EXPLICIT set,

if sparseEnabled = 0 and explicitCutoff = 0, then it is promoted to a FULL set.
if sparseEnabled = 1 and explicitCutoff = 0, then it is promoted to a SPARSE set.
if sparseEnabled = 0 and explicitCutoff > 0 and < 63, and if inserting the element would cause the cardinality to exceed 2 ^ (explicitCutoff - 1), then it is promoted to a FULL.
if sparseEnabled = 1 and explicitCutoff > 0 and < 63, and if inserting the element would cause the cardinality to exceed 2 ^ (explicitCutoff - 1), then it is promoted to a SPARSE.
if sparseEnabled = 0 and explicitCutoff = 63, then the criteria for promotion is implementation-dependent, as this value of explicitCutoff indicates an ‘auto’ promotion mode. Since sparseEnabled = 0 the set can only be promoted to a FULL set.
if sparseEnabled = 1 and explicitCutoff = 63, then the promotion is implementation-dependent, as this value of explicitCutoff indicates an ‘auto’ promotion mode. Since sparseEnabled = 1 the set can only be promoted to a SPARSE set.

When inserting an element into a SPARSE set, if that element would cause the storage size of the SPARSE set to be greater than that of a FULL set, then it is promoted to a FULL set.

六、性能举例 :

digoal=> create table test(c1 hll);  
CREATE TABLE  
digoal=> insert into test select hll_add_agg(hll_hash_integer(t)) from generate_series(1,100000000) g(t);  
INSERT 0 1  
Time: 73342.322 ms  
digoal=> insert into test select hll_add_agg(hll_hash_integer(t)) from generate_series(-50000001,50000000) g(t);  
INSERT 0 1  
Time: 73190.797 ms  
digoal=> select #c1,(100000000-(#c1))/100000000.0 from test;  
     ?column?     |       ?column?         
------------------+----------------------  
 99473843.5133928 |  0.00526156486607164  
 99928107.7019657 | 0.000718922980343103  
(2 rows)  
digoal=> select #hll_union_agg(c1),(150000002-(#hll_union_agg(c1)))/150000002.0 from test;  
     ?column?     |      ?column?        
------------------+--------------------  
 148198541.947098 | 0.0120097335258864  
(1 row)  
Time: 6.776 ms  

Flag Counter

digoal’s 大量PostgreSQL文章入口