递归查询的两个边界：最上手信息与最下手信息设计实操

写递归查询的时候很多人第一反应就是“一条 SQL 能不能递归到底”。真上手了才发现递归本身并不难真正卡住人的是两个边界最上手信息 和 最下手信息。最上手信息就是递归开始前你必须先拿到的那条起点记录比如树结构的根节点、组织架构的总公司、评论区的顶层帖子最下手信息则是递归走到不能再继续往深处走时返回来的那一层结果比如最末级部门、最深层分类、没有子节点的叶子评论。对后端开发、数据工程师和 BI 同学来说把这两个边界想清楚递归查询基本就成功了一大半——否则写出来的 CTE 要么缺起点要么漏终止条件跑一次爆一次内存。这篇文章会从“最上手信息”和“最下手信息”这两个词切入把递归查询的锚点设计、终止条件、性能控制、常见坑位全部过一遍。既有 SQL 层面的递归 CTE 实操也有文件目录、JSON、Python 这类通用场景的例子适合正在啃递归查询的初学者也适合想系统梳理一遍的老手。1. 递归查询的总体设计拆解一条 SQL 里的上下手边界1.1 递归查询说白了就是“自己调用自己的一张临时表”大多数后端开发者第一次接触递归是在 SQL 里的WITH RECURSIVE语法。它的核心结构并不是什么高深算法而是“先给你一行起点然后反复在结果里继续向下找”。以 PostgreSQL 为例语法骨架是这样的WITH RECURSIVE tree AS ( -- 锚点最上手信息递归的起点 SELECT id, name, parent_id, 1 AS depth FROM category WHERE parent_id IS NULL UNION ALL -- 递归项每次从 tree 中取一层继续往下匹配 SELECT c.id, c.name, c.parent_id, tree.depth 1 FROM category c JOIN tree ON c.parent_id tree.id ) SELECT * FROM tree;锚点部分返回的是“初始结果”递归项部分负责把上一轮的结果作为输入再去查下一轮。整个过程不断重复直到递归项查不到新数据整个临时表才定型。信息论一点说锚点就是这个递归计算里的“初始状态”递归项是迭代函数而“递归项查不到数据”这个条件就是天然的最下手信息。很多人在这一步犯错误是只盯着“怎么写递归项”忽略了锚点的质量。实际上锚点决定了两件事一是查询从哪里开始二是整棵树的入口条件对不对。如果锚点选错后面再怎么递归都只是在错误树上打转。1.2 最上手信息负责“启动”最下手信息负责“收尾”我把递归查询的执行过程比喻成查户口你要查一个村子里所有人的家族关系最上手信息就是“村长”这个人最下手信息就是“没有后代的人”。没有村长你连入口都找不到不设定“查到没有后代就停”程序就会在循环引用里疯狂空转。所以在设计任何递归查询前我都会先问自己三个问题递归的起点是谁是根节点、当前登录用户、还是某个固定 ID递归的终点是什么是叶子节点、某个深度阈值还是某条路径不能继续匹配如果数据存在环怎么把已经走过的节点排除掉这三个问题分别对应“最上手信息”“最下手信息”和“循环守卫”。尤其要注意最下手信息不一定只是“查不到下级”它还可以是“深度已达上限”。例如组织架构有 10 层但你需要统计的只是前 5 层此时就应该在递归项的WHERE tree.depth 5里显式截断而不是傻傻递归到底。1.3 为什么很多人觉得递归查询“难写”因为两个边界混在一起了初学者最常见的困惑是不知道锚点里到底该放什么条件。我见过不少开发者拿着一个“根据任意用户查上级链”的需求直接写WHERE parent_id IS NULL结果查出来一堆和当前用户无关的顶层节点。正确做法是最上手信息要从业务入口参数来不是从数据形态来。如果需求是“给定用户 ID 查它的祖先链”锚点就应该是WHERE id :user_id如果需求是“查整棵根树”锚点才用parent_id IS NULL。这两种情况看着差不多实际查询结果天差地别。写 SQL 之前先把“起点是谁”写在一张纸上比直接敲键盘靠谱得多。2. 最上手信息怎么定位入口条件与锚点设计详细拆解2.1 确定“最上手信息”的三个判断标准我把最上手信息总结为三个特征单点可启动、业务语义自然、查询能命中索引。单点可启动指的是锚点查询的结果集不要一开始就特别大。比如组织架构树有 1 万个根级分公司锚点直接WHERE parent_id IS NULL会一次性把 1 万个节点全塞进递归第一轮。此时如果只想从一个分公司下钻最上手信息应该是WHERE id 10086让递归第一轮只返回一条记录后面的轮次再逐步展开。业务语义自然是指起点要和真实世界中的入口对应。菜单树的入口是顶级菜单类目树的入口是根分类权限树的入口是当前用户拥有最高权限的那个角色。确定不了入口写出来的递归只能算是“碰运气查询”。第三个标准容易被忽略锚点必须能利用索引。PostgreSQL 中对parent_id IS NULL这种条件如果列上有索引扫描成本是很低的但如果你的锚点是WHERE name 某某而name列没有索引每次递归的第一轮都会全表扫描一次。所以建表时给外键和查询入口字段加索引是递归查询性能的基本盘。2.2 锚点条件不同递归语义就完全不同同样是分类表三种锚点写法会有三种完全不同的结果需求锚点写法查询结果找整棵树的根WHERE parent_id IS NULL返回所有一级节点从某节点开始向下WHERE id :start_id返回以该节点为根的子树从叶子向上找祖先WHERE id :leaf_id返回该叶子及其上级链这三种都是合法递归但“最上手信息”的选择决定了递归形状。比如“从叶子向上找祖先”这种需求如果用parent_id IS NULL当锚点就跑不到叶子那边去了反而会把整棵树顶层全部捞回来。实际做评论楼中楼、部门血缘分析、商品类目归属时这类向上递归用得非常多我建议单独封装成函数避免每次手写。2.3 给我一条真实数据教你怎么把“最上手”写出来假设有这样一张部门表CREATE TABLE department ( id INT PRIMARY KEY, parent_id INT, name TEXT ); INSERT INTO department VALUES (1, NULL, 总公司), (2, 1, 技术中心), (3, 1, 市场中心), (4, 2, 后端研发部), (5, 2, 前端研发部), (6, 4, 平台组), (7, 4, 订单组);如果想查“技术中心下面全部部门”最上手信息就是技术中心一行WITH RECURSIVE sub_dept AS ( SELECT id, name, parent_id, 1 AS depth FROM department WHERE id 2 UNION ALL SELECT d.id, d.name, d.parent_id, s.depth 1 FROM department d JOIN sub_dept s ON d.parent_id s.id ) SELECT id, name, parent_id, depth FROM sub_dept;这里锚点只取了id 2一行递归项以sub_dept作为驱动源去查子部门。每轮查询都会先读上一轮的结果集再关联 department 表。如果parent_id列有索引PostgreSQL 每轮都走建立在这张“驱动集合”上的嵌套循环性能是可控的。跑出来的结果里depth1是技术中心本身depth2是后端研发部和前端研发部depth3是平台组和订单组。最上手信息的作用在这里体现得非常直观。3. 最下手信息怎么掏终止边界的设定与代价3.1 最下手信息不等于“没有子节点”先搞清楚业务上要哪种“底”递归查询最忌讳的是把“最下手”理解成一个死板的定义。实际项目里“底”至少有三种形态结构上的底当前记录没有子记录也就是叶子节点。查完叶子后递归自然结束。业务上的底明明下面还有子记录但业务只允许展示到第 N 层。例如二级分销只算两级三级菜单只显示三层。路径上的底沿着某条路径走碰到了已经走过的节点。此时不终止的话会无限循环。在 CTE 里自然终止结构底其实不需要额外写条件递归项JOIN tree ON child.parent_id tree.id查不到新数据就会停。但业务底和路径底需要显式处理。比如限制最多 5 层的写法WITH RECURSIVE sub_dept AS ( SELECT id, name, parent_id, 1 AS depth FROM department WHERE id 2 UNION ALL SELECT d.id, d.name, d.parent_id, s.depth 1 FROM department d JOIN sub_dept s ON d.parent_id s.id WHERE s.depth 5 ) SELECT * FROM sub_dept;WHERE s.depth 5就是最下手信息的显式控制。如果不加这个条件而树本身有 100 层递归会继续一层层向下展开最终超出数据库的递归深度限制。PostgreSQL 默认的max_recursive_iterations其实并不存在真正受限制的是工作内存MySQL 8 里则有cte_max_recursion_depth参数默认是 1000一旦超过会直接报错。所以深度截断不是可选项而是保命项。3.2 循环引用是最可怕的最下手陷阱必须主动排除“回头路”树形数据中偶尔会出现循环比如把 A 部门的父级错配成 B 部门而 B 部门的父级又是 A 部门。此时递归项会无限循环最终拖垮数据库。有两种常用解决方案第一种是 PostgreSQL 的 CYCLE 子句直接从 CTE 语法层面检测循环WITH RECURSIVE sub_dept AS ( SELECT id, name, parent_id, 1 AS depth FROM department WHERE id 2 UNION ALL SELECT d.id, d.name, d.parent_id, s.depth 1 FROM department d JOIN sub_dept s ON d.parent_id s.id ) CYCLE id SET is_cycle USING path SELECT * FROM sub_dept WHERE is_cycle false;CYCLE子句会为每一行记录是否形成循环同时把访问过的路径保存下来。我实测这种写法比手动维护“已访问列表”更不容易出错SQL 也简洁很多。第二种是手动维护visited_ids数组适用于 MySQL 8 或老版本 PostgreSQLWITH RECURSIVE sub_dept AS ( SELECT id, name, parent_id, ARRAY[id] AS visited_ids FROM department WHERE id 2 UNION ALL SELECT d.id, d.name, d.parent_id, s.visited_ids || d.id FROM department d JOIN sub_dept s ON d.parent_id s.id WHERE NOT d.id ANY(s.visited_ids) ) SELECT * FROM sub_dept;这里的visited_ids相当于在递归过程中记录“已经踩过的节点”最下手信息变成了“如果某节点已经出现过就停止深入”。这条写法能查出来正常子结构又能挡住循环路径是兼容性最高的方案。3.3 最下手信息怎么返回全路径、深度最小还是叶子集合递归到底以后业务拿到的结果往往不是一张平铺表而是有要求的结构。常见三类输出输出完整血缘路径例如总公司 技术中心 后端研发部 平台组。这类需求一般在上行递归里拼路径字符串或者在拿到递归结果后用程序二次拼接。输出最深层信息例如每个分支最后一级部门。这时候可以利用窗口函数从完整递归结果里抽每个根节点的最大深度。输出叶子集合比如统计哪些部门没有下级。最直接的办法是查递归结果里不存在于任何节点的parent_id集合里的 ID。如果只需要叶子节点不建议把整个树都递归回来再过滤可以在递归项的WHERE NOT EXISTS里直接做WITH RECURSIVE sub_dept AS ( SELECT id, name, parent_id FROM department WHERE parent_id 1 UNION ALL SELECT d.id, d.name, d.parent_id FROM department d JOIN sub_dept s ON d.parent_id s.id ) SELECT s.id, s.name FROM sub_dept s WHERE NOT EXISTS ( SELECT 1 FROM department d2 WHERE d2.parent_id s.id );这个查询的“最下手信息”是NOT EXISTS判定只把叶子行抛出来。缺点是如果树的层级特别深前面递归轮次仍然会把中间节点全部捞回来。想极致优化可以配合深度字段先限流再筛选叶子避免把整个树装进内存。4. 实操一步步用递归 CTE 把树状数据两个方向跑通4.1 准备一张可以反复折腾的测试表工欲善其事必先利其器。建一张通用的“树形节点表”并塞入足够的测试数据。我直接用上面的部门表继续但增加一个sort_no字段用于控制排序。CREATE TABLE department ( id INT PRIMARY KEY, parent_id INT, name TEXT, sort_no INT DEFAULT 0 ); CREATE INDEX idx_dept_parent ON department(parent_id); INSERT INTO department VALUES (1, NULL, 总公司, 0), (2, 1, 技术中心, 1), (3, 1, 市场中心, 2), (4, 2, 后端研发部, 1), (5, 2, 前端研发部, 2), (6, 3, 品牌部, 1), (7, 4, 平台组, 1), (8, 4, 订单组, 2), (9, 5, 移动端组, 1), (10, 7, 基础架构组, 1);这里parent_id建了索引非常重要。没有这个索引每次递归项做JOIN时都要全表扫描数据量一上来性能立刻崩。4.2 自上而下从一条根挖到所有叶子顺手带上层级“最上手信息”在这里是根节点id 1。代码写出来WITH RECURSIVE tree AS ( SELECT id, parent_id, name, sort_no, 1 AS depth, name AS path FROM department WHERE id 1 UNION ALL SELECT d.id, d.parent_id, d.name, d.sort_no, t.depth 1, t.path || || d.name FROM department d JOIN tree t ON d.parent_id t.id ) SELECT depth, id, parent_id, name, path FROM tree ORDER BY path;这段代码同时做了三件事层级累加、路径拼接、按路径排序。path字段是一个非常典型的“下钻轨迹”能直接看出每个节点在整棵树里的位置。ORDER BY path虽然简单但在数据量大的场景下字符串排序不是最优更正规的做法是带上sort_no做多级排序或者回到程序里按树形结构重新组织。以id 1为根结果是depthidparent_idnamepath11NULL总公司总公司221技术中心总公司 技术中心342后端研发部总公司 技术中心 后端研发部474平台组总公司 技术中心 后端研发部 平台组5107基础架构组总公司 技术中心 后端研发部 平台组 基础架构组484订单组总公司 技术中心 后端研发部 订单组352前端研发部总公司 技术中心 前端研发部495移动端组总公司 技术中心 前端研发部 移动端组231市场中心总公司 市场中心363品牌部总公司 市场中心 品牌部这条 SQL 里最容易忽略的是排序字段。很多人在递归最后直接ORDER BY depth, id结果层级一样但顺序完全不是业务想要的前后级顺序。我在实际项目里更倾向于把递归结果先完整取回来再在应用层按父子关系组装成树这样既能控制展示顺序又能减少数据库层的字符串拼接压力。4.3 自下而上从叶子倒推祖先链找出每个节点的完整上司“最下手信息”是这个需求的起点——叶子节点。假设想知道“基础架构组”一路到总公司的血缘关系锚点写id 10递归项改为找父节点WITH RECURSIVE lineage AS ( SELECT id, parent_id, name, 1 AS depth, name AS path FROM department WHERE id 10 UNION ALL SELECT d.id, d.parent_id, d.name, l.depth 1, d.name || || l.path FROM department d JOIN lineage l ON d.id l.parent_id ) SELECT depth, id, parent_id, name, path FROM lineage ORDER BY depth DESC;注意递归项里的关联方向变了JOIN lineage l ON d.id l.parent_id意思是找到当前行的父节点。结果会一层层向上“爬”直到parent_id IS NULL。这也是恒等式最下手信息叶子变成查询的第一个输入最上手信息根节点变成自然停止的地方。运行结果depthidparent_idnamepath51NULL总公司总公司 技术中心 后端研发部 平台组 基础架构组421技术中心技术中心 后端研发部 平台组 基础架构组342后端研发部后端研发部 平台组 基础架构组274平台组平台组 基础架构组1107基础架构组基础架构组这里ORDER BY depth DESC是为了让根节点排在最上面。如果要计算某个节点到根有多少层深度直接取MAX(depth)即可。向上递归在组织架构血缘、菜单权限继承、分类归属回溯这些场景里非常常见比向下递归更容易写错核心原因就是锚点 “最上手信息” 混淆了。4.4 数据量一大递归查询容易碰到什么性能瓶颈递归 CTE 的性能瓶颈几乎都出在同一处每轮递归都会去扫描子表的关联数据而且是在内存里不断膨胀的“工作场”上扫描。数据量小的时候看不出问题几万条节点一旦层级深、分支多工作场会指数级增长。我曾经对一张 8 万行的类目表做全树递归最深的路径有 9 层。如果锚点是根节点整个查询会产生大量中间行排序和去重直接打到几百万行。后来在递归项里加了WHERE深度限制把不必要的分支提前剪掉查询时间从 6 秒降到 0.8 秒。这个优化思路说明一个问题递归查询和普通查询不一样它的性能控制要放在“每一轮”里而不是等全部算完再过滤。实操中我会这样控制先跑EXPLAIN确认递归项里JOIN是否命中了索引。小数据量先验证逻辑再逐步放大数据。确认业务上能接受的最高深度写入递归项作为WHERE条件。如果必须全树递归优先考虑在应用层拆分查询比如按顶层节点分批跑。5. 跨场景递归文件目录、JSON、Python 里的“上手”和“下手”5.1 文件目录最上手是入口路径最下手是文件本身递归查询不只在 SQL 里出现。Linux 上最常用的find命令本质就是目录递归find /data/project -type f -name *.log这条命令的“最上手信息”是/data/project“最下手信息”是-type f也就是递归到文件这条链的末端才停下来输出。如果只看目录find /data/project -type d此时“最下手信息”变为目录本身凡是递归到没有子目录的位置就结束。很多人排查日志时把路径写错其实是“最上手信息”没定位准find 从错误入口递归自然什么都找不到。5.2 JSON 递归展开从根键一路拆到最内层标量接口联调时经常需要把多层嵌套 JSON 拍平。用 Python 递归解析是最常见的写法def flatten_json(data, prefix, resultNone): if result is None: result {} if isinstance(data, dict): for key, value in data.items(): flatten_json(value, f{prefix}.{key} if prefix else key, result) elif isinstance(data, list): for index, item in enumerate(data): flatten_json(item, f{prefix}[{index}], result) else: result[prefix] data return result在这个函数里“最上手信息”是传入的根字典“最下手信息”是else分支——当值不是 dict 也不是 list 时递归终止并记录键值对。如果忘记处理 list只要数据里出现数组递归就会断掉结果少一半字段。这也是递归函数里“最下手信息不完整导致结果丢失”的典型表现。5.3 Python 递归函数入参、横向遍历、纵向跳出的边界设计再举一个解析树形结构返回所有子节点的例子def get_all_children(node, children_table, resultNone): if result is None: result [] children children_table.get(node.id, []) for child in children: result.append(child) get_all_children(child, children_table, result) return result这个函数有两个隐含边界入参node是最上手信息空列表children是最下手信息。递归能跑完的前提是子节点关系表里没有循环。如果存在循环这个函数会直接RecursionError。所以我在写 Python 递归时总会额外传入一个visited集合def safe_get_all_children(node, children_table, visitedNone, resultNone): if visited is None: visited set() if result is None: result [] if node.id in visited: return result visited.add(node.id) for child in children_table.get(node.id, []): result.append(child) safe_get_all_children(child, children_table, visited, result) return result这个visited集合就是循环场景下的“手工最下手信息”。它和 SQL 里的CYCLE子句、visited_ids数组是同一个思路递归可以无限向下但不能无限回头。6. 常见问题排查与避坑实录6.1 问题递归查询直接报错提示超过递归深度或者爆栈处理办法分两个方向如果是 SQL 数据库先查递归上下文是否缺少深度限制。MySQL 8 需要检查参数SET SESSION cte_max_recursion_depth 10000;但设置得太高不是好事。真正该做的是在递归项里加WHERE depth :max_depth把业务限制写进 SQL而不是依赖数据库的默认上限。如果是 Python 或脚本语言爆栈多半是循环引用先检查数据里是否存在 A 指向 B、B 又指向 A 的环再处理循环守卫。6.2 问题结果行数爆炸把内存和临时表撑满递归查询有“宽树效应”每个父节点都有几十个子节点层级一深行数按几何级数往上走。常见表现是查询迟迟不返回磁盘临时文件暴涨。这时要先问自己“我真的需要整棵树吗”绝大多数业务只要某几个分支完全可以在锚点处做裁剪或是在递归项的JOIN条件里加业务过滤。还有一种情况是排序问题递归 CTE 不带ORDER BY时PostgreSQL 的行返回顺序是不保证的。如果要按树形层级稳定输出务必将深度和排序字段一起带出来。避免在递归过程中用DISTINCT那会让每一轮都增加一轮去重开销。6.3 问题同样的 SQL 在 MySQL 和 PostgreSQL 上结果不一样两个数据库的递归 CTE 大体兼容但细节有差异。PostgreSQL 支持CYCLE子句、数组类型、更灵活的类型转换MySQL 8 不支持CYCLE子句也不支持在递归 CTE 里直接使用聚合函数比如SUM、GROUP BY。遇到“父子节点汇总统计”的需求在 MySQL 里通常得先递归取全量再在外面做聚合在 PostgreSQL 里就可以用LATERAL或者窗口函数配合。我用过一个比较麻烦的案例要把某棵子树的节点总数计算出来。PostgreSQL 可以递归后GROUP BY,MySQL 8 则需要把递归 CTE 包一层子查询不然直接报“Recursive query with aggregate is not supported.”。这类兼容性差异写代码之前查一查官方文档能省下不少时间。6.4 常见问题速查表现象根因解决办法递归不返回CPU 持续飙升数据存在循环引用加 CYCLE 子句或 visited 数组报错超出递归深度无深度限制在递归项中加 depth 字段并设上限查出来的叶子不对锚点选错起点确认最上手信息是否是业务入口查询速度越来越慢parent_id 无索引建索引并检查执行计划MySQL 递归里报聚合错误递归项不允许聚合函数先取全量再外包一层查询结果里出现重复节点树结构里一个节点有多个父级按主键去重并修正数据模型这个表里的每一条都是我在实际项目中踩过的坑。特别是“一个节点有多个父级”这种数据模型问题SQL 层面只能去重掩盖根本解法是把多对多关系单独拆成关系表而不是硬塞进单列parent_id。7. 递归查询的上手与下手我最后保留的三个习惯第一个习惯写递归前先把“最上手信息”和“最下手信息”两行注释写在 SQL 顶部。别嫌啰嗦这两行注释能逼着自己把起点和终点想清楚。真的出了问题回头排查也快因为你知道哪里是入口、哪里是出口。第二个习惯任何时候都保留一个depth字段。哪怕业务当前不需要显示层级我也会在锚点里初始化1在递归项里1。理由很简单这是后续做深度限制、调试结果、排查无限循环的唯一抓手。没有这个字段出了问题就只能靠数行数猜层数。第三个习惯给递归数据表建parent_id索引并且尽量让锚点是唯一值。能传id就传id不要图省事写parent_id IS NULL。哪怕业务真的是要从全根开始我也倾向在外面先取一批根节点 ID再逐个递归。每轮递归的起点越小性能越稳。递归查询真正考验的不是语法是你对“从哪开始、到哪结束”这两个边界的理解。把最上手信息和最下手信息当成工程师的“入口意识”和“终止意识”不管是 SQL、文件系统还是 Python你都能写出又快又稳的递归逻辑。如果后续想继续扩展还可以把递归结果做成物化路径、闭包表或者用嵌套集合模型彻底避开递归查询那又是一套值得单独拆开讲的话题。