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 的结构相对固定，因此其序列化过程也更为直接。