使用 Bitmap 实现精确去重
本文介绍如何通过 Bitmap 实现精确去重(Exact Count Distinct)。
Bitmap 去重能够准确计算一个数据集中不重复元素的数量,相比传统的 Count Distinct,可以节省存储空间、加速计算。例如,给定一个数组 A,其取值范围为 [0, n),可采用 (n+7)/8 的字节长度的 bitmap 对该数组去重。即将所有 bit 初始化为 0,然后以数组 A 中元素的取值作为 bit 的下标,并将 bit 置为 1,那么 bitmap 中 1 的个数即为数组 A 中不同元素 (Count Distinct) 的数量。
传统 Count distinct
StarRocks 是基于 MPP 架构实现的,在使用 count distinct 做精确去重时,可以保留明细数据,灵活性较高。但是,由于在查询执行的过程中需要进行多次数据 shuffle(不同节点间传输数据,计算去重),会导致性能随着数据量增大而直线下降。
比如,要通过以下明细数据计算表(dt, page, user_id)每个页面的 UV。
dt | page | user_id |
---|---|---|
20191206 | game | 101 |
20191206 | shopping | 102 |
20191206 | game | 101 |
20191206 | shopping | 101 |
20191206 | game | 101 |
20191206 | shopping | 101 |
StarRocks 在计算时,会按照下图进行计算,先根据 page 列和 user_id 列 group by,最后再 count。
注:图中是 6 行数据在 2 个 BE 节点上计算的示意图。
在上面的计算方式中,由于数据需要进行多次 shuffle,当数据量越来越大时,所需的计算资源就会越来越多,查询也会越来越慢。而使用 Bitmap 去重,就是为了解决传统 count distinct 在大量数据场景下的性能问题。
select page, count(distinct user_id) as uv from table group by page;
| page | uv |
| :---: | :---: |
| game | 1 |
| shopping | 2 |
Bitmap 去重的优势
与传统 count distinct 方式相比,Bitmap 的优势主要体现在以下两点 :
- 节省存储空间:通过用 Bitmap 的一个 Bit 位表示对应下标是否存在,能节省大量存储空间。例如,对 INT32 类型的数据去重,如使用普通的 bitmap,其所需的存储空间只占 COUNT(DISTINCT expr) 的 1/32。StarRocks 采用一种设计的十分精巧的 bitmap,叫做 Roaring Bitmap,相较 Bitmap 会进一步减少内存占用。
- 加速计算:Bitmap 去重使用的是位运算,所以计算速度相较 COUNT(DISTINCT expr) 更快,而且 bitmap 去重在 StarRocks MPP 执行引擎中还可以并行加速处理,提高计算速度。
关于 Roaring Bitmap 的实现,细节可以参考:具体论文和实现。