SQL中的递归公共表表达式：探索无限可能

在 SQL 的世界里，递归公共表表达式（Recursive Common Table Expressions，简称 CTE）是一种强大的工具，它允许我们在查询中执行递归操作，从而解决一些传统 SQL 难以处理的问题。

什么是递归 CTE

递归 CTE 通过定义一个初始查询和一个递归查询，不断地将结果集与自身进行联合，直到满足某个终止条件。

递归 CTE 的基本语法如下：

WITH RECURSIVE cte_name (column_list) AS (
    -- 初始查询
    SELECT ...
    UNION ALL
    -- 递归查询
    SELECT ...
    FROM cte_name
    WHERE ...
)
SELECT ...
FROM cte_name;

递归 CTE 有两个主要部分：

初始查询：定义递归的起始点。
递归查询：定义如何将当前结果集与自身联合以生成下一层的结果。

递归 CTE 有一些限制：

递归查询必须引用 CTE 自身。
必须有一个明确的终止条件，以防止无限递归。
UNION ALL用于合并初始查询和递归查询的结果，因为UNION会去除重复行，而递归过程中可能会产生重复。

使用递归 CTE 实现一些常见的算法

递归 CTE 在数据分析中的常见用法是查询层次结构的数据，例如，可以查询一个组织结构中的所有员工及其上级，或者查询一个文件系统中的所有文件及其父目录。

以下是一个简单的递归 CTE 示例，用于查询一个组织结构中的所有员工及其上级：

WITH RECURSIVE org_hierarchy AS (
    -- 初始查询：选择顶层员工
    SELECT employee_id, manager_id, employee_name
    FROM employees
    WHERE manager_id IS NULL

    UNION ALL

    -- 递归查询：选择每个员工的下属
    SELECT e.employee_id, e.manager_id, e.employee_name
    FROM employees e
    INNER JOIN org_hierarchy oh ON e.manager_id = oh.employee_id
)
SELECT * FROM org_hierarchy;

另一方面，递归 CTE 使 SQL 成为了一门图灵完备的语言，因而也可以实现几乎所有算法。

模拟 for 循环

递归 CTE 最简单的算法应用就是生成一系列数字，用于模拟 for 循环：

WITH RECURSIVE count(n) AS (
    SELECT 0
    UNION ALL
    SELECT n + 1
    FROM count
    WHERE n < 20
)
SELECT n
FROM count;

阶乘计算

在公共表中的每一行维护多列数据，就可以在循环的基础上进行更多的操作，例如计算阶乘。

WITH RECURSIVE factorial(n, fact) AS (
    SELECT 1, 1
    UNION ALL
    SELECT n + 1, (n + 1) * fact
    FROM factorial
    WHERE n < 10
)
SELECT n, fact
FROM factorial;

斐波那契数列

生成斐波那契数列时需要维护 a，b 两个变量，再加上表示循环变量的 n，每行需要三列数据。

WITH RECURSIVE fibonacci(n, a, b) AS (
    SELECT 1, 0, 1
    UNION ALL
    SELECT n + 1, b, a + b
    FROM fibonacci
    WHERE n < 20
)
SELECT n, a AS fibonacci_number
FROM fibonacci;

深度优先搜索（DFS）

递归 CTE 的基础是递归能力，当然也可以用于实现深度优先搜索算法，比如查询一个图的某个节点到其他节点的所有路径（图中不能有环）。

CREATE TABLE edges (
    source text,
    destination text
);

INSERT INTO edges (source, destination)
VALUES ('A', 'B'), ('A', 'C'), ('B', 'D'), ('B', 'E'), ('C', 'F'), ('C', 'G');

WITH RECURSIVE dfs AS (
    SELECT source, destination, concat('A', '->', cast(destination as text)) AS path, 1 AS level
    FROM edges
    WHERE source = 'A'
    UNION ALL
    SELECT d.source, e.destination, concat(d.path, '->', e.destination) AS path, d.level + 1
    FROM edges e
    JOIN dfs d ON e.source = d.destination
)
SELECT *
FROM dfs;

动态规划

对于经典的硬币组合数问题，也可以用递归 CTE 来给出动态规划的算法实现。

CREATE TABLE coins (value int);

INSERT INTO coins (value)
VALUES (1), (2), (5);

WITH RECURSIVE coin_combinations(amount, coin, ways) AS (
    SELECT 0 AS amount, 0 AS coin, 1 AS ways
    UNION ALL
    SELECT cc.amount + c.value, c.value, cc.ways
    FROM coin_combinations cc
    JOIN coins c ON cc.amount + c.value <= 10 AND c.value >= cc.coin
)
SELECT amount, sum(ways) AS total_ways
FROM coin_combinations
WHERE amount = 10
GROUP BY amount;

结论

递归 CTE 极大的提高了 SQL 的表达能力，可以用于实现很多有趣的算法，不过由于递归 CTE 的执行会生成并处理大量的中间结果集，对于内存和 CPU 的要求都很高，在生产环境中还是要谨慎使用。