SelectDB Cloud
开发指南
其他
BITMAP 精准去重

BITMAP精准去重

背景

SelectDB原有的Bitmap聚合函数设计比较通用,但对亿级别以上bitmap大基数的交并集计算性能较差。排查发现主要有两个原因: 一是当bitmap基数较大时,如bitmap大小超过1g,网络/磁盘IO处理时间比较长;二是后端计算节点在scan数据后全部传输到顶层节点进行求交和并运算,给顶层单节点带来压力,成为处理瓶颈。

解决思路是将bitmap列的值按照range划分,不同range的值存储在不同的分桶中,保证了不同分桶的bitmap值是正交的。当查询时,先分别对不同分桶中的正交bitmap进行聚合计算,然后顶层节点直接将聚合计算后的值合并汇总,并输出。如此会大大提高计算效率,解决了顶层单节点计算瓶颈问题。

Create table

建表时需要使用聚合模型,数据类型是 bitmap , 聚合函数是 bitmap_union

CREATE TABLE `user_tag_bitmap` (
  `tag` bigint(20) NULL COMMENT "用户标签",
  `hid` smallint(6) NULL COMMENT "分桶id",
  `bitmap_user_id` bitmap BITMAP_UNION NULL COMMENT ""
) ENGINE=OLAP
AGGREGATE KEY(`tag`, `hid`)
COMMENT "OLAP"
DISTRIBUTED BY HASH(`hid`) BUCKETS 3

表schema增加hid列,表示id范围, 作为hash分桶列。

注意:hid数和BUCKETS要设置合理,hid数设置至少是BUCKETS的5倍以上,以使数据hash分桶尽量均衡。

数据加载时,假如原始数据字段为user_id,数据类型为Bigint。则导入时,让hid = ceil(user_id/5000000), bitmap_user_id = to_bitmap(user_id)。

load数据时,对用户bitmap值range范围纵向切割,例如,用户id在1-5000000范围内的hid值相同,hid值相同的行会分配到一个分桶内,如此每个分桶内到的bitmap都是正交的。可以利用桶内bitmap值正交特性,进行交并集计算,计算结果会被shuffle至top节点聚合。

注意:正交bitmap函数不能用在分区表,因为分区表分区内正交,分区之间的数据是无法保证正交的,则计算结果也是无法预估的。

bitmap_orthogonal_intersect

求bitmap交集函数

语法:

orthogonal_bitmap_intersect(bitmap_column, column_to_filter, filter_values)

参数:

第一个参数是Bitmap列,第二个参数是用来过滤的维度列,第三个参数是变长参数,含义是过滤维度列的不同取值

说明:

查询规划上聚合分2层,在第一层be节点(update、serialize)先按filter_values为key进行hash聚合,然后对所有key的bitmap求交集,结果序列化后发送至第二层be节点(merge、finalize),在第二层be节点对所有来源于第一层节点的bitmap值循环求并集

样例:

select BITMAP_COUNT(orthogonal_bitmap_intersect(user_id, tag, 13080800, 11110200)) from user_tag_bitmap  where tag in (13080800, 11110200);

orthogonal_bitmap_intersect_count

求bitmap交集count函数,语法同原版intersect_count,但实现不同

语法:

orthogonal_bitmap_intersect_count(bitmap_column, column_to_filter, filter_values)

参数:

第一个参数是Bitmap列,第二个参数是用来过滤的维度列,第三个参数开始是变长参数,含义是过滤维度列的不同取值

说明:

查询规划聚合上分2层,在第一层be节点(update、serialize)先按filter_values为key进行hash聚合,然后对所有key的bitmap求交集,再对交集结果求count,count值序列化后发送至第二层be节点(merge、finalize),在第二层be节点对所有来源于第一层节点的count值循环求sum

orthogonal_bitmap_union_count

求bitmap并集count函数,语法同原版bitmap_union_count,但实现不同。

语法:

orthogonal_bitmap_union_count(bitmap_column)

参数:

参数类型是bitmap,是待求并集count的列

说明:

查询规划上分2层,在第一层be节点(update、serialize)对所有bitmap求并集,再对并集的结果bitmap求count,count值序列化后发送至第二层be节点(merge、finalize),在第二层be节点对所有来源于第一层节点的count值循环求sum

使用场景

符合对bitmap进行正交计算的场景,如在用户行为分析中,计算留存,漏斗,用户画像等。

人群圈选:

 select orthogonal_bitmap_intersect_count(user_id, tag, 13080800, 11110200) from user_tag_bitmap where tag in (13080800, 11110200);
 注:13080800、11110200代表用户标签

计算user_id的去重值:

select orthogonal_bitmap_union_count(user_id) from user_tag_bitmap where tag in (13080800, 11110200);
© 2023 北京飞轮数据科技有限公司 京ICP备2022004029号 | Apache、Apache Doris 以及相关开源项目名称均为 Apache 基金会商标