使用 StringView / 德式字符串加速查询：第一部分 - 读取 Parquet

作者：Andrew Lamb / Xiangpeng Hao / 开发者
2024 年 8 月 22 日

导航至

编者注：这是两部分博客系列的第一篇。

本博客描述了我们在 StringView 在 Apache Arrow 的 Rust 实现中的实施经验，并将其集成到 Apache DataFusion 中，显著加速了 ClickBench 基准测试中字符串密集型查询的速度，提升了 20%-200%（图 11）。

获得显著的端到端性能提升并非易事。实施 StringView 本身只是所需工作量的一小部分。 除此之外，我们还必须优化 UTF-8 验证、实施违反直觉的编译器优化、调整块大小以及调整 GC 时间，以实现 FDAP 生态系统的优势。 在开源社区其他成员的帮助下，我们能够克服可能扼杀该项目的性能瓶颈。 我们希望通过更详细地解释挑战和解决方案来做出贡献，以便更多的社区可以从我们的经验中学习。

StringView 基于一个简单的想法：避免一些字符串复制，并通过内联前缀加速比较。 像大多数伟大的想法一样，它只有在 有人清楚地描述它之后才变得“显而易见”。 虽然简单，但直接的实现实际上降低了几乎每个查询的性能。 因此，我们必须运用敏锐的观察和勤奋的工程来实现 StringView 的实际好处。

虽然这段旅程是成功的，但并非所有研究想法都如此幸运。 为了加速研究成果在工业界的采用，将研究原型与实际系统集成非常有价值。 了解真实世界系统的细微之处，更有可能使研究设计2 能够带来实际的系统改进。

StringView 支持已作为 arrow-rs v52.2.0 和 DataFusion v41.0.0 的一部分发布。 您可以通过设置 schema_force_string_view DataFusion 配置选项来试用它，并且我们正在 与社区共同努力，使其成为默认设置。 我们邀请所有人试用它，利用迄今为止投入的努力，并为使其变得更好做出贡献。 图 1：StringView 将字符串密集型 ClickBench 查询性能提高了 20% - 200%

第 1 节：什么是 StringView？

图 2：使用 StringArray 和 StringViewArray 表示相同的字符串内容。

带有前缀的内联字符串概念（Andy Pavlo 称之为“德式字符串” by Andy Pavlo，致敬 TUM，描述它们的 Umbra 论文起源于此）已在许多最新的数据库系统中使用 (Velox, Polars, DuckDB, CedarDB 等），并作为新的 StringViewArray3 类型引入 Arrow。 Arrow 原来的 StringArray 非常节省内存，但在某些操作中效率较低。 StringViewArray 通过前缀内联和更灵活、更紧凑的字符串表示来加速字符串密集型操作。

StringViewArray 由三个组件组成

  1. 视图数组
  2. 缓冲区
  3. 将缓冲区偏移量映射到其物理位置的缓冲区指针（ID）

每个视图长 16 个字节，其内容根据字符串的长度而有所不同

  • 字符串长度 < 12 字节：前四个字节存储字符串长度，剩余 12 个字节存储内联字符串。
  • 字符串长度 > 12 字节：字符串存储在单独的缓冲区中。 长度再次存储在前 4 个字节中，后跟缓冲区 ID（4 个字节）、缓冲区偏移量（4 个字节）和字符串的前缀（前 4 个字节）。

图 2 显示了使用 StringArray（中间）和 StringViewArray（右侧）的相同逻辑内容示例（左侧）

  • 第一个字符串 – “Apache DataFusion” – 长 17 个字节，StringArray 和 StringViewArray 都将字符串的字节存储在缓冲区的开头。 StringViewArray 还在视图中内联了前 4 个字节 – “Apac”。
  • 第二个字符串 “InfluxDB” 仅长 8 个字节，因此 StringViewArray 将字符串内容完全内联到视图结构中，而 StringArray 也将字符串存储在缓冲区中。
  • 第三个字符串 “Arrow Rust Impl” 长 15 个字节，无法完全内联。 StringViewArray 以与第一个字符串相同的形式存储它。
  • 最后一个字符串 “Apache DataFusion” 与第一个字符串具有相同的内容。 可以使用 StringViewArray 避免这种重复，并通过将视图指向先前的位置来重用字节。

StringViewArray 提供了三个优于 StringArray 的机会

  1. 通过偏移量 + 缓冲区格式减少复制
  2. 使用内联字符串前缀进行更快的比较
  3. 使用灵活的视图布局重用重复的字符串值

本博文的其余部分讨论了如何在实际查询场景中应用这些机会来提高性能，我们在此过程中遇到了哪些挑战，以及我们如何解决这些挑战。

第 2 节：更快的 Parquet 加载

Apache Parquet 是存储大规模分析数据的实际标准格式，这些数据通常以 LakeHouse 风格存储，例如 Apache Iceberg 和 Delta Lake。 因此，从 Parquet 有效加载数据对于许多重要的实际工作负载中的查询性能至关重要。

Parquet 以与原始 Arrow StringArray 所需格式略有不同的格式编码字符串（即，字节数组）。 字符串长度与实际字符串数据内联编码（如图 4 左侧所示）。 如前所述，StringArray 要求数据缓冲区是连续且紧凑的——字符串必须一个接一个地跟随。 这一要求意味着将 Parquet 字符串数据读入 Arrow StringArray 需要将字符串字节复制并整合到新缓冲区中，并在单独的数组中跟踪偏移量。 复制这些字符串通常是浪费的。 典型的查询会在加载后立即过滤掉大部分数据，因此大部分复制的数据很快就会被丢弃。

另一方面，将 Parquet 数据读取为 StringViewArray 可以重用与存储 Parquet 页面相同的数据缓冲区，因为 StringViewArray 不要求字符串是连续的。 例如，在图 4 中，StringViewArray 直接引用带有解码后的 Parquet 页面的缓冲区。 字符串 “Arrow Rust Impl” 由偏移量为 37、长度为 15 的 view 表示到该缓冲区中。

图 4：StringViewArray 通过重用解码后的 Parquet 页面来避免复制。

迷你基准测试

理论上重用 Parquet 缓冲区很棒，但是节省复制实际上有多重要？ 我们可以运行以下基准测试在 arrow-rs 中找出答案

cargo bench --bench arrow_reader --features="arrow test_common experimental" "arrow_array_reader/Binary.*Array/plain encoded"

我们的基准测试机器显示，加载 BinaryViewArray 比加载 BinaryArray 快近 2 倍（请参阅下一节，了解为什么这不是 StringViewArray）。

arrow_array_reader/BinaryArray/plain encoded                        time:   [315.86 µs **317.47 µs** 319.00 µs]
arrow_array_reader/BinaryViewArray/plain encoded
time:   [162.08 µs **162.20 µs** 162.32 µs]

您可以阅读更多关于此 arrow-rs 问题的文章：https://github.com/apache/arrow-rs/issues/5904

第 2.1 节：从二进制到字符串

您可能想知道，当这篇文章是关于 StringViewArray 时，我们为什么要报告 BinaryViewArray 的性能。 令人惊讶的是，最初，我们从 Parquet 读取 StringViewArray 的实现比 StringArray 慢得多。 为什么？ 总结：虽然读取 StringViewArray 复制的数据更少，但最初的实现也花费了更多时间来验证 UTF-8（如图 5 所示）。

字符串存储为字节序列。 当从（可能不受信任的）Parquet 文件读取数据时，Parquet 解码器必须确保这些字节序列是有效的 UTF-8 字符串，并且大多数编程语言（包括 Rust）都包含高度 优化的例程来执行此操作。

图 5：从 Parquet 加载字符串的时间。 UTF-8 验证优势最初消除了 StringViewArray 减少复制的优势。

StringArray 可以通过单次调用 UTF-8 验证函数来验证，因为它具有连续的字符串缓冲区。 只要底层缓冲区是 UTF-84，数组中的所有字符串都必须是 UTF-8。 Rust parquet 读取器进行单次函数调用来验证整个缓冲区。

但是，验证任意 StringViewArray 需要对每个字符串进行单独的验证函数调用，因为底层缓冲区也可能包含非字符串数据（例如，Parquet 页面中的长度）。

Rust 中的 UTF-8 验证经过高度优化，并且偏爱较长的字符串（如图 6 所示），这可能是因为它利用 SIMD 指令来执行并行验证。 对每个字符串进行函数调用以验证 UTF-8 而不是对每个字符串进行函数调用的好处，完全超过了避免 StringViewArray 复制的优势。

图 6：UTF-8 验证吞吐量与字符串长度的关系——StringArray 的连续缓冲区可以比 StringViewArray 的缓冲区更快地验证。

这是否意味着我们应该只使用 StringArray？ 不！ 值得庆幸的是，有一种巧妙的解决方法。 关键的观察是，在许多真实世界的数据集中，99% 的字符串都短于 128 个字节，这意味着编码的长度值小于 128，在这种情况下，长度本身也是有效的 UTF-8（实际上，它是 ASCII）。

这种观察意味着，我们可以通过将长度字节视为单个大字符串的一部分来优化 Parquet 页面中 UTF-8 字符串的验证，只要长度值小于 128 即可。 换句话说，在此优化之前，长度字节充当字符串边界，这需要在每个字符串上进行 UTF-8 验证。 在此优化之后，只有长度大于 128 字节的字符串（在 ClickBench 数据集中，小于 1% 的字符串）才是字符串边界，这显著增加了 UTF-8 验证块大小，从而提高了性能。

实际实现只有九行 Rust 代码（带 30 行注释）。 您可以在相关的 arrow-rs 问题中找到更多详细信息：https://github.com/apache/arrow-rs/issues/5995。 正如预期的那样，通过此优化，加载 StringViewArray 比加载 StringArray 快近 2 倍。

第 2.2 节：注意隐式复制

在完成所有避免从 Parquet 加载时复制字符串的工作之后，性能仍然没有达到预期。 我们将问题追溯到一些我们没有意识到的隐式数据复制，如 此问题中所述。

我们最终确定的副本来自以下看似无辜的 Rust 代码行，其中 self.buf 是一个 引用计数 指针，它应该在不复制的情况下转换为缓冲区，以便在 StringViewArray 中使用。

let block_id = output.append_block(self.buf.clone().into());

但是，Rust 类型强制转换规则偏爱 blanket 实现，该实现确实复制了数据。 此实现显示在以下代码块中，其中 impl<T: AsRef<[u8]>> 将接受任何实现 AsRef<[u8]> 的类型，并复制数据以创建新缓冲区。 为了避免复制，用户需要显式调用 from_vec，这将消耗 Vec 并将其转换为缓冲区。

impl<T: AsRef<[u8]>> From<T> for Buffer {
    fn from(p: T) -> Self {
        // copies data here
	 ...
    }
}
impl Buffer { 
  pub fn from_vec<T>(data: Vec<T>) -> Self {
// zero-copy transformation
...
  }
}

诊断这种隐式复制非常耗时，因为它依赖于 Rust 语言的细微语义。 我们需要跟踪数据流的每个步骤，以确保每次复制都是必要的。 为了帮助其他用户并防止将来出错，我们还从 arrow-rs 中 删除了隐式 API，转而使用显式 API。 使用这种方法，我们在代码库中找到并修复了几个 其他意外的副本——希望这种更改将帮助其他 下游用户避免不必要的副本。

第 2.3 节：通过提供更多信息来帮助编译器

Rust 编译器的自动优化在各种用例中通常都表现出色，但有时，它需要额外的提示才能生成最有效的代码。在分析 view 构建的性能时，我们反直觉地发现，构建长字符串比构建短字符串快 10 倍，这使得短字符串在 StringViewArray 上比在 StringArray 上更慢！

正如第 1 节所述，StringViewArray 对长字符串和短字符串的处理方式不同。短字符串（<12 字节）直接内联到 view 结构体中，而长字符串仅内联前 4 个字节。构建 view 的代码如下所示：

if len <= 12 {
   // Construct 16 byte view for short string
   let mut view_buffer = [0; 16];
   view_buffer[0..4].copy_from_slice(&len.to_le_bytes());
   view_buffer[4..4 + data.len()].copy_from_slice(data);
   ...
} else {      
   // Construct 16 byte view for long string
   ByteView {
       length: len,
       prefix: u32::from_le_bytes(data[0..4].try_into().unwrap()),
       buffer_index: block_id,
       offset,
   }
}

代码的两个分支看起来都应该很快：它们都涉及复制最多 16 字节的数据和一些内存移位/存储操作。为什么短字符串的分支会慢 10 倍呢？

通过使用 godbolt 查看汇编代码，我们（在 Ao Li 的帮助下）发现编译器使用 CPU 加载指令将固定大小的 4 个字节复制到长字符串的 view，但它调用了一个函数 ptr::copy_non_overlapping，将内联字节复制到短字符串的 view。区别在于长字符串的前缀大小（4 字节）在编译时已知，因此编译器直接使用高效的 CPU 指令。但是，由于短字符串的大小对编译器来说是未知的，因此它必须调用通用函数 ptr::copy_non_coverlapping。与 CPU 复制指令相比，进行函数调用是不必要的开销。

但是，我们知道一些编译器不知道的事情：短字符串的大小不是任意的——它必须在 0 到 12 字节之间，我们可以利用这些信息来避免函数调用。我们的解决方案使用泛型生成 13 个函数副本，每个副本对应一个可能的前缀长度。代码如下所示，并且查看汇编代码，我们确认没有调用 ptr::copy_non_overlapping，并且只使用了原生 CPU 指令。有关更多详细信息，请参阅 该 issue。

fn make_inlined_view<const LEN: usize>(data: &[u8]) -> u128 {
     let mut view_buffer = [0; 16];
     view_buffer[0..4].copy_from_slice(&(LEN as u32).to_le_bytes());
     view_buffer[4..4 + LEN].copy_from_slice(&data[..LEN]);
     u128::from_le_bytes(view_buffer)
}
pub fn make_view(data: &[u8], block_id: u32, offset: u32) -> u128 {
     let len = data.len();
     // generate special code for each of the 13 possible lengths
     match len {
         0 => make\_inlined\_view::<0>(data),
         1 => make\_inlined\_view::<1>(data),
         2 => make\_inlined\_view::<2>(data),
         3 => make\_inlined\_view::<3>(data),
         4 => make\_inlined\_view::<4>(data),
         5 => make\_inlined\_view::<5>(data),
         6 => make\_inlined\_view::<6>(data),
         7 => make\_inlined\_view::<7>(data),
         8 => make\_inlined\_view::<8>(data),
         9 => make\_inlined\_view::<9>(data),
         10 => make\_inlined\_view::<10>(data),
         11 => make\_inlined\_view::<11>(data),
         12 => make\_inlined\_view::<12>(data),
         _ => {
           // handle long string
}}}

第 2.4 节：端到端查询性能

在前面的章节中，我们特意确保加载 StringViewArray 比 StringArray 更快。在继续之前，我们想验证一下，对减少复制和函数调用的执着是否 वास्तव में 提高了实际查询中的端到端性能。为此，我们在 DataFusion 中评估了一个 ClickBench 查询 (Q20)，该查询统计了有多少 URL 包含单词 "google"。

 SELECT COUNT(*) FROM hits WHERE "URL" LIKE '%google%';

这是一个相对简单的查询；大部分时间都花在加载 “URL” 列以查找匹配的行上。查询计划如下所示：

 Projection: COUNT(*) [COUNT(*):Int64;N]
  Aggregate: groupBy=[[]], aggr=[[COUNT(*)]] [COUNT(*):Int64;N]
    Filter: hits.URL LIKE Utf8("%google%")
      TableScan: hits

我们像这样在 DataFusion 仓库中运行了基准测试：

cargo run --profile release-nonlto --bin dfbench -- clickbench --queries-path benchmarks/queries/clickbench/queries.sql --iterations 3 --query 20 --path benchmarks/data/hits.parquet --string-view

使用 StringViewArray，我们看到了 24% 的端到端性能提升，如图 7 所示。使用 –string-view 参数，端到端查询时间为 944.3 毫秒、869.6 毫秒、861.9 毫秒（三次迭代）。不使用 –string-view 参数，端到端查询时间为 1186.1 毫秒、1126.1 毫秒、1138.3 毫秒。 图 7：StringView 将 ClickBench Q20 的端到端查询时间缩短了 24%。

我们还通过详细的性能分析进行了二次检查，并验证了时间减少确实是由于 Parquet 加载速度更快造成的。

结论

在第一篇博文中，我们描述了如何提高仅使用 StringView 从 Parquet 文件读取字符串的性能。虽然这确实带来了端到端查询性能的提升，但在我们的下一篇文章中，我们将探讨 StringView 在 DataFusion 中实现的额外优化，以及我们在实现这些优化时遇到的一些陷阱。

注意：感谢 InfluxData 赞助这项工作作为暑期实习项目