ClickHou遇见RoaringBitmap
Q&A
Q：如图。
A：当然是⾃带的。其实RoaringBitmap正是ClickHou位图的底层实现（笑
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(ur_id)) FROM ods.analytics_access_log_local
WHERE ts_date = today();
-- 这个位图很长，所以显⽰⼤量乱码hhh
ClickHou提供了很多位图操作的函数，参见，稍后会给出⽰例。
翻翻源码
既然位图都是从groupBitmap函数构建出来的，就来看看与其相关的实现吧。来到AggregateFunctionGroupBitmapData.h，定义如下：
template <typename T>
struct AggregateFunctionGroupBitmapData
{
bool doneFirst = fal;
RoaringBitmapWithSmallSet<T, 32> rbs;
static const char * name() { return "groupBitmap"; }
};
其核⼼就是RoaringBitmapWithSmallSet这个数据结构，继续看代码：
fontstemplate <typename T, UInt8 small_t_size>
class RoaringBitmapWithSmallSet : private boost::noncopyable
{
private:
using Small = SmallSet<T, small_t_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:
hopstep// ......
北京地区学位英语}
roaring_bitmap_t就是RBM在CRoaring库中的实现，SmallSet⼜是什么⿁？其实它的定义位于SmallTa
ble.h中，是⼀个限定⼤⼩（⽆法扩容）的⼩集合，底层⽤数组来存储。在前⾯的结构体⾥，模板参数small_t_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) == d())
{
if (!small.full())
small.inrt(value);
el
{
toLarge();
roaring_bitmap_add(rb, value);
}
}
}
el
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())
{
/
/ interct
for (const auto & x : small)
if (r1.small.Value()) != d())
buffer.push_Value());
// Clear out the original values
small.clear();
for (const auto & value : buffer)
small.inrt(value);
buffer.clear();
cookie是什么意思}
el if (isSmall() && r1.isLarge())
{
for (const auto & x : small)
if (roaring_bitmap_contains(r1.rb, x.getValue()))
buffer.push_Value());
// Clear out the original values
small.clear();
for (const auto & value : buffer)
small.inrt(value);
buffer.clear();
}
el
{
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);
}
};订书机英语
位图部分的源码在整个ClickHou体系中算是相当友好的，看官也可⾃⾏查看，不再赘述。
CH位图的应⽤
我们知道，位图在需要精确统计基数及快速求交集、并集的场景⾮常有⽤。以⽤户⾏为（点击流）数据为例，创建以下的表：
CREATE TABLE tmp.analytics_access_log_bmp (
ts_date Date,
event_type LowCardinality(String),
ur_bmp AggregateFunction(groupBitmap, UInt64)
)
ENGINE = AggregatingMergeTree()k8录音软件
PARTITION BY ts_date
erhuORDER 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(ur_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;
skin是什么意思
这样，我们就可以⾮常快速地统计每天查看过商品详情页的⽤户数：
hydrogenation
SELECT
ts_date,
bitmapCardinality(ur_bmp) AS ur_cnt
FROM tmp.analytics_access_log_bmp
WHERE event_type = 'OpenGoodsDetail';
以及统计前⼀⽇打开过App，后⼀⽇点击过“⽴即购买”的⽤户转化率：
SELECT c1 / c0
FROM (
SELECT bitmapCardinality(
(SELECT ur_bmp FROM tmp.analytics_access_log_bmp
WHERE ts_date = '2020-08-17' AND event_type = 'AppStart')
)
AS c0,
bitmapCardinality(bitmapAnd(
(SELECT ur_bmp FROM tmp.analytics_access_log_bmp
WHERE ts_date = '2020-08-17' AND event_type = 'AppStart'),
(SELECT ur_bmp FROM tmp.analytics_access_log_bmp
WHERE ts_date = '2020-08-18' AND event_type = 'BuyNow')
gloomy什么意思)) AS c1
);
毫⽆疑问，由于位图操作消灭了GROUP BY、JOIN等复杂的关系代数操作，效率有极为明显的提升。
The End
Happy Friday night.
民那晚安晚安。
