DuckDB 中的 Parquet Bloom 过滤器

Hannes Mühleisen

2025-03-07 · 10 分钟

Parquet 文件格式的一个关键特性是，读取器能够选择性地仅读取与特定查询相关的数据。为支持此功能，Parquet 文件包含列统计信息，最显著的是每个行组中每列的最小值和最大值。如果查询使用特定值进行过滤，并且数据（通常如此）是某种程度上排序的，那么读取器可以“证明”特定行组不包含与查询相关的值。DuckDB 充分利用了这一点，即使在查询远程端点时，也能够选择性地仅读取 Parquet 文件中与查询相关的部分。有关其工作原理的详细信息，请参阅我们现在已有些过时的博客文章《使用 DuckDB 精确查询 Parquet》。

然而，这种方法存在一些局限性。如果列的数据是随机打乱的呢？在这种情况下，所有值都会出现在所有行组中，最小值和最大值统计信息的作用就会减弱，因为我们只能排除整个列的最小值和最大值范围之外的值。如果列中不包含太多不同的值，Parquet 将使用字典编码。理论上，该字典可用于排除行组，但这种方法存在两个问题：Parquet（令人费解地）允许在行组的中间从字典编码切换到普通编码。如果仅凭字典来排除行组，但普通编码部分包含查询值，这将导致结果不正确。此外，字典是实际列数据的一部分。如果仅仅为了查看字典而读取列数据，我们实际上已经承担了大部分读取列数据的成本。

鲜为人知的旁注：同样，理论上列元数据包含该列中出现的编码列表。如果该列表是正确的，并且不包含普通编码，那么字典理论上可以用于更早地排除行组。但这种方法的实用性非常可疑。

Parquet Bloom 过滤器

Parquet PMC 的优秀工程师们认识到此处有改进空间，并于 2018 年为 Parquet 添加了Bloom 过滤器。简而言之，Bloom 过滤器是一种紧凑但近似的值集索引结构。对于给定值，它们可以肯定地表明某个值不在集合中，或者可能在集合中，其误报率取决于 Bloom 过滤器的大小和添加到其中的不同值的数量。目前，我们可以将 Bloom 过滤器视为具有神奇属性的不透明字节序列。

使用时，Parquet 文件可以为每个行组中的每列包含一个 Bloom 过滤器。每个 Bloom 过滤器可以位于文件中的任意位置（bloom_filter_offset）。在文件中的该偏移量处，我们找到另一个 Thrift 编码的结构，即BloomFilterHeader。此结构有一个字段用于存储过滤器的长度，以及一些算法设置，这些设置目前是冗余的，因为所有这些设置只有一个有效值。但您必须解码头部，才能找出头部结束和过滤器字节开始的位置。最终，我们找到了 Bloom 过滤器的宝贵神奇字节。我们现在可以根据任何查询谓词测试过滤器，并查看是否可以完全跳过该行组。

更鲜为人知的旁注：虽然列元数据确实包含一个字段来存储过滤器的大小（bloom_filter_length），但它也是可选的，有些写入器（说的就是你，Spark）烦人地只设置偏移量，而不设置长度。此外，规范描述了两种可能的过滤器位置。通过也不要求元数据中包含长度，这使得在单个范围请求中读取 Parquet 文件的所有 Bloom 过滤器变得困难甚至不可能。也不清楚为什么每个 Bloom 过滤器*都*需要以 Thrift 元数据块作为前缀，而这些信息也可以包含在 ColumnMetaData 中。或者，天知道，这些过滤器本可以成为 Parquet 主元数据本身的一部分。最终，我们为了查找和读取 Bloom 过滤器字节而进行了大量的额外读取，原则上需要在读取过滤器和“仅仅”暴力读取列数据之间进行仔细权衡。

DuckDB Bloom 过滤器

截至上一个功能版本 (1.2.0)，DuckDB 同时支持读写 Parquet Bloom 过滤器。这一切对用户来说是完全透明的，无需额外的操作或配置。

写入

目前，Bloom 过滤器支持以下类型：

• 整数类型（TINYINT, UTINYINT, SMALLINT, USMALLINT, INTEGER, UINTEGER, BIGINT, UBIGINT）
• 浮点类型（FLOAT, DOUBLE）
• 字符串类型（VARCHAR 和 BLOB）

嵌套类型（列表、结构体、数组）目前不支持，但可能会在未来的版本中添加。通常，如果 DuckDB 决定在行组内对特定列（块）使用字典编码，则会写入 Bloom 过滤器。有一个 COPY 参数控制最大字典大小（DICTIONARY_SIZE_LIMIT），但此参数默认设置为行组大小（ROW_GROUP_SIZE）的 10%，默认情况下为 122,880 行。这些值已被证明是大多数用例的合理首次近似值，但如果用户遇到性能问题，当然鼓励他们尝试这两个参数。随着 Bloom 过滤器中不同值的数量增加，其大小需要增加以保持一定的误报率。默认情况下，过滤器大小是根据“可接受”的 1% 或 0.01 误报率选择的。新的 BLOOM_FILTER_FALSE_POSITIVE_RATIO COPY 参数控制可接受的比例。通常，读取路径越慢，误报造成的损害越大。

读取

在读取过程中，DuckDB 会自动使用查询中的常量比较过滤谓词（例如 WHERE a = 42）来探测 Bloom 过滤器（如果存在），并跳过那些 Bloom 过滤器可以保证组中没有匹配行的行组。同样，这对用户来说是透明的，无需进行任何配置。

用户可以查明给定的 Parquet 文件是否包含 Bloom 过滤器：parquet_metadata 函数已扩展了两个新列，bloom_filter_offset 和 bloom_filter_length。此外，为了实际查明给定文件和列的哪些行组会被 Bloom 过滤器排除，我们添加了 parquet_bloom_probe 函数。例如，parquet_bloom_probe('file.parquet', 'col1', 42) 会为 file.parquet 中的每个行组返回一个表，该表指示列 col1 的值 42 是否可以保证不在每个行组中。然而，大多数用户无需使用这些函数，它们仅有助于调试（和测试）。

示例用例

让我们通过一个例子来展示 DuckDB 中的 Parquet Bloom 过滤器。首先，我们创建一个示例文件 filter.parquet，它将包含 Bloom 过滤器。

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。

我们还将创建一个等效文件，但不包含 Bloom 过滤器。我们通过将 DICTIONARY_SIZE_LIMIT 设置为 1 来实现这一点。

COPY 'filter.parquet' to 'nofilter.parquet'
(FORMAT parquet, DICTIONARY_SIZE_LIMIT 1, ROW_GROUP_SIZE 10_000_000);

两个文件的内容将是等效的，但 nofilter.parquet 不会使用字典编码，因此也不会使用 Bloom 过滤器。结果，文件也更大，大小为 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 秒。这种巨大差异可以用 Bloom 过滤器来解释！由于 501 实际上并未出现在查询中，DuckDB 可以自动排除所有行组，除了 Bloom 过滤器之外不实际读取任何数据。我们可以使用 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;

我们可以看到有十个行组，并且每个行组都有一个非常紧凑的 Bloom 过滤器，每个过滤器的长度为 47 字节。这大约是向相当大的文件中增加了 500 字节，因此与文件大小无关紧要。

如果我们对另一个文件运行查询，我们可以看到没有 Bloom 过滤器。

FROM parquet_metadata('nofilter.parquet')
SELECT row_group_id, stats_min, stats_max,
       bloom_filter_offset, bloom_filter_length
ORDER BY row_group_id;

我们可以使用 parquet_bloom_probe 函数进一步探索文件中的 Bloom 过滤器。例如，对于值 500（数据中存在），该函数显示如下：

FROM parquet_bloom_probe('filter.parquet', 'r', 500);

因此，Bloom 过滤器无法排除任何行组，因为值 500 包含在所有行组中。但是如果我们尝试一个不存在的值，Bloom 过滤器就发挥作用了：

FROM parquet_bloom_probe('filter.parquet', 'r', 501);

在这里，我们可以自信地跳过所有行组，因为 Bloom 过滤器保证这些行组中不可能有匹配的值。所有这些只需每个行组 47 字节。

结论

DuckDB 对 Parquet 文件的最新 Bloom 过滤器支持可以在某些场景下极大地减少要读取的数据量，从而显著提高查询性能。如果文件是通过慢速网络连接读取，或者行组特别大但其中只有少量不聚集的不同值时，此功能尤其有用。