對于大數據開發人員而言，處理海量數據的判重操作和基數統計是常見需求，而 RoaringBitmap類型及其相關函數是當前非常高效的一種解決方案，許多大數據庫產品已支持RoaringBitmap類型。OceanBase 4.3.3版本，作為專為OLAP場景設計的正式發布（GA）版，也具備這一功能。本文重點闡述 RoaringBitmap 的原理、應用場景，并提供 OceanBase 中 RoaringBitmap 的應用示例。
RoaringBitmap 誕生背景簡介
海量數據的判重和基數統計需求，難度是數據量大且性能要盡可能好。技術方案的關鍵就是數據結構及其算法，數據結構也決定了其算法能力空間。
基礎的數據結構就是常用的數據類型，如數值、字符串、時間等。假設要業務數據數值化存儲，使用整型存儲（無符號），其表達的值域是 [0, 232-1]，一共 4294967296 個數。如果記錄不重復且記錄數滿配，單就這一列會占用存儲空間16GB。這個判重方法有遍歷、排序加二分查找、BloomFilter 等。
所以后來有些場景會用Bitmap（位圖）存儲這個數據，每個位（bit）對應一行記錄的狀態（0表示不存在，1表示存在）。如果記錄不重復且記錄數滿配，這個位圖結構最大存儲空間是512MB。針對位圖的判重效率就非常高。
Bitmap 結構下在海量數據（40億+）的前提下，即使有大量數據重復也不會增加存儲空間和降低判重效率。位圖支持與運算（求交集）、或運算（求并集）。但是如果記錄數不多且重復值很高的情況下（學術界稱之為稀疏矩陣），Bitmap 存儲就有點浪費內存空間（固定 512MB）。于是學術界有提出稀疏位圖（或叫壓縮位圖）概念，Roaring Bitmap 就是稀疏位圖的實現方案中目前認為最好的方案，并且已經被多個數據庫產品支持。比如說 PostgreSQL 、AnalyticDB、PolarDB、Doris、ClickHouse、OceanBase （列舉的不一定全） 。
Roaring Bitmap 原理簡介
32 位地址空間容量下的數據值如果全用 Bitmap 存儲，碰到稀疏矩陣數據，為 0 的位會很多，很浪費存儲空間。RoaringBitmap 對這個 32 位使用做了一些改進，分為高 16 位和低 16 位。高 16 位做為記錄的索引 KEY，低 16 位作為記錄的值 VALUE。所以高 16 位有多少不同的記錄，就有多少個KEY，最多記錄數 216個。有的文章也把每個記錄稱之位一個 HASH Bucket（桶），每個 Bucket 的大小就是低 16 位存儲的記錄數。
低 16 位的數據結構分為三類。如果記錄數少于 4096 個，就使用 16 位的 Short Int 稀疏數組。名為數組，實際上是鏈表結構，以節省空間。如果記錄數超過 4096 個，就開始使用 16 位的 Bitmap 存儲。如果碰到連續的數據，則使用 Run Length Coding（簡稱 RLE）存儲一個開始和結束的整型值。
Roaring Bitmap （后簡稱?rb）也支持兩個?rb?集合求并集、交集、差集、計算基數、排序等。這些操作是 SQL 運算邏輯的基礎。
OceanBase RoaringBitmap 類型和函數
OB 4.3.2 開始支持數據類型?roaringbitmap，以及相關函數。函數列表如下：
| 函數類型 | 函數名稱 | 函數作用 |
|---|---|---|
| 位圖構造函數 | rb_build_empty | 構建一個空的位圖數據。值為0x0100。 |
| rb_build_varbinary | Varbinary 為 OceanBase 私有格式，是由 version 信息、type 信息、data 等部分組成的二進制格式。 | |
| rb_from_string | 通過特定格式的字符串來構建位圖數據。字符串格式為需要構建的位圖數據的每一個元素，并通過逗號隔開，如 1,2,3,4。 | |
| 位圖基數計算函數 | rb_cardinality | 返回輸入位圖數據的基數。 |
| rb_and_cardinality rb_or_cardinality rb_andnot_cardinality | 返回兩個位圖數據做與計算后，得到的新位圖數據的基數。 | |
| rb_and_null2empty_cardinality rb_or_null2empty_cardinality rb_andnot_null2empty_cardinality | 返回兩個位圖數據做與計算后，得到的新位圖數據的基數。 | |
| rb_xor_cardinality | 返回兩個位圖數據做與計算后，得到的新位圖數據的基數。 | |
| 位圖運算函數 | rb_and rb_and_null2empty | 計算兩個位圖數據的交集。 |
| rb_or rb_or_null2empty | 計算兩個位圖數據的并集。 | |
| rb_xor | 提供兩個位圖數據的異或運算。 | |
| rb_andnot rb_andnot_null2empty | 提供兩個位圖數據的與非運算。 | |
| 位圖判斷函數 | rb_is_empty | 判斷輸入的位圖數據是否為空。 |
| 位圖輸出函數 | rb_to_varbinary | 用于以 varbinary 的形式輸出位圖數據。 |
| rb_to_string | 以字符串的形式依次輸出位圖數據的每一個元素，并以逗號隔開。其中元素的輸出格式為 UINT64，輸出的最大元素個數為 1000000。 | |
| 位圖聚合函數 | rb_build_agg | 將數值列聚合為位圖數據。 |
| rb_or_agg | 將位圖列的多行數據進行或運算，并聚合為位圖數據。 | |
| rb_and_agg | 將位圖列的多行數據進行與運算，并聚合為位圖數據。 |
OB Roaring Bitmap 示例
下面以用戶行為分析在 OB 的例子來演示這一功能。
首先構造基礎數據 用戶標簽表。
-- 用戶屬性表：共有100萬個用戶，每個用戶有64個屬性 --
create table t_user_tag (
uid int8,
tag int,
mod_time timestamp,
primary key (tag,uid)
); DELIMITER //CREATE PROCEDURE insert_user_tag(IN min_uid BIGINT, IN max_uid BIGINT)
BEGINDECLARE uid BIGINT UNSIGNED;SET uid = min_uid;WHILE uid <= max_uid DO-- Loop to generate 64 random tags for each userINSERT IGNORE INTO t_user_tagSELECT uid, mod( rand(unix_timestamp())*1000000,1999), current_timestamp() from table(generator(64)); SET uid = uid + 1; -- Move to the next UIDEND WHILE;
END //DELIMITER ;call insert_user_tag(1,250000);
call insert_user_tag(250001,500000);
call insert_user_tag(500001,750000);
call insert_user_tag(750001,1000000);
然后生成標簽和用戶對應索引表，使用?roaringbitmap?類型。
create table t_tag_userbit ( tag int primary key, userbit roaringbitmap,mod_time timestamp
); insert /*+ enable_parallel_dml parallel(3) */ into t_tag_userbit
select tag,rb_build_agg(uid),current_timestamp() from t_user_tag group by tag order by tag;
抽查幾筆數據看看?roaringbitmap?類型的數據特征。
select * from t_tag_userbit where tag in (1,11,111,1111);
這里看到的是 dbeaver 工具格式化后的結果，實際?rb?列是二進制數據。
如果是在命令行?mysql或obclient下，默認這個數據展示可能是亂碼，可以在命令行下加一個參數?--binary-as-hex?，使用十六進制展示 binary 類型數據。
obclient -h127.1 -P2881 -uroot@obmysql -p test --binary-as-hex
下面是一些?roaringbitmap?類型相關的函數演示。
比如格式化顯示和查看基數。
select tag, rb_to_string(userbit),rb_cardinality(userbit), mod_time
from t_tag_userbit where tag in (1382, 1406,10257);
計算同時滿足兩個tag標簽場景的的用戶數。
select rb_cardinality(rb_and_agg(userbit)) from t_tag_userbit where tag in (1990,1998) ;
更新標簽用戶索引表。
update t_tag_userbit set userbit = rb_or(userbit, rb_from_string('61,71,73,74,85')) where tag = 1998;
看一下 SQL 執行計劃。
obclient [test]> explain select rb_cardinality(rb_and_agg(userbit)) from t_tag_userbit where tag in (1002,1990,1998) ;
+-----------------------------------------------------------------------------------------------------+
| Query Plan |
+-----------------------------------------------------------------------------------------------------+
| ======================================================== |
| |ID|OPERATOR |NAME |EST.ROWS|EST.TIME(us)| |
| -------------------------------------------------------- |
| |0 |SCALAR GROUP BY| |1 |14 | |
| |1 |└─TABLE GET |t_tag_userbit|3 |14 | |
| ======================================================== |
| Outputs & filters: |
| ------------------------------------- |
| 0 - output([rb_cardinality(T_FUN_SYS_RB_AND_AGG(t_tag_userbit.userbit))]), filter(nil), rowset=16 |
| group(nil), agg_func([T_FUN_SYS_RB_AND_AGG(t_tag_userbit.userbit)]) |
| 1 - output([t_tag_userbit.userbit]), filter(nil), rowset=16 |
| access([t_tag_userbit.userbit]), partitions(p0) |
| is_index_back=false, is_global_index=false, |
| range_key([t_tag_userbit.tag]), range[1002 ; 1002], [1990 ; 1990], [1998 ; 1998], |
| range_cond([t_tag_userbit.tag IN (1002, 1990, 1998)]) |
+-----------------------------------------------------------------------------------------------------+
15 rows in set (0.041 sec)
從執行計劃看 SQL 引擎有跟 RB 有關的算子 ：T_FUN_SYS_RB_AND_AGG?。
更多閱讀
OB 有了?roaringbitmap?類型，就也可以像 ClickHouse 一樣可以用于類似海量數據用戶標簽畫像等業務場景。
OceanBase? V4.3 現已支持 365天 免費試用，點擊立即開啟 >>?
算法訓練篇11--力扣3.無重復字符的最長字串(難度中等))
——73. 矩陣置零)
