PostgreSQL 有效地找到线性列表中的最后一个后代

Question

我目前正在尝试从类似结构的链表中有效地检索最后一个 decendet。

基本上有一个带有数据系列的 table，根据某些标准我将其拆分以获得这样的列表

current_id | next_id

例如

1  | 2
2  | 3
3  | 4
4  | NULL
42 | 43
43 | 45
45 | NULL
etc...

会产生像

这样的列表

1 -> 2 -> 3 -> 4

和

42 -> 43 -> 45

现在我想从每个列表中获取第一个和最后一个 ID。

这是我现在拥有的：

WITH RECURSIVE contract(ruid, rdid, rstart_ts, rend_ts) AS ( -- recursive Query to traverse the "linked list" of continuous timestamps
    SELECT start_ts, end_ts FROM track_caps tc
    UNION
    SELECT c.rstart_ts, tc.end_ts AS end_ts0 FROM contract c INNER JOIN track_caps tc ON (tc.start_ts = c.rend_ts AND c.rend_ts IS NOT NULL AND tc.end_ts IS NOT NULL)
),
fcontract AS ( --final step, after traversing the "linked list", pick the largest timestamp found as the end_ts and the smallest as the start_ts
    SELECT DISTINCT ON(start_ts, end_ts) min(rstart_ts) AS start_ts, rend_ts AS end_ts
    FROM (
        SELECT rstart_ts, max(rend_ts) AS rend_ts FROM contract
        GROUP BY rstart_ts
    ) sq
    GROUP BY end_ts
)
SELECT * FROM fcontract
ORDER BY start_ts

在这种情况下，我只使用了时间戳，它适用于给定的数据。

基本上，我只是使用递归查询遍历所有节点，直到到达终点，正如 Whosebug 和其他网站上的许多其他帖子所建议的那样。下一个查询删除所有子步骤和 returns 我想要的，如第一个列表示例：1 | 4

为了说明，递归查询产生的结果集如下所示：

尽管它工作得很好，但它非常占用内存，但是在查看 EXPLAIN ANALYZE 的结果时，这绝对不足为奇。对于大约包含 42,600 行的数据集，递归查询会生成高达 849,542,346 行。现在它实际上应该处理大约 2,000,000 行，但现在使用该解决方案似乎非常不可行。

我只是不正确地使用了递归查询吗？有没有办法减少它产生的数据量？（比如删除子步骤？）或者对于这个问题有更好的单一查询解决方案吗？

Answer 1

主要问题是您的递归查询没有正确过滤由您拥有的模型引起的根节点。所以非递归部分已经 select 是整个 table 然后 Postgres 需要对 table 的每一行进行递归。

为了提高效率，仅 select 查询非递归部分中的根节点。这可以使用：

select t1.current_id, t1.next_id, t1.current_id as root_id
from track_caps t1
where not exists (select * 
                  from track_caps t2
                  where t2.next_id = t1.current_id)

现在这仍然不是很有效（与 "usual" where parent_id is null 设计相比），但至少确保递归不需要处理必要的更多行。

要找到每棵树的根节点，只需 select 将其作为查询的非递归部分中的额外列，并将其转移到递归部分中的每一行。

所以你得到这样的结果：

with recursive contract as (
  select t1.current_id, t1.next_id, t1.current_id as root_id
  from track_caps t1
  where not exists (select * 
                    from track_caps t2
                    where t2.next_id = t1.current_id)
  union 
  select c.current_id, c.next_id, p.root_id
  from track_caps c
    join contract p on c.current_id = p.next_id
  and c.next_id is not null
)
select *
from contract
order by current_id;

在线示例：http://rextester.com/DOABC98823

PostgreSQL 有效地找到线性列表中的最后一个后代

PostgreSQL efficiently find last decendant in linear list

sql

postgresql

recursive-query