Parquet 中定长列表的快速路径

# Parquet 中定长列表的快速路径 来源：https://www.morling.dev/blog/fast-path-for-fixed-length-lists-in-parquet/ 在当前的形式下，Apache Parquet 并不适合存储定长列表，例如坐标、RGB(A) 颜色，或者越来越常见的用于搜索和检索工作负载的向量嵌入。一个 768 维的嵌入本质上是一个长度始终相同的浮点数列表，但 Parquet 的 Dremel 机制却将其编码为长度可能逐行变化，并在读取时逐一向外拼写和重构每个向量的结构。这比同一数据的纯扁平列式表示花费大约 3 倍的成本（参见 apache/arrow#34510 (https://github.com/apache/arrow/issues/34510)）。 Parquet 社区已经认识到这个问题，并正在积极努力解决。目前正在讨论 (https://lists.apache.org/thread/qhq33wg1loxhymsyqjnsfsrd82qnv43m) 几种添加定长列表支持的选项，例如以新的逻辑类型 `FIXED_SIZE_LIST` 的形式。最终，这应该能将定长列表数据的解码性能提升到完全扁平模式的水平。然而，在此之前，我们是否可以通过更智能的方式检索有效的定长列表来缩小甚至消除性能差距？ 事实证明，是的，我们可以。 通过检查 Parquet 定义级别和重复级别的 *编码* 数据流，有可能检测出仅包含相同长度列表的数据页，并将这些页置于一条快速路径上，绕过常规的 Dremel 记录重构。我们为即将发布的 Hardwood 版本实现了这一优化，效果显著。具体影响取决于所选的 Hardwood 读取器（行读取 vs. 列读取）以及列表长度。下图展示了解析两个不同列表宽度的 ZSTD 压缩文件的结果，每个文件包含 1.28 亿个四字节浮点值。 短列表（3 个元素，比如三维坐标）对于行读取器有 1.1 倍的适度加速，对于列读取器则有 2.5 倍的显著加速。对于较大的 768 元素列表（例如向量嵌入），加速比分别达到 3.7 倍和 2.5 倍，与存储相同数量值的扁平列持平。行读取器的优势随列表长度增长：它需要为每条记录物化一个列表对象，这是快速路径无法消除的开销。对于短列表（大量记录），该开销占主导地位，收益较小；而对于长列表（少量记录），开销基本消失，快速路径使行读取器降低到扁平列的底层水平。 fixedlist bars 接下来，我们将深入探讨为什么 Parquet 在当前形式下并非存储定长列表的最优选择，以及 Hardwood 的定长列表快速路径如何弥补这一不足。 ## Parquet 的 Dremel 编码https://www.morling.dev/blog/fast-path-for-fixed-length-lists-in-parquet/#_parquets_dremel_encoding 首先，让我们探索 Parquet 究竟如何存储嵌套和重复数据。其存储表示在 2010 年的开创性论文 Dremel (https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/36632.pdf) 中有所描述。一个可选列表（即列表本身可以为 `null`），包含可选元素，具有如下模式： ``` 1 2 3 4 5 optional group mylist (LIST) { repeated group list { optional float element; } } ``` 这种三级编码用于区分 `null` 列表、空列表和 `null` 元素。Parquet 使用*定义级别*的概念来编码序列化数据中的哪些元素是 `null`。在 `mylist` 的例子中，最大定义级别为 3： - 整个列表为 null（定义级别 = 0） - 列表存在但为空（定义级别 = 1） - 列表包含一个 null 元素（定义级别 = 2） - 列表包含一个实际值（定义级别 = 3） *重复级别*的概念用于表达元素在（可能深度嵌套的）文档树中的哪个级别被重复。在我们的例子中，最大重复级别为 1：一个值要么延续当前记录的列表（重复级别 = 1），要么开始一条新记录的列表（重复级别 = 0）。 作为示例，考虑一个包含四个记录的 Parquet 文件，这些记录包含以下 `mylist` 值：`[1.0, null, 1.2]`、`null`、`[]`、`[4.0, 4.1]`。以下是值流以及定义级别和重复级别流： fixedlist dremel example variable 单独的值流会产生歧义；在读取时，无法知道某个值属于哪条记录以及空值的位置。定义级别流对 `null` 和空值进行编码，而重复级别流则确定记录边界。这种机制非常适合编码实际长度可变、可能包含 `null` 元素以及自身可能为 `null` 的列表。 现在，让我们看一个必需（即非可选）元素定长列表的例子（最大定义级别 = 1）： fixedlist dremel example constant 定义级别现在是一个恒定的 1 流；虽然这可以使用游程编码非常高效地编码，但我们理想情况下根本不存储任何内容，因为非空性已经是数据模式的一部分。重复级别是一个重复序列：一个 0 后跟 `n - 1` 个 1，其中 `n` 是列表的固定长度：`0,1,1,0,1,1,0,...`。这大概是你能想到的编码恒定 `n` 的最低效方式，因此可以理解 Parquet 社区正在探索更高效存储定长列表的替代方案。 现在，磁盘占用并不是大问题，因为这些数据编码紧凑。问题是处理开销：需要解码定义级别和重复级别流，为它们分配数组，读取器需要跟踪何时开始一条新记录的新列表，等等。所有这些加起来，导致前面提到的 3 倍减速。 ## 更快地读取有效定长列表https://www.morling.dev/blog/fast-path-for-fixed-length-lists-in-parquet/#_reading_effectively_fixed_length_lists_faster 在 Hardwood 中，我们最近实现了一项优化 (https://github.com/hardwood-hq/hardwood/blob/main/core/src/main/java/dev/hardwood/internal/reader/FixedSizeListDetector.java)，避免了这种开销。通过扫描编码后的定义级别和重复级别（以下简称 def 和 rep 级别），我们可以检测数据集中的列表实际上是否定长，即它们都具有相同的大小。如果是这样，我们可以绕过受影响数据页的常规 Dremel 记录重构机制，从而获得非常好的加速。那么这是如何工作的呢？ 对于 def 级别，这很简单。对于给定页面，我们寻找一个 `max_def_level` 流，其长度与页面中的值数量相匹配。同时处理必需列表（最大定义级别 = 1）和可选列表（最大定义级别 = 2）。Parquet 使用一种混合方案 (https://parquet.apache.org/docs/file-format/data-pages/encodings/#RLE)，即位打包和游程编码 (RLE)，来存储 def 和 rep 级别。假设我们正在处理一个包含 3D 浮点坐标的页面，即 `n` = 3 的定长列表。对于 4 字节浮点数，一个约 1 MB 的页面大约包含 87,000 条记录，每条记录 3 个坐标——总共 261,000 个叶条目（261,000 × 4 字节 ≈ 1 MB）。对于所有存在的列表元素流，编码器会将 def 级别序列化为一个单一的 RLE 运行，由一个 varint 头部组成——运行长度左移一位，释放的低位设置为 0 以标记此为 RLE 运行而不是位打包——后跟一个最大定义级别字节： fixedlist def levels 这种对空值缺失的检查计算复杂度为 O(1)，如果成功，页面会被简单地打上“无空值”标记，从而避免解码和处理 def 级别流。事实上，这种优化并不特定于定长列表；它还能加速常见情况：模式允许空值但碰巧不包含任何空值的列。这种快捷方式众所周知，也已在其他 Parquet 读取器和引擎中实现，包括 DuckDB (https://github.com/duckdb/duckdb/blob/2c2d62b247fdd87311b4f0a00bc7d3e209a0381b/extension/parquet/column_reader.cpp#L719-L723)。 检测编码后 rep 级别流中的重复 0,1,1,0,... 模式要复杂一些。其编码方式取决于 `n` 的值：Parquet 的 RLE/位打包混合方案将记录开始处的 0 和最多后续七个 1 进行位打包。如果列表长度更长——还有更多 1 剩余——剩余的 1 会被放入一个 RLE 运行中。这意味着我们需要查找一系列位打包运行（`n` ≤ 8）或交替出现的位打包和 RLE 运行。 如果通过了 def 级别门控，定长列表检测器会首先尝试检测小 `n` 的 rep 级别。`n` 本身是第一个 0 与下一个 0 之间的距离。对一个周期性位模式进行位打包会产生一个周期性的*字节*模式，周期为 `n / gcd(n, 8)` 个字节：当 `n` 整除 8 时（`n` 属于 {1,2,4,8}）为一个字节，否则为 3/5/7 个字节。例如，对于 `n` = 4，印记为一个字节 `0xee`（`0 1 1 1 0 1 1 1`，LSB 优先读取），即两个记录的列表被一个字节覆盖： fixedlist rep levels bitpacked 如果 `n` = 3，印记为三个字节 `B6 6D DB`，跨越 8 条记录（24 位）。单字节和多字节印记都只计算一次，然后批量应用，每次将八个 rep 级别字节读入一个长整型。如果给定的小 `n` rep 级别流在某个时刻与印记模式不匹配，则意味着列表长度可变，无法采用快速路径。这种技术（SWAR，寄存器内的 SIMD）在基准测试中证明足够快¹。 接下来，讨论 `n` ≥ 16 的情况；此时我们需要寻找重复出现序列：记录边界处的位打包运行，后跟一个由 `n` - 8 个 1 组成的 RLE 运行。在常见情况下，每条记录都落在字节边界上，因此每条记录都是*相同*的字节序列。 例如，对于 `n` = 16，每条记录将有四个字节： fixedlist rep levels rle 我们只需要解析第一条记录的 rep 级别，从而可以推导出 `n` 和步幅（以字节为单位），然后检查整个流是否重复该步幅。它是字节周期的，周期为 `strideBytes`，因此左移一个步幅的流必须等于自身。这种批量比较取代了逐值的 rep 级别处理。 所示的确切字节分割——一个位打包边界组加上一个 RLE 运行——是主流编码器（包括 parquet-java 和 Arrow C++）输出的。然而，这依赖于编码器。Parquet 规范本身只要求 rep 级别解码出正确的序列，而不要求 RLE/位打包混合如何将它们分块成运行。因此，检测器不会硬编码任何特定模式；相反，它从第一条记录推导出步幅，并验证流的其余部分重复该步幅，对于任何它无法识别的布局，则回退到下面描述的标量回退。 第三种也是最后一种情况是 9 ≤ `n` ≤ 15。在这种情况下，没有按记录的步幅可供批量比较：例如，一个 9 元素列表的 rep 级别是 9 位；相对于 8 位字节，其边界每条记录漂移一位，并且仅每 lcm(8, 9) = 72 个值重新对齐。标量回退处理这些情况，逐个运行处理 rep 级别，确保记录边界之间的等距。它读取每个运行的头部，并一次以 64 位字扫描位打包组，同时跳过 1 的 RLE 运行（O(1) 复杂度）而不是展开它们。一旦两条记录的长度不一致，该页面就会被拒绝进入快速路径。由于它不假设布局，该路径也能捕获较不常见的非常规情况：单元素列表，或异常划分运行的写入器。 ## 性能提升https://www.morling.dev/blog/fast-path-for-fixed-length-lists-in-parquet/#_performance_gains 现在，应用此逻辑后我们实际获得了什么——一旦确定给定页面中的所有列表都具有相同长度，“定长列表快速路径”具体指什么？在这种情况下可以应用多项优化： - 按页面批量复制值，而不是逐元素处理 - 偏移量很简单——不需要扫描 rep 级别来恢复记录边界 - 从不物化 def 和 rep 级别数组，减少 GC 压力 效果是显著的。目前快速路径是选择性加入的，因此我们可以轻松测量开启和关闭优化时的定长列表解析时间。图表展示了从 1 到 1536 的 `n` 范围扫描结果。 fixedlist sweep 对于列读取器，优势在整个扫描范围内稳定在大约 2.5 倍。阴影带标记了标量回退宽度（`n` = 9–15），这些宽度不是字节对齐的，因此使检测器的 rep 级别扫描回退到较慢的逐位行走——在列曲线上表现为轻微的下降，并且是检测器开销最大的情况（我们将在下面量化）。行读取器的形状更明显，在中段（`n` ≈ 64–256）攀升至约 3.9 倍的峰值，然后对于大列表稳定在 3.6 倍。列表中罕见的极端情况是长度为 1：每条记录只有一个元素，列表对象创建占主导地位，快速路径对行读取器没有带来优势——如果有的话，反而稍微慢一点²。 当然，对编码后的 def 级别和（特别是）rep 级别流运行这种检测逻辑本身也有成本。那么它是否会惩罚常规的可变长度 `LIST` 列呢？检测器的计算成本很大程度上取决于列表大小和应用的模式逻辑：对于 `n` ≤ 8，需要遍历所有 rep 级别的位打包运行，成本约为常规列表检索成本（延迟）的 1.7%。对于较大的 `n`，高效的 RLE 运行将检测复杂度降低到接近 `O(records)`，因此相对成本从约 0.2%（`n` = 16）降至 0.1% 以下（`n` = 768）。正如预期，最昂贵的情况是标量回退，对于 `n` = 15，检测器相对开销约为 17%。 然而，这些是在微基准测试中单独测量 (https://github.com/hardwood-hq/hardwood-benchmarks/blob/main/results/2026-07-22-fixed-size-list/decode-benchmark.log) 的纯检测延迟。当查看实际的端到端解析时间时，对于所有 `n` 值，快速路径检测器的成本都可以忽略不计。即使在绝对最坏的情况下——即页面中只有最后一个列表与之前所有列表的长度不同（意味着检测器的 O(1) def 级别门控通过，然后它扫描整个 rep 级别流，最后才找到异常列表并回退到常规解码路径）——对所有列表大小（一个除外）的整体处理时间没有可测量的影响 (https://github.com/hardwood-hq/hardwood-benchmarks/blob/main/results/2026-07-22-fixed-size-list/fallback-benchmark.log)。仅在 `n` = 15（一个不常见的宽度，且是开销最大的标量回退情况）时，开销约为 2%，刚好超出 99.9% 的置信区间。 本文中的基准测试基于 JMH (https://github.com/openjdk/jmh)，运行三个分叉，每个分叉进行五次测量。基准测试在 AWS m7i.2xlarge 实例（8 vCPU / 4 物理核心；32 GB RAM）上使用 Java 25（Temurin 构建版）进行。Hardwood 在内部并行化页面解码，因此读取操作使用了所有核心。文件从操作系统的页面缓存中提供。为了考虑运行间的变异性，吞吐量基准测试（上述两个图表）每个运行三次，并显示每个点的中位数。