Parquet 布隆过滤器(Bloom Filter)

问题描述

在当前格式下，列统计信息和字典可以用于谓词下推（Predicate Pushdown）。统计信息包含最小值和最大值，可用于筛选出不在范围内的值。字典更具体，读取器可以筛选出介于最小值和最大值之间但不在字典中的值。然而，当数据的不同值过多时，写入器有时会选择不使用字典，因为字典会占用额外的存储空间。这使得某些高基数（high cardinality）的列，虽然其最小值和最大值相距甚远，但无法受益于谓词下推。

布隆过滤器（Bloom Filter）是一种紧凑的数据结构，用于近似存储一个集合。它可以回答成员查询，返回 “绝对不存在” 或 “可能存在” 的结果，其中假阳性（false positive）的概率可以在初始化过滤器时配置。布隆过滤器不会产生假阴性（false negatives）。

由于布隆过滤器比字典小得多，因此即使在高基数列中，或者存储空间受限的情况下，也可以用于谓词下推。

目标

在高基数列上启用谓词下推，同时使用比字典更少的空间。
当查询未附加布隆过滤器的列或执行非选择性查询时，不引入额外的 I/O 开销。

技术实现

本节介绍 分块布隆过滤器（Split Block Bloom Filters），这是 Parquet 目前支持的唯一布隆过滤器实现。

基本概念

一个 “块（block）” 是分块布隆过滤器的基本组成部分。每个块包含 256 比特，分为 8 个连续的 32 比特字（word）。每个字被视为一个位数组，每个位可以是 “已设置（set）” 或 “未设置（not set）”。

初始化：当一个块初始化时，所有 8 个字的所有位都未设置。
操作：
- block_insert(x): 插入值 x，修改块。
- block_check(x): 检查值 x 是否已插入，返回布尔值。

block_check(x) 的逻辑是：如果 block_insert(x) 之前被调用过，则返回 true，否则以高概率返回 false。

位设置逻辑

每个块的 block_insert 和 block_check 依赖两个重要组件：

salt 数组（8 个奇数常量）：

unsigned int32 salt[8] = {0x47b6137bU, 0x44974d91U, 0x8824ad5bU,
                          0xa2b7289dU, 0x705495c7U, 0x2df1424bU,
                          0x9efc4947U, 0x5c6bfb31U};

mask 方法：将 x 计算为一个块，其中每个字的某个位被设置。
```
block mask(unsigned int32 x) {
  block result;
  for (i in [0..7]) {
    unsigned int32 y = x * salt[i];
    result.getWord(i).setBit(y >> 27);
  }
  return result;
}
```
- mask 计算 x * salt[i] 并右移 27 位（>> 27），得到 0 到 31 之间的整数，然后在相应字的该位上设置 1。

插入和检查

插入（block_insert）

void block_insert(block b, unsigned int32 x) {
  block masked = mask(x);
  for (i in [0..7]) {
    for (j in [0..31]) {
      if (masked.getWord(i).isSet(j)) {
        b.getWord(i).setBit(j);
      }
    }
  }
}

检查（block_check）

boolean block_check(block b, unsigned int32 x) {
  block masked = mask(x);
  for (i in [0..7]) {
    for (j in [0..31]) {
      if (masked.getWord(i).isSet(j) && !b.getWord(i).isSet(j)) {
        return false;
      }
    }
  }
  return true;
}

分块布隆过滤器（SBBF）

结构：由 z 个块组成，其中 z ≥ 1 且 z < 2^31。
初始化：每个块都初始化为全零（所有位未设置）。
操作：
- filter_insert(x): 选择一个块并调用 block_insert(x)。
- filter_check(x): 选择一个块并调用 block_check(x)。

块选择策略

为了避免使用慢速的 取模运算（modulo），采用以下方法选择块：

unsigned int64 i = ((x >> 32) * z) >> 32;

x >> 32 取 x 的高 32 位作为索引来源。
乘以 z 并右移 32 位，从而映射到 [0, z-1] 之间的整数。

布隆过滤器大小计算

布隆过滤器的 check 操作可能产生 假阳性（false positive），即 返回 true 但实际上该值未被插入。假阳性的概率受以下因素影响：

比特位数量 / 插入哈希值数量 比例：
- 1024 个块，26214 个哈希值，假阳性率 ≈ 1.26%。
- 1024 个块，52428 个哈希值，假阳性率 ≈ 18%。
- 1024 个块，13107 个哈希值，假阳性率 ≈ 0.04%。

比特位 / 插入值比率	假阳性概率
6.0	10%
10.5	1%
16.9	0.1%
26.4	0.01%
41.0	0.001%

文件格式

布隆过滤器仅适用于单个列块（Column Chunk），其数据包括：

布隆过滤器头部（Header）：存储位集大小（字节数）。
布隆过滤器位集（Bitset）。

在 Thrift 结构 中定义如下：

struct BloomFilterPageHeader {
  1: required i32 numBytes;
  2: required BloomFilterAlgorithm algorithm;
  3: required BloomFilterHash hash;
  4: required BloomFilterCompression compression;
}

struct ColumnMetaData {
  ...
  14: optional i64 bloom_filter_offset;
}

布隆过滤器可以存储在：

所有行组（Row Group）之后
行组之间

加密

对于敏感数据列，布隆过滤器可能暴露部分信息（如某值是否存在）。因此，敏感列的布隆过滤器应使用 列密钥（Column Key） 进行加密，非敏感列无需加密。

加密使用 AES-GCM 算法，并且：

布隆过滤器头部 使用 “BloomFilter Header”（8） 作为 AAD。
布隆过滤器位集 使用 “BloomFilter Bitset”（9） 作为 AAD。

最佳实践

高基数列优先使用布隆过滤器，而非字典，以节省存储空间。
确保合理设置比特位与插入值比率，控制假阳性率。
对于敏感列，启用加密，以避免数据泄露。