BitmapFileIndex

BitmapFileIndex?這個類 是 Paimon 中一個非常重要的索引類型，它使用位圖（Bitmap）來精確定位數據，尤其擅長處理低基數（low-cardinality）列的等值查詢。

BitmapFileIndex?實現了?FileIndexer?接口，其核心是利用?RoaringBitmap32?這種高效的壓縮位圖數據結構。

BitmapFileIndex?的核心職責是為列中的每一個獨立值（distinct value）創建一個位圖。位圖中的每一位對應文件中的一行數據。如果某行的值是?X，那么在值?X?對應的位圖里，該行號對應的位就會被置為 1。

它的工作原理:

• 寫入時: 遍歷數據文件，為遇到的每個唯一值（比如 'male', 'female'）維護一個?RoaringBitmap32。當第?i?行的值是 'male' 時，就在 'male' 對應的位圖中將第?i?位置為 1。
• 查詢時: 當查詢條件為?WHERE gender = 'male'?時，它會直接加載 'male' 對應的位圖。這個位圖精確地記錄了所有?gender?為 'male' 的行號。Paimon 的讀取器可以利用這些行號，只讀取文件中特定的行，從而避免全量掃描。

它特別適用于等值查詢 (=)、IN 查詢、IS NULL?以及它們的反向操作 (!=,?NOT IN,?IS NOT NULL)。

BitmapFileIndex?的主要邏輯同樣封裝在內部類?Writer?和?Reader?中。

BitmapFileIndex?(外部類)

這個外部類非常簡潔，主要負責：

1. 配置管理: 存儲列的?DataType?和用戶傳入的?Options。
2. 工廠方法: 提供?createWriter()?和?createReader()?方法，用于創建具體的讀寫實例。

// ... existing code ...
public class BitmapFileIndex implements FileIndexer {public static final int VERSION_1 = 1;public static final int VERSION_2 = 2;public static final String VERSION = "version";public static final String INDEX_BLOCK_SIZE = "index-block-size";private final DataType dataType;private final Options options;public BitmapFileIndex(DataType dataType, Options options) {
// ... existing code ...}@Overridepublic FileIndexWriter createWriter() {return new Writer(dataType, options);}@Overridepublic FileIndexReader createReader(SeekableInputStream seekableInputStream, int start, int length) {
// ... existing code ...}
// ... existing code ...

值得注意的是，它定義了兩個版本?VERSION_1?和?VERSION_2，這表明其序列化格式有過演進。

Writer?(靜態內部類)

Writer?負責構建位圖索引并將其序列化到字節數組。

• 核心成員:

  // ... existing code ...
  private static class Writer extends FileIndexWriter {// ...private final Map<Object, RoaringBitmap32> id2bitmap = new HashMap<>();private final RoaringBitmap32 nullBitmap = new RoaringBitmap32();private int rowNumber;// ...
  }
  // ... existing code ...
  

  • id2bitmap: 這是最核心的數據結構，一個?Map。它的?Key?是列中的獨立值（比如 'male'），Value?是該值對應的?RoaringBitmap32?位圖。
  • nullBitmap: 單獨為?NULL?值維護一個位圖。
  • rowNumber: 一個計數器，記錄當前處理到文件的第幾行。

這個 Map 結構使得等值查詢變得極其高效。

當有一個查詢 WHERE city = '北京' 時，Reader 的邏輯是：

直接在 id2bitmap 這個 Map（從索引文件中反序列化回來）中查找 key = '北京'。
立即就能找到對應的 RoaringBitmap32，其內容是 {0, 2, 5}。
這個位圖精確地告訴了查詢引擎：只需要去數據文件中讀取第 0、2、5 行，其他行都可以完全跳過。

• write(Object key)?方法:

  // ... existing code ...@Overridepublic void write(Object key) {if (key == null) {nullBitmap.add(rowNumber++);} else {id2bitmap.computeIfAbsent(valueMapper.apply(key), k -> new RoaringBitmap32()).add(rowNumber++);}}
  // ... existing code ...
  

  這個邏輯非常清晰：每來一個值?key，就將其對應的位圖（如果是新值就創建一個新的）的?rowNumber?位設置為 1，然后行號加一。

• serializedBytes()?方法: 這是最復雜的部分，它定義了位圖索引的物理存儲格式。

  1. 序列化位圖: 將?id2bitmap?和?nullBitmap?中的所有?RoaringBitmap32?對象序列化成字節數組。
  2. 優化: 這里有一個重要的優化。如果一個值的位圖基數（cardinality）為 1，意味著這個值在文件中只出現了一次。此時，沒有必要存儲整個位圖，只需記錄下它出現的行號即可。

     // ... existing code ...if (v.getCardinality() == 1) {bitmapOffsets.put(k, -1 - v.iterator().next());} else {
     // ... existing code ...
     

     代碼通過存儲一個負數?-1 - rowNumber?來表示這種情況，既節省了空間，又傳遞了信息。
  3. 構建元數據 (BitmapFileIndexMeta): 將所有值的位圖在最終字節數組中的偏移量（offset）和長度（length）等信息打包成一個元數據對象。
  4. 寫入文件: 按照?[版本號] -> [元數據] -> [位圖數據體]?的順序將所有內容寫入一個?ByteArrayOutputStream?并返回。

Reader?(靜態內部類)

Reader?負責解析索引文件，并根據查詢條件返回一個結果位圖。

• 延遲加載 (Lazy Loading):?Reader?的設計采用了延遲加載模式。在構造時，它只記錄了輸入流和起始位置。只有當?visit?系列方法被真正調用時，它才會去解析元數據?readInternalMeta()。這避免了不必要的 IO。

• visitIn(FieldRef fieldRef, List<Object> literals)?方法: 這是處理?IN?和?=?查詢的核心。

  // ... existing code ...private RoaringBitmap32 getInListResultBitmap(List<Object> literals) {return RoaringBitmap32.or(literals.stream().map(it ->bitmaps.computeIfAbsent(valueMapper.apply(it), this::readBitmap)).iterator());}
  // ... existing code ...
  

  它的邏輯是：

  1. 對查詢條件中的每一個值（literals），調用?readBitmap?方法找到或加載它對應的位圖。
  2. 使用?RoaringBitmap32.or?操作將所有這些位圖進行邏輯或運算。結果就是所有滿足?IN (...)?條件的行的集合。

• readBitmap(Object bitmapId)?方法: 這個方法根據?bitmapId（也就是列的值）去元數據中查找它的偏移量和長度，然后從輸入流的正確位置讀取數據，反序列化成一個?RoaringBitmap32?對象。它同樣處理了行號被編碼為負數的情況。

• 處理其他查詢:

  • visitNotIn: 先調用?getInListResultBitmap?得到命中的位圖，然后調用?bitmap.flip(0, rowCount)?對整個文件的行范圍進行邏輯非操作，得到不匹配的行。
  • visitIsNull?/?visitIsNotNull: 本質上是調用?visitIn?/?visitNotIn?并傳入?null?作為字面量。

getValueMapper

這是一個輔助方法，用于將某些 Paimon 的數據類型轉換為更適合做 Map Key 的類型。例如，它會將?Timestamp?對象轉換為毫秒或微秒的?long?值，將?BinaryString?進行?copy()?以確保其作為 Key 的穩定性。

多個SST的索引？

MergeTreeWriter?寫入的數據，由于?RollingFileWriter?的機制，確實可能會被切分成多個 SST 文件。

那么，既然數據分布在多個文件中，之前我們討論的?BitmapFileIndex?那種簡單的、從0開始遞增的行號（rowNumber）就行不通了。因為行號?100?可能在文件A，也可能在文件B，產生了歧義。

Paimon 在這里并沒有使用跨文件的全局行號。實際上，Paimon 的索引（包括位圖索引）和數據文件是緊密綁定的，索引的作用域僅限于其對應的單個 SST 文件。

讓我們來梳理一下?MergeTreeWriter?的工作流程，看看它是如何處理這個問題的：

MergeTreeWriter?的核心寫入邏輯在?flushWriteBuffer?方法中。

// ... existing code ...private void flushWriteBuffer(boolean waitForLatestCompaction, boolean forcedFullCompaction)throws Exception {if (writeBuffer.size() > 0) {
// ... existing code ...final RollingFileWriter<KeyValue, DataFileMeta> dataWriter =writerFactory.createRollingMergeTreeFileWriter(0, FileSource.APPEND);try {writeBuffer.forEach(keyComparator,mergeFunction,changelogWriter == null ? null : changelogWriter::write,dataWriter::write);} finally {
// ... existing code ...dataWriter.close();if (changelogWriter != null) {changelogWriter.close();}}List<DataFileMeta> dataMetas = dataWriter.result();
// ... existing code ...for (DataFileMeta dataMeta : dataMetas) {newFiles.add(dataMeta);compactManager.addNewFile(dataMeta);}}
// ... existing code ...}
// ... existing code ...

這里的關鍵是?RollingFileWriter。當內存中的?writeBuffer?被刷寫時：

1. writerFactory.createRollingMergeTreeFileWriter(...)?創建一個?dataWriter。這個?Writer?內部包含了創建 SST 文件及其關聯索引（如位圖索引）的全部邏輯。
2. dataWriter::write?被調用，數據被寫入。RollingFileWriter?會監控文件大小，一旦達到閾值（target-file-size），它會自動關閉當前文件，并創建一個新的 SST 文件繼續寫入。
3. 當所有數據寫完后，dataWriter.result()?會返回一個?List<DataFileMeta>，這里面就包含了本次刷寫生成的所有?SST 文件的元數據。每個?DataFileMeta?都包含了文件名、key 的統計信息、以及它自己的索引文件的位置信息。

這里的核心要點是：

• 索引是在?RollingFileWriter?內部，為它正在寫入的那個 SST 文件實時創建的。
• 當?RollingFileWriter?決定關閉當前的 SST 文件（比如文件A）并開啟一個新文件（文件B）時，文件A的索引構建過程也隨之結束。文件A和它的索引被“固化”下來。
• 接著，RollingFileWriter?會為新的文件B重新開始一個全新的索引構建過程。對于文件B的位圖索引來說，它的行號（rowNumber）會從 0 重新開始計數。

所以，我們最終得到的是這樣的結構：

• SST 文件 A + 它自己的索引文件（行號 0 -> N）
• SST 文件 B + 它自己的索引文件（行號 0 -> M）
• SST 文件 C + 它自己的索引文件（行號 0 -> K）
• ...

每個 SST 文件都是一個獨立的、自包含的單元，擁有自己獨立的、行號從0開始的索引。

當查詢引擎需要讀取數據時，它會：

1. 從 Manifest 文件中獲取一個分區（Partition）和桶（Bucket）下的所有?DataFileMeta?列表。
2. 對于一個查詢（例如?WHERE city = '北京'），它會遍歷這個列表中的每一個?DataFileMeta。
3. 對每一個?DataFileMeta，它會加載其對應的位圖索引文件。
4. 在索引中查找?'北京'?對應的位圖，得到一個只在該文件內有效的行號列表（比如文件A中是?{0, 2, 5}，文件B中可能是?{10, 28}）。
5. 利用這些行號，從對應的 SST 文件中精確地讀取數據。

總結

行號只在單個 SST 文件內部有效，它就是該條記錄在這個文件中的物理行偏移量（從0開始）。Paimon 通過將索引和數據文件強綁定的方式，解決了跨文件行號不唯一的問題。查詢時，會對每個文件都應用一次“索引過濾 -> 讀取數據”的流程。

這種設計雖然在查詢時需要檢查多個文件，但它極大地簡化了寫入和 Compaction 的邏輯，這也是 LSM-Tree（Log-Structured Merge-Tree）架構的典型特征。后續的 Compaction 過程會把這些小的、分散的文件合并成更大的文件，從而提高查詢效率。

總結

BitmapFileIndex?是一個功能強大且設計精巧的索引實現：

• 優點:
  • 對于低基數列的等值和 IN 查詢極其高效，可以精確過濾到行級別。
  • 底層使用?RoaringBitmap32，在空間和性能上都非常出色。
  • 實現了多種優化，如對基數為1的值的特殊處理、延遲加載等。
• 適用場景:
  • 非常適合基數較低的列，如性別、國家、狀態碼、枚舉類型等。
• 不適用場景:
  • 高基數列（如用戶ID、交易ID），因為會為每個獨立值創建一個位圖，導致索引本身變得非常龐大。
  • 范圍查詢（>、<），它無法有效處理。對于范圍查詢，Paimon 提供了?BSI?(Bit-Sliced Index) 索引。

總而言之，BitmapFileIndex?是 Paimon 文件過濾體系中的一把利器，與?BloomFilter（用于高基數列等值查詢）和?BSI（用于數值范圍查詢）等共同構成了強大的索引矩陣。

RoaringBitmap32?類分析：Paimon 的封裝層

RoaringBitmap32?是 Paimon 項目對第三方庫?org.roaringbitmap.RoaringBitmap?的一個封裝（Wrapper）類。它本身不實現復雜的位圖邏輯，而是將所有操作都委托（delegate）給內部持有的一個?RoaringBitmap?實例。

// ... existing code ...
public class RoaringBitmap32 {public static final int MAX_VALUE = Integer.MAX_VALUE;private final RoaringBitmap roaringBitmap;public RoaringBitmap32() {this.roaringBitmap = new RoaringBitmap();}private RoaringBitmap32(RoaringBitmap roaringBitmap) {this.roaringBitmap = roaringBitmap;}
// ... existing code ...

Paimon 為什么要進行這樣一層封裝，而不是直接在項目中使用?org.roaringbitmap.RoaringBitmap?呢？主要有以下幾個原因：

1. 統一接口與隔離依賴：通過封裝，Paimon 可以在自己的?org.apache.paimon.utils?包下提供一個穩定的、受控的位圖 API。未來如果想更換底層位圖的實現（比如換成另一個性能更好的庫），只需要修改?RoaringBitmap32?的內部實現，而上層業務代碼（如?BitmapFileIndex）完全不需要改動。這遵循了良好的“面向接口編程”和“依賴倒置”原則。

2. 簡化與定制：org.roaringbitmap.RoaringBitmap?庫的功能非常強大和全面。RoaringBitmap32?只暴露了 Paimon 項目實際需要用到的那部分 API，使得接口更簡潔、意圖更明確。同時，如果需要，也可以在這個封裝層上增加一些 Paimon 特有的輔助方法或邏輯。

3. 提供靜態工廠方法：RoaringBitmap32?提供了一系列非常方便的靜態方法，用于執行位圖間的邏輯運算，如?and,?or,?andNot。這些方法返回一個新的?RoaringBitmap32?實例，使得代碼更具可讀性和流式編程的風格。

   // ... existing code ...
   public static RoaringBitmap32 and(final RoaringBitmap32 x1, final RoaringBitmap32 x2) {return new RoaringBitmap32(RoaringBitmap.and(x1.roaringBitmap, x2.roaringBitmap));
   }public static RoaringBitmap32 or(final RoaringBitmap32 x1, final RoaringBitmap32 x2) {return new RoaringBitmap32(RoaringBitmap.or(x1.roaringBitmap, x2.roaringBitmap));
   }
   // ... existing code ...
   

核心方法

RoaringBitmap32?的實例方法基本都是對?roaringBitmap?成員同名方法的直接調用，例如：

• add(int x): 添加一個整數到位圖。
• contains(int x): 檢查整數是否存在。
• getCardinality(): 獲取位圖中存儲的整數數量（基數）。
• serialize(DataOutput out)?/?deserialize(DataInput in): 序列化和反序列化，這是索引持久化的關鍵。
• or(RoaringBitmap32 other): 與另一個位圖進行或運算（修改自身）。
• flip(long rangeStart, long rangeEnd): 對一個范圍內的位進行翻轉（0變1，1變0）。

org.roaringbitmap.RoaringBitmap：核心引擎

這是 Roaring Bitmap 算法的 Java 實現，也是 Paimon 位圖功能的真正核心。它是一種高度壓縮的位圖數據結構，旨在解決傳統位圖在存儲稀疏數據時的空間浪費問題。

如果我們直接用一個?long[]?或?byte[]?數組來實現位圖，會遇到什么問題？RoaringBitmap?又是如何解決的？

假設我們要存儲 0 到 1,000,000 之間的一些整數。

傳統位圖 (long[]?/?byte[])

• 原理: 創建一個足夠大的位數組，每一位對應一個可能的整數。例如，要表示 0 到 1,000,000，我們需要?1,000,001?位。如果用?long[]?數組，每個?long?是 64 位，就需要?1,000,001 / 64 ≈ 15,626?個?long?元素，占用?15,626 * 8 ≈ 125 KB?內存。
• 優點:
  • 實現簡單，位操作（get,?set）非常快，是 O(1) 復雜度。
• 致命缺點:?空間占用與數據的最大值（universe size）成正比，而與數據的密集度無關。
  • 場景一（密集數據）: 如果我們要存儲 0 到 1,000,000 之間的所有奇數（約50萬個），傳統位圖占用 125 KB，這很高效。
  • 場景二（稀疏數據）: 如果我們只存儲兩個數：{10, 1,000,000}。傳統位圖仍然需要占用 125 KB?的空間來表示這整個范圍，其中絕大部分位都是 0，造成了巨大的空間浪費。

Roaring Bitmap

• 原理: 它是一種混合式（Hybrid）的數據結構，巧妙地結合了多種存儲方式來達到最優壓縮。

  1. 分塊 (Chunking): 它將 32 位的整數空間（0 到 2^32-1）分成 2^16 = 65536 個塊（Container）。每個塊負責 2^16 = 65536 個連續的整數。一個整數?x?存儲在第?x / 65536?個塊中。
  2. 智能容器 (Smart Container): 每個塊（Container）根據其內部存儲的數據的稀疏程度，動態地選擇兩種存儲結構之一：
     • ArrayContainer: 當塊內存儲的整數數量少于 4096?個時使用。它就是一個簡單的、有序的?short?數組，直接存儲這幾千個整數的低16位。空間占用與元素個數成正比。
     • BitmapContainer: 當塊內存儲的整數數量多于 4096?個時使用。它就是一個傳統的位圖（用?long[]?實現），大小固定為?65536 / 8 = 8 KB。
  3. 頂層結構: 頂層是一個有序數組，存儲了所有非空塊的“塊號”（高16位）和指向對應 Container 的指針。

• 優點:

  • 極致的空間壓縮:
    • 對于稀疏數據，它使用?ArrayContainer，空間只和元素個數有關。存儲?{10, 1,000,000}?只需要極小的空間（兩個塊，每個塊里一個?ArrayContainer，每個?ArrayContainer?存一個?short）。
    • 對于密集數據，它自動轉換為?BitmapContainer，空間效率和傳統位圖一樣高。
    • 它能在?ArrayContainer?和?BitmapContainer?之間自動轉換，始終保持最優狀態。
  • 高效的集合運算: 兩個 Roaring Bitmap 之間的與、或、非等操作經過高度優化，通常比操作解壓后的數據要快得多。

Paimon 使用?RoaringBitmap32?作為其?BitmapFileIndex?和?BSI?索引的基石，正是看中了它在各種數據分布下都能提供出色的空間壓縮率和極高的集合運算性能，這對于構建高效的數據庫索引至關重要。

BSI

BSI?是?Bit-Sliced Index?的縮寫，中文譯為“位切片索引”。

它是一種專門為加速數值類型（如整數、小數、日期、時間戳）的范圍查詢（如?>、<、>=、<=）而設計的索引技術。

與我們之前討論的?BitmapFileIndex（位圖索引）不同：

• 位圖索引：為列中的每個獨立值創建一個位圖，擅長等值查詢?(=,?IN)。
• 位切片索引 (BSI)：它不關心具體的值是什么，而是將每個數值的二進制表示進行“垂直”切分，為每一個比特位（bit position）創建一個位圖。

假設我們有以下數據要索引：

傳統的位圖索引會為值?5, 2, 7, 1?分別創建位圖。

而 BSI 會這樣做：

1. 按位切片：將所有數值的二進制表示按位對齊，然后“垂直”地看每一列（每一個比特位）。
2. 為每個比特位創建位圖：
   • bit 0 (最低位):?1, 0, 1, 1?-> 創建位圖?B0 = {0, 2, 3}?(記錄了哪些行的第0位是1)
   • bit 1:?0, 1, 1, 0?-> 創建位圖?B1 = {1, 2}
   • bit 2:?1, 0, 1, 0?-> 創建位圖?B2 = {0, 2}
   • bit 3 (最高位):?0, 0, 0, 0?-> 創建位圖?B3 = {}?(空)

最終，BSI 索引存儲的就是?B0, B1, B2, B3?這一組位圖。

當執行范圍查詢，比如?age > 5?(二進制?0101) 時，BSI 可以通過對這些位圖進行高效的位運算來快速找出所有滿足條件的行，而無需逐個比較原始值。這背后的算法（如 O'Neil's algorithm）保證了其高效性。

BitSliceIndexBitmapFileIndex?這個類同樣實現了?FileIndexer?接口，其核心邏輯也封裝在內部類?Writer?和?Reader?中。

BitSliceIndexBitmapFileIndex?(外部類)

這個外部類非常簡潔，主要負責：

1. 存儲列的?DataType。
2. 提供?createWriter()?和?createReader()?工廠方法。createReader?方法負責從輸入流中讀取索引的元數據，并構造一個?Reader?實例。

// ... existing code ...
public class BitSliceIndexBitmapFileIndex implements FileIndexer {public static final int VERSION_1 = 1;private final DataType dataType;public BitSliceIndexBitmapFileIndex(DataType dataType, Options options) {this.dataType = dataType;}@Overridepublic FileIndexWriter createWriter() {
// ... existing code ...}@Overridepublic FileIndexReader createReader(SeekableInputStream inputStream, int start, int length) {
// ... existing code ...}
// ... existing code ...

Writer?(靜態內部類)

Writer?負責構建 BSI 索引并將其序列化。

• 核心邏輯:
  1. valueMapper: 首先，它通過?getValueMapper?將各種數值類型（Int,?Decimal,?Timestamp?等）統一轉換成?Long?類型進行處理。這是一個標準化的過程。
  2. StatsCollectList: 它使用一個內部類?StatsCollectList?來收集所有行的值。這里有一個值得注意的實現細節：// todo: Find a way to reduce the risk of out-of-memory.，這表明當前實現會將一個列的所有值都加載到內存的?List<Long> values?中，在數據量極大時可能存在OOM風險。
  3. 正負數分離: BSI 算法通常處理非負整數。為了支持負數，Paimon 的實現非常巧妙：它創建了兩個獨立的?BitSliceIndexRoaringBitmap.Appender，一個叫?positive?用于處理所有正數和零，另一個叫?negative?用于處理所有負數（取絕對值后存入）。
  4. 構建與序列化: 遍歷內存中的?values?列表，將正數和負數分別追加到對應的?Appender?中。最后，將?positive?和?negative?這兩個 BSI 索引結構序列化到字節數組中。

// ... existing code ...private static class Writer extends FileIndexWriter {private final Function<Object, Long> valueMapper;private final StatsCollectList collector;public Writer(DataType dataType) {
// ... existing code ...}@Overridepublic void write(Object key) {collector.add(valueMapper.apply(key));}@Overridepublic byte[] serializedBytes() {try {
// ... existing code ...BitSliceIndexRoaringBitmap.Appender positive =new BitSliceIndexRoaringBitmap.Appender(collector.positiveMin, collector.positiveMax);BitSliceIndexRoaringBitmap.Appender negative =new BitSliceIndexRoaringBitmap.Appender(collector.negativeMin, collector.negativeMax);for (int i = 0; i < collector.values.size(); i++) {Long value = collector.values.get(i);if (value != null) {if (value < 0) {negative.append(i, Math.abs(value));} else {positive.append(i, value);}}}
// ... existing code ...} catch (Exception e) {throw new RuntimeException(e);}}
// ... existing code ...}
// ... existing code ...

Reader?(靜態內部類)

Reader?負責解析 BSI 索引，并根據查詢條件執行過濾。

• 核心成員:

  • positive: 用于正數的 BSI 索引實例。
  • negative: 用于負數的 BSI 索引實例。
  • valueMapper: 同樣用于將查詢的字面量（literal）轉換成?Long。

• 查詢處理:?Reader?重寫了?visit...?系列方法來處理不同的查詢謂詞。

  • visitEqual(..)?/?visitIn(..): 對于等值查詢，它判斷查詢值是正還是負，然后調用對應 BSI 實例的?eq()?方法獲取匹配的位圖。
  • visitLessThan(..)?/?visitGreaterThan(..)?等范圍查詢: 這是 BSI 的核心優勢所在。邏輯會變得復雜一些，因為它需要同時考慮正數和負數部分。
    • 例如，查詢?value < N：
      • 如果?N?是正數，那么結果是?(所有負數) OR (所有小于N的正數)。代碼實現為?RoaringBitmap32.or(positive.lt(value), negative.isNotNull())。
      • 如果?N?是負數（比如 -5），那么查詢?value < -5?等價于查詢?abs(value) > 5?且?value?是負數。代碼實現為?negative.gt(Math.abs(value))。
    • 其他范圍查詢也遵循類似的邏輯，通過組合?positive?和?negative?兩個 BSI 索引的查詢結果（lt,?lte,?gt,?gte）來得到最終的位圖。

// ... existing code ...private static class Reader extends FileIndexReader {private final int rowNumber;private final BitSliceIndexRoaringBitmap positive;private final BitSliceIndexRoaringBitmap negative;
// ... existing code ...@Overridepublic FileIndexResult visitLessThan(FieldRef fieldRef, Object literal) {return new BitmapIndexResult(() -> {Long value = valueMapper.apply(literal);if (value < 0) {return negative.gt(Math.abs(value));} else {return RoaringBitmap32.or(positive.lt(value), negative.isNotNull());}});}
// ... existing code ...}
// ... existing code ...

總結

BitSliceIndexBitmapFileIndex?是 Paimon 利用 BSI 技術實現的高效范圍查詢索引。

• 優點:
  • 極大地加速了對數值、日期、時間戳等類型的范圍查詢。
  • 底層同樣使用?RoaringBitmap32，空間和性能都有保障。
  • 通過分離正負數的處理，巧妙地將 BSI 算法擴展到了整個數值范圍。
• 缺點/待優化:
  • 當前的寫入實現在構建索引時會將整列數據加載到內存，存在潛在的 OOM 風險。
• 適用場景:
  • 經常需要進行范圍過濾的數值型列，例如?age > 18，order_amount BETWEEN 100 AND 1000，event_time > '2023-01-01'?等。

它與?BitmapFileIndex?(用于等值查詢) 和?BloomFilter?(用于高基數列等值查詢) 共同構成了 Paimon 強大而全面的文件內索引體系。

序列化說明

BitmapFileIndex?的序列化比?BitSliceIndexBitmapFileIndex?復雜得多，這主要是由它們各自處理的數據特點和為了極致優化空間而采取的不同策略決定的。

我們來深入剖析一下二者的序列化過程，看看?BitmapFileIndex.Writer?到底“復雜”在哪里，以及為什么這么設計。

BitSliceIndexBitmapFileIndex?序列化：簡單直接

我們先回顧一下 BSI 索引的序列化，它的邏輯非常清晰：

1. 數據收集: 將一整列的數值加載到內存中的一個?List<Long>。
2. 正負分離: 創建兩個?BitSliceIndexRoaringBitmap.Appender，一個用于正數，一個用于負數。
3. 構建與序列化: 遍歷內存列表，將值送入對應的?Appender。Appender?內部會完成所有位切片和位圖構建的復雜工作。最終，調用?positive.serialize()?和?negative.serialize()?得到兩個字節塊。
4. 寫入文件: 將這兩個字節塊和一些簡單的元數據（如長度）直接寫入輸出流。

簡單原因總結：BSI 的結構是固定的——就是一組位圖（正數部分）+ 另一組位圖（負數部分）。它的序列化過程就是把這兩大塊數據“拍”到文件里，結構清晰，沒有太多花樣。

BitmapFileIndex?序列化：精打細算，復雜但高效

BitmapFileIndex?的序列化過程要復雜得多，因為它在“寸土寸金”地優化存儲空間，特別是針對低基數（low-cardinality）列的場景。

我們來分解?BitmapFileIndex.Writer.serializedBytes()?的核心步驟：

// ... existing code ...@Overridepublic byte[] serializedBytes() {try {// ... 初始化 ...// 1. 將每個值的位圖都序列化成字節數組，存在內存 Map 中byte[] nullBitmapBytes = nullBitmap.serialize();Map<Object, byte[]> id2bitmapBytes =id2bitmap.entrySet().stream().collect(Collectors.toMap(Map.Entry::getKey, e -> e.getValue().serialize()));// 2. 構建元數據，這里是復雜性的核心LinkedHashMap<Object, Integer> bitmapOffsets = new LinkedHashMap<>();LinkedList<byte[]> serializeBitmaps = new LinkedList<>();int[] offsetRef = { /* ... */ };id2bitmap.forEach((k, v) -> {// 【優化點 1】如果一個值只出現了一次if (v.getCardinality() == 1) {// 不存儲完整的位圖，而是直接將行號編碼到 offset 字段bitmapOffsets.put(k, -1 - v.iterator().next());} else {// 對于出現多次的值，才真正存儲它的位圖byte[] bytes = id2bitmapBytes.get(k);serializeBitmaps.add(bytes);bitmapOffsets.put(k, offsetRef[0]);offsetRef[0] += bytes.length;}});// 【復雜點 2】根據版本創建不同的 Meta 對象BitmapFileIndexMeta bitmapFileIndexMeta;if (version == VERSION_1) {// ... 創建 V1 Meta} else if (version == VERSION_2) {// ... 創建 V2 Meta，包含更多信息} else {// ...}// 3. 序列化 Meta 部分bitmapFileIndexMeta.serialize(dos);// 4. 序列化 Body 部分（真正的位圖數據）if (nullBitmap.getCardinality() > 1) {dos.write(nullBitmapBytes);}for (byte[] bytes : serializeBitmaps) {dos.write(bytes);}return output.toByteArray();} catch (Exception e) {throw new RuntimeException(e);}}
// ... existing code ...

復雜性分析：

1. 對“基數為1”的特殊優化（核心差異）:

   • 場景: 在很多列中，大量的值可能只出現一次（例如，用戶ID列）。
   • 問題: 如果一個值?X?只出現在第?100?行，為它創建一個完整的?RoaringBitmap?對象再序列化，會占用幾十個甚至上百個字節，而我們真正需要的信息僅僅是“行號100”。這是一種巨大的浪費。
   • BitmapFileIndex?的策略: 它在序列化時檢查每個值對應的位圖基數（v.getCardinality() == 1）。如果基數是1，它根本不序列化這個位圖。取而代之，它玩了一個技巧：它將這個唯一的行號編碼成一個負數（-1 - rowNumber），并直接存放在元數據（BitmapFileIndexMeta）的?offset?字段里。
   • 效果: 當?Reader?讀取時，如果發現?offset?是個負數，它就知道這是一個只出現一次的值，通過?RoaringBitmap32.bitmapOf(-1 - offset)?就能瞬間原地構造出位圖，而無需去文件主體（Body）中讀取任何數據。這個優化極大地減少了索引文件的體積。

2. 兩段式文件結構（Meta + Body）:

   • BitmapFileIndex?將索引文件清晰地分為兩部分：
     • Meta (頭部): 存儲了所有值到其位圖位置的映射（bitmapOffsets）、總行數等元信息。對于基數為1的值，信息就全部在這里了。
     • Body (主體): 緊湊地存放了所有基數大于1的位圖的序列化字節流。
   • 這種設計允許?Reader?先只讀取和解析頭部的 Meta 數據。只有當查詢真正需要某個（基數>1的）值的位圖時，才根據 Meta 中的?offset?和?length?信息，精確地?seek?到文件主體的特定位置去加載那一段字節碼。這是一種延遲加載（Lazy Loading），避免了一次性將所有位圖反序列化到內存中，優化了讀取性能和內存使用。

3. 版本兼容性 (VERSION_1?vs?VERSION_2):

   • 代碼中處理了兩種版本的元數據格式 (BitmapFileIndexMeta?和?BitmapFileIndexMetaV2)。這增加了代碼的邏輯分支和復雜性，但保證了對舊版本索引文件的向后兼容。V2?版本可能增加了新的元信息（如?nullBitmapBytes.length）或優化了存儲結構（如?BitmapIndexBlock），以支持更高效的查找。

結論：BitmapFileIndex?的序列化之所以復雜，是因為它不僅僅是在“存儲”數據，更是在進行一次深度的“數據壓縮和布局優化”。它針對位圖索引最常見的低基數場景做了專門的設計，通過犧牲一些代碼的簡潔性，換來了存儲空間和讀取性能上的巨大優勢。而?BitSliceIndexBitmapFileIndex?的結構相對固定，因此其序列化過程也更為直接。