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

Question

关闭。这个问题需要更多focused .它目前不接受答案。












想改善这个问题吗？更新问题，使其仅关注一个问题 editing this post .

7年前关闭。




Improve this question




我用谷歌搜索并阅读了一些文章，例如
this postgreSQL manual page
或 this blog page
并尝试自己进行查询并取得了一定的成功(其中一部分挂起，而其他一些运行良好且快速)，
但到目前为止我还不能完全理解这种魔法是如何工作的。

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

以及人们应该知道的基本准则和典型错误是什么with recursive查询？

Answer 1

首先，让我们尝试简化和澄清 manual page 上给出的算法描述。 .为简化起见，仅考虑 union all在 with recursive现在的条款(和 union 以后):

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 的所有最高级别的项目(根)。 table :

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 的所有第 2 级项目。 table :

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 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

这个最简单的外部选择将输出整个外部记录集，正如我们所知，它包含来自初始选择的所有输出行和循环中的每次递归选择的执行，它们的原始输出顺序 - 就像上面的示例一样! limit 1000部分将防止悬挂，用超大输出替换它，您将能够看到错过的停止点。

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

现在要提到的最后一件事 - 使用 的区别union 而不是 union all在 with 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