ClickHouse实现Bitmap类函数算法RoaringBitmap

0.抛出大数据老生常谈问题

给定含有40亿个不重复的位于[0,2^32-1]区间内的整数集合，如何快速判定某个数

是否在该集合内？

用什么结构? Bloom Filter,HyperLogLog…bitmap是基础

为撒用位图？ 省空间-- 16g，500mb

缺点是什么？连续整数的问题

1.ClickHouse的bitmap实现算法roaringbitmap

将32位无符号整数按照高16位分桶，即最多有2^16即65536个桶，也就是container。

存储数据时，按照数据的高16位找到container，如果没有就新建一个，再将低16位放入container中

ArrayContainer —-小于4096

BitmapContainer —大于4096

RunContainer —连续存储优化

2.Bitmap类函数介绍

函数功能介绍

利用聚合函数groupBitmap的groupBitmapState方法，可以将Integer类型的字段转换成Bitmap

利用bitmapBuild方法，传入Array类型，可以将其转换为Bitmap

另外，其它的方法主要是用于Bitmap自身或之间的位运算，Bitmap与Array双向转换。

groupBitmap：返回的是对应列的cardinality值

groupBitmapState：返回对应整数列的bitmap类型，相当于是将对应列的所有值以Array类型组织，再调用bitmapBuild函数

bitmapAnd: 从运算角度看是进行按位与操作，从sql角度看就是两部分的条件都要满足

bitmapOr：从运算角度看是进行按位或操作，从sql角度看就是两部分的条件任意满足一个即可

bitmapXor：从运算角度来看是进行按位异或操作(相同为0相异为1)，从sql角度看就是满足条件A不满足条件B或者满足条件B而不满足条件A

bitmapAndnot:从运算角度来看是进行按与非，从sql角度看用户当作流失用户

—注意规避问题

select　

--仅仅支持UInt32（42亿+整型,int32 21亿+）

bitmapContains(groupBitmapMergeState(uv),toUInt32(9379716501)) as is_exists,　

has(bitmapToArray(groupBitmapMergeState(uv)),9379716501) as array_is_exists　

from user_tags_bitmap where tag='user_first_dt' and value='20230310'

3.实际案例-用户标签用bitmap存储应用

#利用clickhouse bitmap高效能力分析用户行为场景

select

arrayJoin(bitmapToArray(bitmapAnd(hot_b,cold_b))) as "数组转行list",

bitmapToArray(bitmapAnd(hot_b,cold_b)) as "留存用户",

bitmapCardinality(bitmapOr(hot_b,cold_b)) as "全部用户",

bitmapCardinality(bitmapAnd(hot_b,cold_b)) as "留存数",

bitmapAndCardinality(hot_b,cold_b) as "留存数--优秀写法",

bitmapCardinality(bitmapAnd(hot_b,cold_b))/bitmapCardinality(hot_b) as "留存率",

bitmapAndnotCardinality(hot_b,cold_b) as "流失用户数",

bitmapCardinality(bitmapAndnot(hot_b,cold_b))/bitmapCardinality(hot_b) as "流失率",

bitmapAndnotCardinality(cold_b,hot_b) as "新用户数"

from

(

select 1 as join_id,groupBitmapMergeState(uv) as hot_b

from user_tags_bitmap where tag='app_login_date' and value='2023-03-10'

) hot

join

(

select 1 as join_id,groupBitmapMergeState(uv) as cold_b

from user_tags_bitmap where tag='app_login_date' and value='2023-03-17'

) cold on hot.join_id=cold.join_id