使用 Parquet 的 Bloom 过滤器

作者：Trevor Hilton / 开发者
2024年5月28日

注意：我们于2024年6月6日更新了这篇文章，以反映宝贵的社区反馈。

摘要

在本文中，我们探讨了何时以及如何使用 Parquet 中的 Bloom 过滤器，它们对写入的 Parquet 文件的影响，以及在大批量高基数数据（1）处理中的有效性。

总之，我们发现

• 与每个 Parquet 行组中不同值的数量更接近的 Bloom 过滤器参数在处理大量高基数聚类数据时实现了最佳的修剪效率。
• 使用这种 Bloom 过滤器，查询时间减少了1/30，但存储空间每行组每列需要额外2 KB 至 8 KB。
• 选择与整个数据集基数匹配的 Bloom 过滤器参数会带来巨大的存储惩罚，但我们的实验中并不需要这样做。

不同输入参数的计算 Bloom 过滤器大小表可在Bloom 过滤器大小中查看。

背景与动机

当查询包含在Apache Parquet文件中的数据时，有几种技术可以提高查询速度。一种方法使用Bloom 过滤器来修剪整个行/列块。Bloom 过滤器对于包含许多不同伪随机值的列特别有用，例如标识符或 UUID。这与包含有序数据、基数较低或已被行组元数据中的 min/max 统计信息有效修剪的列不同。Bloom 过滤器的支持在 Apache Rust（2）和 Java（3）Parquet 格式实现以及Apache DataFusion 查询引擎中。

在 InfluxData，我们经常处理高基数数据，并考虑了多种索引策略。鉴于 Bloom 过滤器是 Apache Parquet 和我们用来支持它们的库的一部分，它们是一个吸引人的选择。然而，关于它们在实际中的有效性或如何设置调整旋钮的相关信息很少。具体来说，我们想知道

• Bloom 过滤器会增加 Parquet 文件的大小多少？
• 对于具有高基数的数据（例如，100k 到 1M 个不同值），Parquet Bloom 过滤器如何提高查询性能？

Bloom 过滤器的用例

考虑图 1 中的示例 Parquet 文件，该文件存储在不同云区域托管的不同主机服务器上运行的容器 CPU 使用情况。

图1：示例Parquet文件，包含三个按增加的基数排序的列以及时间和cpu列；《地区》具有10个基数，主机具有1,000个基数，而container_id具有1,000,000个基数。数据集的基数与最高基数列的基数相对应，即1,000,000。此Parquet文件由两个行组组成，每个行组都包含每个列的最小值和最大值的元数据。

此Parquet文件中的行按地区排序，然后按主机排序，然后按container_id排序，以匹配生成数据的实体的层次结构。在实践中，对于每个唯一的地区、主机和container_id组合，将有许多行，即代表不同时间戳的CPU使用情况。

如果我们使用图1中的地区和container_id作为谓词查询Parquet文件，例如

SELECT * FROM 'fig1.parquet' WHERE region = 'us-east-2' AND container_id = 'CCC';

则查询引擎将剪枝行组2，因为us-east-2超出了行组2元数据中包含的地区列的最小/最大值，因此只会解码来自行组1的行。但是，如果我们只使用container_id进行查询，例如

SELECT * FROM 'fig1.parquet' WHERE container_id = 'CCC';

则查询引擎必须扫描两个行组，因为仅凭元数据本身不能根据各自的container_id值的最小/最大值排除任何一个组（值CCC落在AAA..DDD和BBB..FFF范围内）。

这就是Bloom过滤器发挥作用的地方。将Bloom过滤器应用于container_id列允许查询引擎在将该列用作谓词时剪枝行组。

Parquet的Bloom过滤器实现

Parquet使用Split Block Bloom过滤器（SBBF）。在写入Parquet数据时，通过指定以下参数按列配置SBBF

• 唯一值数（NDV）
• 假阳性概率（FPP）

Bloom过滤器通过其长度和偏移量从Parquet文件中读取，这些长度和偏移量存储在每个行组的元数据中，并由DataFusion用于在查询文件时过滤出整个行组。似乎有理由假设NDV应接近其应用的列的基数，但NDV越大，Bloom过滤器在文件中占用的空间就越多。

我们感兴趣的是了解低估NDV的影响，因为这可以节省存储空间。此外，我们假设选择的FPP应与Bloom过滤器可以得到的剪枝量相对应。

Bloom过滤器大小

Bloom过滤器不是免费的。它们存储在Parquet文件中，因此会产生存储开销。根据所需的NDV和FPP计算来确定过滤器的大小。FPP可以计算为⁴

其中f是FPP，k是哈希函数的数量，n是NDV，而m是Bloom过滤器的总位数。要达到所需的FPP和NDV所需的位数可以通过上述公式重新排列来确定

SBBF使用八个哈希函数，以干净地适合SIMD通道⁵。因此，k被设置为8。SBBF将这些m位分布在一组块中，每个块的大小为256位，即32字节。Rust⁶和Java⁷的Parquet Bloom过滤器实现都确定字节数为

m除以8以表示字节。

使用上述公式可以计算各种FPP和NDV⁸值的大小

实验

设置

虽然前一部分的理论结果具有参考价值，但我们想验证这些结果是否与实际情况相符。为此，我们开发了parquet-bloom-filter-analysis工具。

它是一个用Rust编写的命令行工具，可以生成具有指定列数的Parquet文件，每列具有以下属性：

• 基数，即唯一值的数量
• 可选的Bloom过滤器，包含FPP和NDV参数

此外，在生成一组文件时，我们指定以下参数：

• 要生成的Parquet文件数量
• 最大行组大小
• 重复因子

生成的行按照列的基数递增的顺序排序，如图1中的示例。重复因子用于为生成的列值的每个唯一组合生成重复行，从而通过列值的唯一组合聚类数据。这类似于图1示例中每个区域/主机/容器组合在不同时间戳记录了大量的CPU使用率指标。

我们使用parquet-bloom-filter-analysis进行了以下实验：

1. NDV对大小的影响：对于基数为1M和100k的数据，以固定的FPP和变化的NDV参数生成少量文件，以确定在各自的基数下这些参数的可接受基线，并验证对Parquet文件大小的影响是否符合理论。
2. 查询性能影响：为1M和100k基数生成更大量的Parquet文件，以评估在更现实的规模上使用Bloom过滤器所能实现的查询性能提升。

系统规格

所有实验都是在以下配置的机器上运行的：

NDV对大小的影响：1M基数

我们生成了一个包含三个列的数据集，其属性如下：

这导致总共100M行数据，每列值的唯一组合有100行。

以下是生成数据的示例

+----------+-------------+--------------+
| col_0    | col_1       | col_2        |
+----------+-------------+--------------+
| first-52 | second-4119 | third-136666 |
| first-52 | second-4119 | third-230251 |
| first-52 | second-4119 | third-287794 |
| first-52 | second-4119 | third-360226 |
| first-52 | second-4119 | third-584614 |
| first-52 | second-4119 | third-672996 |
| first-52 | second-4119 | third-952788 |
| first-52 | second-4174 | third-002478 |
| first-52 | second-4174 | third-236114 |
| first-52 | second-4174 | third-439784 |
| first-52 | second-4174 | third-477628 |
| first-52 | second-4174 | third-540914 |
| ...                                   |
+----------+-------------+--------------+

从那里，我们在基数最高的列上创建一个Bloom过滤器，即列3，通过将FPP设置为0.01，并改变NDV。选择0.01的FPP是因为生成的数据只包含100个行组，这应该对应于解码行组减少两个数量级，即每100个行组中只有1个被解码，这是最佳修剪效率。

存储成本可以通过计算使用Bloom过滤器时的平均Parquet文件大小与平均基线文件大小的差来衡量。此数据集的基线文件大小是通过不使用Bloom过滤器编码相同数据确定的。

为了了解实际修剪了多少行组，我们使用Datafusion的CLI⁹工具来确定在查询列时实际修剪了多少行组，如下所示：

EXPLAIN ANALYZE SELECT * FROM '<data\_folder>/' WHERE col_2 = '<target_value>'; 

<data_folder>对应于使用感兴趣FPP/NDV生成数据集的位置，并对代表范围<target_value>进行了测试。

结果

基准存储成本，即没有Bloom过滤器的平均Parquet文件大小为647,080.5字节。以下是固定FPP为0.01，不同NDV的结果。

增量 - 平均文件大小与基准文件大小的差值；RG - 行组。

讨论/关键观察结果

• DataFusion使用每个行组8 KB的Bloom过滤器，修剪了超过90%的行组，同时文件大小增加了12%。所有不匹配的行组都进行了修剪，每个组增加16 KB的冗余，文件大小增加了20%。
• 相对成本似乎很高，但在实际应用中会低得多。例如，InfluxDB生成的Parquet文件通常为MB大小，存储了许多更多的列，包括时间戳和64位浮点列。因此，我们预计每个行组增加8-16 KB将导致存储增长约1%或更少。
• 选择与列的实际基数非常接近的NDV会带来巨大的存储成本（每个行组2 MB），但不会提高修剪效率，因此似乎并不必要。

NDV对大小的影響：100k基数

与之前的实验类似，这个实验使用具有以下属性的数据

有两个区别：重复因子为1000（与100相比），第三列的基数是100k（与1M相比）。这保持了行数和Parquet文件与之前实验的一致性，同时保持了生成数据的顺序。

文件大小和修剪效率的测量方法与之前的实验相同。

结果

基准存储成本，即没有添加Bloom过滤器的平均Parquet文件大小为71,965.6字节。以下是固定FPP为0.01，不同NDV的结果。

增量 - 平均文件大小与基准文件大小的差值；RG - 行组。

讨论/关键观察结果

• 对文件大小的影响与之前的实验相同，与理论结果一致，即Bloom过滤器的大小与它过滤的数据的基数无关。
• DataFusion在NDV为1,000时成功修剪了所有不匹配的行组，每个行组只增加约2K的冗余。
• 修剪效率在比之前实验更低的NDV（1,000）时饱和

查询性能影响：100k基数

为了评估Bloom过滤器在更现实规模下的性能，我们生成了具有以下属性的Parquet数据

这对应于基数100k的数据集，分布在10k个文件中。数据生成时没有使用Bloom过滤器以建立基线，并在第三列上使用Bloom过滤器，即使用100k基数，FPP为0.01，NDV为1,000。

在这个场景中，我们想检查的两件事是

1. 修剪效率是否与上面进行的规模较小的实验保持一致？
2. 我们能否测量在带有Bloom过滤器的文件和不带有Bloom过滤器的文件之间查询性能的改进？

（1）可以通过分析查询来选择列3的单个值来回答，而（2）可以通过执行查询并测量响应时间来回答。

结果

实验生成了10,000个文件，以下为平均文件大小

基于这些数字，计算出的每个行组的冗余仍然是2,076.8字节，与之前的实验相同；然而，基线是9,112.87字节，而之前是71,965.60字节。

使用第三列（即基数100k的列）作为谓词执行查询，其值跨越其基数范围内的所有值（第三-[00000, 99999]）

RG - 行组。

讨论/关键观察结果

• 布隆过滤器带来的开销与较大文件相同，但在规模放大时加剧。可能是因为列式数据正在压缩，而元数据中的布隆过滤器没有。
• 布隆过滤器清理了行组统计信息无法清理的行组，从而显著提高了查询延迟（约为1/30）
• 所有可用值的最小/最大值处的谓词值将基于行组统计信息本身提供快速查询。

查询性能影响：1M基数

这个实验使用了与上一个例子相同的设置，生成了10,000个文件；然而，在这个情况下，第三列的基数增加到1M。复制因子被调整以保持生成数据的顺序

FPP和NDV参数也保持不变，在FPP 0.01和NDV 1,000。这是为了看看在这样一个规模和基数下，是否可以使用更低的NDV，从而减小布隆过滤器的大小，尽管在较小的规模下，1,000的NDV在1 M基数下影响不大（参见上一个实验）。

结果

实验生成了10,000个文件，平均文件大小如下

因此，布隆过滤器的开销为每行组2,076.8 B。

查询使用第3列（即基数1M的列）作为谓词，值为其基数内的总值范围（第三-[000000, 999999]）

RG - 行组。

讨论/关键观察结果

• 尽管使用NDV仅为1,000，但在这一规模和基数下，布隆过滤器仍然有效

结论

当使用Parquet时，布隆过滤器可以在较大的数据量下提供显著的查询性能提升，尽管会增加额外的存储成本。好消息是，更适度的布隆过滤器参数，在有序数据中相当有效，可以减轻存储成本。

一些悬而未决的问题包括

• 是否可以使用更适度的布隆过滤器参数，即NDV < 1,000，以达到相同的效果，从而进一步减轻存储成本？
• 压缩写入Parquet文件中的布隆过滤器（目前不是Parquet规范的一部分）是否会有任何好处？
• 如果我们对应用布隆过滤器的列存储更长或更复杂的数据，例如UUID，我们是否能够实现相同的效果？

相关博客文章

• Apache Parquet
• Apache Parquet 简介
• 以毫秒延迟查询Parquet
• Flight、DataFusion、Arrow和Parquet：使用FDAP架构构建InfluxDB 3.0

1. 我们使用“基数”一词来指代数据集中所有值（即所有parquet文件及其行组的总和）的独特值数量。本文中用于分析生成的数据按顺序排列，使得给定行组中的独特值数量小于整个数据集的基数。

2. 另请参阅，有关Apache Rust Parquet布隆过滤器支持的跟踪问题

3. 另请参阅，有关Apache Spark中布隆过滤器支持的博客文章

4. 另请参阅Cache Efficient Bloom filters for Shared Memory Machines

5. 参见 分割块Bloom过滤器

6. 参见Rust Parquet实现的最佳字节数 源码

7. 参见Java Parquet实现的相关代码 源码

8. 参见 Rust Playground链接

9. 参见 DataFusion CLI