Skip to main content
  1. 经验技巧分享/
  2. thinking in SQL | 废话SQL,思维与实践/

递归查询

··1173 字
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) 分别对应 fabfab_1n

  • 递归引用、终止条件
-- 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 关键字不是必须的。其他如 mysqlDB2 都采用 CTE 语法。

oracle #

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

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

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

语法如下:

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

connect bystart 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 列保持了从迭代初始状态,可以用来做为数据的分组,它是同一分组数据的根。rootlevel 也是非常重要的调试手段。

员工 上级 工资 团队 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;
                                    ....#
                                   ..#*..
                                 ..+####+.
                            .......+####....   +
                           ..##+*##########+.++++
                          .+.##################+.
              .............+###################+.+
              ..++..#.....*#####################+.
             ...+#######++#######################.
          ....+*################################.
 #############################################...
          ....+*################################.
             ...+#######++#######################.
              ..++..#.....*#####################+.
              .............+###################+.+
                          .+.##################+.
                           ..##+*##########+.++++
                            .......+####....   +
                                 ..+####+.
                                   ..#*..
                                    ....#
                                    +.