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。