sql - 如何使用 WITH RECURSIVE 子句进行选择

Question

我已经用谷歌搜索并阅读了一些文章，比如这个 postgreSQL 手册页或这个博客页面，并尝试自己进行查询并取得了一定的成功（其中一部分挂起，而其他的工作又好又快），但到目前为止我还不能完全理解这是怎么回事魔术作品。

任何人都可以给出非常清楚的解释来展示这种查询语义和执行过程，更好地基于典型样本，如阶乘计算或(id,parent_id,name)表中的全树扩展？

with recursive为了进行良好的查询，应该知道哪些基本准则和典型错误？

score 69 · Accepted Answer

首先，让我们尝试简化和澄清手册页上给出的算法描述。为了简化它，现在（和以后）只考虑union allin子句：with recursiveunion

WITH RECURSIVE pseudo-entity-name(column-names) AS (
    Initial-SELECT
UNION ALL
    Recursive-SELECT using pseudo-entity-name
)
Outer-SELECT using pseudo-entity-name

为了澄清它，让我们用伪代码描述查询执行过程：

working-recordset = result of Initial-SELECT

append working-recordset to empty outer-recordset

while( working-recordset is not empty ) begin

    new working-recordset = result of Recursive-SELECT 
        taking previous working-recordset as pseudo-entity-name

    append working-recordset to outer-recordset

end

overall-result = result of Outer-SELECT 
    taking outer-recordset as pseudo-entity-name

甚至更短——数据库引擎执行初始选择，将其结果行作为工作集。然后它对工作集重复执行递归选择，每次将工作集的内容替换为获得的查询结果。当递归选择返回空集时，此过程结束。并且首先通过初始选择然后通过递归选择给出的所有结果行被收集并提供给外部选择，该结果成为整体查询结果。

此查询正在计算3 的阶乘：

WITH RECURSIVE factorial(F,n) AS (
    SELECT 1 F, 3 n
UNION ALL
    SELECT F*n F, n-1 n from factorial where n>1
)
SELECT F from factorial where n=1

初始选择SELECT 1 F, 3 n为我们提供初始值：3 为参数，1 为函数值。
递归选择SELECT F*n F, n-1 n from factorial where n>1表明，每次我们需要将最后一个函数值乘以最后一个参数值并递减参数值。
数据库引擎像这样执行它：

首先它执行 initail select，它给出了工作记录集的初始状态：

F | n
--+--
1 | 3

然后它用递归查询转换工作记录集并获得它的第二个状态：

F | n
--+--
3 | 2

然后是第三个状态：

F | n
--+--
6 | 1

在第三种状态下，递归选择中没有遵循n>1条件的行，因此工作集是循环退出。

外部记录集现在包含由初始和递归选择返回的所有行：

F | n
--+--
1 | 3
3 | 2
6 | 1

外部选择过滤掉外部记录集中的所有中间结果，只显示最终的阶乘值，它成为整体查询结果：

F 
--
6

现在让我们考虑一下表forest(id,parent_id,name)：

id | parent_id | name
---+-----------+-----------------
1  |           | item 1
2  | 1         | subitem 1.1
3  | 1         | subitem 1.2
4  | 1         | subitem 1.3
5  | 3         | subsubitem 1.2.1
6  |           | item 2
7  | 6         | subitem 2.1
8  |           | item 3

这里的“扩展完整树”意味着在计算它们的级别和（可能）路径时以人类可读的深度优先顺序对树项进行排序。如果不使用 WITH RECURSIVE 子句（或 Oracle CONNECT BY 子句，PostgreSQL 不支持），这两项任务（正确排序和计算级别或路径）都无法在一个（甚至任何恒定数量的）SELECT 中解决。但是这个递归查询可以完成这项工作（嗯，几乎可以，请参见下面的注释）：

WITH RECURSIVE fulltree(id,parent_id,level,name,path) AS (
    SELECT id, parent_id, 1 as level, name, name||'' as path from forest where parent_id is null
UNION ALL
    SELECT t.id, t.parent_id, ft.level+1 as level, t.name, ft.path||' / '||t.name as path
    from forest t, fulltree ft where t.parent_id = ft.id
)
SELECT * from fulltree order by path

数据库引擎像这样执行它：

首先，它执行 initail select，它给出了表中所有最高级别的项目（根）forest：

id | parent_id | level | name             | path
---+-----------+-------+------------------+----------------------------------------
1  |           | 1     | item 1           | item 1
8  |           | 1     | item 3           | item 3
6  |           | 1     | item 2           | item 2

然后，它执行递归选择，它给出了forest表中的所有第二级项目：

id | parent_id | level | name             | path
---+-----------+-------+------------------+----------------------------------------
2  | 1         | 2     | subitem 1.1      | item 1 / subitem 1.1
3  | 1         | 2     | subitem 1.2      | item 1 / subitem 1.2
4  | 1         | 2     | subitem 1.3      | item 1 / subitem 1.3
7  | 6         | 2     | subitem 2.1      | item 2 / subitem 2.1

然后，它再次执行递归选择，检索 3d 级别项目：

id | parent_id | level | name             | path
---+-----------+-------+------------------+----------------------------------------
5  | 3         | 3     | subsubitem 1.2.1 | item 1 / subitem 1.2 / subsubitem 1.2.1

现在它再次执行递归选择，试图检索第 4 级项目，但没有它们，所以循环退出。

外部 SELECT 设置正确的人类可读行顺序，按路径列排序：

id | parent_id | level | name             | path
---+-----------+-------+------------------+----------------------------------------
1  |           | 1     | item 1           | item 1
2  | 1         | 2     | subitem 1.1      | item 1 / subitem 1.1
3  | 1         | 2     | subitem 1.2      | item 1 / subitem 1.2
5  | 3         | 3     | subsubitem 1.2.1 | item 1 / subitem 1.2 / subsubitem 1.2.1
4  | 1         | 2     | subitem 1.3      | item 1 / subitem 1.3
6  |           | 1     | item 2           | item 2
7  | 6         | 2     | subitem 2.1      | item 2 / subitem 2.1
8  |           | 1     | item 3           | item 3

注意/：仅当项目名称中没有标点符号排序规则时，结果行顺序才会保持正确。如果我们在中重命名Item 2，Item 1 *它将打破行顺序，位于Item 1及其后代之间。
更稳定的解决方案是在查询中使用制表符 ( E'\t') 作为路径分隔符（稍后可以用更具可读性的路径分隔符替换：在外部选择中，在显示给人类之前等）。制表符分隔的路径将保持正确的顺序，直到项目名称中有制表符或控制字符 - 可以轻松检查和排除，而不会失去可用性。

修改最后一个查询以扩展任意子树非常简单 - 您只需将条件替换parent_id is null为perent_id=1（例如）。请注意，此查询变体将返回相对于 Item 1.

现在谈谈典型的错误。递归查询最显着的典型错误是在递归选择中定义了错误的停止条件，这会导致无限循环。

例如，如果我们where n>1在上面的阶乘示例中省略了条件，则执行递归选择将永远不会给出一个空集（因为我们没有过滤掉单行的条件）并且循环将无限继续。

这是您的某些查询挂起的最可能原因（另一个非特定但仍然可能的原因是非常无效的选择，它在有限但很长时间内执行）。

据我所知，没有太多特定于 RECURSIVE 的查询指南可以提及。但我想建议（相当明显）一步一步的递归查询构建过程。

分别构建和调试您的初始选择。
用脚手架 WITH RECURSIVE 将其包裹起来，
然后开始构建和调试您的递归选择。

推荐的脚手架结构是这样的：

WITH RECURSIVE rec( <Your column names> ) AS (
    <Your ready and working initial SELECT>
UNION ALL
    <Recursive SELECT that you are debugging now>
)
SELECT * from rec limit 1000

这个最简单的外部选择将输出整个外部记录集，正如我们所知，它包含来自初始选择的所有输出行以及每个循环中以原始输出顺序执行的 recusive select 的执行 - 就像上面的示例一样！该limit 1000部件将防止挂起，用超大输出代替它，您将能够在其中看到错过的停止点。

在调试初始和递归选择构建并调试您的外部选择之后。

现在要提到的最后一件事 - usingunion而不是union allinwith recursive子句的区别。它引入了行唯一性约束，导致我们的执行伪代码中有两行：

working-recordset = result of Initial-SELECT

discard duplicate rows from working-recordset /*union-specific*/

append working-recordset to empty outer-recordset

while( working-recordset is not empty ) begin

    new working-recordset = result of Recursive-SELECT 
        taking previous working-recordset as pseudo-entity-name

    discard duplicate rows and rows that have duplicates in outer-recordset 
        from working-recordset /*union-specific*/

    append working-recordset to outer-recordset

end

overall-result = result of Outer-SELECT 
    taking outer-recordset as pseudo-entity-name

sql - 如何使用 WITH RECURSIVE 子句进行选择

1 回答 1

Related

Reference