ClickHouse Bloom Filter Skip Index

🔍 什么是 Bloom Filter Skip Index？

Bloom Filter Skip Index 是 ClickHouse 中的一种 数据跳过索引机制，不是传统的 B+ Tree 类型索引。它通过在每个数据块（granule）中为指定字段建立布隆过滤器，在查询时先判断是否“可能包含目标值”，从而跳过不相关的数据块，实现显著加速。

适合用于：

查询中经常出现 =, IN, LIKE 等条件的字段
高基数（unique 值很多）字段，如 email、UUID、session_id
大宽表或日志型表，查询字段较分散

⚙️ Bloom Filter 索引工作机制

✅ 插入阶段（建索引 + 写入）

ClickHouse 将表数据分成 granule（颗粒），每个 granule 默认约 8192 行。
每个 granule 对于被索引的字段，建立一个布隆过滤器：
- 使用多种哈希函数对字段值进行哈希
- 把对应的 bit 位设置为 1
所有布隆过滤器信息写入 .idx 索引文件，与数据文件并存。

✅ 查询阶段（跳过扫描）

查询来临时，ClickHouse对查询条件（如 email = '[email protected]'）执行相同的哈希操作。
然后逐块读取 Bloom Filter 判断：
- 如果所有对应 bit 位都是 1 → 可能有 → 读取数据块进一步判断
- 如果有任意 bit 位是 0 → 一定没有 → 跳过该 granule

这一步完成时，ClickHouse 就跳过了大量与查询无关的数据块，极大减少磁盘 IO 和 CPU 解压计算。

🔢 参数详解

1. `bloom_filter(x)`

表示布隆过滤器允许的最大误判率。例如：

1	INDEX idx_email email TYPE bloom_filter(0.01)

0.01 ➜ 表示误判率为 1%
误判率越低 ➜ 索引越大，跳过精度越高，insert 写入开销略高
ClickHouse 会自动计算：
- 位图长度（bit array size）
- 使用的哈希函数个数（通常 3~7 个）

2. `GRANULARITY`

控制每多少个 granule 建一个布隆索引（最小为 1）：

1	GRANULARITY 1

1 表示每个 granule 都建一个索引
4 表示每 4 个 granule 共享一个索引

🌟 粒度越小，跳过越精细，Bloom Filter 越多；粒度越大，索引越小但误判率更高。

❓❓❓ 常见问题 & 回答整理

❓ Bloom Filter 是怎么判断是否“包含某个值”的？

布隆过滤器不存储原始值，只通过哈希函数记录 bit 位。

例如 [email protected]：

会被多个哈希函数处理 → 变成几个 bit 位（如 1129、4073、7217）
这些位在索引中被置为 1
查询时用相同哈希函数检查这些位：
- 全是 1：可能存在（不确定）
- 有 0：一定不存在 → 跳过该块 ✅

❓ Bloom Filter 中的哈希函数是怎么工作的？

✅ Bloom Filter 并不真的用 N 个完全不同的哈希函数！
而是使用两个基础哈希函数（通常来自 MurmurHash3），通过如下公式派将一个值映射到多个 bit 位位置：
这是 Kirsch and Mitzenmacher 提出的经典优化：

1
H(i, x) = h1(x) + i * h2(x) mod m
h1(x) 和 h2(x) 是基础哈希函数（来自 MurmurHash3）

i 是第几个函数（0～k-1）

m 是 bit array 的大小（通常是 2^13 = 8192）

最终得到 k 个 bit 位置

ClickHouse 源码实现是：

使用 MurmurHash3（快速 + 高熵 + 分布均匀）
默认取 2 个基础 hash 值（比如 h1 和 h2）
然后用上面那个公式生成多个位置

比如设置了：

1	bloom_filter(0.01)

ClickHouse 内部会根据你的目标误判率自动算出要几个 hash：

1% 误判率时，通常是 6～7 个 hash 函数
0.1% 误判率时，可能会上到 9～10 个

这些不是单独函数，而是从 h1, h2 推导的派生位置，真正底层实现是在 C++ 代码里算出来的。
这样只需两次哈希计算就能派生出多个位置，大大降低计算成本，同时保留高效的分布特性。

❓ 会不会误判？（误把不存在的数据块当成可能有）

是的，这是 Bloom Filter 的设计特点：

False Positive（假阳性） 是允许的
它永远不会出现 False Negative（即漏掉真正的数据）

误判率可通过 bloom_filter(0.01) 控制，但数据块越大、插入越多，bit 被重复置 1 的概率也越大 ➜ 误判率升高

❓ 插入数据量越来越大时，ClickHouse 会自动扩展 Bloom Filter 吗？

不会！

每个 granule 的 Bloom Filter 是固定配置，建表时的参数定死：bit 位大小、哈希函数个数
数据多了只是产生更多的 granule，每个都按原配置建索引
想调整参数，只能重建表 or 重写数据（如 OPTIMIZE FINAL）

❓ `GRANULARITY` 设置对误判的影响？

GRANULARITY 1：每 8192 行就建一个索引，跳过粒度细，误判率低
GRANULARITY 4：每 32768 行一个索引，跳过效果变差，误判率升高，但索引文件更小

选择时应根据查询频率 + 字段基数来权衡性能与空间

❓ 为什么有时候明明 `= 'x'` 结果还是加载了很多数据块？

可能是布隆过滤器判断“可能存在”但其实是误判（bit 位刚好都被其他值设置过了）

✅ 使用建议

字段特征	是否适合建 Bloom Filter 索引	推荐设置
高基数（email, UUID, token）	✅ 是	`bloom_filter(0.01) GRANULARITY 1`
低基数（gender, status）	❌ 否	不推荐，几乎全部误判
查询常用字段	✅ 是	精度越高，跳过效果越明显
数据量巨大	✅ 是	可以配合分区和 TTL 控制 granule 数量

📌 总结一句话

Bloom Filter Skip Index 是 ClickHouse 中提升查询性能的重要武器，适用于高基数、频繁被查的字段，通过设置合理的误判率和 granularity，可在大数据量场景下显著提升查询速度。

📎 后续可做（选项）

构建“索引策略推荐器”：根据字段类型 + 基数 + 查询频率智能推荐是否建索引
编写 Python 脚本演示 Bloom Filter bit 位变化 + 查询误判过程
建立实验对比不同配置对查询耗时和误判率的影响