Recursive CTE解析

2019-10-17 SQL 阅读量

PostgreSQL递归CTE解析

虽然本文以PG为主，但是递归CTE这个特性在MySQL，MariaDB等RDBMS都提供了。在讲解递归CTE之前先简单介绍下什么是CTE：CTE即Common Table Expression，以With语句开头，功能是在当前SQL执行期间起到一个临时表的作用。如果规划器分析到查询代价很高，还会执行物化提高效率（与PG的物化视图行为类似），CTEs在整个SQL语句执行周期内只会执行一次，CTEs之间还可以有依赖关系。

CTE的例子

给定以下两表，查询同时修了X和Y两门课且成绩均大于等于40的学生信息：

grades表：

栏位 | 类型 | Collation | Nullable | Default
——-+———+———–+———-+———
class | text | | |
sid | integer | | |
grade | integer | | |

student表：

栏位 | 类型 | Collation | Nullable | Default
——+———+———–+———-+———
sid | integer | | |
name | text | | |

WITH ctex AS ( SELECT * FROM grades WHERE grade >= 40 AND class = 'X'),
     ctey AS ( SELECT * FROM grades WHERE grade >= 40 AND class = 'Y')
SELECT ctex.sid, ctex.class, ctex.grade, ctey.class, ctey.grade 
FROM ctex JOIN ctey ON ctex.sid = ctey.sid;

上面的查询我使用了两个CTE，分别查询课程为X和Y且成绩大于等于40的分数记录，然后基于SID做一个inner join，即求得同时修了X和Y的课的学生ID为1和4：

sid | class | grade | class | grade
—–+——-+——-+——-+——-
1 | X | 50 | Y | 70
4 | X | 60 | Y | 100
(2 行记录)

使用CTE能让代码可读性更高，另一方面能提高查询效率，毕竟滥用子查询伤眼效率还不一定高。

递归CTE

本文的重点在递归版本的CTE，虽然是recursive，但用迭代iterative来描述更适合。

想象数据库里有一个储存SQL查询结果的list（以python list为例），递归CTE由锚成员和迭代成员组成。步骤如下：

1.首先执行锚成员查询，将查询的结果存入list的第一个位置

2.然后执行迭代成员的查询，这个迭代成员的查询会使用到其index-1位置的SQL查询结果来计算出一个新的结果，并把结果存入list的第二个位置

3.如此类推，最后通过UNION或UNION ALL合并查询结果（行为类似pandas的concat函数）

下面是一个SQL版range的实现：

WITH RECURSIVE cte AS (
    SELECT 1 as num
    UNION
    SELECT num+1 FROM cte
    WHERE num < 10
)
SELECT * FROM cte;

其中，SELECT 1 AS num是锚成员，首先执行锚成员的查询，存入list，然后执行SELECT num+1 FROM cte，即调用锚成员的查询结果(num = 1)，再加1；然后where num < 10是迭代条件；使用UNION合并所有行（合并list里的所有成员）；上面的代码相当于python的range(1, 11)，结果如下：

num
1
2
3
4
5
6
7
8
9
10
(10 行记录)

更复杂点的例子

首先执行下面的SQL语句创建表和导入数据：

CREATE TABLE employees (
   employee_id serial PRIMARY KEY,
   full_name VARCHAR NOT NULL,
   manager_id INT
);
INSERT INTO employees (
   employee_id,
   full_name,
   manager_id
)
VALUES
   (1, 'Michael North', NULL),
   (2, 'Megan Berry', 1),
   (3, 'Sarah Berry', 1),
   (4, 'Zoe Black', 1),
   (5, 'Tim James', 1),
   (6, 'Bella Tucker', 2),
   (7, 'Ryan Metcalfe', 2),
   (8, 'Max Mills', 2),
   (9, 'Benjamin Glover', 2),
   (10, 'Carolyn Henderson', 3),
   (11, 'Nicola Kelly', 3),
   (12, 'Alexandra Climo', 3),
   (13, 'Dominic King', 3),
   (14, 'Leonard Gray', 4),
   (15, 'Eric Rampling', 4),
   (16, 'Piers Paige', 7),
   (17, 'Ryan Henderson', 7),
   (18, 'Frank Tucker', 8),
   (19, 'Nathan Ferguson', 8),
   (20, 'Kevin Rampling', 8);

然后想找出员工ID为2的雇员的全部下属（下属的下属也被包含在内）

可以使用下面的递归CTE：

WITH RECURSIVE subordinates AS (
   SELECT
      employee_id,
      manager_id,
      full_name
   FROM
      employees
   WHERE
      employee_id = 2
   UNION
      SELECT
         e.employee_id,
         e.manager_id,
         e.full_name
      FROM
         employees e
      INNER JOIN subordinates s ON s.employee_id = e.manager_id
) SELECT
   *
FROM
   subordinates;

首先先选出了employee_id为2的雇员信息作为锚成员的查询结果（只有一条记录），然后在UNION后面的迭代成员从“锚结果 JOIN employees”的结果里查询出manger_id等于2的全部雇员信息，然后再重复迭代成员的查询，查找manager_id为2的雇员的所有下属。

上面的查询等价于下面的CTE：

WITH cte AS ( SELECT employee_id, manager_id, full_name FROM employees WHERE employee_id = 2),
     cte1 AS ( SELECT e.employee_id, e.manager_id, e.full_name FROM employees e
         JOIN cte s ON s.employee_id = e.manager_id),
     cte2 AS ( SELECT e.employee_id, e.manager_id, e.full_name FROM employees e
         JOIN cte1 s ON s.employee_id = e.manager_id)
SELECT * FROM cte UNION SELECT * FROM cte1 UNION SELECT * FROM cte2 ORDER BY employee_id;

为了达到同样的目的，使用嵌套CTE需要写3个CTE（还是已知employee_id为2的这个人的下属有多少层的前提下），而使用递归CTE可以简化代码，并实现普通查询无法实现的查询。