使用 StringView / 德式字符串加速查询：第二部分 - 字符串操作

作者：Andrew Lamb / Xiangpeng Hao / 开发者
2024 年 9 月 3 日

导航至

第 3 节：更快的字符串操作

在第一篇博文中，我们讨论了使用 StringViewArray 加速 Parquet 加载所需的细微差别，通过重用缓冲区和减少复制。在本文的第二部分中，我们将描述剩余的旅程：为实际的查询处理实现额外的有效操作。

第 3.1 节 更快的比较

字符串比较无处不在；它是 cmp、min/max 和 like/ilike 内核的核心。StringViewArray 旨在通过内联前缀加速此类比较——关键的观察是，在许多情况下，只有字符串的前几个字节决定了字符串比较的结果。

例如，要比较字符串 InfluxDB 和 Apache DataFusion，我们只需要查看第一个字节即可确定字符串的顺序或相等性。在这种情况下，由于 A 在字母表中比 I 更靠前，因此 Apache DataFusion 排序在前，我们知道这两个字符串不相等。尽管只需要第一个字节，但当这些字符串存储为 StringArray 时，比较它们需要两次内存访问：1) 加载字符串偏移量，以及 2) 使用偏移量来定位字符串字节。对于诸如 cmp 之类的底层操作，这些操作在查询的热路径中被调用数百万次，避免这种额外的内存访问可以显着提高查询性能。

对于 StringViewArray，通常只需要一次内存访问即可加载 view 结构。只有当结果无法从前缀确定时，才需要第二次内存访问。对于上面的示例，不需要第二次访问。这种技术在实践中非常有效：对于超过 60% 的短于 12 字节的真实世界字符串，第二次访问永远是不必要的，因为它们完全存储在前缀中。

然而，操作字符串的函数必须专门化才能利用内联前缀。除了底层比较内核之外，我们还实现了 广泛的其他 StringViewArray 操作，涵盖了 ClickBench 查询中看到的函数和操作。在所有字符串操作中支持 StringViewArray 需要付出相当大的努力，值得庆幸的是，Arrow 和 DataFusion 社区已经在努力这样做了（如果您想提供帮助，请参阅 https://github.com/apache/datafusion/issues/11752）。

第 3.2 节：更快的 take 和 filter

在诸如 WHERE url <> ‘’ 之类的过滤器操作之后，为了避免处理空 url，DataFusion 通常会合并结果以形成一个仅包含通过元素的新的数组。这种合并确保批次大小足够大，可以从后续步骤中的 向量化处理中受益。

合并操作是使用 arrow-rs 中的 take 和 filter 内核实现的。对于 StringArray，这些内核需要将字符串内容复制到新的缓冲区，而缓冲区之间没有“空洞”。这种复制可能很昂贵，尤其是在新数组很大时。

然而，StringViewArray 的 take 和 filter 可以通过重用旧数组中的缓冲区来避免复制。内核只需要创建一个新的 view 列表，这些列表指向旧缓冲区中相同的字符串。图 1 说明了两种字符串表示形式的输出之间的差异。StringArray 创建了两个新的字符串，偏移量分别为 0-17 和 17-32，而 StringViewArray 只是简单地指向偏移量分别为 0 和 25 的原始缓冲区。 图 1：StringViewArray 的零拷贝 take/filter

第 3.3 节：何时进行 GC？

零拷贝 take/filter 非常适合快速生成大型数组，但对于高选择性过滤器来说，它不是最优的，因为大多数字符串都被过滤掉了。当基数下降时，StringViewArray 缓冲区变得稀疏——缓冲区内存中只有一小部分字节被任何 view 引用。这会导致过多的内存使用，尤其是在 先过滤后合并的场景中。例如，一个包含 10M 个字符串的 StringViewArray 在经过一些过滤器操作后可能只引用 1M 个字符串；然而，由于零拷贝 take/filter，（重用的）10M 缓冲区无法被释放/重用。

为了释放未使用的内存，我们实现了一个 垃圾回收 (GC) 例程，将数据整合到新的缓冲区中，以释放旧的稀疏缓冲区。由于 GC 操作会复制字符串，类似于 StringArray，因此我们必须小心何时调用它。如果我们过早调用 GC，我们会导致不必要的复制，从而失去 StringViewArray 的大部分好处。如果我们过晚调用 GC，我们会长时间持有大型缓冲区，从而增加内存使用量并降低缓存效率。Polars 博客关于 StringView 的文章也提到了垃圾回收时机带来的挑战。

arrow-rs 实现了 GC 过程，但由用户决定何时调用它。我们利用查询引擎的语义，并观察到 CoalseceBatchesExec 运算符（它将较小的批次合并为较大的批次）通常在记录基数预计会缩小时使用，这与 StringViewArray 中的 GC 场景完美契合。因此，我们在 CoalseceBatchesExec1 中实现了 GC 过程，并使用启发式方法来估计缓冲区何时过于稀疏。

第 3.4 节：函数内联的艺术：不多不少

与字符串内联类似，函数内联是将短函数嵌入到调用者中，以避免函数调用（调用者/被调用者保存）的开销的过程。通常，Rust 编译器在决定何时内联方面做得很好。但是，可以使用 #[inline(always)]指令覆盖其默认设置。在性能关键型代码中，内联代码允许我们将大型函数组织成较小的函数，而无需支付函数调用的运行时成本。

但是，函数内联并不总是更好，因为它会导致更大的函数体，这使得 LLVM 更难优化（例如，次优的 寄存器溢出），并且有溢出 CPU 指令缓存的风险。我们观察到一些性能回归，其中函数内联在实现 StringViewArray 比较内核时导致性能更慢。需要仔细检查和调整代码，以帮助编译器生成高效的代码。更多详细信息可以在此 PR 中找到：https://github.com/apache/arrow-rs/pull/5900。

第 3.5 节：缓冲区大小调整

StringViewArray 允许使用多个缓冲区，这实现了灵活的缓冲区布局，并可能减少复制数据的需要。然而，大量的缓冲区会降低其他操作的性能。例如，get_array_memory_size() 需要对每个缓冲区的内存大小求和，这在有数千个小缓冲区的情况下会花费很长时间。在某些情况下，我们发现多次调用 concat_batches 会导致数组包含数百万个缓冲区，这是非常昂贵的。

例如，考虑一个 StringViewArray，其之前的默认缓冲区大小为 8 KB。使用此配置，保存 4GB 的字符串数据需要近 50 万个缓冲区！较大的数组需要较大的缓冲区大小，但我们不能随意增加默认缓冲区大小，因为小数组会占用过多的内存（大多数数组至少需要一个缓冲区）。缓冲区大小调整在查询处理中尤其成问题，因为我们经常需要构建小批量的字符串数组，并且大小在规划时是未知的。

为了平衡缓冲区大小的权衡，我们再次利用查询处理 (DataFusion) 语义来决定何时使用更大的缓冲区。在合并批次时，我们将多个小的字符串数组组合在一起，并设置较小的缓冲区大小以保持总内存消耗较低。在字符串聚合中，我们聚合整个 Datafusion 分区，这可能会生成大量的字符串，因此我们设置了更大的缓冲区大小 (2MB)。

为了帮助处理语义未知的情况，我们还实现了一个经典的动态指数缓冲区大小增长策略，该策略以较小的缓冲区大小 (8KB) 开始，并将每个新缓冲区的大小加倍，最大可达 2MB。我们在 arrow-rs 中实现了这个策略，并默认启用它，以便 StringViewArray 的其他用户也可以从这个优化中受益。有关更多详细信息，请参阅此问题：https://github.com/apache/arrow-rs/issues/6094。

第 3.6 节：端到端查询性能

我们在优化 StringViewArray 过滤操作方面取得了重大进展。现在，让我们在真实世界中测试它，看看它的效果如何！

让我们考虑 ClickBench 查询 22，它选择多个字符串字段（URL、Title 和 SearchPhase）并应用多个过滤器。

SELECT 
  "SearchPhrase", 
  MIN("URL"), MIN("Title"), COUNT(\*) AS c, COUNT(DISTINCT "UserID") 
FROM hits 
WHERE 
  "Title" LIKE '%Google%' AND 
  "URL" NOT LIKE '%.google.%' AND 
  "SearchPhrase" <> '' 
GROUP BY "SearchPhrase" 
ORDER BY c DESC 
LIMIT 10;

我们使用 DataFusion 代码库中的以下命令运行了基准测试。同样，–string-view 选项表示我们使用 StringViewArray 而不是 StringArray。

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

为了消除使用 StringViewArray 加速 Parquet 读取的影响（请参阅本博客的第一部分），图 2 仅绘制了在 FilterExec 中花费的时间。在没有 StringViewArray 的情况下，过滤器耗时 7.17 秒；使用 StringViewArray 后，过滤器仅耗时 4.86 秒，时间减少了 32%。此外，我们看到端到端查询性能提高了 17%。 图 2：StringViewArray 将 ClickBench 查询 22 的过滤时间减少了 32%。

第 4 节：更快的字符串聚合

到目前为止，我们已经讨论了如何利用 StringViewArray 的两个特性：减少复制和更快的过滤。本节重点介绍重用字符串字节来重复字符串值。

正如本博客的第一部分所述，如果两个字符串具有相同的值，则 StringViewArray 可以使用两个不同的 view 指向相同的缓冲区范围，从而避免在缓冲区中重复字符串字节。这使得 StringViewArray 类似于存储字符串的 Arrow DictionaryArray——两种数组类型都非常适合只有少数不同值的字符串。

重复数据删除字符串值可以显着减少 StringViewArray 中的内存消耗。然而，此过程开销很大，涉及散列每个字符串并维护散列表，因此在创建 StringViewArray 时不能默认执行此操作。我们在 arrow-rs 中为高级用户引入了选择性字符串重复数据删除模式，这些用户知道他们的数据只有少数不同的值，并且减少内存消耗的好处超过了数组构建的额外开销。

我们再次利用 DataFusion 查询语义来识别具有重复值的 StringViewArray，例如具有多个分组键的聚合查询。例如，一些 ClickBench 查询按两列分组

  • UserID（接近 100 万个不同值的整数）
  • MobilePhoneModel（少于一百个不同值的字符串）

在这种情况下，输出行数为 count(distinct UserID) * count(distinct MobilePhoneModel，即 1 亿。MobilePhoneModel 的每个字符串值重复 100 万次。使用 StringViewArray，我们可以通过将重复的值指向相同的底层缓冲区来节省空间。

使用 StringView 加速字符串聚合是 改进 DataFusion 聚合性能的更大项目的一部分。我们有一个使用 StringView 的 概念验证实现，可以将多列字符串聚合提高 20%。我们非常希望得到您的帮助，使其达到生产就绪状态！

第 5 节：StringView 的陷阱

大多数现有的博客文章（包括这篇）都侧重于使用 StringViewArray 相对于其他字符串表示形式（如 StringArray）的好处。正如我们所讨论的，即使实现它需要大量的工程投入，但在许多情况下，StringViewArray 仍然是对 StringArray 的重大改进。

然而，在某些情况下，StringViewArray 比 StringArray 慢。为了完整起见，我们在此列出了这些情况

  1. 小字符串（当字符串短于 8 字节时）：StringViewArray 的每个元素至少消耗 16 字节的内存——view 结构的大小。对于小字符串数组，StringViewArray 比 StringArray 消耗更多内存，因此可能由于 CPU 缓存上额外的内存压力而导致性能降低。
  2. 大量重复的短字符串：与第一点类似，StringViewArray 可能比 DictionaryArray 慢并且需要更多内存，因为 1) 只有当字符串长度超过 12 字节时，它才能重用缓冲区中的字节，并且 2) 始终使用 32 位偏移量，即使较小的尺寸（8 位或 16 位）也可以表示所有不同的值。
  3. 过滤： 正如我们上面提到的，StringViewArray 通常比相应的 StringArray 消耗更多内存，并且在没有 GC 的情况下，内存膨胀会迅速占据性能主导地位。然而，调用 GC 也会减少减少复制带来的好处，因此必须仔细调整。

第 6 节：结论与总结

在这两篇博文中，我们讨论了在 arrow-rs 中实现 StringViewArray 然后将其集成到 DataFusion 中需要做些什么。我们对 ClickBench 查询的评估表明，StringView 可以将字符串密集型工作负载的性能提高高达 2 倍。

鉴于 DataFusion 已经在 ClickBench 上表现非常出色，使用 StringViewArray 实现的端到端性能提升展示了这项技术的强大之处，当然，这对 DataFusion 以及构建在其之上的系统来说都是一个胜利。

StringView 是一个大型项目，受到了社区的巨大支持。 特别是，我们要感谢 @tustvold、@ariesdevil、@RinChanNOWWW、@ClSlaid、@2010YOUY01、@chloro-pn、@a10y、@Kev1n8、@Weijun-H、@PsiACE、@tshauck 和 @xinlifoobar 的宝贵贡献！

正如引言所述，“德式字符串”是一个相对简单的研究想法，它可以避免一些字符串复制并加速比较。 然而，在实践中应用这个（伟大的）想法需要在认真的软件工程方面进行大量投入。 再次，我们鼓励研究界继续帮助将研究想法应用于工业系统（例如 DataFusion），因为这样做在评估未来研究问题以获得最大潜在影响时提供了宝贵的视角。

  1. 此操作中还有其他可能的优化，社区正在努力，例如 https://github.com/apache/datafusion/issues/7957。