Postgresql递归自联接

Question

我在postgres中的表如下所示,表存储ID之间的链式关系,我希望有一个查询可以产生结果,如"vc1" - >"rc7"或"vc3" - >"rc7",我会仅查询第一列ID1中的ID

ID1     ID2
"vc1"   "vc2"
"vc2"   "vc3"
"vc3"   "vc4"
"vc4"   "rc7"

所以我想在这里提供一些"头"ID,我必须获取尾部(链中的最后一个)id.

Answer 1

这是WITH RECURSIVEPostgreSQL 8.4及更高版本中提供的简单递归公用表expression()的经典用法.

在此处演示:http://sqlfiddle.com/#!12/78e15/9

给定样本数据为SQL:

CREATE TABLE Table1
    ("ID1" text, "ID2" text)
;

INSERT INTO Table1
    ("ID1", "ID2")
VALUES
    ('vc1', 'vc2'),
    ('vc2', 'vc3'),
    ('vc3', 'vc4'),
    ('vc4', 'rc7')
;

你可以写:

WITH RECURSIVE chain(from_id, to_id) AS (
  SELECT NULL, 'vc2'
  UNION
  SELECT c.to_id, t."ID2"
  FROM chain c
  LEFT OUTER JOIN Table1 t ON (t."ID1" = to_id)
  WHERE c.to_id IS NOT NULL
)
SELECT from_id FROM chain WHERE to_id IS NULL;

这样做是迭代地遍历链,将每一行添加到chain表中作为从指针到指针.当遇到"to"引用不存在的行时,它将为该行添加一个null''引用.下一次迭代将注意到'to'引用为null并产生零行,这导致迭代结束.

然后,外部查询通过不存在的to_id来获取已被确定为链的末尾的行.

需要花费一些精力来了解递归CTE.他们要理解的关键事项是:

• 它们以初始查询的输出开始,它们反复与"递归部分"(UNIONor 之后的查询UNION ALL)的输出结合,直到递归部分不添加任何行.这会停止迭代.

• 它们并不是真正的递归,更具迭代性,尽管它们对于您可能使用递归的各种事物都有好处.

所以你基本上是在循环中构建一个表.您不能删除行或更改它们,只能添加新行,因此通常需要一个外部查询来过滤结果以获得所需的结果行.您经常会添加包含中间数据的额外列,您可以使用这些列来跟踪迭代状态,控制停止条件等.

它可以帮助查看未过滤的结果.如果我用简单的方法替换最终的摘要查询,SELECT * FROM chain我可以看到生成的表:

 from_id | to_id 
---------+-------
         | vc2
 vc2     | vc3
 vc3     | vc4
 vc4     | rc7
 rc7     | 
(5 rows)

第一行是手动添加的起始点行,您可以在其中指定要查找的内容 - 在本例中为vc2.每个后续行都是由UNIONed递归项添加的,它对LEFT OUTER JOIN前一个结果执行a 并返回一组新的行,这些行将前一个to_id(现在在from_id列中)与下一个对配对to_id.如果LEFT OUTER JOIN不匹配则to_id则为null,导致下一次调用现在返回行并结束迭代.

因为此查询不会尝试每次只添加最后一行,所以实际上每次迭代都会重复一些工作.为了避免这种情况,您需要使用更像Gordon的方法,但是当您扫描输入表时,还要在前一个深度字段上进行过滤,因此您只加入了最新的行.在实践中,这通常不是必需的,但它可能是非常大的数据集或无法创建适当索引的问题.

可以在关于CTE的PostgreSQL文档中学到更多.

Answer 2

这是使用递归CTE的SQL:

with recursive tr(id1, id2, level) as (
      select t.id1, t.id2, 1 as level
      from t union all
      select t.id1, tr.id2, tr.level + 1
      from t join
           tr
           on t.id2 = tr.id1
     )
select *
from (select tr.*,
             max(level) over (partition by id1) as maxlevel
      from tr
     ) tr
where level = maxlevel;

这是SQLFiddle