Paimon 布隆过滤器索引

布隆过滤器原理

布隆过滤器的最优参数推导是其理论核心，理解了这个过程，就能明白 BloomFilter64 构造函数里计算公式的由来了。

下面我们一步步来推导。

首先，我们定义几个关键变量：

n: 预估要插入的元素数量 (对应代码中的 items)。
m: 位图（BitSet）的总位数 (对应代码中的 numBits)。
k: 哈希函数的个数 (对应代码中的 numHashFunctions)。
p: 误判率，即假阳性概率 (False Positive Probability, 对应代码中的 fpp)。

我们的目标是推导出 p 与 n, m, k 之间的关系。

单个哈希函数不命中某一位的概率: 假设哈希函数是完全随机的，那么一个哈希函数的结果命中位图中任意一位的概率是 1/m。反之，不命中这一位的概率就是 1 - 1/m。
k 个哈希函数都不命中某一位的概率: 对于一个要插入的元素，它会经过 k 个哈希函数计算。这 k 个哈希函数都不命中位图中特定某一位的概率是 (1 - 1/m)^k。
插入 n 个元素后，某一位仍为 0 的概率: 当我们将 n 个元素全部插入后，相当于总共进行了 n * k 次哈希计算。某个特定的位在经历这所有 n*k 次哈希后，仍然是 0（即从未被命中）的概率是 (1 - 1/m)^(nk)。
插入 n 个元素后，某一位为 1 的概率: 反过来，某个特定的位是 1 的概率就是 1 - (1 - 1/m)^(nk)。
发生误判的概率 p: 现在，我们测试一个本不存在于集合中的新元素。发生误判意味着，这个新元素经过 k 个哈希函数计算后，得到的 k 个位恰好都已经是 1。这个事件发生的概率就是 p = (某一位为 1 的概率)^k。所以，p = (1 - (1 - 1/m)^(nk))^k。

为了方便计算，我们使用一个广为人知的近似公式：当 x 趋向于无穷大时，(1 - 1/x)^x ≈ e^(-1)。因此，(1 - 1/m)^(nk) = ((1 - 1/m)^m)^(nk/m) ≈ (e^(-1))^(nk/m) = e^(-nk/m)。

将这个近似带入 p 的公式，我们得到一个更简洁的表达式：

p ≈ (1 - e^(-nk/m))^k

现在，我们的问题变成了：当 n 和 m 固定时，k 取何值能让 p 最小？

这是一个求极值的问题。为了方便求导，我们对 p 的近似公式两边取自然对数： ln(p) ≈ k * ln(1 - e^(-nk/m))

令 f(k) = k * ln(1 - e^(-nk/m))，我们对 k 求导并令其为 0就能得到结果。我们可以通过一个更直观的结论来得到结果（这也是标准推导中使用的方法）：

当位图中 0 和 1 的数量大致相等时，布隆过滤器的效率最高。即，一个位是 1 的概率为 1/2 时，误判率 p 最小。

所以，我们令“某一位为 1 的概率”等于 1/2： 1 - e^(-nk/m) = 1/2 e^(-nk/m) = 1/2

两边取自然对数： -nk/m = ln(1/2) = -ln(2) nk/m = ln(2)

解出 k：

k = (m/n) * ln(2)

这就是最优哈希函数个数的计算公式。ln(2) 约等于 0.693。

现在我们知道了最优的 k，可以将其代入误判率 p 的公式中，来求解 m。

从第 2 步我们知道 p ≈ (1/2)^k （因为当 k 最优时，1 - e^(-nk/m) 恰好等于 1/2）。将最优 k 的公式 k = (m/n) * ln(2) 代入： p ≈ (1/2)^((m/n) * ln(2))

两边取自然对数： ln(p) ≈ ((m/n) * ln(2)) * ln(1/2) ln(p) ≈ ((m/n) * ln(2)) * (-ln(2)) ln(p) ≈ -(m/n) * (ln(2))^2

现在，我们整理这个公式，解出 m：

m = - (n * ln(p)) / (ln(2))^2

这就是在给定元素数量 n 和期望误判率 p 的情况下，计算所需最小位图大小 m 的公式。

现在我们回头看 BloomFilter64 的构造函数，你会发现代码完全就是这些公式的直接实现：

// ... existing code ...public BloomFilter64(long items, double fpp) {// 对应公式: m = - (n * ln(p)) / (ln(2))^2int nb = (int) (-items * Math.log(fpp) / (Math.log(2) * Math.log(2)));// 将位数向上对齐到字节的整数倍this.numBits = nb + (Byte.SIZE - (nb % Byte.SIZE));// 对应公式: k = (m/n) * ln(2)this.numHashFunctions =Math.max(1, (int) Math.round((double) numBits / items * Math.log(2)));this.bitSet = new BitSet(new byte[numBits / Byte.SIZE], 0);}
// ... existing code ...

第一行计算 nb，完全匹配我们推导出的 m 的公式，其中 items 是 n，fpp 是 p。
第三行计算 numHashFunctions，也完全匹配我们推导出的 k 的公式，其中 numBits 是 m，items 是 n。

关于为什么0和1相等时布隆过滤器最好的说明

直觉的核心：信息论与平衡

从上面两个极端可以看出，布隆过滤器的效率取决于一种平衡。

一方面，我们希望 k 尽可能大，这样“测试”的条件就更苛刻，偶然通过测试的概率 p 的指数部分 k 就更大，p 会更小。
另一方面，我们不希望 k 太大，因为这会让位图迅速被填满（1 的比例迅速升高），导致“测试”的基础概率（即一个随机位是 1 的概率）变得很高，这又会推高 p。

最优状态，就是在这两种力量之间找到完美的平衡点。

这个平衡点，从信息论的角度来看，就是信息熵最大的状态。对于一个只有 0 和 1 的系统，当 0 和 1 的数量各占一半（50%）时，系统的不确定性最大，它能携带的信息量也最大。

当位图中 1 的比例是 50% 时，它处在信息量最大的状态。这意味着它对“哪些元素被添加了”这件事保留了最多的区分度。
此时，一个随机位是 1 的概率是 1/2。
一个不存在的元素，它对应的 k 个随机位恰好都是 1 的概率是 (1/2)^k。

总结一下直觉:

一个几乎全为 0 的位图和一个几乎全为 1 的位图，都没有什么“信息含量”。前者告诉你“啥都没有”，后者告诉你“啥都有可能”。只有当 0 和 1 数量均衡时，位图才处在最“混乱”、最“不可预测”的状态，此时它对世界的描述能力最强，区分度最高，因此误判的概率也就最低。

`BloomFilterFileIndex`

我们来全面且有条理地分析 BloomFilterFileIndex 这个类。它是 Paimon 自建索引体系中布隆过滤器（Bloom Filter）的具体实现，扮演着至关重要的角色。

这个类遵循了 Paimon 索引框架定义的 FileIndexer 接口，提供了创建布隆过滤器索引的写入器（Writer）和读取器（Reader）的能力。

BloomFilterFileIndex 的核心职责是：

提供布隆过滤器的写入逻辑：在数据文件生成时，收集列中的所有值，构建一个布隆过滤器。
提供布隆过滤器的读取和判断逻辑：在查询时，加载布隆过滤器，并用它来快速判断一个查询条件（等值查询）是否绝对不可能在文件中命中。如果布隆过滤器判断不存在，那么就可以安全地跳过整个文件，从而极大地提升查询性能。

它通过 BloomFilterFileIndexFactory 被注册到 Paimon 的 FileIndexer 体系中，当用户配置 'file-index.bloom-filter.columns' = '...' 时，就会实例化这个类来工作。

org.apache.paimon.fileindex.FileIndexerFactory

// ... existing code ...
org.apache.paimon.fileindex.bloomfilter.BloomFilterFileIndexFactory
// ... existing code ...

结构分析

BloomFilterFileIndex 本身是一个入口和配置类，其核心逻辑封装在两个静态内部类 Writer 和 Reader 中。

BloomFilterFileIndex 外部类主要负责配置的解析和对象的创建。

构造函数:
```
// ... existing code ...
public BloomFilterFileIndex(DataType dataType, Options options) {this.dataType = dataType;this.items = options.getInteger(ITEMS, DEFAULT_ITEMS);this.fpp = options.getDouble(FPP, DEFAULT_FPP);
}
// ... existing code ...
```
它接收列的 DataType 和用户通过 WITH 子句传入的 Options。它会解析两个关键参数：
- items (file-index.bloom-filter.items): 预估的列中独立值的数量（NDV），默认为 100 万。
- fpp (file-index.bloom-filter.fpp): 期望的假阳性率（False Positive Probability），默认为 0.1。这两个参数共同决定了布隆过滤器底层位图（BitSet）的大小和哈希函数的数量，是空间占用和准确率之间的权衡。
createWriter() 和 createReader(): 这两个方法是 FileIndexer 接口的实现，它们是工厂方法，分别用于创建真正的写入器和读取器实例，并将解析好的配置传递进去。

`writer` (静态内部类)

Writer 负责构建布隆过滤器并将其序列化。

核心成员:
```
// ... existing code ...
private static class Writer extends FileIndexWriter {private final BloomFilter64 filter;private final FastHash hashFunction;
// ... existing code ...
```
- filter: 一个 BloomFilter64 实例。这是 Paimon 实现的 64 位哈希的布隆过滤器。所有的值都会被添加到这个过滤器中。
- hashFunction: 一个 FastHash 实例。Paimon 为不同的数据类型（数值、字符串等）提供了专门的、高性能的哈希函数，以获得更好的哈希分布。FastHash.getHashFunction(type) 会根据列类型返回最合适的哈希函数。
write(Object key) 方法:
```
// ... existing code ...@Overridepublic void write(Object key) {if (key != null) {filter.addHash(hashFunction.hash(key));}}
// ... existing code ...
```
这个方法每接收一个列值 (key)，就先用 hashFunction 计算出它的 64 位哈希值，然后调用 filter.addHash() 将这个哈希值添加到布隆过滤器中。这个过程会设置底层 BitSet 中的若干个位。

serializedBytes() 方法:

// ... existing code ...@Overridepublic byte[] serializedBytes() {int numHashFunctions = filter.getNumHashFunctions();byte[] serialized = new byte[filter.getBitSet().bitSize() / Byte.SIZE + Integer.BYTES];// big endianserialized[0] = (byte) ((numHashFunctions >>> 24) & 0xFF);serialized[1] = (byte) ((numHashFunctions >>> 16) & 0xFF);serialized[2] = (byte) ((numHashFunctions >>> 8) & 0xFF);serialized[3] = (byte) (numHashFunctions & 0xFF);filter.getBitSet().toByteArray(serialized, 4, serialized.length - 4);return serialized;}
// ... existing code ...

当文件写入完成时，这个方法被调用，它定义了 Paimon 布隆过滤器的序列化格式：

前 4 个字节: 以大端序 (Big Endian) 存储哈希函数的数量 (numHashFunctions)。
后续所有字节: 存储布隆过滤器底层的 BitSet 的内容。

`Reader` (静态内部类)

Reader 负责反序列化布隆过滤器并提供查询能力。

构造函数:

// ... existing code ...public Reader(DataType type, byte[] serializedBytes) {// big endian, not little endianint numHashFunctions =((serializedBytes[0] & 0xFF) << 24)| ((serializedBytes[1] & 0xFF) << 16)| ((serializedBytes[2] & 0xFF) << 8)| (serializedBytes[3] & 0xFF);BitSet bitSet = new BitSet(serializedBytes, 4);this.filter = new BloomFilter64(numHashFunctions, bitSet);this.hashFunction = FastHash.getHashFunction(type);}
// ... existing code ...

源码注释中写的是 little endian，但从代码实现 (byte[0] << 24) ... 来看，这实际上是大端序 (Big Endian) 的解析方式。这是一个小小的代码注释与实现不符的地方。

它执行与 Writer.serializedBytes() 相反的操作：

从字节数组的前 4 个字节解析出哈希函数的数量。
用剩下的字节构建 BitSet。
使用这两个信息重建一个 BloomFilter64 对象。

visitEqual(FieldRef fieldRef, Object key) 方法:
```
// ... existing code ...@Overridepublic FileIndexResult visitEqual(FieldRef fieldRef, Object key) {return key == null || filter.testHash(hashFunction.hash(key)) ? REMAIN : SKIP;}
// ... existing code ...
```
这是查询的核心。当查询引擎传来一个等值过滤条件（如 WHERE col = 'some_value'）时：
1. key 就是 'some_value'。
2. 用同样的 hashFunction 计算 key 的哈希值。
3. 调用 filter.testHash() 在布隆过滤器中进行判断。
4. 结果：
  - 如果 testHash 返回 true（可能存在），则此过滤器无法给出确定性结论，必须继续读取该文件。返回 REMAIN。
  - 如果 testHash 返回 false（绝对不存在），则可以确定该文件中没有任何一行的 col 等于 'some_value'。返回 SKIP，整个文件被跳过。

总结

BloomFilterFileIndex 是 Paimon 索引框架中一个设计精良、职责清晰的组件。它通过组合 BloomFilter64 和 FastHash，为 Paimon 提供了独立于文件格式（Parquet/ORC）的、高效的布隆过滤器索引能力。其内部的 Writer 和 Reader 分别负责索引的构建和使用，定义了清晰的序列化格式，并通过 visitEqual 方法与查询引擎的谓词下推逻辑无缝集成，是 Paimon 实现文件级别过滤（File Skipping）的关键技术之一。

`BloomFilter64`

它是 Paimon 中布隆过滤器功能的核心底层实现，负责处理具体的数学和位运算逻辑。

BloomFilter64 与 BloomFilterFileIndex 的关系是：BloomFilterFileIndex 是面向 Paimon 索引框架的“门面”，而 BloomFilter64 则是真正干活的“引擎”。

BloomFilter64 的设计目标非常明确：提供一个高效、低内存占用的布隆过滤器实现。它的名字 64 强调了它处理的是 64位的哈希值（long）。这与 Paimon 中另一个 BloomFilter 类（处理32位哈希值）形成了对比。使用 64 位哈希可以进一步降低哈希冲突的概率。

它的主要职责包括：

根据预估元素数量和期望假阳性率，计算并初始化布隆过滤器所需的最佳参数（位图大小、哈希函数个数）。
提供 addHash 方法，将一个 64 位哈希值添加到过滤器中。
提供 testHash 方法，判断一个 64 位哈希值是否可能存在于过滤器中。
与内部的 BitSet 类协作，完成底层的位操作。

构造函数分析

BloomFilter64 提供了两个构造函数，分别用于创建和加载。

创建新的布隆过滤器

// ... existing code ...public BloomFilter64(long items, double fpp) {// 1. 计算最优的位数 (m)int nb = (int) (-items * Math.log(fpp) / (Math.log(2) * Math.log(2)));// 2. 将位数向上对齐到字节的整数倍this.numBits = nb + (Byte.SIZE - (nb % Byte.SIZE));// 3. 计算最优的哈希函数个数 (k)this.numHashFunctions =Math.max(1, (int) Math.round((double) numBits / items * Math.log(2)));// 4. 初始化底层的 BitSetthis.bitSet = new BitSet(new byte[numBits / Byte.SIZE], 0);}
// ... existing code ...

这个构造函数体现了布隆过滤器的核心数学原理：

计算 numBits (m): m = - (n * ln(p)) / (ln(2)^2) 是计算最优位图大小的经典公式，其中 n 是 items（预估元素数量），p 是 fpp（假阳性率）。
字节对齐: nb + (Byte.SIZE - (nb % Byte.SIZE)) 是一个巧妙的技巧，它将计算出的位数 nb 向上取整到最近的 8 的倍数，以确保 bitSet 的底层 byte[] 数组大小是整数。
计算 numHashFunctions (k): k = (m / n) * ln(2) 是计算最优哈希函数数量的公式。结果被四舍五入并确保至少为 1。
初始化 BitSet: 根据计算出的位数，创建一个全为 0 的 byte 数组，并用它来初始化 BitSet。

从已有数据加载布隆过滤器

// ... existing code ...public BloomFilter64(int numHashFunctions, BitSet bitSet) {this.numHashFunctions = numHashFunctions;this.numBits = bitSet.bitSize();this.bitSet = bitSet;}
// ... existing code ...

这个构造函数用于从序列化的数据中恢复一个布隆过滤器。它直接接收已经计算好的 numHashFunctions 和包含位图数据的 BitSet 对象，用于反序列化的场景。

核心算法：`addHash` 和 `testHash`

这两个方法是布隆过滤器算法的精髓，它们都采用了一种称为 "Kirsch-Mitzenmacher" 优化 的技巧来模拟多个哈希函数。

// ... existing code ...public void addHash(long hash64) {// 1. 将 64 位哈希拆分为两个 32 位哈希int hash1 = (int) hash64;int hash2 = (int) (hash64 >>> 32);// 2. 循环 k 次，模拟 k 个哈希函数for (int i = 1; i <= numHashFunctions; i++) {// 3. 生成组合哈希：g_i(x) = h1(x) + i * h2(x)int combinedHash = hash1 + (i * hash2);// 4. 确保哈希值为正数if (combinedHash < 0) {combinedHash = ~combinedHash;}// 5. 计算在位图中的位置并设置该位int pos = combinedHash % numBits;bitSet.set(pos);}}public boolean testHash(long hash64) {int hash1 = (int) hash64;int hash2 = (int) (hash64 >>> 32);for (int i = 1; i <= numHashFunctions; i++) {int combinedHash = hash1 + (i * hash2);if (combinedHash < 0) {combinedHash = ~combinedHash;}int pos = combinedHash % numBits;// 只要有一个位没有被设置，就说明元素肯定不存在if (!bitSet.get(pos)) {return false;}}// 所有位都被设置了，说明元素可能存在return true;}
// ... existing code ...

算法解析:

哈希拆分: 仅用一个 64 位的哈希输入，通过将其拆分为高 32 位和低 32 位，得到了两个独立的 32 位哈希值 hash1 和 hash2。
模拟多哈希: 利用公式 g_i(x) = h1(x) + i * h2(x)，通过改变 i 的值，可以用 hash1 和 hash2 线性组合出 numHashFunctions 个不同的哈希值。这避免了执行 k 次独立的、计算成本高的哈希函数，极大地提升了性能。
正数处理: if (combinedHash < 0) { combinedHash = ~combinedHash; } 确保了 combinedHash 总是正数，这样取模操作 % numBits 的结果也会落在 [0, numBits-1] 的预期范围内。
位操作:
- addHash: 将计算出的所有 pos 对应的位设置为 1。
- testHash: 检查计算出的所有 pos 对应的位是否都为 1。只要有一个位是 0，就可以立即断定元素不存在，并返回 false。

内部类 `BitSet`

这是一个非常轻量级的、针对布隆过滤器场景优化的位图实现。

// ... existing code ...public static class BitSet {private static final byte MAST = 0x07; // 等价于二进制 00000111private final byte[] data;
// ... existing code ...public void set(int index) {// 找到字节: index / 8  (等价于 index >>> 3)// 找到位:   index % 8  (等价于 index & 7, 即 index & MAST)data[(index >>> 3) + offset] |= (byte) ((byte) 1 << (index & MAST));}public boolean get(int index) {return (data[(index >>> 3) + offset] & ((byte) 1 << (index & MAST))) != 0;}
// ... existing code ...}
}

位运算技巧: 它没有使用 Java 自带的 java.util.BitSet，而是直接操作 byte[] 数组，这减少了对象开销，更适合序列化和内存控制。
index >>> 3 (无符号右移3位) 是一个非常高效的计算 index / 8 的方法，用于定位到 index 所在的字节。
index & MAST (按位与 0x07) 是一个高效的计算 index % 8 的方法，用于定位到在该字节内的具体哪一位。
set 使用按位或 |= 操作来将目标位置1，而不影响其他位。
get 使用按位与 & 操作来检查目标位是否为1。