1.为什么使用bitmap表

1.1.存储成本低

好处一： 如果有一个超大的无序且不重复的整数集合，用Bitmap的存储成本是非常低的。

假设有个1,2,5的数字集合，如果常规的存储方法，要用3个Int32空间。其中一个Int32就是32位的空间。三个就是3*32Bit，相当于12个字节。

如果用Bitmap怎么存储，只用8Bit（1个字节）就够了。每一位代表一个数，位号就是数值，1标识有，0标识无。如下图：

这样的一个字节可以存8个整数，每一个数的存储成本实质上是1Bit。

也就是说Bitmap的存储成本是Array[Int32]的1/32,是Array[Int64]的1/64。

1.2.天然去重

好处二：因为每个值都只对应唯一的一个位置，不能存储两个值，所以Bitmap结构可以天然去重。

1.3.快速定位

好处三：非常方便快速的查询某个元素是否在集合中。

如果我有一个需求，比如想判断数字“3”是否存在于该集合中。若是传统的数字集合存储，那就要逐个遍历每个元素进行判断，时间复杂度为O(N)。

但是若是Bitmap存储只要查看对应的下标数的值是0还是1即可，时间复杂度为O(1)。

1.4.集合间计算

好处四：集合与集合之间的运算非常快。

如果我有另一个集合2、3、7，我想查询这两个集合的交集。

传统方式[1,2,5]与[2,3,7] 取交集就要两层循环遍历。

而Bitmap只要把00100110和10001100进行与操作就行了。而计算机做与、或、非、异或 等等操作是非常快的。

1.5.优势场景

综上，Bitmap非常适合的场景：

（1）海量数据的压缩存储

（2）去重存储

（3）判断值存在于集合

（4）集合之间的交并差

1.6.局限性

当然这种方式也有局限性：

（1）只能存储正整数而不是字符串

（2）存储的值必须是无序不重复

（3）不适合存储稀疏的集合，比如一个集合存了三个数[5,1230000,88880000] 这三个数，用Bitmap存储的话其实就不太划算。（但是clickhouse使用的RoaringBitmap，优化了这个稀疏问题。）

2.在CK中使用bitmap表

2.1.案例说明

首先，如下是用户的标签宽表，如果想根据标签划分人群，比如90后+偏好美食。那么无非是对列值进行遍历筛选，但是当这张表有1000个标签时，如果要索引生效并不是每列有索引就行，要每种查询组合建一个索引才能生效，索引数量相当于1000个列排列组合的个数，这显然是不可能的。

那么更好的办法是按字段重组成Bitmap。

如果能把数据调整成这样的结构，想进行条件组合，那就简单了。

比如：[美食] + [90后] = Bitmap[3,5] & Bitmap[1,3,5] = 3,5 这个计算速度相比宽表条件筛选是非常非常快的。

2.2.准备测试表和数据

1、创建测试表

create table user_tag_merge 
(   uid UInt64,
	gender String,
	agegroup String,
	favor String
)engine=MergeTree()
order by (uid);

2、插入测试数据到宽表

insert into user_tag_merge values(1,'M','90后','sm');
insert into user_tag_merge values(2,'M','70后','sj');
insert into user_tag_merge values(3,'M','90后','ms');
insert into user_tag_merge values(4,'F','80后','sj');
insert into user_tag_merge values(5,'F','90后','ms');

验证数据写入：

3、创建bitmap表

create table user_tag_value_bitmap
 ( 
  tag_code String,
	tag_value String ,
	us AggregateFunction(groupBitmap,UInt64)
)engine=AggregatingMergeTree()
 partition by  (tag_code) 
 order by (tag_value);

Bitmap表必须选择AggregatingMergeTree引擎。

对应的Bitmap字段，必须是AggregateFunction(groupBitmap,UInt64)，groupBitmap标识数据的聚合方式，UInt64标识最大可存储的数字长度。

业务结构上，稍作了调整。把不同的标签放在了同一张表中，但是因为根据tag_code进行了分区，所以不同的标签实质上还是物理分开的。

2.3.处理步骤

1、每个值前面，补上字段名，用()组合成元组

select  
    ('agegroup', agegroup ),
    ('gender',gender ), 
    ('favor',favor ),
    uid 
from user_tag_merge;

2、每个列用[]拼接成数组

select  
    [('agegroup', agegroup),
    ('gender',gender), 
    ('favor',favor)] tag_code_value,
    uid 
from user_tag_merge;

3、用arrayJoin炸开，类似于hive中的explode

SELECT
    arrayJoin([('agegroup', agegroup), ('gender', gender), ('favor', favor)]) AS tag_code_value,
    uid
FROM user_tag_merge;

4、把元组中的字段名和字段值拆开，并用这两个作为维度聚合uid

5、把groupArray 替换成 groupBitmapState

SELECT
    tag_code_value.1 AS tag_code,
    tag_code_value.2 AS tag_value,
    groupBitmapState (uid) AS us
FROM (
    SELECT
        arrayJoin([('agegroup', agegroup), ('gender', gender), ('favor', favor)]) AS tag_code_value,
        uid
    FROM user_tag_merge
) AS tv
GROUP BY
    tag_code_value.1,
    tag_code_value.2;

这里聚合成bitmap的列没有显示是正常的，因为bitmap的结构本身无法用正常文本显示。

6、接下来我们可以插入到bitmap表中

insert into user_tag_value_bitmap
select 
    tag_code_value.1 as tag_code,tag_code_value.2 as tag_value ,
    groupBitmapState( uid ) us
from (
    SELECT
        arrayJoin([('agegroup', agegroup), ('gender', gender), ('favor', favor)]) AS tag_code_value,
        uid 
    FROM user_tag_merge
)tv 
group by tag_code_value.1,tag_code_value.2;

7、插入完成后，使用普通查询依旧不会正常显示

可以通过bitmapToArray函数验证

2.4.对bitmap进行查询

条件组合查询

查询[90后]+[美食]的用户

select  
bitmapToArray(  
    bitmapAnd(  
        (select   us from user_tag_value_bitmap
           where tag_value='ms' and tag_code='favor'), 
        (select   us from user_tag_value_bitmap
            where tag_value='90后' and tag_code='agegroup') 
    )
)as res

这里首先用条件筛选出us, 每个代表一个Bitmap结构的uid集合，找到两个Bitmap后用bitmapAnd函数求交集。 然后为了观察结果用bitmapToArray函数转换成可见的数组。

这里首先用条件筛选出us, 每个代表一个Bitmap结构的uid集合，找到两个Bitmap后用bitmapAnd函数求交集。 然后为了观察结果用bitmapToArray函数转换成可见的数组。

范围值查询

取 [90后]或者[80后] + [美食]

select  
bitmapToArray(  
    bitmapAnd(  
        (select groupBitmapMergeState(us) us from user_tag_value_bitmap
            where tag_value='ms' and tag_code='favor'), 
        (select groupBitmapMergeState(us) from user_tag_value_bitmap
            where tag_value in ('90后','80后') and tag_code='agegroup') 
    )
)as res

因为查询时，有可能需要针对某一个标签，取多个值，甚至是一个区间范围，那就会涉及多个值的userId集合，因此需要在子查询内部用groupBitmapMergeState进行一次合并，其实就多个集合取并集。

3.CK bitmap函数汇总

转载请注明：西门飞冰的博客 » Clickhouse普通表转bitmap表