DuckDB 支持 Parquet 布隆过滤器性能飙升
如果你对parquet不太了解, 可以先看一下这篇:
DuckDB 支持利用已有parquet文件内的bloom filter来过滤不需要访问的row group, 同时支持在往parquet文件写入数据时, 生成column 对应row group的对应bloom filter, 使得通过存在、不存在来过滤字段值的效率大幅度提升.
原文
https://duckdb.org/2025/03/07/parquet-bloom-filters-in-duckdb.html
Parquet 文件格式的主要特性之一是读取器可以选择性地只读取与特定查询相关的数据。为了支持这一点，Parquet 文件包含列统计信息，最显著的是每个行组中每列的最小值和最大值(column row group对应column value min,max)。如果查询使用特定值进行过滤，并且数据 (通常) 经过某种排序，则读取器可以“证明”特定行组不能包含与查询相关的值(但不是所有column 都是sort key, 只有一列能成为sort key)。DuckDB 充分利用了这一点，并且能够 (即使在查询远程端点时, 例如oss, s3) 选择性地仅读取与查询相关的 Parquet 文件部分。
但是，这种方法有一些局限性。如果某列的数据是随机打乱的，会怎么样？在这种情况下，所有值都会出现在所有行组中，最小值和最大值统计信息就没那么有用了，因为我们只能排除整列最小值和最大值之外的值。如果列中没有太多不同的值，Parquet 将使用字典编码。理论上，字典可用于消除行组，但这种方法存在两个问题：Parquet（莫名其妙地）允许在行组中途从字典切换到纯文本编码。(也就是存储字典的空间有限, 不能存下所有唯一值时, 或者说不同的row group可能有不同的编码) 如果仅使用字典来消除行组，但纯文本部分包含查询值，则会导致不正确的结果。此外，字典是实际列数据的一部分。如果我们读取列数据只是为了查看字典，那么我们首先已经承担了读取列的大部分成本。
晦涩的旁注：同样，理论上，列元数据包含该列中出现的编码列表。如果该列表正确且不包含纯编码，则字典可以（同样，理论上）用于稍早的行组消除。但这种方法的实用性非常可疑。
Parquet 布隆过滤器
Parquet PMC的优秀员工已经意识到这里还有改进的空间，并于 2018 年为 Parquet 添加了布隆过滤器。简而言之，布隆过滤器是一组值的紧凑但近似的索引结构(用某些位置的若干个bit代表某个原始值是否存在, 如果有很多个唯一值, bit不够用, 可能导致bloom value中的某些bit全为1表达其"实际不存在的原始值".)。对于给定的值，他们可以肯定地说某个值不在集合中，或者它可能在集合中，假阳性率取决于布隆过滤器的大小和添加到其中的不同值的数量。目前，我们可以将布隆过滤器视为具有魔法属性的不透明字节序列。
使用时，Parquet 文件可以包含每个行组中每列的布隆过滤器。每个布隆过滤器可以位于文件中的任意位置（bloom_filter_offset）。在文件的偏移量处，我们发现另一个 Thrift 编码的结构BloomFilterHeader。此结构有一个用于过滤器长度的字段，以及一些算法设置，这些设置目前是多余的，因为所有算法设置只有一个有效设置。但必须解码标头才能找出标头的结束位置和过滤器字节的开始位置。最后，我们得到了布隆过滤器的宝贵魔法字节。现在我们可以针对任何查询谓词测试过滤器，看看是否可以完全跳过行组。
更晦涩的旁注：虽然列元数据确实包含一个字段来存储过滤器的大小（bloom_filter_length），但它也是可选的，有些编写器（说说你，Spark）很烦人地只设置了偏移量，而不是长度。此外，规范描述了两个可能的过滤器位置。由于元数据中也不要求长度，这使得在单个范围请求中读取 Parquet 文件的所有布隆过滤器变得困难/不可能。同样不清楚的是，为什么每个布隆过滤器都需要以 Thrift 元数据 blob 作为前缀，而这些信息也可以包含在 ColumnMetaData 中。或者，上帝保佑，过滤器可能成为主要 Parquet 元数据本身的一部分。最后，我们需要进行大量额外的读取才能找到和读取布隆过滤器字节，原则上需要在读取过滤器和“仅仅”强制读取列之间进行仔细的权衡。
DuckDB 布隆过滤器
从上一个功能版本 (1.2.0) 开始，DuckDB 支持读取和写入Parquet Bloom 过滤器。这对用户完全透明，无需额外操作或配置。
写入
目前支持以下类型的布隆过滤器：
整数类型 TINYINT UTINYINT SMALLINT USMALLINT INTEGER UINTEGER BIGINT UBIGINT浮点类型 FLOAT, DOUBLE字符串类型 VARCHAR和BLOB
目前不支持嵌套类型（列表、结构体、数组），但可能会在将来的版本中添加。通常，如果 DuckDB 决定对行组内的某个列（块）使用字典编码，则会编写布隆过滤器。有一个COPY参数控制最大字典大小（DICTIONARY_SIZE_LIMIT
），但此参数默认设置为行组大小的 10%（ROW_GROUP_SIZE
），默认为 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
该表指示是否可以保证值42
不在每个行组中或不在每个列中col1
。然而，大多数用户不需要使用这些函数，它们只是帮助调试（和测试）。
示例用例
让我们通过一个示例展示 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。
我们还将创建一个等效文件，但没有布隆过滤器。我们通过将设置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; -- 0.002 s
SELECT sum(r) FROM 'nofilter.parquet' WHERE r = 501; -- 0.1 s
第一个查询在大约 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;
我们可以看到有 10 个行组，并且每个行组都有一个非常紧凑的布隆过滤器，每个长度为 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;
我们可以使用该函数进一步探索文件中的布隆过滤器parquet_bloom_probe
。例如，对于值 500（存在于数据中），该函数显示以下内容：
FROM parquet_bloom_probe('filter.parquet', 'r', 500);
因此，布隆过滤器无法排除任何行组，因为该值500包含在所有行组中。但是，如果我们尝试一个不存在的值，布隆过滤器就会出问题：
FROM parquet_bloom_probe('filter.parquet', 'r', 501);
在这里，我们可以放心地跳过所有行组，因为布隆过滤器保证这些行组中不会有匹配的值。每个行组有 47 个字节。
结论
DuckDB 新增了对 Parquet 文件的 Bloom filter 支持，这可以大大减少某些场景下需要读取的数据量，从而大幅提高查询性能。如果文件是通过较慢的网络连接读取的，或者行组特别大且包含少量不同但非聚类的值，那么此功能尤其有用。
