转载：DuckDB 中的 Parquet 布隆过滤器 - l1t1/note GitHub Wiki
DuckDB 中的 Parquet 布隆过滤器
原文 发布日期: 2025-03-07
作者: Hannes Mühleisen
TL;DR: DuckDB 现在支持读取和写入 Parquet 布隆过滤器。
Parquet 文件格式的一个关键特性是读者能够选择性地读取与特定查询相关的数据。为了支持这一点，Parquet 文件包含列统计信息，最显著的是每个行组中每列的最小值和最大值。如果查询使用特定值进行过滤，并且数据通常是有序的，读者可以“证明”某个行组不可能包含与查询相关的值。DuckDB 充分利用了这一点，即使在查询远程端点时，也能够选择性地只读取与查询相关的 Parquet 文件部分。有关其工作原理的详细信息，请参阅我们之前的博客文章“使用 DuckDB 精确查询 Parquet”。
然而，这种方法有一些局限性。如果列的数据是随机打乱的怎么办？在这种情况下，所有值都会出现在所有行组中，最小值和最大值统计信息的用处就不大了，因为我们只能排除那些在整个列的最小值和最大值之外的值。如果列中的不同值不多，Parquet 会使用字典编码。理论上，该字典可以用来排除行组，但这种方法有两个问题：Parquet（莫名其妙地）允许在行组中中途从字典编码切换到普通编码。如果仅使用字典来排除行组，但普通编码部分包含查询的值，这将导致错误的结果。此外，字典是实际列数据的一部分。如果我们读取列数据只是为了查看字典，那么我们已经承担了读取列的大部分成本。
晦涩的旁注：再次，理论上列元数据包含该列中出现的编码列表。如果该列表是正确的并且不包含普通编码，字典可以——再次，理论上——用于稍微提前排除行组。但这种方法的实用性非常值得怀疑。
Parquet 布隆过滤器
Parquet PMC 的好人们已经认识到这里有改进的空间，并在 2018 年为 Parquet 添加了布隆过滤器。简而言之，布隆过滤器是一种紧凑但近似的索引结构，用于一组值。对于给定的值，它们可以确定地说某个值不在集合中，或者它可能在集合中，误报率取决于布隆过滤器的大小和添加到其中的不同值的数量。目前，我们可以将布隆过滤器视为具有神奇属性的不透明字节序列。
使用时，Parquet 文件可以包含每个行组中每列的布隆过滤器。每个布隆过滤器可以位于文件中的任意位置（bloom_filter_offset）。在文件的该偏移处，我们会找到另一个 Thrift 编码的结构，即 BloomFilterHeader。该结构有一个字段用于过滤器的长度，以及一些算法设置，这些设置目前是冗余的，因为所有这些设置只有一个有效值。但你必须解码头部才能找到头部结束和过滤器字节开始的位置。最后，我们到达了布隆过滤器的宝贵字节。我们现在可以针对任何查询谓词测试过滤器，看看是否可以完全跳过该行组。
更晦涩的旁注：虽然列元数据确实包含一个字段来存储过滤器的大小（bloom_filter_length），但它也是可选的，一些写入器（看着你，Spark）令人恼火地只设置偏移量，而不设置长度。此外，规范描述了两种可能的过滤器位置。通过也不要求在元数据中设置长度，这使得在一次范围请求中读取 Parquet 文件的所有布隆过滤器变得困难甚至不可能。也不清楚为什么布隆过滤器每个都需要用 Thrift 元数据块作为前缀，而这些信息也可以包含在 ColumnMetaData 中。或者，天哪，过滤器本可以成为主 Parquet 元数据的一部分。最终，我们最终需要进行大量额外的读取来查找和读取布隆过滤器字节，原则上需要在读取过滤器和“仅仅”暴力读取列之间进行仔细的权衡。
DuckDB 布隆过滤器
自上一个功能版本（1.2.0）以来，DuckDB 支持读取和写入 Parquet 布隆过滤器。这对用户完全透明，不需要任何额外的操作或配置。
写入
目前，布隆过滤器支持以下类型：
- 整数类型（
TINYINT、UTINYINT、SMALLINT、USMALLINT、INTEGER、UINTEGER、BIGINT、UBIGINT） - 浮点类型（
FLOAT、DOUBLE） - 字符串类型（
VARCHAR和BLOB）
嵌套类型（列表、结构体、数组）目前不支持，但可能会在未来的版本中添加。通常，如果 DuckDB 决定对行组中的特定列（块）使用字典编码，则会写入布隆过滤器。有一个 COPY 参数控制最大字典大小（DICTIONARY_SIZE_LIMIT），但该参数默认设置为行组大小（ROW_GROUP_SIZE）的 10%，默认情况下为 122,880 行。这些值已被发现是大多数用例的合理初步近似值，但如果用户遇到性能问题，当然鼓励他们尝试这两个参数。随着布隆过滤器中不同值的数量增加，其大小需要增加以保持一定的误报率。默认情况下，过滤器大小选择使用“可接受”的误报率 1% 或 0.01。新的 BLOOM_FILTER_FALSE_POSITIVE_RATIO COPY 参数控制可接受的比率。通常，误报对读取路径越慢的影响越大。
读取
在读取过程中，DuckDB 会自动使用查询中的常量比较过滤谓词（例如，WHERE a = 42）来探测布隆过滤器（如果存在），并跳过布隆过滤器可以保证没有匹配行的行组。同样，这对用户完全透明，不需要进行任何配置。
用户可以查看给定的 Parquet 文件是否包含布隆过滤器：parquet_metadata 函数扩展了两个新列，bloom_filter_offset 和 bloom_filter_length。此外，为了实际找出给定文件和列的布隆过滤器会排除哪些行组，我们添加了 parquet_bloom_probe 函数。例如，parquet_bloom_probe('file.parquet', 'col1', 42) 返回一个表，指示对于 file.parquet 中的每个行组，列 col1 中的值 42 是否可以保证不在每个行组中。大多数用户不需要使用这些函数，它们只是帮助调试（和测试）。
示例用例
让我们通过一个示例展示 DuckDB 中的 Parquet 布隆过滤器。首先，我们创建一个包含布隆过滤器的示例文件 filter.parquet：
COPY (
FROM range(10) r1, range(10_000_000) r2
SELECT r1.range * 100 AS r
ORDER BY random()
)
TO 'filter.parquet'
(FORMAT parquet, ROW_GROUP_SIZE 10_000_000);
SELECT r, count(*)
FROM 'filter.parquet'
GROUP BY r
ORDER BY r;
该文件包含 10 个不同的值 (0, 100, 200 ... 900)，每个值重复一千万次。因此，总共有 1 亿行。生成的 Parquet 文件大小为 88 MB。
我们还将创建一个等效的文件，但不包含布隆过滤器。我们通过将 DICTIONARY_SIZE_LIMIT 设置为 1 来实现这一点：
COPY 'filter.parquet' to 'nofilter.parquet'
(FORMAT parquet, DICTIONARY_SIZE_LIMIT 1, ROW_GROUP_SIZE 10_000_000);
两个文件的内容是等效的，但 nofilter.parquet 不会使用字典编码，因此不会使用布隆过滤器。结果，该文件也更大，大小为 181 MB。然而，在查询不存在的值时，差异要大得多，在我们的示例中为 501：
.timer on
SELECT sum(r) FROM 'filter.parquet' WHERE r = 501;
SELECT sum(r) FROM 'nofilter.parquet' WHERE r = 501;
第一个查询在大约 0.002 秒内完成，而第二个查询需要 0.1 秒。这种巨大差异可以解释为布隆过滤器！由于 501 实际上不在查询中，DuckDB 可以自动排除所有行组，而不实际读取除布隆过滤器之外的任何数据。我们可以使用 parquet_metadata 函数进一步探讨这一点：
FROM parquet_metadata('filter.parquet')
SELECT row_group_id, stats_min, stats_max,
bloom_filter_offset, bloom_filter_length
ORDER BY row_group_id;
| row_group_id | stats_min | stats_max | bloom_filter_offset | bloom_filter_length |
|---|---|---|---|---|
| 0 | 0 | 900 | 92543967 | 47 |
| ... | ||||
| 9 | 0 | 900 | 92544390 | 47 |
我们可以看到有十个行组，每个行组都有一个相当紧凑的布隆过滤器，长度为 47 字节。这对于一个相当大的文件来说，大约增加了 500 字节，因此对文件大小的影响可以忽略不计。
如果我们在另一个文件上运行查询，我们可以看到缺少布隆过滤器：
FROM parquet_metadata('nofilter.parquet')
SELECT row_group_id, stats_min, stats_max,
bloom_filter_offset, bloom_filter_length
ORDER BY row_group_id;
| row_group_id | stats_min | stats_max | bloom_filter_offset | bloom_filter_length |
|---|---|---|---|---|
| 0 | 0 | 900 | NULL | NULL |
| ... |
我们可以使用 parquet_bloom_probe 函数进一步探索文件中的布隆过滤器。例如，对于值 500（存在于数据中），该函数显示如下：
FROM parquet_bloom_probe('filter.parquet', 'r', 500);
| file_name | row_group_id | bloom_filter_excludes |
|---|---|---|
| filter.parquet | 0 | false |
| ... | ... | ... |
| filter.parquet | 9 | false |
因此，布隆过滤器不能排除任何行组，因为值 500 包含在所有行组中。但如果我们尝试一个不存在的值，布隆过滤器就会发挥作用：
FROM parquet_bloom_probe('filter.parquet', 'r', 501);
| file_name | row_group_id | bloom_filter_excludes |
|---|---|---|
| filter.parquet | 0 | true |
| ... | ... | ... |
| filter.parquet | 9 | true |
在这里，我们可以自信地跳过所有行组，因为布隆过滤器保证这些行组中不可能有匹配的值。所有这些仅需每个行组 47 字节。
结论
DuckDB 对 Parquet 文件的新布隆过滤器支持可以大大减少在某些情况下需要读取的数据量，从而大大提高查询性能。这在文件通过慢速网络连接读取或行组特别大且具有少量不同但非聚集值的情况下特别有用。