DuckDB的递归CTE性能改进

来源https://github.com/duckdb/duckdb/pull/22211优化递归 CTE 性能 #22211作者:kryonix我终于能够分享这个 PR拉取请求了我感到非常兴奋。说实话我想实现这个功能已经好几年了但一直没时间真正去做。高效执行递归 CTE公共表表达式并不是很多人会思考或关心的事情因此相关的研究很少而且优秀的开源实现基本上也不存在。然而我花在这上面的时间多到我自己都不想承认并把我最好的见解和想法都整合到了这个 PR 中。递归 CTE 执行成本很高因为当前的实现虽然简单但缺乏优化。其执行的基本原理出奇地简单基于半朴素semi-naive评估策略。然而简单之处到此为止性能、并行化和优化才刚拉开序幕。DuckDB 的主要瓶颈在于对于 CTE 的递归部分每次递归迭代都会创建、调度、执行和销毁所有管道pipeline。这极其昂贵也是递归 CTE 执行缓慢的主要原因尤其是当递归部分操作的数据量很小的时候。在这种情况下创建和销毁管道的开销主导了执行时间并且无法很好地分摊。主要瓶颈如下每次递归 CTE 迭代都涉及管道的创建和销毁。对 CTE 递归部分采用静态且过度并行的执行方式当递归部分处理少量数据时无法高效执行。在递归 CTE 的各个迭代之间不复用任何执行状态导致冗余工作和额外开销。这个 PR 通过引入一种新的递归 CTE 执行策略来解决这些瓶颈从而实现更高效的执行。主要更改包括现在线程数会根据正在处理的数据大小动态确定从而允许在递归部分跨迭代处理不同数据量时实现更高效的执行。由于我们可以完美地估计递归工作表的基数因此可以用它来确定每次递归 CTE 迭代的最佳线程数从而在并行执行无益时避免其开销并在有益时使用更多线程。现在执行状态会在递归 CTE 的各个迭代之间复用从而减少了冗余工作和开销。如果在 CTE 的递归部分使用了 HashJoin 运算符这种复用尤其高效因为它可以在迭代之间复用哈希表。现在规划器Planner会尽可能将 CTE 的递归部分放在 HashJoin 的 PROBE探测侧以利用哈希表复用的优化。物理运算符现在有了Reset()方法允许在不销毁和重新创建运算符的情况下重置其状态。此方法用于在迭代之间重置 CTE 递归部分中运算符的状态。PhysicalRecursiveCTE运算符现在在 CTE 的各个迭代之间复用了更多的数据结构从而减少了开销和冗余工作。这方面的例子包括工作表的ColumnDataCollection、DataChunk对象和PipelineExecutor对象。我们跟踪哪些管道在递归 CTE 的各个迭代之间是不变的并且仅在必要时重置这些管道的状态。对于本质上是单线程的递归 CTE现在有一种特殊的执行策略可以在单线程中执行 CTE 的递归部分从而在无益时避免并行执行和通用调度的开销。所有这些改进共同带来了显著的性能提升。但另一方面实现变得明显更加复杂例如因为我们必须为 CTE 的递归部分实现自定义调度逻辑并且必须小心处理跨迭代的运算符和管道状态的重置。另外也是让这个 PR 变得如此庞大的原因是我们必须为物理运算符添加大量的新Reset()方法。然而如果遇到任何不支持重置的运算符我们会回退到完全重置这使实现更加健壮和面向未来因为当添加新的运算符时我们总能为其添加重置支持。所有这些也适用于USING KEY变体的递归 CTE因为两者共享相同的执行引擎和策略。速度有多快性能提升是显著的。不幸的是目前还没有标准化的递归 CTE 基准测试但是 neumannt 实现了一套很棒的 Advent of Code编程挑战谜题这些谜题使用了递归 CTE可以用来衡量递归 CTE 的性能。https://github.com/neumannt/aoc24Day此 PR 与 DuckDB 主分支相比的加速比012.04 倍022.02 倍033.23 倍041.05 倍051.22 倍064.80 倍071.16 倍081.13 倍091.38 倍101.17 倍111.49 倍121.19 倍132.17 倍148.08 倍155.65 倍181.86 倍193.07 倍2011.25 倍212.66 倍231.99 倍252.51 倍如您所见某些查询的性能提升显著高达 11 倍而有些查询则没有那么大的提升。但没有性能回退总体而言递归 CTE 的性能得到了全面显著提升。此外由于多线程的工作方式查询的运行时间现在在不同运行之间更加稳定这是一个不错的改进。一个典型但没实际意义的递归 CTE 基准测试查询如下WITHRECURSIVE cteAS(SELECT1ASnUNIONALLSELECTn1FROMcteWHEREn1000000)SELECT*FROMcte;这通常被认为是 DuckDB 中递归 CTE 的最坏情况因为递归部分只操作单行这完全打乱了 DuckDB 的执行引擎。尽管如此此 PR 将性能提升了大约 25 倍。另一个最坏情况的查询是这个线性图查询DROPTABLEIFEXISTSgraph;CREATETABLEgraph(hereINTEGER,thereINTEGER);-- 1 - 2 - ... - 100000INSERTINTOgraphSELECTi,i1FROMgenerate_series(0,100000)g1(i);WITHRECURSIVE cteAS(SELECThere,thereFROMgraphWHEREhere0UNIONALLSELECTg.here,g.thereFROMgraph gJOINcteONcte.thereg.here)SELECT*FROMcte;对于递归 CTE 来说这个查询同样是最坏情况因为这里的递归部分同样只操作单行。然而可能更糟糕的是graph表在递归 CTE 的每次迭代中都被完全扫描使得graph g JOIN cte ON cte.there g.here这部分执行成本非常高昂。通过这个 PR性能得到了巨大提升大约 100 倍但您实际上可以通过改变graph表中的行数来选择这个倍数。对于此类查询能够在迭代之间复用在graph表上构建的哈希表是一个改变游戏规则的因素因为它允许我们只扫描graph表一次然后用每次迭代产生的新行持续进行探测。这是递归 CTE 中一种非常常见的模式而这个 PR 正是针对这种模式进行了优化。这应该会使递归 CTE 在图查询中更加实用而图查询正是递归 CTE 的一个常见用例。