ClickHouse遇见RoaringBitmap
Q&A
Q：如图。
A：当然是自带的。其实RoaringBitmap正是ClickHouse位图的底层实现（笑
RoaringBitmap的预备知识请见这里。
在CH中产生位图
使用普通函数bitmapBuild可以由无符号整形数的数组直接产生位图，e.g.
WITH bitmapBuild([32, 65, 127, 1026]) AS bm
SELECT bm,toTypeName(bm);
┌─bm─┬─toTypeName(bm)─────────────────────────┐
│ A� │ AggregateFunction(groupBitmap, UInt16) │
└────┴────────────────────────────────────────┘
可见，位图在CH中的本质是AggregateFunction(groupBitmap, UInt*)类型的（*由位图中的最大值弹性决定），即groupBitmap这个聚合函数产生的中间结果。根据聚合函数的combinator语法，加上-Merge后缀再查询一次：
WITH bitmapBuild([32, 65, 127, 1026]) AS bm
SELECT bm,groupBitmapMerge(bm);
┌─bm─┬─groupBitmapMerge(bm)─┐
│ A� │ 4 │
└────┴──────────────────────┘
也就是说，groupBitmap函数返回的是位图的基数（即1的数量）。显然，与-Merge后缀相对，我们还可以用-State后缀来对某一列生成位图：
SELECT groupBitmapState(toUInt64(user_id)) FROM ods.analytics_access_log_local
WHERE ts_date = today();
-- 这个位图很长，所以显示大量乱码hhh
ClickHouse提供了很多位图操作的函数，参见官方文档，稍后会给出示例。
翻翻源码
既然位图都是从groupBitmap函数构建出来的，就来看看与其相关的实现吧。来到AggregateFunctionGroupBitmapData.h，定义如下：
template <typename T>
struct AggregateFunctionGroupBitmapData
{
bool doneFirst = false;
RoaringBitmapWithSmallSet<T, 32> rbs;
static const char * name() { return "groupBitmap"; }
};
其核心就是RoaringBitmapWithSmallSet这个数据结构，继续看代码：
template <typename T, UInt8 small_set_size>
class RoaringBitmapWithSmallSet : private boost::noncopyable
{
private:
using Small = SmallSet<T, small_set_size>;
using ValueBuffer = std::vector<T>;
Small small;
roaring_bitmap_t * rb = nullptr;
void toLarge()
{
rb = roaring_bitmap_create();
for (const auto & x : small)
roaring_bitmap_add(rb, x.getValue());
}
public:
// ......
}
roaring_bitmap_t就是RBM在CRoaring库中的实现，SmallSet又是什么鬼？其实它的定义位于SmallTable.h中，是一个限定大小（无法扩容）的小集合，底层用数组来存储。在前面的结构体里，模板参数small_set_size设为32，说明它最多只能容下32个元素。
继续向下读一段：
public:
bool isLarge() const { return rb != nullptr; }
bool isSmall() const { return rb == nullptr; }
~RoaringBitmapWithSmallSet()
{
if (isLarge())
roaring_bitmap_free(rb);
}
void add(T value)
{
if (isSmall())
{
if (small.find(value) == small.end())
{
if (!small.full())
small.insert(value);
else
{
toLarge();
roaring_bitmap_add(rb, value);
}
}
}
else
roaring_bitmap_add(rb, value);
}
UInt64 size() const
{
return isSmall()
? small.size()
: roaring_bitmap_get_cardinality(rb);
}
// ....
这下就非常明显了：当位图的基数少于32时，仅使用SmallSet存储；一旦超过此阈值，就调用toLarge()方法转化为RoaringBitmap，此后都在RoaringBitmap上操作。之所以有这种区别，想来是因为SmallSet在小数据量下的性能比RBM更优吧。
当然，在RoaringBitmapWithSmallSet之间进行运算时，就需要分情况讨论了。举个栗子，两个CH位图做按位与运算（对应bitmapAnd函数），对应方法如下：
void rb_and(const RoaringBitmapWithSmallSet & r1)
{
ValueBuffer buffer;
if (isSmall() && r1.isSmall())
{
// intersect
for (const auto & x : small)
if (r1.small.find(x.getValue()) != r1.small.end())
buffer.push_back(x.getValue());
// Clear out the original values
small.clear();
for (const auto & value : buffer)
small.insert(value);
buffer.clear();
}
else if (isSmall() && r1.isLarge())
{
for (const auto & x : small)
if (roaring_bitmap_contains(r1.rb, x.getValue()))
buffer.push_back(x.getValue());
// Clear out the original values
small.clear();
for (const auto & value : buffer)
small.insert(value);
buffer.clear();
}
else
{
roaring_bitmap_t * rb1 = r1.isSmall() ? r1.getNewRbFromSmall() : r1.getRb();
roaring_bitmap_and_inplace(rb, rb1);
if (r1.isSmall())
roaring_bitmap_free(rb1);
}
}
- 当this为小位图时，遍历this并逐个检查其中的元素在r1是否存在（只是根据r1的大小不同调用的方法不同而已），将重合的元素放入缓存，再重新插入this中。
- 当this为大位图时，直接调用CRoaring自带的roaring_bitmap_and_inplace()方法做与运算。注意如果r1为小位图，需要先调用getNewRbFromSmall()方法生成新的RBM。
位图操作函数的定义与实现都位于FunctionsBitmap.h内，例如刚才说过的bitmapAnd函数：
using FunctionBitmapAnd = FunctionBitmap<BitmapAndImpl, NameBitmapAnd>;
template <typename T>
struct BitmapAndImpl
{
static void apply(AggregateFunctionGroupBitmapData<T> & bitmap_data_1, const AggregateFunctionGroupBitmapData<T> & bitmap_data_2)
{
bitmap_data_1.rbs.rb_and(bitmap_data_2.rbs);
}
};
位图部分的源码在整个ClickHouse体系中算是相当友好的，看官也可自行查看，不再赘述。
CH位图的应用
我们知道，位图在需要精确统计基数及快速求交集、并集的场景非常有用。以用户行为（点击流）数据为例，创建以下的表：
CREATE TABLE tmp.analytics_access_log_bmp (
ts_date Date,
event_type LowCardinality(String),
user_bmp AggregateFunction(groupBitmap, UInt64)
)
ENGINE = AggregatingMergeTree()
PARTITION BY ts_date
ORDER BY event_type
SETTINGS index_granularity = 16;
这里是以日期和事件类型作为key，将符合条件的用户ID以位图存储。注意为了配合AggregateFunction，引擎应使用AggregatingMergeTree，并且此表的行数肯定偏少，所以索引粒度可适当降低。
取一些数据灌入表中：
INSERT INTO tmp.analytics_access_log_bmp
SELECT
ts_date,event_type,
groupBitmapState(toUInt64(user_id))
FROM ods.analytics_access_log_local
WHERE ts_date >= '2020-08-15' AND ts_date <= '2020-08-20'
GROUP BY ts_date,event_type;
这样，我们就可以非常快速地统计每天查看过商品详情页的用户数：
SELECT
ts_date,
bitmapCardinality(user_bmp) AS user_cnt
FROM tmp.analytics_access_log_bmp
WHERE event_type = 'OpenGoodsDetail';
以及统计前一日打开过App，后一日点击过“立即购买”的用户转化率：
SELECT c1 / c0
FROM (
SELECT bitmapCardinality(
(SELECT user_bmp FROM tmp.analytics_access_log_bmp
WHERE ts_date = '2020-08-17' AND event_type = 'AppStart')
) AS c0,
bitmapCardinality(bitmapAnd(
(SELECT user_bmp FROM tmp.analytics_access_log_bmp
WHERE ts_date = '2020-08-17' AND event_type = 'AppStart'),
(SELECT user_bmp FROM tmp.analytics_access_log_bmp
WHERE ts_date = '2020-08-18' AND event_type = 'BuyNow')
)) AS c1
);
毫无疑问，由于位图操作消灭了GROUP BY、JOIN等复杂的关系代数操作，效率有极为明显的提升。
The End
Happy Friday night.
民那晚安晚安。
