SQL 递归查询（Recursive Common Table Expression, Recursive CTE）是数据库开发中一个强大而灵活的工具，尤其在处理树形结构或图结构数据时表现出色。本文将从程序员的角度，详细讲解 SQL 递归查询的原理、实现方式、性能优化、MyBatis 中的应用，以及实际案例和注意事项。

1. 什么是 SQL 递归查询？

1.1 背景与需求

在数据库开发中，经常会遇到需要处理层次结构数据的场景，例如：

  • 组织结构：公司部门之间的上下级关系。
  • 权限系统：权限树（如菜单、角色权限）。
  • 家谱：家族成员之间的亲属关系。
  • 图结构：社交网络中的朋友关系、路径搜索。

这些数据通常以树形结构或图结构存储在数据库中，表中包含一个字段（如 ParentId）来表示记录之间的父子关系。例如：

Id ParentId Name Label
1 10 小明 权限A
2 20 小红 权限B
10 30 小明爸 权限C
20 40 小红妈 权限D
30 NULL 小明爷爷 权限E
40 NULL 小红外婆 权限F

在这个表中，Id 是记录的唯一标识，ParentId 指向父记录的 Id，NULL 表示没有父记录（即根节点）。如果我们需要从某些节点（例如 Id=1 和 Id=2）开始，向上查找所有父节点（包括父节点的父节点），传统 SQL 查询（例如多次 JOIN）会非常复杂。这时，递归查询就派上用场了。

1.2 递归查询的定义

SQL 递归查询是通过递归公共表表达式（Recursive Common Table Expression, Recursive CTE）实现的。WITH RECURSIVE 是 SQL 标准语法，允许开发者定义一个临时结果集（CTE），并通过递归的方式不断扩展这个结果集，直到满足终止条件。

递归查询通常用于：

  • 查找树形结构中的所有祖先或后代。
  • 计算图中的路径或距离。
  • 构建层次结构的完整视图。

1.3 支持递归查询的数据库

  • PostgreSQL：从 8.4 版本开始支持 WITH RECURSIVE。
  • MySQL：从 8.0 版本开始支持（5.x 版本不支持）。
  • Oracle：从 11g 版本开始支持 WITH RECURSIVE，但更常用 CONNECT BY 语法。
  • SQL Server：从 2005 版本开始支持。
  • SQLite：从 3.8.3 版本开始支持。

如果数据库不支持 WITH RECURSIVE，可以考虑使用存储过程或在应用层实现递归逻辑。

2. SQL 递归查询的原理

2.1 递归查询的结构

一个典型的递归查询由以下部分组成：

  1. 基础查询（Base Case）：定义递归的起点，即初始结果集。
  2. 递归查询（Recursive Case）：定义如何基于当前结果集查找新记录。
  3. 终止条件：当递归查询不再产生新记录时，递归停止。
  4. 最终查询：从递归结果集中选择最终输出。

以下是一个简单的递归查询示例：

  1. WITH RECURSIVE MenuTree AS (
  2.     -- 基础查询：选择起点节点
  3.     SELECT Id, ParentId, Name, Label
  4.     FROM base_permission
  5.     WHERE Id IN (1, 2)
  6.     UNION ALL
  7.     -- 递归查询：向上查找父节点
  8.     SELECT p.Id, p.ParentId, p.Name, p.Label
  9.     FROM base_permission p
  10.     INNER JOIN MenuTree mt ON p.Id = mt.ParentId
  11. )
  12. SELECT * FROM MenuTree;

2.2 递归查询的执行过程

递归查询的执行过程可以分为以下步骤：

步骤 1：执行基础查询

  • 基础查询是递归的起点，生成初始结果集。
  • 在上述示例中，WHERE Id IN (1, 2) 找到 Id=1 和 Id=2 的记录：
    • Id=1, ParentId=10, Name="小明", Label="权限A"
    • Id=2, ParentId=20, Name="小红", Label="权限B"
  • 这些记录被放入 MenuTree 临时结果集。

步骤 2：执行递归查询（第一次迭代）

  • 递归查询基于当前 MenuTree 的内容，查找新记录。
  • 当前 MenuTree 包含：
    • Id=1, ParentId=10
    • Id=2, ParentId=20
  • INNER JOIN 查找 p.Id = mt.ParentId，即 p.Id IN (10, 20)：
    • 找到 Id=10, ParentId=30 和 Id=20, ParentId=40。
  • 使用 UNION ALL 将这些新记录追加到 MenuTree：
    • MenuTree 现在包含：[Id=1, Id=2, Id=10, Id=20]。

步骤 3：执行递归查询（第二次迭代）

  • 当前 MenuTree 包含：
    • Id=1, ParentId=10
    • Id=2, ParentId=20
    • Id=10, ParentId=30
    • Id=20, ParentId=40
  • INNER JOIN 查找 p.Id IN (10, 20, 30, 40)：
    • p.Id=10 和 p.Id=20 已经加入 MenuTree，不会产生新记录。
    • p.Id=30 找到 Id=30, ParentId=NULL。
    • p.Id=40 找到 Id=40, ParentId=NULL。
  • 追加到 MenuTree：[Id=1, Id=2, Id=10, Id=20, Id=30, Id=40]。

步骤 4：执行递归查询（第三次迭代）

  • 当前 MenuTree 包含：
    • Id=1, ParentId=10
    • Id=2, ParentId=20
    • Id=10, ParentId=30
    • Id=20, ParentId=40
    • Id=30, ParentId=NULL
    • Id=40, ParentId=NULL
  • INNER JOIN 查找 p.Id IN (10, 20, 30, 40, NULL, NULL)：
    • p.Id=10, 20, 30, 40 已经加入 MenuTree。
    • p.Id=NULL 无法匹配（NULL 不参与比较）。
  • 没有新记录产生，递归停止。

步骤 5：执行最终查询

  • SELECT * FROM MenuTree 返回 MenuTree 中的所有记录：
    • Id=1, ParentId=10, Name="小明", Label="权限A"
    • Id=2, ParentId=20, Name="小红", Label="权限B"
    • Id=10, ParentId=30, Name="小明爸", Label="权限C"
    • Id=20, ParentId=40, Name="小红妈", Label="权限D"
    • Id=30, ParentId=NULL, Name="小明爷爷", Label="权限E"
    • Id=40, ParentId=NULL, Name="小红外婆", Label="权限F"

2.3 递归查询的执行次数

  • 基础查询：执行 1 次。
  • 递归查询：执行次数等于树的最大深度（D）减 1。
    • 在上述示例中，树的最大深度是 3（Id=1 -> Id=10 -> Id=30），递归查询执行 2 次。
  • 最终查询：执行 1 次。
  • 总执行次数：1 + (D-1) + 1 = D + 1 次。

3. 递归查询的实现方式

3.1 向上递归（查找祖先）

上述示例是向上递归，即从子节点查找所有父节点。SQL 如下：

  1. WITH RECURSIVE MenuTree AS (
  2.     SELECT Id, ParentId, Name, Label
  3.     FROM base_permission
  4.     WHERE Id IN (1, 2)
  5.     UNION ALL
  6.     SELECT p.Id, p.ParentId, p.Name, p.Label
  7.     FROM base_permission p
  8.     INNER JOIN MenuTree mt ON p.Id = mt.ParentId
  9. )
  10. SELECT * FROM MenuTree;

3.2 向下递归（查找后代）

如果需要从父节点查找所有子节点，只需调整 INNER JOIN 的条件：

  1. WITH RECURSIVE MenuTree AS (
  2.     SELECT Id, ParentId, Name, Label
  3.     FROM base_permission
  4.     WHERE Id = 30 -- 从根节点开始
  5.     UNION ALL
  6.     SELECT p.Id, p.ParentId, p.Name, p.Label
  7.     FROM base_permission p
  8.     INNER JOIN MenuTree mt ON p.ParentId = mt.Id
  9. )
  10. SELECT * FROM MenuTree;
  • 变化：p.ParentId = mt.Id 表示查找 base_permission 中 ParentId 等于 MenuTree 中 Id 的记录，即查找子节点。

3.3 处理多条记录的输入

如果起点是多条记录（例如 Id IN (1, 2, ...)），可以使用 IN 条件：

  1. WITH RECURSIVE MenuTree AS (
  2.     SELECT Id, ParentId, Name, Label
  3.     FROM base_permission
  4.     WHERE Id IN (1, 2, 3)
  5.     UNION ALL
  6.     SELECT p.Id, p.ParentId, p.Name, p.Label
  7.     FROM base_permission p
  8.     INNER JOIN MenuTree mt ON p.Id = mt.ParentId
  9. )
  10. SELECT * FROM MenuTree;

4. MyBatis 中实现递归查询

MyBatis 是一个流行的 Java 持久化框架，支持通过 XML 或注解定义 SQL 语句。以下是如何在 MyBatis 中实现上述递归查询。

4.1 需求分析

假设我们需要：

  1. 查询 base_permission 表中的所有 Id（作为递归的起点）。
  2. 使用这些 Id 进行递归查询，查找所有父权限。

4.2 实体类

  1. public class Permission {
  2.     private Long id;
  3.     private Long parentId;
  4.     private String name;
  5.     private String label;
  7.     // Getter 和 Setter
  8.     public Long getId() { return id; }
  9.     public void setId(Long id) { this.id = id; }
  10.     public Long getParentId() { return parentId; }
  11.     public void setParentId(Long parentId) { this.parentId = parentId; }
  12.     public String getName() { return name; }
  13.     public void setName(String name) { this.name = name; }
  14.     public String getLabel() { return label; }
  15.     public void setLabel(String label) { this.label = label; }
  16. }

4.3 Mapper 接口

  1. public interface PermissionMapper {
  2.     List<Long> selectPermissionIds();
  3.     List<Permission> selectMenuTree(List<Long> permissionIds);
  4. }

4.4 XML 映射文件

  1. <mapper namespace="com.example.mapper.PermissionMapper">
  2.     <!-- 查询所有 permssionId -->
  3.     <select id="selectPermissionIds" resultType="long">
  4.         SELECT Id AS permssionId
  5.         FROM base_permission
  6.     </select>
  8.     <!-- 递归查询 -->
  9.     <select id="selectMenuTree" parameterType="list" resultType="com.example.entity.Permission">
  10.         WITH RECURSIVE MenuTree AS (
  11.             SELECT Id, ParentId, Name, Label
  12.             FROM base_permission
  13.             WHERE Id IN
  14.             <foreach collection="list" item="id" open="(" separator="," close=")">
  15.                 #{id}
  16.             </foreach>
  17.             UNION ALL
  18.             SELECT p.Id, p.ParentId, p.Name, p.Label
  19.             FROM base_permission p
  20.             INNER JOIN MenuTree mt ON p.Id = mt.ParentId
  21.         )
  22.         SELECT * FROM MenuTree
  23.     </select>
  24. </mapper>

4.5 调用代码

  1. SqlSession session = sqlSessionFactory.openSession();
  2. try {
  3.     PermissionMapper mapper = session.getMapper(PermissionMapper.class);
  5.     // 1. 查询所有 permssionId
  6.     List<Long> permissionIds = mapper.selectPermissionIds();
  7.     if (permissionIds == null || permissionIds.isEmpty()) {
  8.         System.out.println("No permission IDs found.");
  9.         return;
  10.     }
  12.     // 2. 使用 permssionId 列表执行递归查询
  13.     List<Permission> menuTree = mapper.selectMenuTree(permissionIds);
  14.     for (Permission permission : menuTree) {
  15.         System.out.println("ID: " + permission.getId() + ", Name: " + permission.getName());
  16.     }
  17. } finally {
  18.     session.close();
  19. }

4.6 执行过程

  1. 第一步：selectPermissionIds：
    • 执行 SELECT Id AS permssionId FROM base_permission。
    • 返回 [1, 2, 10, 20, 30, 40]。
  2. 第二步：selectMenuTree：
    • <foreach> 生成 WHERE Id IN (1, 2, 10, 20, 30, 40)。
    • 数据库执行递归查询：
      • 基础查询：找到 Id=1, 2, 10, 20, 30, 40。
      • 递归查询：向上查找父节点（例如 Id=1 的 ParentId=10 已经包含在起点中，无需进一步递归）。
    • 最终返回所有记录。

5. 递归查询的性能分析

5.1 时间复杂度

  • 基础查询：执行 1 次，时间复杂度为 O(N)，其中 N 是 base_permission 表的记录数。
  • 递归查询：执行 D-1 次（D 是树的最大深度），每次迭代需要扫描 base_permission 表，时间复杂度为 O(D * N)。
  • 总时间复杂度：O(D * N)。

5.2 空间复杂度

  • MenuTree 临时结果集存储所有记录，空间复杂度为 O(M)，其中 M 是最终结果集的记录数。

5.3 重复匹配问题

在递归查询中，MenuTree 中的记录会不断增加，INNER JOIN 每次迭代都会尝试匹配所有 ParentId：

  • 重复匹配：ParentId 可能被多次匹配（例如 ParentId=10 在多次迭代中出现）。
  • 数据库行为：数据库不会显式记录“已比对过的记录”，但由于 Id 是唯一的，同一个 Id 只会加入 MenuTree 一次。

优化重复匹配

  • 去重 ParentId：
    1. WITH RECURSIVE MenuTree AS (
    2.     SELECT Id, ParentId, Name, Label
    3.     FROM base_permission
    4.     WHERE Id IN (1, 2)
    5.     UNION ALL
    6.     SELECT DISTINCT p.Id, p.ParentId, p.Name, p.Label
    7.     FROM base_permission p
    8.     INNER JOIN (SELECT DISTINCT ParentId FROM MenuTree WHERE ParentId IS NOT NULL) mt
    9.     ON p.Id = mt.ParentId
    10. )
    11. SELECT * FROM MenuTree;
  • 索引：确保 Id 和 ParentId 有索引，加速 INNER JOIN。

6. 实际案例：权限树查询

6.1 场景描述

在一个权限管理系统中，base_permission 表存储了权限的层次结构。用户可能有多个权限（permssionId），我们需要查找这些权限及其所有父权限。

6.2 实现代码

已在上文给出，这里不再赘述。

6.3 结果分析

  • 输入：permssionId1=1, permssionId2=2。
  • 输出：
    • Id=1, ParentId=10, Name="小明", Label="权限A"
    • Id=2, ParentId=20, Name="小红", Label="权限B"
    • Id=10, ParentId=30, Name="小明爸", Label="权限C"
    • Id=20, ParentId=40, Name="小红妈", Label="权限D"
    • Id=30, ParentId=NULL, Name="小明爷爷", Label="权限E"
    • Id=40, ParentId=NULL, Name="小红外婆", Label="权限F"

7. 注意事项与优化建议

7.1 数据库支持

  • 确保数据库支持 WITH RECURSIVE（MySQL 8.0+、PostgreSQL、SQL Server 等）。
  • 如果不支持，可以使用存储过程或在 Java 代码中实现递归。

7.2 性能优化

  • 索引：为 Id 和 ParentId 创建索引。
  • 去重：使用 DISTINCT 避免重复记录。
  • 分批处理：如果起点记录过多，分批执行递归查询。

7.3 异常处理

  • 空结果：如果 permssionId 列表为空，IN () 会导致语法错误，需在 MyBatis 中添加条件：
    1. <if test="list != null and list.size > 0">
    2.     <foreach collection="list" item="id" open="(" separator="," close=")">
    3.         #{id}
    4.     </foreach>
    5. </if>

8. 总结

SQL 递归查询是处理层次结构数据的强大工具，通过 WITH RECURSIVE 可以轻松实现树形结构的遍历。本文从原理、实现、性能分析到 MyBatis 应用，全面讲解了递归查询的方方面面。希望这篇文章能帮助你在实际开发中更好地使用递归查询，解决复杂的业务需求。