TiDB 公共表表达式CTE实现剖析物化方案的设计与执行全流程【免费下载链接】tidbTiDB is built for agentic workloads that grow unpredictably, with ACID guarantees and native support for transactions, analytics, and vector search. No data silos. No noisy neighbors. No infrastructure ceiling.项目地址: https://gitcode.com/GitHub_Trending/ti/tidb导读公共表表达式Common Table Expression简称 CTE是 SQL:1999 引入的标准特性允许用户在单条语句内定义可复用的临时结果集是编写层次查询如组织树、BOM 拆解和复杂分析 SQL 的核心工具。本篇文章以 TiDB 官方设计文档 docs/design/2021-04-18-common-table-expression.md 为主体结合 pkg/planner/core/operator/logicalop/logical_cte.go、pkg/executor/cte.go、pkg/executor/cte_table_reader.go、pkg/util/cteutil/storage.go 等实现源码完整讲解 TiDB 如何采用物化Materialization方式实现非递归与递归 CTE以及从解析、逻辑计划、物理计划到执行器的全生命周期。读完本文你将掌握 TiDB 中WITH/WITH RECURSIVE的语法语义、cte_max_recursion_depth与tidb_mem_quota_query等关键系统变量的作用、迭代执行与磁盘溢写原理并能据此排查递归查询性能与资源使用问题。一、CTE 是什么动机与核心优势1.1 CTE 的引入背景CTE 由 SQL:1999 标准引入它是在单条语句内部存在的临时结果集定义后可在同一条语句的后续位置反复引用。设计文档 docs/design/2021-04-18-common-table-expression.md 明确指出CTE 与派生表derived table有一定相似性但具备派生表无法比拟的三大优势可被多次引用同一个 CTE 可以在语句中多处使用且只计算一次可读性更好把复杂子查询拆成带名字的步骤SQL 结构更清晰可做层次查询通过递归 CTE 遍历树状/图状数据。1.2 非递归 CTE 示例非递归 CTE 本质是可命名的子查询多个 CTE 之间可以互相独立定义并在主查询中 JOINWITH cte1 AS (SELECT c1 FROM t1), cte2 AS (SELECT c2 FROM t2) SELECT cte1.c1, cte2.c2 FROM cte1, cte2 WHERE cte1.c1 cte2.c2 AND cte1.c1 100;1.3 递归 CTE 示例递归 CTE 用于层次查询通常由两部分组成Seed part种子部分产生初始数据Recursive part递归部分基于上一轮迭代结果继续计算直到不再产生新行为止。WITH RECURSIVE cte1 AS ( SELECT part, sub_part FROM t WHERE part human -- seed part UNION ALL SELECT t.part, t.sub_part FROM t, cte1 WHERE cte1.sub_part t.part -- recursive part ) SELECT * FROM cte1;该语句典型应用于 BOM物料清单展开、组织架构树、地铁换乘等场景从根节点human出发逐层向下遍历。二、总体设计为什么选择 Materialization 而非 Merge2.1 两种主流实现方案对比设计文档将 CTE 的实现路线归纳为两种这也是主流数据库的共同选择实现方式思路优点局限Merge合并/内联展开类似视图将 CTE 定义原地展开到每个引用处优化器可把外层谓词下推到内层查询CTE 被多次引用时会产生重复计算Materialization物化用临时存储保存 CTE 计算结果引用时直接读取多次引用只物化一次递归 CTE 只能由此实现无法天然做谓词下推可能引入物化开销设计文档给出的选型结论是Merge在大多数场景下更优谓词可下推但当同一个 CTE 被多次引用时Materialization占优而递归 CTE 在架构上只能通过Materialization实现因为每一轮迭代都需要把上一轮输出作为下一轮输入反复读取。2.2 TiDB 的取舍一期只做 Materialization为了降低实现复杂度和 bug 概率TiDB 第一版对非递归与递归 CTE 统一采用Materialization暂不在两种方式间做运行时选择。设计文档将Merge及merge/no_merge提示列入 Future Work详见下文未来工作。这也意味着在一期实现中非递归 CTE 也存在物化开销设计文档在Impacts Risks中对此有明确说明。物化方案带来的最大红利是无论同一个 CTE 被引用多少次底层数据只物化一次。因此执行器层通过一张 map 记录所有引用同一 CTE 的子计划确保这些子计划只被优化optimize与执行execute一次——对应到当前源码即 pkg/executor/cte.go 中cteProducer结构及其被多个CTEExec共享的引用计数机制详见第六节。三、内存与磁盘物化中间结果的存储策略3.1 RowContainer 与自动溢写物化结果存放于RowContainer中。执行时数据首先驻留内存一旦内存占用超过tidb_mem_quota_query查询内存配额默认通常为 1GB可在会话内调整中间结果会自动溢写spill到磁盘。说明tidb_mem_quota_query的值与生效语义以 pkg/sessionctx/vardef/sysvar.go 与 pkg/sessionctx/variable/session.go 中的系统变量注册为准该变量可通过SET tidb_mem_quota_query ...在会话内调整。这一能力由MemTracker与RowContainer的 SpillDiskAction 协作完成。在执行器侧pkg/executor/cte.go 中的setupCTEStorageTracker为每张 CTE 存储表resTbl/iterInTbl/iterOutTbl挂接内存与磁盘 Tracker并注册溢写 actionmemTracker : tbl.GetMemTracker() memTracker.SetLabel(memory.LabelForCTEStorage) memTracker.AttachTo(parentMemTracker) if vardef.EnableTmpStorageOnOOM.Load() { actionSpill tbl.ActionSpill() ... }当内存超限时触发溢写后续读取仍然透明——这是 TiDB 支撑超大规模递归物化结果的关键设计。3.2 递归深度上限与超时保护递归 CTE 的迭代次数在优化期无法精确预知因此设计上做了两件事代价估算采用 seed part 的代价作为整个 CTE 的代价新增系统变量cte_max_recursion_depth限制最大迭代轮数达到上限即报错终止。该变量在 pkg/sessionctx/variable/session.go 中注册为会话级CTEMaxRecursionDepth字段。执行器 pkg/executor/cte.go 在computeRecursivePart中每轮迭代都会校验if p.curIter p.ctx.GetSessionVars().CTEMaxRecursionDepth { return exeerrors.ErrCTEMaxRecursionDepth.GenWithStackByArgs(p.curIter) }对应错误信息记录在 errors.toml 中Recursive query aborted after %d iterations. Try increasing cte_max_recursion_depth to a larger value当遇到Recursive query aborted报错时即可据此调大cte_max_recursion_depth。与此同时迭代终止还受max_execution_time约束防止恶意/失控递归拖垮执行。3.3 三个关键终止条件汇总综合设计文档与源码一轮迭代结束后判定继续或终止的条件为本轮迭代没有产生新数据iterOutTbl为空、iterInTbl无 chunk迭代轮数达到cte_max_recursion_depth执行时间达到max_execution_time若递归 CTE 上带有LIMIT输出行数达到 LIMIT 要求时也会提前终止迭代见 pkg/executor/cte.go 中的limitDone判定hasLimit tbl.NumRows() limitEnd。设计文档特别指出递归 CTE 支持 LIMIT是防止无限递归的实用手段用户不必担心忘记写终止条件而导致死循环。四、新增数据结构逻辑算子与物理算子4.1 逻辑算子LogicalCTE与LogicalCTETable设计文档给出的核心逻辑算子定义对应到当前源码 pkg/planner/core/operator/logicalop/logical_cte.go 已演化为type LogicalCTE struct { LogicalSchemaProducer Cte *CTEClass CteAsName ast.CIStr ... } type CTEClass struct { // seed part 与 recursive part 之间的连接词是 UNION DISTINCT 还是 UNION ALL IsDistinct bool // seed part / recursive part 的逻辑计划 SeedPartLogicalPlan base.LogicalPlan RecursivePartLogicalPlan base.LogicalPlan // 非递归 CTE 时为 nil // 物理计划 SeedPartPhysicalPlan base.PhysicalPlan RecursivePartPhysicalPlan base.PhysicalPlan // 中间存储的 ID IDForStorage int HasLimit bool LimitBeg uint64 LimitEnd uint64 ... }各核心字段含义IsDistinctseed 与 recursive 之间为UNION [DISTINCT]true还是UNION ALLfalse决定物化结果是否需要去重SeedPartLogicalPlan种子部分逻辑计划RecursivePartLogicalPlan递归部分逻辑计划非递归 CTE 时为 nilIDForStorage指向中间存储的 ID供写侧LogicalCTE与读侧LogicalCTETable对齐LimitBeg/LimitEnd递归 CTE 上使用 LIMIT 时的起止行号用于提前终止。不同引用同一 CTE 的LogicalCTE会共享同一个CTEClass保证只优化一次、只执行一次。LogicalCTETable则代表读取端通过idForStorage定位临时结果集并作为普通表那样被扫描。4.2 物理算子PhysicalCTE与PhysicalCTETable对应逻辑层物理层新增 pkg/planner/core/operator/physicalop/physical_cte.go 与 pkg/planner/core/operator/physicalop/physical_cte_table.go。物理计划生成阶段只做一件事把 seed part 与 recursive part 各自转换成物理计划CTE 自身不参与执行器选择因此避免了双实现带来的正确性风险。值得一提的是当前LogicalCTE的PredicatePushDown已支持把外层谓词推入 seed 部分见logical_cte.go中的实现这属于对设计文档Future Work向物化表下推谓词的落地推进。4.3 执行器CTEExec与CTETableReaderExec设计文档描述的原始 executor 结构在当前源码 pkg/executor/cte.go 中被重构为CTEExec 共享的cteProducer模式seed 与 recursive 的执行器、三张存储表、去重哈希表、LIMIT 信息、内存/磁盘 Tracker 全部收敛到cteProducer中由所有引用同一 CTE 的CTEExec共享type cteProducer struct { seedExec exec.Executor recursiveExec exec.Executor resTbl cteutil.Storage // 最终输出 iterInTbl cteutil.Storage // 每轮迭代输入 iterOutTbl cteutil.Storage // 每轮迭代输出 hashTbl join.BaseHashTable isDistinct bool hasLimit bool limitBeg uint64 limitEnd uint64 ... }而 pkg/executor/cte_table_reader.go 中的CTETableReaderExec仅用于递归 CTE它顺序读取iterInTbl把上一轮输出交给 recursive part 中的上层算子继续加工。关键实现在Next中通过迭代号GetIter()判断是否需要回到表头重读——因为 Selection 等算子可能用 for 循环多次拉取仅靠chkIdx判断会出错。4.4 存储抽象Storage设计文档给出的Storage接口在 pkg/util/cteutil/storage.go 中得到完整实现。核心设计点是引用计数由于一个Storage可能被多个执行器同时读写只有当最后一个使用方调用Close()时才真正释放底层资源。接口语义如下OpenAndRef()首次调用打开底层存储之后调用仅将引用计数 1DerefAndClose()引用计数 -1减到 0 时真正关闭底层RowContainerAdd(chk)/GetChunk(idx)/GetRow(ptr)写入 / 按 chunk 读取 / 按行读取Lock()/Unlock()存储可能被并发访问需要加锁串行化填充过程Done()/SetDone()标记物化是否完成供并发读取方等待Reopen()/SwapData()用于新一轮迭代时重置输入表或交换输入/输出表数据。StorageRC是该接口基于chunk.RowContainer的默认实现。之所以提供Reopen而不是复用旧容器是因为旧RowContainer内部的memTracker/actionSpill等元信息不会被自动重置直接新建更安全。源码注释还点出了它的典型用法storage.Lock() if !storage.Done() { // fill all data into storage } storage.UnLock() // read data from storage五、CTE 的一生从解析到执行的完整流水线设计文档用Life of a CTE串联起五个阶段下面结合 SQL 示例逐步拆解。5.1 Parsing解析解析阶段将 CTE 定义解析为最外层select stmt的一棵子树CTE 定义与主查询共享同一个 AST 上下文。5.2 Logical Plan逻辑计划构建与校验AST 构建出LogicalCTE后需要完成三件事① 区分 seed part 与 recursive part分别构建逻辑计划② 执行合法性校验校验规则包括不支持相互递归cte1 - cte2 - cte1seed part 与 recursive part 的列数必须一致所有 seed part 必须位于 recursive part之前recursive part 中不允许出现ORDER BY、聚合函数、窗口函数与DISTINCT。③ 识别同一 CTE使多处引用共享同一份逻辑计划对应CTEClass的共享机制。以文档中的示例 SQL 为例WITH RECURSIVE cte1 AS ( SELECT c1 FROM t1 UNION ALL SELECT c1 FROM cte1 WHERE cte1.c1 10 ) SELECT * FROM t2 JOIN cte1;其逻辑计划形态为主查询 JOIN 一侧为t2表扫描另一侧是LogicalCTELogicalCTE内部又挂载 seed 计划t1扫描与 recursive 计划对cte1自引用的过滤读取。其中对cte1的引用会被构建成LogicalCTETable通过IDForStorage指向LogicalCTE的中间存储。设计文档原图 docs/design/imgs/logical_plan.png 展示了该示例逻辑计划的结构形态。5.3 Physical Plan物理计划逻辑阶段完成后LogicalCTE转换为PhysicalCTELogicalCTETable转换为PhysicalCTETable。seed 与 recursive 部分各走各自的优化流程当前实现在LogicalCTE.DeriveStats中调用utilfuncp.DoOptimize分别完成随后进入构建执行器阶段。设计文档原图 docs/design/imgs/physical_plan.png 给出了物理计划树的对应形态。5.4 Build Executor构建执行器此阶段构造三个关键对象CTEExec迭代式地求值 seed part 与 recursive partCTETableReaderExec读取上一轮迭代结果并返回给父算子Storage保存物化结果CTEExec负责写入CTETableReaderExec负责读取。设计文档原图 docs/design/imgs/executors.png 展示了最终的执行器树拓扑。在构建过程中存储被赋以引用计数并做内存/磁盘 Tracker 的初始化为运行期溢写做好准备。5.5 Execution迭代执行设计文档给出的CTEExec执行骨架其核心思想是第一个执行到的CTEExec负责填充存储其余并发读取方等待填充完成后直接读取配合Done()标志与锁实现func (e *CTEExec) Next(req *Chunk) { // 1. 第一个执行的 CTEExec 负责填充 storage。 e.storage.Lock() defer e.storage.Unlock() if !e.storage.Done() { // 1.1 计算 seed part数据写入 e.iterInTbl。 // 1.2 循环计算 recursive part直到满足终止条件。 e.storage.SetDone() } // 2. 从 e.resTbl 返回 chunk。 }对照当前源码这一逻辑在CTEExec.Next()pkg/executor/cte.go中被实现为持有resTbl锁若!hasCTEResult()则依次调用openProducerExecutor与genCTEResult内部同步执行computeSeedPartcomputeRecursivePart完成时resTbl.SetDone()最后getChunk返回结果。存储填充与读取的协作流程可以概括为以下步骤对应设计文档原图 docs/design/imgs/cte_computation.png计算SeedExec所有输出 chunk 写入iterInTbl作为第一轮迭代的输入迭代计算RecursiveExecCTETableReaderExec从iterInTbl读取上一轮结果 → 上层算子继续处理 → 输出写入iterOutTbl每轮迭代结束时把iterOutTbl的数据复制/交换到iterInTbl作为下轮输入并同时追加到resTbl保存全量结果依据上文 3.3 的四个终止条件判断是否结束迭代。实际源码中这一步对应setupTblsForNewIterationUNION ALL 场景直接调用iterInTbl.SwapData(iterOutTbl)交换底层 RowContainer避免整表拷贝UNION DISTINCT 场景则需先经过去重再写入。iterInTbl/iterOutTbl均通过Reopen()清理后进入下一轮。5.6 UNION [DISTINCT] 的去重处理当 CTE 使用UNION [DISTINCT]而非UNION ALL时需要在物化过程中去重。源码 pkg/executor/cte.go 的处理方式如下使用哈希表join.BaseHashTable按全部列计算哈希做全局去重先把 chunk 内自重复的行滤除chkHashTbl再与Storage中已有行比对hashTbl滤除跨 chunk 重复重复行通过 Chunk 的Sel标记剔除而非物理删除哈希冲突时调用codec.EqualChunkRow逐列比较真实值兜底保证结果正确性。需要指出设计文档中的去重发生在从iterOutTbl拷贝到resTbl之前而当前实现将 seed 阶段的去重写入iterInTbl/resTbl前也纳入了同一哈希机制computeSeedPart中调用tryDedupAndAdd这是落地实现相对设计文档的进一步细化。六、多引用场景并发与共享的执行正确性Materialization的核心优势是一次计算、多处读取。但这要求执行器在多个算子并发读取同一物化结果时仍然正确。设计文档到源码经历了清晰的关键决策填充过程串行化resTbl.Lock()/Unlock()保证同一时刻只有一个生产者真正填充状态收敛到共享的cteProducerresTbl、iterInTbl被所有引用同一 CTE 的CTEExec及CTETableReaderExec共享引用计数管理生命周期存储对象只在最后一个使用方Close()时真正释放OpenAndRef/DerefAndClose配对调用iterOutTbl由首个打开 recursiveExec 的生产者创建并在其 Close 中释放。此外为处理关联子查询Correlated Column场景——例如同一个 CTE 出现在 Apply 算子内层、随外层每行重复求值——源码在CTEExec.Open中会比较关联列的哈希码发生变化时对cteProducer执行reset()重新物化保证每轮外层取值下得到正确的 CTE 结果。这是设计文档未展开、但当前实现已补齐的细节。七、测试设计回顾覆盖面与仓库佐证设计文档规划的测试矩阵可以归纳为三个层次仓库中均有对应落地功能测试非递归/递归 CTE 基本用法、CTE 内再定义 CTE、子查询中使用 CTE、在UPDATE/DELETE/INSERT中使用 CTE、CTE 名与表名冲突、CTE 与表/CTE 的 JOIN、CTE 内使用表达式。对应测试见 pkg/executor/test/cte/cte_test.go 与 pkg/planner/core/tests/cte/cte_test.go以及集成测试 tests/integrationtest/t/executor/cte.test。场景测试CTE 与PREPARE/EXECUTE/Plan Cache、分区表、Stale Read、聚簇索引、SPM/Hint/Binding 的组合使用。压力/基准测试设计文档要求报告特定场景下的内存占用、磁盘占用与 QPS。源码中通过 failpoint如testCTEStorageSpill、assertIterTableSpillToDisk注入溢写触发与断言逻辑验证内存超限后中间表正确落盘。设计文档的 Compatibility Tests 一节标注为 None因为 CTE 是纯新增特性不影响既有行为Benchmark 则被列为持续跟进项。八、影响、风险与未来演进8.1 影响与风险设计文档明确CTE 作为新特性不影响整体性能。唯一需要提示的风险点是——一期只用Materialization实现非递归 CTE在部分场景如 CTE 仅被引用一次且谓词本可下推性能可能不如基于Merge的实现。实际使用中若发现单次引用的 CTE 出现额外物化开销可评估改写为派生表或普通子查询。8.2 替代方案调研Investigation Alternatives主流数据库对非递归 CTE 通常同时支持Merge与Materialization选型经验如下子查询中无副作用如不含random()、cur_timestamp()等易变函数时倾向MergeCTE 被多次引用时Materialization更优理想情况下应支持用户通过hint显式指定实现方式。关于Materialization本身各系统普遍使用可溢写容器存储物化结果与 TiDB 的RowContainer思路一致递归 CTE 的计算步骤也大同小异差异主要在优化手段上包括推迟物化时机、向临时结果下推谓词以缩小物化规模。8.3 未来工作Future Work设计文档末尾列出的演进路线包括支持Merge方式及配套 hintmerge/no_merge让非递归 CTE 在适合场景获得谓词下推收益优化物化路径的谓词下推缩小物化表规模——如前文所述当前LogicalCTE.PredicatePushDown已实现向 seed part 的下推向物化结果整体下推仍在演进中MPP 支持后续将在 TiFlash 侧实现分布式CTEExec但 CTE 定义中的 SQL 目前仍可下推到 TiFlash 执行。九、实战小结在 TiDB 中使用与调优 CTE 的建议把设计原理落到实际使用可以总结出以下可直接操作的要点递归查询必须考虑终止保护为递归 CTE 加上WHERE终止条件或LIMIT避免无限递归拖垮集群。迭代上限可通过变量放宽报错Recursive query aborted after %d iterations. Try increasing cte_max_recursion_depth to a larger value时用SET cte_max_recursion_depth 1000;示例值调大上限并按需同步调整max_execution_time。关注物化资源的消耗递归层级深、中间结果大时物化数据会受tidb_mem_quota_query约束自动溢写到磁盘可通过EXPLAIN ANALYZE与memory/disk相关监控观察resTbl等存储的溢出情况源码logTbls会按迭代输出各表的内存/磁盘占用日志。单次引用的简单 CTE 谨慎权衡鉴于一期统一走物化仅被引用一次的简单 CTE 若出现性能瓶颈考虑改写为派生表。注意递归部分的语法红线recursive part 中不能使用ORDER BY、聚合、窗口函数与DISTINCT否则会校验失败。以上建议均建立在设计文档 docs/design/2021-04-18-common-table-expression.md 与当前源码实现pkg/planner/core/operator/logicalop/logical_cte.go、pkg/executor/cte.go、pkg/util/cteutil/storage.go之上可进一步结合仓库内cte.test/cte.result等集成测试用例加深理解。【免费下载链接】tidbTiDB is built for agentic workloads that grow unpredictably, with ACID guarantees and native support for transactions, analytics, and vector search. No data silos. No noisy neighbors. No infrastructure ceiling.项目地址: https://gitcode.com/GitHub_Trending/ti/tidb创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考