Q&A
Q：如圖。
A：當(dāng)然是自帶的。其實(shí)RoaringBitmap正是ClickHouse位圖的底層實(shí)現(xiàn)（笑
RoaringBitmap的預(yù)備知識(shí)請(qǐng)見這里。
在CH中產(chǎn)生位圖
使用普通函數(shù)bitmapBuild可以由無(wú)符號(hào)整形數(shù)的數(shù)組直接產(chǎn)生位圖，e.g.
WITH bitmapBuild([32, 65, 127, 1026]) AS bm
SELECT bm,toTypeName(bm);
┌─bm─┬─toTypeName(bm)─────────────────────────┐
│ A? │ AggregateFunction(groupBitmap, UInt16) │
└────┴────────────────────────────────────────┘
可見，位圖在CH中的本質(zhì)是AggregateFunction(groupBitmap, UInt*)類型的（*由位圖中的最大值彈性決定），即groupBitmap這個(gè)聚合函數(shù)產(chǎn)生的中間結(jié)果。根據(jù)聚合函數(shù)的combinator語(yǔ)法，加上-Merge后綴再查詢一次：
WITH bitmapBuild([32, 65, 127, 1026]) AS bm
SELECT bm,groupBitmapMerge(bm);
┌─bm─┬─groupBitmapMerge(bm)─┐
│ A? │ 4 │
└────┴──────────────────────┘
也就是說(shuō)，groupBitmap函數(shù)返回的是位圖的基數(shù)（即1的數(shù)量）。顯然，與-Merge后綴相對(duì)，我們還可以用-State后綴來(lái)對(duì)某一列生成位圖：
SELECT groupBitmapState(toUInt64(user_id)) FROM ods.analytics_access_log_local
WHERE ts_date = today();
-- 這個(gè)位圖很長(zhǎng)，所以顯示大量亂碼hhh
ClickHouse提供了很多位圖操作的函數(shù)，參見官方文檔，稍后會(huì)給出示例。
翻翻源碼
既然位圖都是從groupBitmap函數(shù)構(gòu)建出來(lái)的，就來(lái)看看與其相關(guān)的實(shí)現(xiàn)吧。來(lái)到AggregateFunctionGroupBitmapData.h，定義如下：
template <typename T>
struct AggregateFunctionGroupBitmapData
{
bool doneFirst = false;
RoaringBitmapWithSmallSet<T, 32> rbs;
static const char * name() { return "groupBitmap"; }
};
其核心就是RoaringBitmapWithSmallSet這個(gè)數(shù)據(jù)結(jié)構(gòu)，繼續(xù)看代碼：
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庫(kù)中的實(shí)現(xiàn)，SmallSet又是什么鬼？其實(shí)它的定義位于SmallTable.h中，是一個(gè)限定大?。o(wú)法擴(kuò)容）的小集合，底層用數(shù)組來(lái)存儲(chǔ)。在前面的結(jié)構(gòu)體里，模板參數(shù)small_set_size設(shè)為32，說(shuō)明它最多只能容下32個(gè)元素。
繼續(xù)向下讀一段：
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);
}
// ....
這下就非常明顯了：當(dāng)位圖的基數(shù)少于32時(shí)，僅使用SmallSet存儲(chǔ)；一旦超過(guò)此閾值，就調(diào)用toLarge()方法轉(zhuǎn)化為RoaringBitmap，此后都在RoaringBitmap上操作。之所以有這種區(qū)別，想來(lái)是因?yàn)镾mallSet在小數(shù)據(jù)量下的性能比RBM更優(yōu)吧。
當(dāng)然，在RoaringBitmapWithSmallSet之間進(jìn)行運(yùn)算時(shí)，就需要分情況討論了。舉個(gè)栗子，兩個(gè)CH位圖做按位與運(yùn)算（對(duì)應(yīng)bitmapAnd函數(shù)），對(duì)應(yīng)方法如下：
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);
}
}
- 當(dāng)this為小位圖時(shí)，遍歷this并逐個(gè)檢查其中的元素在r1是否存在（只是根據(jù)r1的大小不同調(diào)用的方法不同而已），將重合的元素放入緩存，再重新插入this中。
- 當(dāng)this為大位圖時(shí)，直接調(diào)用CRoaring自帶的roaring_bitmap_and_inplace()方法做與運(yùn)算。注意如果r1為小位圖，需要先調(diào)用getNewRbFromSmall()方法生成新的RBM。
位圖操作函數(shù)的定義與實(shí)現(xiàn)都位于FunctionsBitmap.h內(nèi)，例如剛才說(shuō)過(guò)的bitmapAnd函數(shù)：
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);
}
};
位圖部分的源碼在整個(gè)ClickHouse體系中算是相當(dāng)友好的，看官也可自行查看，不再贅述。
CH位圖的應(yīng)用
我們知道，位圖在需要精確統(tǒng)計(jì)基數(shù)及快速求交集、并集的場(chǎng)景非常有用。以用戶行為（點(diǎn)擊流）數(shù)據(jù)為例，創(chuàng)建以下的表：
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以位圖存儲(chǔ)。注意為了配合AggregateFunction，引擎應(yīng)使用AggregatingMergeTree，并且此表的行數(shù)肯定偏少，所以索引粒度可適當(dāng)降低。
取一些數(shù)據(jù)灌入表中：
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;
這樣，我們就可以非?？焖俚亟y(tǒng)計(jì)每天查看過(guò)商品詳情頁(yè)的用戶數(shù)：
SELECT
ts_date,
bitmapCardinality(user_bmp) AS user_cnt
FROM tmp.analytics_access_log_bmp
WHERE event_type = 'OpenGoodsDetail';
以及統(tǒng)計(jì)前一日打開過(guò)App，后一日點(diǎn)擊過(guò)“立即購(gòu)買”的用戶轉(zhuǎn)化率：
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
);
毫無(wú)疑問(wèn)，由于位圖操作消滅了GROUP BY、JOIN等復(fù)雜的關(guān)系代數(shù)操作，效率有極為明顯的提升。
The End
Happy Friday night.
民那晚安晚安。
