更新时间:2024-11-27 GMT+08:00
HLL数据类型
HLL(HyperLoglog)是统计数据集中唯一值个数的高效近似算法。它有着计算速度快,节省空间的特点,不需要直接存储集合本身,而是存储一种名为HLL的数据结构。每当有新数据加入进行统计时,只需要把数据经过哈希计算并插入到HLL中,最后根据HLL就可以得到结果。
HLL与其他算法的比较请参见表1。
项目 |
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常数级别。
- 当前默认规格下可计算最大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。
HLL的应用场景
- 使用hll数据类型场景
- 创建带有hll类型的表并向表中插入空的hll。
1 2
CREATE TABLE helloworld (id integer, set hll); INSERT INTO helloworld(id, set) VALUES (1, hll_empty());
- 把整数经过哈希计算加入到hll中。
1
UPDATE helloworld SET set = hll_add(set, hll_hash_integer(12345)) WHERE id = 1;
- 把字符串经过哈希计算加入到hll中。
1
UPDATE helloworld SET set = hll_add(set, hll_hash_text('hello world')) WHERE id = 1;
- 得到hll中的distinct值。
1 2 3 4 5
SELECT hll_cardinality(set) FROM helloworld WHERE id = 1; hll_cardinality ----------------- 2 (1 row)
- 创建带有hll类型的表并向表中插入空的hll。
- 使用hll进行网站访客统计场景
- 创建原始数据表facts,记录用户访问网站时间。
1 2 3 4
CREATE TABLE facts ( date date, user_id integer );
- 插入用户访问过网站的数据。
1 2 3 4 5 6 7 8
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));
- 创建表并指定列为hll。根据日期把数据分组,并把数据插入到hll中。
1 2 3 4 5 6 7 8 9
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;
- 计算每一天访问网站不同用户数量。
1 2 3 4 5 6 7 8 9 10 11 12
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)
- 计算在2019.02.20到2019.02.26一周中有多少不同用户访问过网站。
1 2 3 4 5
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)
- 计算昨天访问过网站而今天没访问网站的用户数量。
1 2 3 4 5 6 7 8 9 10 11 12
SELECT date, (#hll_union_agg(users) 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)
- 创建原始数据表facts,记录用户访问网站时间。
- 插入数据不满足hll数据结构要求时报错场景
当用户给hll类型的字段插入数据的时候,必须保证插入的数据满足hll数据结构要求,如果解析后不满足就会报错。
例如: 插入数据'E\\1234'时,该数据不满足hll数据结构,不能解析成功因此失败报错。
1 2 3
CREATE TABLE test(id integer, set hll); INSERT INTO test VALUES(1, 'E\\1234'); ERROR: invalid input syntax for integer: "E\\1234"
父主题: 数据类型