如何选择使用WITH RECURSIVE子句

Question

我已经谷歌搜索并阅读了一些像 这个postgreSQL手册页 或这个博客页面的文章, 并尝试自己成功地进行查询(其中一部分挂起,而其他人工作良好和快速),但到目前为止,我无法完全理解这是怎么回事魔术作品.

任何人都可以给出非常明确的解释来证明这样的查询语义和执行过程,更好地基于典型的样本,如因子计算或从(id,parent_id,name)表中完全树扩展？

什么是基本的指导和常见的错误,人们应该知道如何做出好的with recursive疑问？

Answer 1

首先,让我们尝试简化和阐明手册页上给出的算法描述.为了简化,只考虑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在递归选择中没有跟随条件的行,所以第四个工作集是循环退出.

外部记录集现在包含所有行,由initial和recursive select返回:

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及其后代.
更稳定的解决方案是使用tab character(E'\t')作为查询中的路径分隔符(稍后可以用更可读的路径分隔符替换:在外部选择中,在移位到人类之前等).制表符分隔的路径将保持正确的顺序,直到项目名称中有选项卡或控制字符 - 可以轻松检查和排除,而不会丢失可用性.

修改最后一个查询以扩展任意子树非常简单 - 您只需parent_id is null要用perent_id=1(例如)替换条件.请注意,此查询变量将返回相对于的 所有级别和路径Item 1.

现在关于典型的错误.特定于递归查询的最显着的典型错误是在递归选择中定义不良停止条件,这导致无限循环.

例如,如果我们where n>1在上面的factorial示例中省略条件,则递归select的执行将永远不会给出空集(因为我们没有条件来过滤掉单行)并且循环将无限地继续.

这是你的一些查询挂起的最可能的原因(另一个非特定但仍然可能的原因是非常无效的选择,它在有限但非常长的时间内执行).

有没有太多的递归查询特定guidlines说,据我所知.但我想建议(相当明显)逐步递归查询构建过程.

• 单独构建和调试初始选择.

• 使用带有RECURSIVE构造的脚手架包裹它,
  并开始构建和调试递归选择.

推荐的scuffolding结构是这样的:

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

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

• 调试初始和递归后选择构建并调试外部选择.

现在最后要提到的是 - 使用union而不是使用union allin 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