数据库OLAP嵌入式数据库数据分析【免费下载链接】duckdbDuckDB is an analytical in-process SQL database management system项目地址https://gitcode.com/GitHub_Trending/du/duckdb点击查看免费下载DuckDB 的benchmark/recursive_cte目录是一组专门用于回归验证递归查询正确性与性能的研究型基准其中flummi子目录引入了一类与众不同的负载由 Flummi 编译器把命令式程序自动编译为递归 CTE的生成式查询。本文以 flummi/README.md 为主线结合基准模板、加载数据、顶层 benchmark 定义与test/sql/cte/recursive_cte_flummi.test_slow回归测试完整剖析这套工作负载的来龙去脉、运行方式与验证方法帮助你理解 DuckDB 递归 CTE 引擎在面对任意控制流时的真实压力形态。一、背景Flummi 把命令式程序编译成递归 CTEFlummi上游仓库 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四个参数的含义参数作用示例取值flummi_ray.benchmark${LOAD}加载哪个数据脚本ray→load/ray.sql${QUERY}运行哪个性能查询flummi_ray→queries/performance/flummi_ray.sql${BENCHMARK_NAME}基准显示名称Flummi recursive ray tracer${DESCRIPTION}基准描述Render a deterministic 384 by 240 image with Flummis generated ray tracer模板的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 LOADray QUERYflummi_ray BENCHMARK_NAMEFlummi recursive ray tracer DESCRIPTIONRender a deterministic 384 by 240 image with Flummis generated ray tracer同理flummi_kmeans.benchmark 定义为Run Flummis generated k-means program over deterministic pointsflummi_life.benchmark 则复用父目录的recursive_cte.benchmark.in模板TIERperformance、QUERYflummi_life。五、工作负载详解从计数器到光线追踪5.1 Counter最小控制流程序flummi_counter.sql是最小规模的冒烟示例用于验证程序计数器推进这一基本机制。在 recursive_cte_flummi.test_slow 中通过read_text读取后执行期望输出为10 0 9 455.2 BFS含不可达节点与环flummi_bfs.sql运行在 8 节点、含不可达节点节点 8与环的图上图数据由测试内联构造edges同时插入反向边以构成无向图期望输出8 5 3 75.3 k-core冒烟版flummi_k_core.sql的场景是保留一个 K4 完全子图、剔除一个两节点分量6 个节点中 1–4 构成 K45–6 是孤立边。期望输出4 1 4 10即核心大小为 4、起始标签 1、存活节点 4、发射值 10。5.4 Paths有向无环图上的全对最短路径flummi_paths.sql在一张 6 节点、带边权重的 DAG 上运行输出为两列数值加一列结果校验 MD515 50 baae867701af8a4d31a49c9a7e7d98da5.5 Community detection社区发现性能版flummi_community_detection.sql使用 load/community_detection.sql 生成的 10000 节点、每人两条边的确定性数据期望输出9200 10000 499950005.6 Connected components连通分量性能版flummi_connected_components.sql的数据由100 个分量 × 100 层的规则网格构成约 1 万节点期望输出700 9900 244650该负载还被用来验证高线程数下的 frontier 并行度测试用 120000 节点 / 60000 条边、SET threads32并通过enable_logging(PhysicalOperator, storagememory)duckdb_logs_parsed断言PhysicalRecursiveCTE的scheduled_tasks scheduled_workers即确实存在可摊薄的多 worker 任务期望输出60000 60000 35999400005.7 k-meansflummi_kmeans.sql对 2000 个确定性生成的点执行递归 k-means期望输出包含簇数、点数、两个质心坐标及计数2 2000 1007.055603 999.141113 985 10155.8 k-coreUSING KEY对比版flummi_k_core_using_key.sql在 50 份拷贝 × 16 节点的数据上运行测试同时以SET threads1与SET threads4执行并要求结果一致500 1 794 198750随后用PRAGMA explain_outputphysical_onlyEXPLAIN断言物理计划中出现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_bytes476 / 10396与output_md5bd8910442ccf5092381413e278421dd0/b219e422e83fc2ca892f7edeb1a22c00。5.10 Conways Game of Lifeflummi_life.sql在SET threads2下执行输出202 12019 5d5cfdb73d7bc1caf12a5af0ce64a0335.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 Flummis 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 负载都遵循三条适配准则确定性输入把上游示例中的随机输入替换为确定性数据如 k-means 用(i * 37) % 1000 (i % 7) * 0.1这类纯函数公式生成坐标社区发现用node.id // 50分块构造边规模裁剪把超大的示例缩小到 CI 可承受的量级光线追踪 384×240、元胞自动机 10×10×10、连通分量按 100 层分块同时保留原始访问模式紧凑结果校验查询最终只返回少量聚合值或行数 字节数 MD5便于在 answers/performance 中用 CSV 答案文件做精确比对。由于生成式 SQL 已静态提交任何人无需安装 Flummi 即可复现全部结果。七、构建与运行方式按 recursive_cte/README.md 的说明构建并运行解释型基准BUILD_BENCHMARK1 make release build/release/benchmark/benchmark_runner benchmark/recursive_cte/.*其中BUILD_BENCHMARK1使构建系统编译benchmark/benchmark_runner见 benchmark/benchmark_runner.cpp 与 benchmark/include/interpreted_benchmark.hpp正则benchmark/recursive_cte/.*会匹配全部递归 CTE 基准包括 7 个flummi_*.benchmark。load阶段执行对应load/*.sqlrun阶段执行queries/performance/*.sqlresult阶段与answers/performance/*.csv对比。八、正确性回归测试recursive_cte_flummi.test_slowtest/sql/cte/recursive_cte_flummi.test_slow 是这套负载的官方测试化形态其运行手法很值得借鉴读取 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));约束运行时间SET max_execution_time30000;30 秒上限与SET threads4;避免失控查询拖垮 CI断言结果query IIII等语句直接比对期望输出大输出则比对output_md5运行时度量通过CALL enable_logging(PhysicalOperator, storagememory)与duckdb_logs_parsed(PhysicalOperator)检查PhysicalRecursiveCTE的RuntimeMetricsscheduled_tasks、scheduled_workers、epochs把并行度是否被有效利用也变成可断言的正确性属性。这也呼应了源码层面的实现事实DuckDB 的递归 CTE 由物理算子PhysicalRecursiveCTE驱动测试中duckdb_logs_parsed的class PhysicalRecursiveCTE而USING KEY变体对应物理计划中的RECURSIVE_KEY_JOINstandard_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嵌入式数据库数据分析【免费下载链接】duckdbDuckDB is an analytical in-process SQL database management system项目地址https://gitcode.com/GitHub_Trending/du/duckdb点击查看免费下载相关推荐BAML 递归调用性能基准解析compute::binary tree depth 20 工作负载BAML 递归调用性能基准解析compute::binary tree depth 20 工作负载 导读 本文围绕 BAML 仓库中 speedtest 基准编程语言AI Agent编译器CLI人工智能LangGraph递归控制处理复杂嵌套工作流的深度限制LangGraph递归控制处理复杂嵌套工作流的深度限制 引言为什么递归控制如此重要 在构建复杂的AI代理系统时我们经常会遇到需要处理嵌套工作流的情况。无人工智能AI AgentAgent 框架流程编排后端33-js-concepts递归算法递归思想与尾递归优化技术33 js concepts递归算法递归思想与尾递归优化技术 引言递归的魔力与挑战 你是否曾经遇到过这样的困境面对一个复杂的嵌套数据结构传统的循环方法显教程前端文档上一篇React Native Airbnb Clone底部导航栏与模态路由的完整实现方案下一篇angular-bootstrap-nav-tree实战案例构建多级分类导航菜单创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考