↓跳到主要内容
  1. Skills/
  2. thinking in SQL | 废话SQL，思维与实践/

递归查询

··字数 4588·10 分钟
sql 概念 sql技巧
目录

递归，是一种特殊形式的循环。在编程语言中，递归通过函数自身重复调用（自已调用自己）来实现，并在重复调用的过程设置一个退出条件，以保证递归调用不会进行死循环，或者调用深度不超过编程语言运行时所能支持的最大堆栈深度。 本文将介绍如何编写递归形式的SQL查询，不是学习数学，不用担心。

通常在学习编程语言的递归实现时，都以 Fabonacci sequence（斐波那契数列） 为例子。

文中并没有严格区分 递归（recursion）、循环迭代（iteration）的定义，两者在数学上是有区别的。

斐波那契数列的数学公式：

F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）

仅演示，非最优实现

在 python 中，使用递归的方式实现如下：

~/Users/youwu.today
➜  python3
Python 3.9.12 (main, Mar 26 2022, 15:51:15)
[Clang 13.1.6 (clang-1316.0.21.2)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> def fab(n=10):
...     f = n
...     if n == 0 or n == 1:
...             return n
...     if n > 1:
...             f = fab(n-1) + fab(n-2)
...     return f
...
>>> fab(1)
1
>>> fab(5)
5
>>> fab(6)
8
>>> fab(10)
55
>>> [fab(x) for x in range(10)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
>>>

使用普通的 for 循环实现。

>>> def fab_loop(n=10):
... 	a, b = 0, 1
... 	r = a
... 	for i in range(n):
... 		a, b = b , a + b
... 		r = a
... 	return r
...
>>> [fab_loop(x) for x in range(10)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

通过上面例子，递归实现有两个特点：

  1. 初始状态
  2. 退出循环的终止条件
  3. （非边界状态）每一次迭代的逻辑是可复用

若使用SQL查询（不是在过程式的PL/SQL中，无法使用for循环控制语句；也没有函数递归调用支持）来实现，也必须满足以上各点。

后面将看到各个常见数据库中，如何编写递归形式的SQL。各数据库几乎无一例外的利用了 common table expression with 表达式来实现查询。

在 postgres 中实现递归查询 #

以斐波纳契数列为例。

-- coded in postgres 14
with recursive rec(fab, fab_1, n) as
( 
  values(0, 1, 1)
  union all
  select fab_1, fab + fab_1, n + 1
  from   rec
  where  n < 10
)
select *
from   rec;
 fab | n
-----+----
   0 |  0
   1 |  1
   1 |  2
   2 |  3
   3 |  4
   5 |  5
   8 |  6
  13 |  7
  21 |  8
  34 |  9
  55 | 10
(11 rows)

postgres 14 文档 7.8.2. Recursive Queries ，给出了详细说明。

  • 递归查询的SQL语句结构
with recursive cte_name(column, level [,...]) as
(
	initial-select
	union all
	recursive-select
)
select 
from   cte_name

分为 with recursive cte_name(column, level [,...])( ... union all...) with 表达式、initial-select 初始子查询、recursive-select 递归子查询 三个部分。

  • with 表达式 CTE

使用 recursive 关键字，来声明 with 表达式 所定义的查询可以在递归子查询（recursive-select）子语中被引用（通过cte的名称）。初始子查询 （initial-select） 与递归子查询（recursive-select）的选择列的列数、数据类型要与 cte 中定义的列数与数据类型一致。

  • 初始查询
with recursive rec(fab, fab_1, n) as
( 
  values(0, 1, 1)
  union all
  ...
)
...

初始子查询（initial-select）values(0, 1, 1) 规定了递归迭代的初始数据行，(0, 1, 1) 分别对应 fab，fab_1，n。

  • 递归引用、终止条件
-- coded in postgres 14
with recursive rec(fab, fab_1, n) as
( 
  ...
  union all
  select fab_1, fab + fab_1, n + 1
  from   rec
  where  n < 10
  ...
)
...

递归子查询（recursive-select）子语定义每次迭代的数据操作，并通 n < 10 来限制迭代的次数（或者称为深度），即迭代终止退出条件。注意 n < 10 声明的是终止前的条件，因n+1 的存在，查询结果中会包含 n=10 的行。UNION [ALL] 将初始子查询 （initial-select） 与递归子查询（recursive-select）两部的结果集连接起来。

如果第一遍没看懂本段递归SQL，没关系，有悟花了好多年才搞明白。

在结束本节之前，再次梳理、总结递归SQL的逻辑过程（本段描述参考了sqlite中的关于 递归查询的说明 ）：

  1. 执行初始子查询（initial-select）的结果添加到输出结果队列
  2. 若队列非空
    1. 从队列中取出一行
    2. 将该行插入递归表
    3. 假设该单行是递归表中的唯一行并运行递归子查询，将所有结果添加到队列中。

各知名数据库产品的递归查询实践 #

sqlite #

以斐波纳契数列（n=10）为例。

with rec(fab, fab_1, n) as
( values(0, 1, 0)
  union all
  select fab_1, fab + fab_1, n + 1
  from   rec
  where  n < 10
)
select fab, n
from   rec;

sqlite 中，与 postgres 数据库中的实现相同，只是recursive 关键字不是必须的。其他如 mysql、DB2 都采用 CTE 语法。

oracle #

oracle 数据库除了可以使用 CTE 方式外，还有另一种特有的函数用法。

oracle 数据库将递归查询称为 hierarchical queries（分层查询） 。既然是分层，那边就会有根、叶子、父子关系、层级等。

CTE 方式不再敖述。本小节主要讲解 oracle 专有函数。

语法如下：

connect by [nocycle] 条件语句
[start with] 条件语句

connect by、start with 子语的顺序谁先谁后都可以。 start with 指定了迭代的起始位置，connect by 指定迭代层次结构的父行和子行之间的关系，其中使用到了 piror 操作符来标记父行。关于语法的详细说明，可以见官方SQL手册 Hierarchical Queries 。

比起 with 语句的 的 CTE，connect by 函数比较难以掌握，也不通用化。如果你编写的SQL有通用化需求，或者需要移动到其它数据库产品，建议使用 CTE 来实现递归。

为了配合 connect by 递归查询，oracle 数据库还提供了若干个 Hierarchical Query Pseudocolumns（分层查询伪列） 与函数以辅助控制。

CONNECT_BY_ISCYCLE 伪列
，当前行既是子行又是父行时，CONNECT_BY_ISCYCLE 伪列返回 1，否则返回 0，与与《分组聚合》中的 grouping函数 功能类似。
CONNECT_BY_ISLEAF 伪列
当前行是树叶节点时，CONNECT_BY_ISLEAF 返回 1，否则为 0，它的值表示该分支的递归迭代是否结束。因为最后一层的行，就是树叶子。
LEVEL 伪列
LEVEL 伪列记录了从初始行（根）开始，按照 connect by 条件关联到各层级，从根开始为1，每迭代一次，LEVEL列的值增加 1。
SYS_CONNECT_BY_PATH
本函数是在分层查询中，可以指定某字段按分层的顺序拼接起来，有点类似于分组字符串拼接。在机构树的递归中，使用 SYS_CONNECT_BY_PATH(机构名称, '->')，可以得到类似于 根机构->一级分支->二级分支->...->叶子机构形式的字符串，不过要小心这个结果是否会超过 oracle数据库字符串字段的最大长度（4000字节）。
CONNECT_BY_ROOT 函数
分层查询并不局限于只有一个根，从多个起始点开始迭代也是可以的。比如机构树数，我们从一批“一级分支”出发，找到每一个“一级分支”下所有的叶子机构。若使用SYS_CONNECT_BY_PATH 将机构名称拼接起来，可以发现，连接串最前位置的名称，它所对应的行就是 level = 1 的行，根行。只不过 LEVEL 只能用来标识当前行的层次深度，而 CONNECT_BY_ROOT 是用来告诉我们，当前行归属的根（根据父子关系向父级找到 level = 1）行的某个字段值。CONNECT_BY_ROOT 函数较为特殊，调用时不能使用括号，只能用 CONNECT_BY_ROOT 字段名 的形式，更像是修饰型声明关键字。

各数据库产品关于递归查询的说明 #

数据库 说明
postgres 14 Recursive Queries
sqlite Recursive Common Table Expressions
oracle 11g hierarchical queries
oracle 21c hierarchical queries
mysql 8 Recursive Common Table Expressions

递归查询的用途 #

文章开头使用了斐波纳契数列为例，演示如果使用SQL实现递归循环。但循环仅仅是功能，需要转换为实际的应用才能发挥价值。

创建多行数据 #

递归查询的结果一般情况下都是多行的，通过观察斐波纳契数列的递归SQL查询，发现列 n 正好是一个自增1的序列。可以通过简化，得到:

-- coded in postgres 14
with recursive rec(n) as
( values(1)
  union all
	select n + 1
	from   rec
	where  n < 10
)
select n
from   rec;
 n
----
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
(10 rows)

当你不知道命令行工具 seq 可以为我们创建序列，又需要一个序列时，即可以通过本例的方式使用SQL来快速创建。甚至在为数据表创建测试数据时，可以使用本方法来生成数据行数精确的数据集。当然，在 postgres 和 sqlite 中，可以使用 generate_series 表函数来达到目的。

树型父子结构数据 #

比如在“麻将扑克”部门，有“筒”团队，“萬”团队，“桃”团队，经历了人事调动，部分“筒”员工去到了“萬”团队，而加入了个人“桃”员工，以员工表的形式记录如下：

员工 上级 工资
🀇 10000
🀈 🀇 8000
🀉 🀊 8000
🀊 🀇 8000
🀋 🀇 8000
🀙 11000
🀚 🀇 8000
🀛 🀙 8000
🀜 🀙 8000
🀝 🀛 7000
🂡 10000
🂢 🂡 8000
🂣 🂡 8500
🂤 🂡 9000
🂥 🀙 8000

上述示例，从上级到员工之间，有直属、有间接管理（二级以上），若此时想知道每一个团队的工资总和、平均数，该如何统计？

根据本文中的递归查询，我们可以先从最上层的员工入手（根，团队长），迭代找出直接下级，以此类推，直至无下级（叶子节点）。

-- coded in postgres 14
with recursive
  emp(employee, manager, salary, root, level) as
(
  select "员工"
       , "上级"
       , "工资"
       , "员工"
       , 1 
  from   "员工表"
  where  "上级" is null
  union all
  select "员工表"."员工"
       , "员工表"."上级"
       , "员工表"."工资"
       , emp.root
       , emp.level + 1
  from   emp
  inner  join "员工表"
  on     emp.employee = "员工表"."上级"
)
select employee "员工"
     , manager  "上级"
     , salary   "工资"
     , root     "团队"
     , level
from   emp
order  by root, level, employee;

root 列保持了从迭代初始状态，可以用来做为数据的分组，它是同一分组数据的根。root、level 也是非常重要的调试手段。

员工 上级 工资 团队 level
🀇 10000 🀇 1
🀈 🀇 8000 🀇 2
🀊 🀇 8000 🀇 2
🀋 🀇 8000 🀇 2
🀚 🀇 8000 🀇 2
🀉 🀊 8000 🀇 3
🀙 11000 🀙 1
🀛 🀙 8000 🀙 2
🀜 🀙 8000 🀙 2
🂥 🀙 8000 🀙 2
🀝 🀛 7000 🀙 3
🂡 10000 🂡 1
🂢 🂡 8000 🂡 2
🂣 🂡 8500 🂡 2
🂤 🂡 9000 🂡 2

数据集从父子结构的员工表转为按团队（同一个root，以队长表示团队）为分组的人员表，那么计算团队的工资总和、平均工资就非常轻松了。

-- coded in postgres 14
-- 将上例的外层查询改为 group by 分组聚合
with recursive
  emp(employee, manager, salary, root, level) as
(
  ...
)
select root     "团队"
     , sum(salary)   "工资总和"
     , avg(salary)   "平均工资"
from   emp
group  by root;
团队 工资总和 平均工资
🂡 35500 8875.0000000000000000
🀙 42000 8400.0000000000000000
🀇 50000 8333.3333333333333333

有时，还也可以根据数据中的树型父子引用关系，构建结构图，如组织机构图。

with recursive
  emp(employee, manager, salary, root, level, path1, path2) as
(
  select "员工"
       , "上级"
       , "工资"
       , "员工"
       , 1
			 , "员工"
			 , "员工"
  from   "员工表"
  where  "上级" is null
  union all
  select "员工表"."员工"
       , "员工表"."上级"
       , "员工表"."工资"
       , emp.root
       , emp.level + 1
       , cast(concat(emp.path1,'->',"员工表"."员工") as varchar(255))
       , cast(concat(rpad('└', emp.level*2, '─'),'>',"员工表"."员工") as varchar(255))
  from   emp
  inner  join "员工表"
  on     emp.employee = "员工表"."上级"
)
select employee "员工"
     , root
     , level
		 , path1
		 , path2
from   emp
order  by root, level, employee;
员工 root level path1 path2
🀇 🀇 1 🀇 🀇
🀈 🀇 2 🀇->🀈 └─>🀈
🀊 🀇 2 🀇->🀊 └─>🀊
🀋 🀇 2 🀇->🀋 └─>🀋
🀚 🀇 2 🀇->🀚 └─>🀚
🀉 🀇 3 🀇->🀊->🀉 └───>🀉
🀙 🀙 1 🀙 🀙
🀛 🀙 2 🀙->🀛 └─>🀛
🀜 🀙 2 🀙->🀜 └─>🀜
🂥 🀙 2 🀙->🂥 └─>🂥
🀝 🀙 3 🀙->🀛->🀝 └───>🀝
🂡 🂡 1 🂡 🂡
🂢 🂡 2 🂡->🂢 └─>🂢
🂣 🂡 2 🂡->🂣 └─>🂣
🂤 🂡 2 🂡->🂤 └─>🂤

画对称图形 #

来自 sqlite 文档， Outlandish Recursive Query Examples 。

-- sqlite 3.37.0
WITH RECURSIVE
  xaxis(x) AS (VALUES(-2.0) UNION ALL SELECT x+0.05 FROM xaxis WHERE x<1.2),
  yaxis(y) AS (VALUES(-1.0) UNION ALL SELECT y+0.1 FROM yaxis WHERE y<1.0),
  m(iter, cx, cy, x, y) AS (
    SELECT 0, x, y, 0.0, 0.0 FROM xaxis, yaxis
    UNION ALL
    SELECT iter+1, cx, cy, x*x-y*y + cx, 2.0*x*y + cy FROM m 
     WHERE (x*x + y*y) < 4.0 AND iter<28
  ),
  m2(iter, cx, cy) AS (
    SELECT max(iter), cx, cy FROM m GROUP BY cx, cy
  ),
  a(t) AS (
    SELECT group_concat( substr(' .+*#', 1+min(iter/7,4), 1), '') 
    FROM m2 GROUP BY cy
  )
SELECT group_concat(rtrim(t),x'0a') FROM a;

                                    ....#
                                   ..#*..
                                 ..+####+.
                            .......+####....   +
                           ..##+*##########+.++++
                          .+.##################+.
              .............+###################+.+
              ..++..#.....*#####################+.
             ...+#######++#######################.
          ....+*################################.
 #############################################...
          ....+*################################.
             ...+#######++#######################.
              ..++..#.....*#####################+.
              .............+###################+.+
                          .+.##################+.
                           ..##+*##########+.++++
                            .......+####....   +
                                 ..+####+.
                                   ..#*..
                                    ....#
                                    +.
↑