层级数据查询治理实战：从递归 CTE 失控到路径枚举与闭包表

dbaai

层级数据查询治理实战：从递归 CTE 失控到路径枚举与闭包表

一、具体的问题

接手一个电商后台，类目表 categories 二十万行左右，最深八层，挂在类目下的商品三千万条。运营每点开一个一级类目，页面就要统计这个类目连同它下面所有子孙类目一共多少商品。

原来的实现很直接：一个递归 CTE，从当前类目往下逐层展开拿到全部子孙 id，再 join 商品表做 count。上线初期没人觉得有问题，因为测试库的类目只有几千行。等真实数据进来，这个接口的 P99 从三十毫秒爬到两秒四，后台首页一打开，运营就先去泡茶。

真正让人难受的不是慢，而是慢得没道理：类目表总共二十万行，整表扫一遍也就几万次逻辑读，凭什么查个子孙要两秒？监控里能看到数据库 CPU 被一条反复执行的小 SQL 吃掉，单条不算长，但一秒内要跑两三百次，每次都在干同一件事——把同一棵子树重新递归走一遍。

二、核心原理

第一，递归 CTE 是迭代展开，不是一次索引跳转。

递归部分内部有一张工作集（work table），第 N 层的输入是第 N−1 层的输出。父集合是"算出来才知道"的，优化器没法预先把整棵子树当成一个连续区间一次扫掉。所以代价大致等于：层数 × 每层行数 × 单次 join 成本 × 回表次数。层数越深、每层越宽，成本是乘出来的，不是加出来的。

第二，parent_id 上的索引只解决"找直接子节点"。

它能让你快速拿到某个节点的下一层，但对"跳过整棵子树"这件事无能为力。于是每次查询都把子树从根开始重走一遍。而类目树是典型的读多写少结构——同一棵子树一天可能被走几千遍，这笔重复劳动一直没人记账。

第三，能不能把树的结构提前算成可索引的形态？

能。这就是物化路径（path enumeration）、闭包表（closure table）、嵌套集（nested set）三种做法共同的思想：把层级关系从"父指针"翻译成一段能在 B+ 树上顺序扫过去的形态。

• 路径枚举：每个节点存一条从根到自己的路径，形如 /1/12/135/。查子孙就是 WHERE path LIKE '/1/12/%'，一次范围扫描，零递归。
  
• 闭包表：单独一张表存所有 (祖先, 后代, 深度) 对，查子孙是一次等值 join，深度过滤顺手就带了。
  
• 嵌套集：左右值编码，查子孙是一次 BETWEEN 区间扫描，读最快，写最贵——插入一个节点要改一大片 lft/rgt。
  

读多写少选前两种；写放大明显（子树经常整体搬迁）的场景要掂量再定。

三、实例参考（动手步骤）

以下以 categories(id, parent_id, name) 为例，PostgreSQL 与 MySQL 8 都能跑通，SQL Server / Oracle 的差异在步骤里点明。

步骤 0：确认现状基线

先别改代码，先把代价量出来，否则改完也不知道好在哪。

2. EXPLAIN (ANALYZE, BUFFERS)          -- PostgreSQL
3. WITH RECURSIVE sub AS (
4.   SELECT id FROM categories WHERE id = 12
5.   UNION ALL
6.   SELECT c.id FROM categories c JOIN sub s ON c.parent_id = s.id
7. )
8. SELECT count(*) FROM sub;

复制代码

MySQL 8.0.18+ 直接 EXPLAIN ANALYZE 同一条语句；SQL Server 在 SSMS 里 SET STATISTICS IO, TIME ON；Oracle 用 DBMS_XPLAN.DISPLAY_CURSOR(NULL, NULL, 'ALLSTATS LAST')。

记三个数：实际返回行数、逻辑读（PG 看 shared hit+read，MySQL 看 rows examined，SQL Server 看 logical reads）、实际耗时。这三个数是后面所有对比的基准。

步骤 1：加 path 列并回填

2. ALTER TABLE categories ADD COLUMN path varchar(512);

复制代码

回填（PostgreSQL 写法，MySQL 8 把 || 换成 CONCAT()）：

2. WITH RECURSIVE t AS (
3.   SELECT id, '/' || id || '/' AS path
4.   FROM categories WHERE parent_id IS NULL OR parent_id = 0
5.   UNION ALL
6.   SELECT c.id, t.path || c.id || '/' FROM categories c JOIN t ON c.parent_id = t.id
7. )
8. UPDATE categories c SET path = t.path FROM t WHERE c.id = t.id;

复制代码

两个细节必须注意：路径首尾都要补分隔符，靠 / 做边界，否则 /1/12% 会把 /1/120/ 一起捞进来；长度按最深路径预估，八层、六位 id 大约 56 字符，给 512 很宽裕，但如果主键是 UUID，直接上 text。

步骤 2：建索引，把递归换成一次前缀扫描

2. CREATE INDEX idx_categories_path ON categories (path varchar_pattern_ops);  -- PostgreSQL
3. -- MySQL: CREATE INDEX idx_categories_path ON categories (path);

复制代码

查询改成一行：

2. SELECT id FROM categories WHERE path LIKE '/1/12/%';

复制代码

PG 的 varchar_pattern_ops 是为了让 LIKE '常量前缀%' 在面对非 C collation 时仍能走索引；MySQL 的 utf8mb4_general_ci 一般能走前缀范围扫描。千万别写成 LIKE '%/1/12/%'——左模糊直接把索引用废。

步骤 3：写时维护 path

新增节点：父节点的 path 拼上自己的 id 和 /。移动子树：一条 UPDATE 做前缀替换。

2. UPDATE categories
3. SET path = replace(path, '/1/12/', '/1/15/')
4. WHERE path LIKE '/1/12/%';

复制代码

这里就是路径枚举的写放大所在：搬一个有两千个子孙的类目，要改两千行，务必放进一个事务，并且靠分隔符保证匹配串不串味（/1/2/ 和 /1/12/ 是两回事）。

步骤 4：读压力再上一档时才考虑闭包表

2. CREATE TABLE category_closure (
3.   ancestor   int      NOT NULL,
4.   descendant int      NOT NULL,
5.   depth      smallint NOT NULL,
6.   PRIMARY KEY (ancestor, descendant)
7. );

复制代码

自身对自身 depth=0 一行，其余由递归 CTE 一次性铺满。查子孙是 WHERE ancestor = 12，一次索引扫描，AND depth <= 2 顺手就把"只看两层"也解决了。代价是行数 O(节点数 × 平均深度)，二十万节点八层能做到百万行量级，维护成本比 path 高，通常只有 path 撑不住时才上。

步骤 5：递归 CTE 别删，但要加固

临时核算、path 尚未回填完的场景还得用递归。加固三件事：

• 加深度上限：MySQL 的 cte_max_recursion_depth 默认 1000，深树要显式调；PG 在递归 CTE 里加 WHERE depth < 20 更直接。
  
• 防环：PG 12+ 用 CYCLE id SET is_cycle USING path；Oracle 用 CONNECT BY NOCYCLE；MySQL 8 没有 CYCLE 子句，只能在递归里自己拼 id 数组用 MEMBER OF 判重。
  
• 先治脏数据：parent_id 指向不存在的节点、自引用、孤立小环，这三类才是递归挂住的真正源头。
  

治理前后对比

指标	治理前	治理后
单次查子孙耗时 P99	2400 ms	12 ms
语句扫描行数	约 180 万	约 2100
递归层数	8 层，逐层 join	0 层，一次范围扫描
后台首页整页加载	3.1 s	180 ms
归类目库 CPU 占用	峰值 92%	峰值 21%
单条类目新增	8 ms	35 ms（多写一列）
移动子树（2000 子孙）	8 ms	约 160 ms（一条 UPDATE 改 2000 行）

读侧收益两个数量级，写侧付出几毫秒到一百多毫秒。类目树读写比大约 500:1，这笔账很清楚。

四、实操检查清单

• 用 EXPLAIN ANALYZE 记录了治理前的实际行数、逻辑读、耗时，不凭"感觉很慢"下判断。
  
• 路径列首尾都补了分隔符，查询条件写成 '/a/b/%'，不是 '/a/b%'。
  
• 前缀查询确认走范围扫描（PG 看 Index Cond，MySQL 看 type=range），不是全表扫。
  
• 路径列长度按「最深层数 × 单节点长度」留足余量，或干脆用 text。
  
• 新增、移动、删除三处写入逻辑都维护了 path，不是只改新增。
  
• 移动子树的 UPDATE 在事务里，且带 WHERE path LIKE 旧前缀，避免误伤其它分支。
  
• 已排查环、自引用、孤儿节点；保留的递归 CTE 都配有深度上限与防环手段。
  
• MySQL 检查过 cte_max_recursion_depth，PG 侧配了 statement_timeout 兜底，防止递归把连接挂死。
  
• 回填 path 后跑过 ANALYZE / ANALYZE TABLE，统计信息是新的。
  
• 应用层缓存了「类目 id → 子孙 id 列表」，类目变动才失效，不再每次请求都查库。
  

几个容易踩的坑

分隔符没包住。 /1/12% 命中 /1/120/，子孙凭空多出一整棵不相干的子树。而且结果看起来"挺合理"，往往几个月都发现不了。

只加列不建索引。 path 有了，查询还在全表扫，性能纹丝不动，然后误判成方案不行。

PG 忘了 varchar_pattern_ops。 默认 collation 下 LIKE 前缀不一定走索引，加完一 EXPLAIN 还是 Seq Scan，很容易被当成索引建错了。

移动子树只改自己一行。 子孙的 path 全成僵尸路径，之后查谁都不对，还得靠全表重建才能救回来。

把 path 当业务字段用。 有人往里塞排序号、状态标记，最后谁也不敢动它。它只该存结构。

递归 CTE 不设上限。 脏数据一个环，PG 那边连接挂住不动，MySQL 报 Recursive query aborted 整条语句回滚，排查半天才发现问题在数据不在 SQL。

上了闭包表却不控行数。 二十万节点、平均深度六层，闭包表一百多万行，每次插入还要维护 O(深度) 行，写多的场景会反过来成为新瓶颈。

回到开头那个两秒四的接口：它的问题从来不是 SQL 写得不好，而是树的结构没有被提前算成可索引的形态，每次请求都要求数据库现场把树重新爬一遍。递归 CTE 是通用解，不是高性能解——这个区分，值得在动手改代码之前先想清楚。