BITMAP精准去重

概述

云数据库 SelectDB 版支持Bitmap类型，在Aggregate数据模型中，Bitmap类型的Value字段可以和集合的交并集聚合函数配合，实现数据的精确去重功能。

传统数据仓库中的Bitmap去重功能，对亿级别以上Bitmap大基数的交并集计算性能较差，有两个主要原因：一是当Bitmap基数较大（超过1 GB）时，网络和磁盘IO处理时间比较长；二是集群在扫描数据后，会全部传输到顶层节点进行并集运算，给顶层单节点带来压力。

SelectDB针对分布式环境进行了优化设计，可以将Bitmap列的值按照Hash分桶划分打散，使得不同值存储在不同的分桶中，保证不同分桶的Bitmap值是正交的，基数大幅降低。当查询时，先分别对不同分桶中的正交Bitmap进行聚合计算，然后再由顶层节点将聚合计算后的值合并输出。如此会大大提高计算效率，也解决了顶层节点的单点计算瓶颈问题。

使用示例

1. 建表时需要使用Aggregate数据模型，Value字段的数据类型是Bitmap，聚合函数是集合的交并集函数，例如Bitmap_UNION，同时需要创建一个列用来表示分桶ID，示例如下。

   说明

   用于分桶ID的列和BUCKETS要设置合理，用于分桶ID的列的基数至少是BUCKETS的5倍以上，以使数据Hash分桶后尽量均衡。

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

   在创建表的Schema中增加了列hid，作为Hash分桶列，可代表user_id列值的范围。

2. 数据导入。

   LOAD LABEL user_tag_Bitmap_test
   (
       DATA INFILE('hdfs://abc')
       INTO TABLE user_tag_Bitmap
       COLUMNS TERMINATED BY ','
       (tmp_tag, tmp_user_id)
       SET (
           tag = tmp_tag,
           hid = ceil(tmp_user_id/500),
           user_id = to_Bitmap(tmp_user_id)
       )
   )
   # 注意：500这个数不固定，可按需调整

3. 导入数据的格式如下，两列数据分别为tag、user_id。

   11111111,1
   11111112,2
   11111113,3
   11111114,4
   ...

   在导入数据时，SelectDB会对列user_id的Bitmap值的Range进行切割。例如，user_id在[1,5000000)区间时hid值相同，会分配到一个分桶内，因此每个分桶内到的Bitmap都是正交的。以这种方式进行切割，可以利用桶间Bitmap值正交的特性，大幅降低集合交并集的计算量。

4. 在完成导入之后，可以通过调用Bitmap函数来进行Bitmap的相关操作。具体可调用的Bitmap函数，可以参考SQL手册中的Bitmap函数章节。

正交Bitmap函数

Bitmap查询提供了Bitmap_orthogonal_intersect函数、orthogonal_Bitmap_intersect_count​函数、orthogonal_Bitmap_union_count函数、orthogonal_Bitmap_expr_calculate函数、orthogonal_Bitmap_expr_calculate_count函数供正交场景使用。下文将分别介绍这五种函数。

Bitmap_orthogonal_intersect

对字段的Bitmap交集，求计算出的具体值。

语法

orthogonal_Bitmap_intersect(Bitmap_column, column_to_filter, filter_values)

参数说明

示例

SELECT Bitmap_COUNT(orthogonal_Bitmap_intersect(user_id, tag, 13080800, 11110200)) FROM user_tag_Bitmap WHERE tag IN (13080800, 11110200);

查询执行时聚合分为2层：在第一层，SelectDB先按filter_values对tag进行过滤，然后对SQL中的所有聚合Key列（此处为tag列）的Bitmap求交集；在第二层，SelectDB对所有来源于第一层的Bitmap值循环求并集。

orthogonal_Bitmap_intersect_count​

对字段的Bitmap交集，求值的数量。语法同intersect_count，但实现不同。

语法

orthogonal_Bitmap_intersect_count(Bitmap_column, column_to_filter, filter_values)

参数说明

示例

SELECT orthogonal_Bitmap_intersect_count(user_id, tag, 1150000, 1150001, 390006) FROM user_tag_Bitmap WHERE tag IN (1150000, 1150001, 390006);

查询执行时聚合分为2层：在第一层，SelectDB先按filter_values对tag进行过滤，然后对SQL中的所有聚合Key列（此处为tag列）的Bitmap求交集，再计算结果Bitmap的count值；在第二层，SelectDB对所有来源于第一层的count值循环求sum。

orthogonal_Bitmap_union_count

对字段的Bitmap并集，求值的数量。语法同Bitmap_union_count，但实现不同。

语法

orthogonal_Bitmap_union_count(Bitmap_column)

参数说明

示例

SELECT orthogonal_Bitmap_union_count(user_id) FROM user_tag_Bitmap WHERE tag IN (1150000, 1150001, 390006);

查询执行时聚合分为2层：在第一层，SelectDB先对所有Bitmap求并集，再计算结果Bitmap的count值；在第二层，SelectDB对所有来源于第一层的count值循环求sum。

orthogonal_Bitmap_expr_calculate

对表达式的Bitmap交/并/差集合，求计算出的具体值。

语法

orthogonal_Bitmap_expr_calculate(Bitmap_column, filter_column, input_string)

参数说明

示例

SELECT orthogonal_Bitmap_expr_calculate(user_id, tag, '(833736|999777)&(1308083|231207)&(1000|20000-30000)') FROM user_tag_Bitmap WHERE tag IN (833736,999777,130808,231207,1000,20000,30000);

查询执行时聚合分为2层：在第一层，SelectDB先解析input_string获取tag过滤条件，然后进行数据过滤，过滤后的数据按照input_string表达式进行Bitmap计算；在第二层，SelectDB对所有来源于第一层的Bitmap值求并集，并返回最终Bitmap结果。

orthogonal_Bitmap_expr_calculate_count

对表达式的Bitmap交/并/差集合，求计算出的值的数量，语法和参数同orthogonal_Bitmap_expr_calculate。

语法

orthogonal_Bitmap_expr_calculate_count(Bitmap_column, filter_column, input_string)

参数说明

示例

SELECT orthogonal_Bitmap_expr_calculate_count(user_id, tag, '(833736|999777)&(1308083|231207)&(1000|20000-30000)') FROM user_tag_Bitmap WHERE tag IN (833736,999777,130808,231207,1000,20000,30000);

查询执行时聚合分为2层：在第一层，SelectDB先解析input_string获取tag过滤条件，然后进行数据过滤，过滤后的数据按照input_string表达式进行Bitmap计算，最后计算结果Bitmap的count值；在第二层，SelectDB对所有来源于第一层的Bitmap值求并集，并返回最终Bitmap结果。