Roaring Bitmap函数
Roaring Bitmap是一种高效的Bitmap压缩算法,目前已被广泛应用在各种语言和各种大数据平台,常用于去重、标签筛选、时间序列等计算中。本文将为您介绍如何使用Roaring Bitmap函数。
版本要求
仅3.1.6.4及以上版本支持roaringbitmap类型及Roaring Bitmap相关函数。
使用限制
在AnalyticDB MySQL使用Roaring Bitmap函数,具体限制如下:
不支持直接SELECT某个roaringbitmap类型。如需查看roaringbitmap字段中的元素,请用unnest操作,如:
SELECT * FROM unnest(rb_build(array[1,2,3]));
roaringbitmap类型仅在OSS外表原生支持。AnalyticDB MySQL不支持直接创建含有roaringbitmap类型列的表。如果查询AnalyticDB MySQL内表时使用Roaring Bitmap函数,需要使用
rb_build_varbinary
将varbinary类型转换成roaringbitmap类型,如:// 定义adb内表 CREATE TABLE test_rb_cstore (id int, rb varbinary); // 通过Roaring Bitmap函数计算 SELECT rb_cardinality(rb_build_varbinary(rb)) FROM test_rb_cstore;
函数列表
Roaring Bitmap函数包括标量函数和聚合函数。
标量函数
函数名 | 输入 | 输出 | 描述 | 示例 |
rb_build | int[] | roaringbitmap | 通过int数组生成一个roaringbitmap。 |
|
rb_build_varbinary | varbinary | roaringbitmap | 通过二进制类型生成一个roaringbitmap。 |
|
rb_cardinality | roaringbitmap | bigint | 计算roaringbitmap基数。 |
|
rb_contains | roaringbitmap, int | boolean | 判断roaringbitmap是否包含int。 |
|
rb_and | roaringbitmap, roaringbitmap | roaringbitmap | 两个roaringbitmap求交集。 |
|
rb_or | roaringbitmap, roaringbitmap | roaringbitmap | 两个roaringbitmap求并集。 |
|
rb_xor | roaringbitmap, roaringbitmap | roaringbitmap | 两个roaringbitmap求异或。 |
|
rb_and_null2empty | roaringbitmap,roaringbitmap | roaringbitmap | And计算。当输入的某一个参数为Null时,输出为另一个参数。当某一参数输入为 |
|
rb_or_null2empty | roaringbitmap,roaringbitmap | roaringbitmap | Or计算。当输入为Null时,Bitmap会按空({})来处理。 |
|
rb_andnot_null2empty | roaringbitmap,roaringbitmap | roaringbitmap | AndNot计算。当输入为Null时,Bitmap会按空({})来处理。 |
|
rb_and_cardinality | roaringbitmap,roaringbitmap | integer | And计算并返回基数。 |
|
rb_and_null2empty_cardinality | roaringbitmap,roaringbitmap | integer | And计算并返回基数。当输入为Null时,Bitmap会按空({})来处理。 |
|
rb_or_cardinality | roaringbitmap,roaringbitmap | integer | Or计算并返回基数。 |
|
rb_or_null2empty_cardinality | roaringbitmap,roaringbitmap | integer | Or计算并返回基数。当输入为Null时,Bitmap会按空({})来处理。 |
|
rb_xor_cardinality | roaringbitmap,roaringbitmap | integer | Xor计算并返回基数。 |
|
rb_andnot_cardinality | roaringbitmap,roaringbitmap | integer | AndNot计算并返回基数。 |
|
rb_andnot_null2empty_cardinality | roaringbitmap,roaringbitmap | integer | AndNot计算并返回基数。当输入为Null时,Bitmap会按空({})来处理。 |
|
rb_is_empty | roaringbitmap | boolean | 判断是否为空的Bitmap。 |
|
rb_clear | roaringbitmap,bigint,bigint | roaringbitmap | 清除指定范围(不包括 range_end)。 |
|
rb_contains | roaringbitmap, roaringbitmap | boolean | 判断第一个Bitmap是否包含第二个Bitmap。 |
|
rb_flip | roaringbitmap, integer, integer | roaringbitmap | 翻转Bitmap中特定的Offset段。 |
|
rb_minimum | roaringbitmap | integer | 返回Bitmap中最小的Offset,如果Bitmap为空则返回异常。 |
|
rb_maximum | roaringbitmap | integer | 返回Bitmap中最大的Offset,如果Bitmap为空则返回异常。 |
|
rb_rank | roaringbitmap,integer | integer | 返回Bitmap中小于等于指定Offset的基数。 |
|
rb_to_array | roaringbitmap | integer | 返回Bitmap对应整型数组。 |
|
rb_to_varbinary | roaringbitmap | varbinary | 返回Bitmap对应varbinary类型。 |
|
聚合函数
函数名 | 输入数据类型 | 输出数据类型 | 描述 | 示例 |
rb_build_agg | integer | roaringbitmap | 将Offset聚合成bitmap。 |
|
rb_or_agg | roaringbitmap | roaringbitmap | Or聚合计算。 |
|
rb_and_agg | roaringbitmap | roaringbitmap | And聚合计算。 |
|
rb_xor_agg | roaringbitmap | roaringbitmap | Xor聚合计算。 |
|
rb_or_cardinality_agg | roaringbitmap | integer | Or聚合计算并返回其基数。 |
|
rb_and_cardinality_agg | roaringbitmap | integer | And聚合计算并返回其基数。 |
|
rb_xor_cardinality_agg | roaringbitmap | integer | Xor聚合计算并返回其基数。 |
|
示例
如下内容将为您介绍Roaring Bitmap函数完整的使用示例。
创建一个含有roaringbitmap类型的外表。
CREATE TABLE `test_rb` ( `id` int, `rb` roaringbitmap ) engine = 'oss' TABLE_PROPERTIES = '{ "endpoint":"oss-cn-zhangjiakou.aliyuncs.com", "accessid":"LTAIF****5FsE"", "accesskey":"Ccw****iWjv", "url":"oss://testBucketName/roaringbitmap/test_for_user/", "format":"parquet" }';
说明外表相关的参数说明,请参见不带分区的数据文件创建OSS外表。
向表中写入数据。
重要通过INSERT INTO写入数据时性能较差,如果需要写入的数据较多,建议在创建外表前使用ETL工具生成parquet格式的数据文件并上传到对应的OSS路径。
INSERT INTO test_rb SELECT 1, rb_build(array[1,2,3]); INSERT INTO test_rb SELECT 2, rb_build(array[2,3,4,5]);
使用Roaring Bitmap标量函数进行基数计算。
SELECT id, rb_cardinality(rb) FROM test_rb;
返回结果如下:
+------+--------------------+ | id | rb_cardinality(rb) | +------+--------------------+ | 2 | 4 | | 1 | 3 | +------+--------------------+
使用Roaring Bitmap聚合函数进行聚合计算。
SELECT rb_or_cardinality_agg(rb) FROM test_rb;
返回结果如下:
+---------------------------+ | rb_or_cardinality_agg(rb) | +---------------------------+ | 5 | +---------------------------+
圈人场景实践
实践过程中,需要将原始标签表转化成Roaring Bitmap标签表,然后进行Roaring Bitmap计算。流程如下图所示:
步骤一:准备原始标签表
创建测试用的原始标签表users_base。
CREATE TABLE users_base( uid INT, tag1 STRING, // tag1取值范围是:x,y,z。 tag2 STRING, // tag2取值范围是:a,b。 tag3 INT // tag3取值范围是:1~10。 );
生成1亿行随机数据,假设生成的数据为用户标签数据。
SUBMIT JOB INSERT OVERWRITE users_base SELECT CAST(ROW_NUMBER() OVER (ORDER BY c1) AS INT) AS uid, SUBSTRING('xyz', FLOOR(RAND() * 3) + 1, 1) AS tag1, SUBSTRING('ab', FLOOR(RAND() * 2) + 1, 1) AS tag2, CAST(FLOOR(RAND() * 10) + 1 AS INT) as tag3 FROM ( SELECT A.c1 FROM UNNEST(RB_BUILD_RANGE(0, 10000)) AS A(c1) JOIN (SELECT c1 FROM UNNEST(RB_BUILD_RANGE(0, 10000)) AS B(c1) ));
查询原始标签表users_base的10行数据。
SELECT * FROM users_base LIMIT 10;
返回结果如下:
+--------+------+------+------+ | uid | tag1 | tag2 | tag3 | +--------+------+------+------+ | 74526 | y | b | 3 | | 75611 | z | b | 10 | | 80850 | x | b | 5 | | 81656 | z | b | 7 | | 163845 | x | b | 2 | | 167007 | y | b | 4 | | 170541 | y | b | 9 | | 213108 | x | a | 10 | | 66056 | y | b | 4 | | 67761 | z | a | 2 | +--------+------+------+------+
步骤二:原始标签表分组
在设计Roaring Bitmap标签表时,可以利用分布式计算引擎的并发能力,建议引入一个分组字段(本例中使用user_group),将uid分组并行计算。分组的大小可以根据集群ACU总数(计算ACU数+存储ACU数)和实际业务情况进行取舍,遵循以下原则:
一般分组越多计算能力越强,但是分组过多又会导致每个Roaring Bitmap字段中的元素太少,不能充分利用Bitmap的计算特性。
实践过程中建议保证每个分组的Roaring Bitmap空间中数据小于1亿条。例如,原始的uid空间是100亿,可以使用100个分组,每个分组空间为1亿。
本示例使用16个分组,根据uid%16
分组并记录在user_group字段,根据uid/16
计算偏移并记录在offset字段,uid = 16 * offset + user_goup
。后续使用offset来计算Roaring Bitmap。
该分组方式只是一个例子,实际业务中请根据需求设计分组函数。
创建添加分组字段后的标签表users。
CREATE TABLE users( uid INT, tag1 STRING, tag2 STRING, tag3 INT, user_group INT, // 分组字段 offset INT //偏移字段 );
将users_base表中的数据写入users表。
SUBMIT JOB INSERT OVERWRITE users SELECT uid, tag1, tag2, tag3, CAST(uid%16 AS INT), CAST(FLOOR(uid/16) AS INT) FROM users_base;
查询users表的10行数据。
SELECT * FROM users LIMIT 10;
返回结果如下:
+---------+------+------+------+------------+--------+ | uid | tag1 | tag2 | tag3 | user_group | offset | +---------+------+------+------+------------+--------+ | 377194 | z | b | 10 | 10 | 23574 | | 309440 | x | a | 1 | 0 | 19340 | | 601745 | z | a | 7 | 1 | 37609 | | 753751 | z | b | 3 | 7 | 47109 | | 988186 | y | a | 10 | 10 | 61761 | | 883822 | x | a | 9 | 14 | 55238 | | 325065 | x | b | 6 | 9 | 20316 | | 1042875 | z | a | 10 | 11 | 65179 | | 928606 | y | b | 5 | 14 | 58037 | | 990858 | z | a | 8 | 10 | 61928 | +---------+------+------+------+------------+--------+
步骤三:构建Roaring Bitmap标签表
创建tag1的Roaring Bitmap标签表tag_tbl_1。
CREATE TABLE `tag_tbl_1` ( `tag1` STRING, `rb` ROARINGBITMAP, `user_group` INT ) engine = 'oss' TABLE_PROPERTIES = '{ "endpoint":"oss-cn-zhangjiakou.aliyuncs.com", "accessid":"LTAIF****5FsE"", "accesskey":"Ccw****iWjv", "url":"oss://testBucketName/roaringbitmap/tag_tbl_1/", "format":"parquet" }';
将users表的数据写入tag_tbl_1表。
INSERT OVERWRITE tag_tbl_1 SELECT tag1, RB_BUILD_AGG(offset), user_group FROM users GROUP BY tag1, user_group;
查询tag_tbl_1标签表的数据。
SELECT tag1, user_group, RB_CARDINALITY(rb) FROM tag_tbl_1;
返回结果如下:
+------+------------+--------------------+ | tag1 | user_group | rb_cardinality(rb) | +------+------------+--------------------+ | z | 7 | 2082608 | | x | 10 | 2082953 | | y | 7 | 2084730 | | x | 14 | 2084856 | ..... | z | 15 | 2084535 | | z | 5 | 2083204 | | x | 11 | 2085239 | | z | 1 | 2084879 | +------+------------+--------------------+
创建tag2的Roaring Bitmap标签表tag_tbl_2。
CREATE TABLE `tag_tbl_2` ( `tag2` STRING, `rb` ROARINGBITMAP, `user_group` INT ) engine = 'oss' TABLE_PROPERTIES = '{ "endpoint":"oss-cn-zhangjiakou.aliyuncs.com", "accessid":"LTAIF****5FsE"", "accesskey":"Ccw****iWjv", "url":"oss://testBucketName/roaringbitmap/tag_tbl_2/", "format":"parquet" }';
将users表的数据写入tag_tbl_2表。
INSERT OVERWRITE tag_tbl_2 SELECT tag2, RB_BUILD_AGG(offset), user_group FROM users GROUP BY tag2, user_group;
查询tag_tbl_2标签表的数据。
SELECT tag2, user_group, RB_CARDINALITY(rb) FROM tag_tbl_2;
返回结果如下:
+------+------------+--------------------+ | tag2 | user_group | rb_cardinality(rb) | +------+------------+--------------------+ | b | 11 | 3121361 | | a | 6 | 3124750 | | a | 1 | 3125433 | .... | b | 2 | 3126523 | | b | 12 | 3123452 | | a | 4 | 3126111 | | a | 13 | 3123316 | | a | 2 | 3123477 | +------+------------+--------------------+
步骤四:使用Roaring Bitmap标签表计算分析
场景一:过滤筛选分析
场景一以分析tag1 in (x, y)
的用户在tag2维度的柱状图为例。
为了方便理解,先查询出满足
tag1 in (x, y)
条件的用户。SELECT tag2, t1.user_group AS user_group, RB_CARDINALITY(RB_AND(t2.rb, rb1)) AS rb FROM tag_tbl_2 AS t2 JOIN ( SELECT user_group, rb AS rb1 FROM tag_tbl_1 WHERE tag1 IN ('x', 'y')) AS t1 ON t1.user_group = t2.user_group;
返回结果如下:
+------+------------+---------+ | tag2 | user_group | rb | +------+------------+---------+ | b | 3 | 1041828 | | a | 15| 1039859 | | a | 9 | 1039140 | | b | 1 | 1041524 | | a | 4 | 1041599 | | b | 1 | 1041381 | | b | 10| 1041026 | | b | 6 | 1042289 | +------+------------+---------+
查询满足
tag1 in (x, y)
的用户在tag2维度的柱状图。SELECT tag2, SUM(cnt) FROM ( SELECT tag2, t1.user_group AS user_group, RB_CARDINALITY(RB_AND(t2.rb, rb1)) AS cnt FROM tag_tbl_2 AS t2 JOIN ( SELECT user_group, rb AS rb1 FROM tag_tbl_1 WHERE tag1 IN ('x', 'y')) AS t1 ON t1.user_group = t2.user_group ) GROUP BY tag2;
返回结果如下:
+------+----------+ | tag2 | sum(cnt) | +------+----------+ | a | 33327868 | | b | 33335220 | +------+----------+
场景二:Roaring Bitmap标签表交并差计算
从tag1的Roaring Bitmap标签表tag_tbl_1读取满足tag1 = 'x' or tag1 = 'y'
条件的数据,从tag2的Roaring Bitmap标签表tag_tbl_2读取满足tag2 = 'b'
条件的数据,对两个标签表的数据进行交并差计算,得到同时满足tag1 = 'x' or tag1 = 'y'
且tag2 = 'b'
的用户。
SELECT user_group, RB_CARDINALITY(rb) FROM (
SELECT
t1.user_group AS user_group,
RB_AND(rb1, rb2) AS rb
FROM
(
SELECT
user_group,
RB_OR_AGG(rb) AS rb1
FROM
tag_tbl_1
WHERE
tag1 = 'x'
OR tag1 = 'y'
GROUP BY
user_group
) AS t1
JOIN (
SELECT
user_group,
RB_OR_AGG(rb) AS rb2
FROM
tag_tbl_2
WHERE
tag2 = 'b'
GROUP BY
user_group
) AS t2 ON t1.user_group = t2.user_group
GROUP BY user_group);
返回结果如下:
+------------+--------------------+
| user_group | rb_cardinality(rb) |
+------------+--------------------+
| 10 | 2083679 |
| 3 | 2082370 |
| 9 | 2082847 |
| 2 | 2086511 |
...
| 1 | 2082291 |
| 4 | 2083290 |
| 14 | 2083581 |
| 15 | 2084110 |
+------------+--------------------+
场景三:原始标签表和Roaring Bitmap标签表交并差计算
从tag1的Roaring Bitmap标签表tag_tbl_1读取满足tag1 = 'x' or tag1 = 'y'
条件的数据,从原始标签表users读取满足tag2 = 'b'
条件的数据,对两个标签表的数据进行交并差计算,得到同时满足tag1 = 'x' or tag1 = 'y'
且tag2 = 'b'
的数据。
SELECT user_group, RB_CARDINALITY(rb) FROM (
SELECT
t1.user_group AS user_group,
RB_AND(rb1, rb2) AS rb
FROM
(
SELECT
user_group,
RB_OR_AGG(rb) AS rb1
FROM
tag_tbl_1
WHERE
tag1 = 'x'
OR tag1 = 'y'
GROUP BY
user_group
) AS t1
JOIN (
SELECT
user_group,
RB_BUILD_AGG(offset) AS rb2
FROM
users
WHERE
tag2 = 'b'
GROUP BY
user_group
) AS t2 ON t1.user_group = t2.user_group
GROUP BY user_group);
返回结果如下:
+------------+--------------------+
| user_group | rb_cardinality(rb) |
+------------+--------------------+
| 3 | 2082370 |
| 1 | 2082291 |
| 0 | 2082383 |
| 4 | 2083290 |
| 11 | 2081662 |
| 13 | 2085280 |
...
| 14 | 2083581 |
| 15 | 2084110 |
| 9 | 2082847 |
| 8 | 2084860 |
| 5 | 2083056 |
| 7 | 2083275 |
+------------+--------------------+
场景四:将满足场景二的Roaring Bitmap导出到OSS
创建用于导出计算结果的标签表tag_tbl_3。
CREATE TABLE `tag_tbl_3` ( `user_group` INT, `rb` ROARINGBITMAP )engine = 'oss' TABLE_PROPERTIES = '{ "endpoint":"oss-cn-zhangjiakou.aliyuncs.com", "accessid":"LTAIF****5FsE"", "accesskey":"Ccw****iWjv", "url":"oss://testBucketName/roaringbitmap/tag_tbl_3/", "format":"parquet" }';
将满足场景二的计算结果导出到标签表tag_tbl_3。
INSERT OVERWRITE tag_tbl_3 SELECT t1.user_group AS user_group, RB_AND(rb1, rb2) AS rb FROM ( SELECT user_group, RB_OR_AGG(rb) AS rb1 FROM tag_tbl_1 WHERE tag1 = 'x' OR tag1 = 'y' GROUP BY user_group ) AS t1 JOIN ( SELECT user_group, RB_OR_AGG(rb) AS rb2 FROM tag_tbl_2 WHERE tag2 = 'b' GROUP BY user_group ) AS t2 ON t1.user_group = t2.user_group;
说明SQL语句执行结束后,文件会以parquet格式存放在
oss://testBucketName/roaringbitmap/tag_tbl_3/
路径中。
场景五:将tag1的标签表的数据导入内表加速查询效果
创建一个内表tag_tbl_1_cstore,并将rb字段定义为VARBINARY类型。
CREATE TABLE `tag_tbl_1_cstore` ( `tag1` VARCHAR, `rb` VARBINARY, `user_group` INT );
将tag1的标签表的数据从OSS导入到内表tag_tbl_1_cstore。
INSERT INTO tag_tbl_1_cstore SELECT tag1, RB_TO_VARBINARY(rb), user_group FROM tag_tbl_1;
查询tag_tbl_1_cstore表的数据。
SELECT tag1, user_group, RB_CARDINALITY(RB_OR_AGG(RB_BUILD_VARBINARY(rb))) FROM tag_tbl_1_cstore GROUP BY tag1, user_group;
返回结果如下:
+------+------------+---------------------------------------------------+ | tag1 | user_group | rb_cardinality(rb_or_agg(rb_build_varbinary(rb))) | +------+------------+---------------------------------------------------+ | y | 3 | 2082919 | | x | 9 | 2083085 | | x | 3 | 2082140 | | y | 11 | 2082268 | | z | 4 | 2082451 | ... | z | 2 | 2081560 | | y | 6 | 2082194 | | z | 7 | 2082608 | +------+------------+---------------------------------------------------+