PostgreSQL hll (HyperLogLog) extension for State of The Art Cardinality Estimation Algorithm - 3
背景
接下来主要讲一下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