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.

民那晚安晚安。