PostgreSQL은 선형 목록에서 마지막 decendant를 효율적으로 찾습니다.

Question

현재 구조와 같은 링크 된 목록에서 마지막 decendet을 효율적으로 검색하려고합니다. |

는 기본적으로 나는이

current_id 같은 목록을 얻으려면 그것을 분할 특정 기준으로, 데이터 계열이있는 테이블있다 > - 2 -> 3 -> 4

및

42 -> 43 -> 45

next_id 예

는

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

는

1과 같이 나열 초래

이제 각 목록에서 첫 번째와 마지막 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

는 재귀 쿼리가 설정 한 생산 결과는 다음과 같습니다

1 | 2 
2 | 3 
3 | 4 
1 | 3 
2 | 4 
1 | 4 

을 같이 잘 작동으로,이 결과를 볼 때 절대적으로 놀랍지 그러나 꽤 메모리 돼지입니다 EXPLAIN ANALYZE. 대략 42,600 개의 행으로 구성된 데이터 집합의 경우 재귀 쿼리는 무려 849,542,346 개의 행을 생성합니다. 이제 실제로 실제로 약 2,000,000 행을 처리하기로되어 있었지만 지금 당장은이 솔루션을 사용하면 매우 실용적이지 않은 것처럼 보입니다.

부적절하게 재귀 쿼리를 사용 했습니까? 생성하는 데이터의 양을 줄이는 방법이 있습니까? (하위 단계 제거와 같은) 또는이 문제에 대한 단일 쿼리 솔루션이 있습니까?

Answer 1

주된 문제점은 재귀 쿼리가 가지고있는 모델로 인해 루트 노드를 올바르게 필터링하지 않는다는 것입니다. 따라서 비 재귀적인 부분은 이미 테이블을 테이블로 선택한 다음, Postgres는 테이블의 모든 행마다 재귀해야합니다.

더 효율적으로 만들려면 쿼리의 비 재귀 부분에서 루트 노드 만 선택하십시오. 이제이 (이하 "보통"where parent_id is null 디자인에 비해) 여전히 매우 효율적이지 않다

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