位图索引与 BloomFilter 在 OLAP 中的应用

考察点

考察对两种概率/位图结构的原理理解和落地场景的掌握。面试官想看你能否讲清各自的前提条件（位图要低基数、Bloom 要允许假阳性）、在 ClickHouse 和 Doris 里的具体形态，以及精确去重这类经典应用。追问常考 BloomFilter 误判率和位图去重的实现细节。

参考答案

位图索引：把谓词变成位运算

位图索引的思路很直白：某列有 N 个不同取值，就为每个取值维护一个长度为行数的 bit 数组，第 i 位为 1 表示第 i 行等于这个值。查询条件直接转成位运算：city='北京' AND channel='app' 就是两个 bitmap 做 AND，结果位图里为 1 的行就是命中行。集合运算（IN、OR）也是天然的位操作，现代 CPU 一次能处理 64 位甚至 512 位（SIMD），快得离谱。

代价同样明显：基数一高，bitmap 数量爆炸，一列几万个取值就要几万个位图，存储和构建都不可行。所以位图索引的适用前提是低基数列——性别、状态码、省份、渠道这类几十个到几百个取值的字段是它的主场。工程上用 RoaringBitmap 压缩稀疏位图，把存储压下来、交并运算保持高效，这基本是业界标准实现。

位图的两个实战场景

第一个是过滤加速。Doris、StarRocks 支持对列建 Bitmap 索引，等值和 IN 查询直接走位图。第二个是精确去重加速，这是位图在 OLAP 里最出彩的应用：用户画像、留存分析里大量 COUNT DISTINCT user_id，如果把 user_id 预先映射成连续整数（全局字典编码），那么「某天活跃用户的集合」就是一个 RoaringBitmap，跨天留存 = 两天位图做 AND 再 count，UV 合并 = OR 再 count——精确去重从「扫描明细做大集合去重」变成「位图交并」，快几个数量级。Doris 的 bitmap_union/bitmap_intersect 函数、hive/Spark 侧预生成位图列导入，都是这个套路。

BloomFilter：用误判换 IO

BloomFilter 解决的问题不同：快速判断「一个值肯定不在这个集合里」。结构上是一个 bit 数组加 k 个哈希函数，写入时把 k 个哈希位置 1，查询时只要有一位是 0 就肯定不存在，全是 1 则「可能存在」。关键性质：不会漏报（假阴性为零），会误报（假阳性），误判率由数组大小和哈希个数决定——比如每元素 10 bit、k 取 7 左右，误判率大约 1%。

OLAP 里的典型用法有两个。一是存储层过滤：Doris 对高基数列（如 user_id、订单号）支持 BloomFilter 索引，等值查询先问 BloomFilter，「肯定不存在」就整块跳过不读，省掉大量 IO。ClickHouse 也有 bloom_filter 类型的跳数索引，逻辑一样，作用在 granule 粒度。二是 join 下推：分布式引擎做大表 join 时，先把小表 join key 建成 BloomFilter 发给大表扫描侧过滤，大表数据提前丢弃大部分，shuffle 量暴降——这是 MPP 引擎的常规优化。

两者的对照

实践里的判断逻辑

一个列该不该建这类索引，判断顺序是：先看查询模式是不是等值/集合类（范围查询这两种都帮不上忙），再看基数——低基数上位图（还能享受交并加速），高基数上 BloomFilter，中间地带（几千到几十万）看实测。还要注意 BloomFilter 索引在数据持续追加时要随 block 重建，高更新频率表上维护成本不可忽视。ClickHouse 里建跳数索引前要先想清楚它的粒度是 granule（默认 8192 行），只有列值在 granule 间有聚集性时过滤效果才好，完全随机的列建 BloomFilter 基本白建。

可能的追问

• BloomFilter 为什么不能删除元素？—— 一个 bit 可能被多个元素共享，清零会误伤别人。要删除得用 Counting BloomFilter（计数替代 bit）或者定期重建。
• 位图做精确去重的前提是什么？—— 元素要先全局字典编码成连续整数，位图位置才有意义。编码本身要一套全局 ID 映射服务（或离线预生成），这是工程上最贵的一环。
• ClickHouse 的 bloom_filter 跳数索引什么时候没用？—— 列值在 granule 内完全随机分布时，几乎每个 granule 都「可能存在」，过滤率接近零。它对按该列有局部聚集（如按用户分桶写入）的表才有效。