• 数据库
• OLAP
• 嵌入式数据库
• 数据分析

DuckDB 的benchmark/recursive_cte目录是一组专门用于回归验证递归查询正确性与性能的研究型基准，其中flummi子目录引入了一类与众不同的负载：由 Flummi 编译器把命令式程序自动编译为递归 CTE的生成式查询。本文以 flummi/README.md 为主线，结合基准模板、加载数据、顶层 benchmark 定义与test/sql/cte/recursive_cte_flummi.test_slow回归测试，完整剖析这套工作负载的来龙去脉、运行方式与验证方法，帮助你理解 DuckDB 递归 CTE 引擎在面对任意控制流时的真实压力形态。

一、背景：Flummi 把命令式程序编译成递归 CTE

Flummi（上游仓库 DBatUTuebingen/flummi，本套件固定在其提交5d979a526f65fcaf838003b5b7b5c189d35325f4）的核心思想是：将命令式程序的控制流表示为一条递归 CTE。生成出的查询会在递归状态中同时携带：

• 程序计数器（program counter）：当前执行到哪一条指令；
• 控制流标签（control-flow label）：分支、循环、函数调用的去向标记；
• 发射值（emitted values）：程序print等输出动作产生的值；
• 存活程序变量（live program variables）：当前仍然被后续指令读取的变量集合。

这意味着每轮递归迭代相当于"执行一条指令"，递归终止即程序结束。从 父目录 README 的描述可知，这套生成式负载刻意与同目录下"算法特定"的手写递归负载形成互补：它锻炼的是 DuckDB 递归引擎对通用、任意、控制流密集程序的承载能力，而不是针对某个特定算法手写的递归形态。

二、与USING KEY工作负载的区别：不同的递归计划形态

benchmark/recursive_cte目录中的其他工作负载（BFS、Bellman-Ford、连通分量、DVR、Game of Life、k-means、PageRank、Kruskal）均以当前 DuckDB 的USING KEY ... UNION ALL语法手写而成，它们直接利用"重复访问同一张经常更新的递归状态表"这一访问模式。而 Flummi 负载则完全不同：

• 计划形态由编译器决定，DuckDB 只能"被动接受"生成的递归结构；
• 程序计数器 + 标签驱动的迭代方式会产生逐行推进、小步迭代的递归形状，而非算法特有的"frontier 扩散"形状；
• 部分工作负载（如flummi_k_core_using_key）提供了同算法的 Flummi 生成版与手写USING KEY版，可用来直接对比两种计划形态的差异。

这种互补性正是该套件被收编进recursive_cte基准组的价值所在。

三、目录结构与负载清单

benchmark/recursive_cte/ ├── flummi/ │ ├── README.md # 本主题文档 │ ├── recursive_cte_flummi.benchmark.in # 基准模板（模板化参数） │ └── load/ # 确定性加载数据 │ ├── ray.sql # 光线追踪场景：三角形 + 球体 │ ├── kmeans.sql │ ├── community_detection.sql │ ├── connected_components.sql │ └── k_core_using_key.sql ├── queries/ │ ├── smoke/ # 小型冒烟查询（保留小演示输入） │ │ ├── flummi_counter.sql │ │ ├── flummi_bfs.sql │ │ ├── flummi_k_core.sql │ │ └── flummi_paths.sql │ └── performance/ # 规模化性能查询 │ ├── flummi_community_detection.sql │ ├── flummi_connected_components.sql │ ├── flummi_generations.sql │ ├── flummi_k_core_using_key.sql │ ├── flummi_kmeans.sql │ ├── flummi_life.sql │ └── flummi_ray.sql ├── answers/performance/ # 期望结果 CSV ├── flummi_ray.benchmark # 顶层基准定义（7 个 flummi_*.benchmark） ├── flummi_kmeans.benchmark ├── flummi_life.benchmark ├── flummi_generations.benchmark ├── flummi_community_detection.benchmark ├── flummi_connected_components.benchmark └── flummi_k_core_using_key.benchmark

按 flummi/README.md 的说明，适配后的生成式 SQL 直接以源文件形式提交在queries/smoke与queries/performance下（对应仓库路径为 benchmark/recursive_cte/queries/smoke 与 benchmark/recursive_cte/queries/performance），因此运行 DuckDB 测试不需要安装 Flummi 编译器。上游提交只用来固定原始输入数据的出处。

四、基准模板：recursive_cte_flummi.benchmark.in解析

所有flummi_*.benchmark顶层文件都指向同一个模板 recursive_cte_flummi.benchmark.in，其结构为：

# name: ${FILE_PATH} # description: ${DESCRIPTION} # group: [recursive_cte] name ${BENCHMARK_NAME} group Recursive CTE load benchmark/recursive_cte/flummi/load/${LOAD}.sql run benchmark/recursive_cte/queries/performance/${QUERY}.sql result benchmark/recursive_cte/answers/performance/${QUERY}.csv

四个参数的含义：

模板的group Recursive CTE将其归入递归 CTE 基准组，result行指明答案文件位置用于结果校验。例如 flummi_ray.benchmark 的完整定义如下：

# name: benchmark/recursive_cte/flummi_ray.benchmark # group: [recursive_cte] template benchmark/recursive_cte/flummi/recursive_cte_flummi.benchmark.in LOAD=ray QUERY=flummi_ray BENCHMARK_NAME=Flummi recursive ray tracer DESCRIPTION=Render a deterministic 384 by 240 image with Flummi's generated ray tracer

同理，flummi_kmeans.benchmark 定义为Run Flummi's generated k-means program over deterministic points，flummi_life.benchmark 则复用父目录的recursive_cte.benchmark.in模板（TIER=performance、QUERY=flummi_life）。

五、工作负载详解：从计数器到光线追踪

5.1 Counter：最小控制流程序

flummi_counter.sql是最小规模的冒烟示例，用于验证"程序计数器推进"这一基本机制。在 recursive_cte_flummi.test_slow 中通过read_text读取后执行，期望输出为：

10 0 9 45

5.2 BFS：含不可达节点与环

flummi_bfs.sql运行在 8 节点、含不可达节点（节点 8）与环的图上，图数据由测试内联构造（edges同时插入反向边以构成无向图），期望输出：

8 5 3 7

5.3 k-core

冒烟版flummi_k_core.sql的场景是"保留一个 K4 完全子图、剔除一个两节点分量"：6 个节点中 1–4 构成 K4，5–6 是孤立边。期望输出4 1 4 10，即核心大小为 4、起始标签 1、存活节点 4、发射值 10。

5.4 Paths：有向无环图上的全对最短路径

flummi_paths.sql在一张 6 节点、带边权重的 DAG 上运行，输出为两列数值加一列结果校验 MD5：

15 50 baae867701af8a4d31a49c9a7e7d98da

5.5 Community detection（社区发现）

性能版flummi_community_detection.sql使用 load/community_detection.sql 生成的 10000 节点、每人两条边的确定性数据，期望输出：

9200 10000 49995000

5.6 Connected components（连通分量）

性能版flummi_connected_components.sql的数据由100 个分量 × 100 层的规则网格构成（约 1 万节点），期望输出：

700 9900 244650

该负载还被用来验证高线程数下的 frontier 并行度：测试用 120000 节点 / 60000 条边、SET threads=32，并通过enable_logging('PhysicalOperator', storage='memory')+duckdb_logs_parsed断言PhysicalRecursiveCTE的scheduled_tasks > scheduled_workers（即确实存在可摊薄的多 worker 任务），期望输出：

60000 60000 3599940000

5.7 k-means

flummi_kmeans.sql对 2000 个确定性生成的点执行递归 k-means，期望输出包含簇数、点数、两个质心坐标及计数：

2 2000 1007.055603 999.141113 985 1015

5.8 k-coreUSING KEY对比版

flummi_k_core_using_key.sql在 50 份拷贝 × 16 节点的数据上运行，测试同时以SET threads=1与SET threads=4执行并要求结果一致：

500 1 794 198750

随后用PRAGMA explain_output='physical_only'+EXPLAIN断言物理计划中出现RECURSIVE_KEY_JOIN——这是对"生成式递归与USING KEY优化能够协同工作"的直接证据：

physical_plan <REGEX>:.*RECURSIVE_KEY_JOIN.*

5.9 Generations：元胞自动机

flummi_generations.sql原始参数为50 × 50 × 50，测试中通过 SQLreplace()把height/width/iterations缩减为10 × 10 × 10（小向量构建时）以控制运行时间，输出以行数 + 字节数 + MD5 校验：

22 1308 5998b31dc0f1b502e94fb79edb15ecb5

该负载还覆盖了两条并行度断言：小输入下scheduled_workers = epochs可接受（无多余并行浪费）；规模化输入下scheduled_workers > epochs必须成立（物化扇出值得占用两个以上 worker）。测试用current_setting('standard_vector_size')区分小向量（<1024）与常规构建，分别校验output_bytes（476 / 10396）与output_md5（bd8910442ccf5092381413e278421dd0/b219e422e83fc2ca892f7edeb1a22c00）。

5.10 Conway's Game of Life

flummi_life.sql在SET threads=2下执行，输出：

202 12019 5d5cfdb73d7bc1caf12a5af0ce64a033

5.11 Ray tracer：光线追踪

flummi_ray.sql是本套件中最具分量的负载。按 README 说明，它保留了阴影（shadows）、反射深度（reflection depth）与原始球体场景，但把渲染分辨率从上游的3480 × 2160降为384 × 240，并配套在 flummi_ray.benchmark 中给出描述Render a deterministic 384 by 240 image with Flummi's generated ray tracer。

场景数据在 load/ray.sql 中：6 个三角形（含两面墙、地面、左右墙面与背墙）与 4 个球体（一个光源'l'、两个反射球'r'、一个材质球'm'），每个对象带 RGB 颜色、中心/顶点坐标与半径。Release 构建的基准会校验渲染结果的图像长度与校验和。

README 特别指出：生成的 ray 查询故意不纳入 RelDebug SQLLogicTest（即test_slow回归测试）——即使把渲染图像进一步缩小，仅绑定（binding）与优化（optimizing）这条约 5800 行的递归计划就需要大约两分钟。这从侧面说明：编译器生成的"大而扁"的递归计划是 DuckDB 优化器需要面对的真实压力场景。其余选中的程序则全部在test_slow中有缩放的正确性覆盖。

六、适配原则：可复现、可校验、规模可控

综合 README 与测试代码，所有 Flummi 负载都遵循三条适配准则：

1. 确定性输入：把上游示例中的随机输入替换为确定性数据（如 k-means 用(i * 37) % 1000 + (i % 7) * 0.1这类纯函数公式生成坐标；社区发现用node.id // 50分块构造边）；
2. 规模裁剪：把超大的示例缩小到 CI 可承受的量级（光线追踪 384×240、元胞自动机 10×10×10、连通分量按 100 层分块），同时保留原始访问模式；
3. 紧凑结果校验：查询最终只返回少量聚合值或行数 + 字节数 + MD5，便于在 answers/performance 中用 CSV 答案文件做精确比对。

由于生成式 SQL 已静态提交，任何人无需安装 Flummi 即可复现全部结果。

七、构建与运行方式

按 recursive_cte/README.md 的说明，构建并运行解释型基准：

BUILD_BENCHMARK=1 make release build/release/benchmark/benchmark_runner "benchmark/recursive_cte/.*"

其中BUILD_BENCHMARK=1使构建系统编译benchmark/benchmark_runner（见 benchmark/benchmark_runner.cpp 与 benchmark/include/interpreted_benchmark.hpp），正则"benchmark/recursive_cte/.*"会匹配全部递归 CTE 基准（包括 7 个flummi_*.benchmark）。load阶段执行对应load/*.sql，run阶段执行queries/performance/*.sql，result阶段与answers/performance/*.csv对比。

八、正确性回归测试：recursive_cte_flummi.test_slow

test/sql/cte/recursive_cte_flummi.test_slow 是这套负载的"官方测试化"形态，其运行手法很值得借鉴：

1. 读取 SQL：用read_text把.sql文件内容读入变量，再以query(getvariable('flummi_sql'))动态执行，避免了把巨型查询硬编码进测试：

   SET VARIABLE flummi_sql = (SELECT content FROM read_text('benchmark/recursive_cte/queries/performance/flummi_kmeans.sql')); SELECT * FROM query(getvariable('flummi_sql'));

2. 约束运行时间：SET max_execution_time=30000;（30 秒上限）与SET threads=4;，避免失控查询拖垮 CI；
3. 断言结果：query IIII等语句直接比对期望输出；大输出则比对output_md5；
4. 运行时度量：通过CALL enable_logging('PhysicalOperator', storage='memory')与duckdb_logs_parsed('PhysicalOperator')检查PhysicalRecursiveCTE的RuntimeMetrics（scheduled_tasks、scheduled_workers、epochs），把"并行度是否被有效利用"也变成可断言的正确性属性。

这也呼应了源码层面的实现事实：DuckDB 的递归 CTE 由物理算子PhysicalRecursiveCTE驱动（测试中duckdb_logs_parsed的class = 'PhysicalRecursiveCTE'），而USING KEY变体对应物理计划中的RECURSIVE_KEY_JOIN；standard_vector_size分支则表明递归执行与向量化宽度（Vector大小，默认 2048）直接相关——小向量配置下任务粒度变细，并行度断言会自动放宽。

九、总结

Flummi 工作负载为 DuckDB 的递归查询验证体系补齐了"编译器生成、控制流密集"这一重要维度：既有 5 个确定性加载脚本和 11 个生成式查询（counter / bfs / k-core / paths / community detection / connected components / k-means / k-core-using-key / generations / life / ray），又有模板化 benchmark 定义、CSV 答案校验和 SQLLogicTest 回归覆盖。它证明 DuckDB 不仅能高效执行手写算法级递归（USING KEY形态），也能以确定、可校验的方式承载任意命令式程序经控制流编译而来的递归计划——包括那条需要两分钟才能完成绑定与优化的 5800 行光线追踪计划。

如需深入，建议从 flummi/README.md 出发，依次阅读 recursive_cte_flummi.benchmark.in、load/ray.sql、flummi_ray.benchmark 与 recursive_cte_flummi.test_slow，即可完整还原这套负载从数据、查询、基准到回归测试的闭环。

• 数据库
• OLAP
• 嵌入式数据库
• 数据分析