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/aoc24）
| Day | 此 PR 与 DuckDB 主分支相比的加速比 |
|---|---|
| 01 | 2.04 倍 |
| 02 | 2.02 倍 |
| 03 | 3.23 倍 |
| 04 | 1.05 倍 |
| 05 | 1.22 倍 |
| 06 | 4.80 倍 |
| 07 | 1.16 倍 |
| 08 | 1.13 倍 |
| 09 | 1.38 倍 |
| 10 | 1.17 倍 |
| 11 | 1.49 倍 |
| 12 | 1.19 倍 |
| 13 | 2.17 倍 |
| 14 | 8.08 倍 |
| 15 | 5.65 倍 |
| 18 | 1.86 倍 |
| 19 | 3.07 倍 |
| 20 | 11.25 倍 |
| 21 | 2.66 倍 |
| 23 | 1.99 倍 |
| 25 | 2.51 倍 |
如您所见，某些查询的性能提升显著（高达 11 倍），而有些查询则没有（那么）大的提升。但没有性能回退，总体而言，递归 CTE 的性能得到了全面显著提升。此外，由于多线程的工作方式，查询的运行时间现在在不同运行之间更加稳定，这是一个不错的改进。
一个典型（但没实际意义）的递归 CTE "基准测试"查询如下：
WITHRECURSIVE cteAS(SELECT1ASnUNIONALLSELECTn+1FROMcteWHEREn<1000000)SELECT*FROMcte;这通常被认为是 DuckDB 中递归 CTE 的最坏情况，因为递归部分只操作单行，这完全打乱了 DuckDB 的执行引擎。尽管如此，此 PR 将性能提升了大约 25 倍。
另一个最坏情况的查询是这个"线性图"查询：
DROPTABLEIFEXISTSgraph;CREATETABLEgraph(hereINTEGER,thereINTEGER);-- 1 -> 2 -> ... -> 100000INSERTINTOgraphSELECTi,i+1FROMgenerate_series(0,100000)g1(i);WITHRECURSIVE cteAS(SELECThere,thereFROMgraphWHEREhere=0UNIONALLSELECTg.here,g.thereFROMgraph gJOINcteONcte.there=g.here)SELECT*FROMcte;对于递归 CTE 来说，这个查询同样是最坏情况，因为这里的递归部分同样只操作单行。然而，可能更糟糕的是，graph表在递归 CTE 的每次迭代中都被（完全）扫描，使得graph g JOIN cte ON cte.there = g.here这部分执行成本非常高昂。通过这个 PR，性能得到了巨大提升，大约 100 倍（但您实际上可以通过改变graph表中的行数来选择这个倍数）。对于此类查询，能够在迭代之间复用在graph表上构建的哈希表是一个改变游戏规则的因素，因为它允许我们只扫描graph表一次，然后用每次迭代产生的新行持续进行探测。这是递归 CTE 中一种非常常见的模式，而这个 PR 正是针对这种模式进行了优化。这应该会使递归 CTE 在图查询中更加实用，而图查询正是递归 CTE 的一个常见用例。