PostgreSQL高效地查找線性列表中的最後一個decendant

我目前嘗試從結構鏈表中有效地檢索最後一個分數。PostgreSQL高效地查找線性列表中的最後一個decendant

本質上有一個數據系列的表，一定的標準我分裂後拿到這樣

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

在這種情況下，我只是用它的時間戳爲給定的數據很好地工作。

基本上我只是使用遍歷所有節點的遞歸查詢，直到它到達結尾，正如StackOverflow和其他網站上的許多其他帖子所建議的。下一個查詢將刪除所有子步驟，並返回我想要的內容，如第一個列表示例中所示：1 | 4

爲了方便說明，由遞歸查詢設置產生的結果是這樣的：

隨着很好，因爲它的工作原理，這是相當然而內存豬在看的結果時，這是絕對令人吃驚EXPLAIN ANALYZE。對於大約42,600行的數據集，遞歸查詢產生了高達849,542,346行。現在它實際上應該處理大約2,000,000行，但現在這個解決方案看起來非常不可行。

我只是不正確地使用遞歸查詢？有沒有辦法減少它產生的數據量？（如刪除子步驟？）或者是否有更好的單一查詢解決方案來解決這個問題？

來源

2017-03-06 pfannkuchen_gesicht

也許我失去了一些東西，但不是簡單地'在那裏NEXT_ID不null'？ –

@a_horse_with_no_name但是我如何獲得屬於使用where子句選擇的最後一個id的列表的第一個id？ –

主要問題是您的遞歸查詢不能正確地過濾由您擁有的模型導致的根節點。所以非遞歸部分已經選擇了整個表，然後Postgres需要遞歸表中的每一行。

爲了使效率更高，請僅在查詢的非遞歸部分選擇根節點。這是可以做到用：

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)

現在還不是十分有效的（相對於「通常」設計），但至少可以確保遞歸併不需要處理那麼多需要行。

要查找每個樹的根節點，只需在查詢的非遞歸部分中選擇它作爲額外的列，並將其傳遞到遞歸部分中的每一行。

所以你風像這樣的東西：

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

來源

2017-03-06 22:25:53

還不錯，它佔了行數的一半。但是你提到了其他的「設計」。我不會在那裏面對幾乎相同的問題嗎？在那裏，我只需輕鬆獲得第一個節點，而不得不搜索最後一個節點。在這裏我有相反的意思。獲取最後一個節點很簡單，但我必須在某種意義上檢索第一個節點的列表。 –

PostgreSQL高效地查找線性列表中的最後一個decendant

回答

相關問題