[PostgreSQL] 재귀 쿼리

7 분 소요

회사에서 기능을 구현하다 재귀 쿼리를 사용하게 되어 정리한다.

개요

회사 MLOps 시스템에서 다루는 모델은 다른 모델로부터 파생될 수 있다. 베이스 모델을 기점으로 해서 베이스 모델 → 파생 모델 1 → 파생 모델 2 → ...와 같은 체인을 형성할 수 있다는 의미이다. 이를 위해 모델 테이블은 아래와 같은 자기 참조 구조로 설계되어 있다.

CREATE TABLE model (
    id BIGINT PRIMARY KEY,
    name VARCHAR(255),
    parent_model_id BIGINT,
    FOREIGN KEY (parent_model_id) REFERENCES model(id)
);

참고: 자기 참조와 순환 참조

위의 테이블 구조만 놓고 보면, 테이블이 자기 자신을 참조하는 것 같아, 이거 뭔가 순환 참조 아닌가 하는 생각이 들 수 있지만, 엄연히 다르다.

순환 참조: 여러 테이블이 체인처럼 서로를 참조하다가 다시 처음 테이블로 돌아오는 것

자기 참조: 테이블 한 행이 같은 테이블의 다른 행을 참조하는 것

자기 참조의 경우, 계층 구조를 표현하는 표준적인 방법으로, 대부분의 RDBMS에서 지원된다. 표현할 수 있는 관계 예시로는 아래와 같은 것들이 있다.

조직도: 직원 → 상사

카테고리 트리: 하위 카테고리 → 상위 카테고리

파일: 폴더 → 상위 폴더

이런 자기 참조 테이블에서, 재귀 쿼리를 이용하면 모델 체인 혹은 모델 트리 조회를 쉽게 할 수 있다. PostgreSQL 기준으로, 재귀 쿼리를 어떻게 사용할 수 있는지 알아 보자.

재귀 쿼리

아래와 같이 쿼리를 작성하면 된다. CTE가 쿼리 내에서 반복 실행되는 구조다.

WITH RECURSIVE cte_name AS (
    -- 1. Base Case: 재귀의 시작점
    SELECT ... WHERE 조건
    
    UNION ALL
    
    -- 2. Recursive Case: 반복 부분
    SELECT ... 
    FROM 원본테이블
    JOIN cte_name ON ...  -- 자기 자신(CTE)을 참조!
)
SELECT * FROM cte_name;

참고: CTE(Common Table Expression)

더 큰 쿼리에서 사용되기 위한 보조 구문으로, 하나의 쿼리를 위해 필요한 임시 결과 집합

임시 결과 집합에 이름을 붙인 것

루트 모델의 id가 1이라고 할 때, 루트 모델로부터 이어지는 모델 체인을 찾는 쿼리는 아래와 같이 작성할 수 있다.

WITH RECURSIVE model_tree AS (
		-- 1. Base: 루트 모델
		SELECT
				id,
				name,
				parent_model_id,
				0 AS depth -- 시작은 depth 0
		FROM model
		WHERE id = 1 -- 모델 id 1에서 시작
		
		UNION ALL
		
		-- 2~N. Recursive: 자식 찾기
		SELECT 
				m.id,
				m.name,
				m.parent_model_id,
				mt.depth + 1 -- 이전 depth + 1
		FROM model m
		JOIN model_tree mt ON m.parent_model_id = mt.id -- 이전 결과와 조인
) 
SELECT * FROM model_tree
ORDER BY depth ASC, id ASC;

아래와 같은 데이터가 있다고 가정하자.

-- model(id, name, parent_model_id)
model(1, 'yolo-base', NULL) 
model(3, 'yolo-traffic', 1)
model(4, 'yolo-traffic-v2', 3)
model(5, 'yolo-cctv', 1)

그러면, 아래와 같은 과정을 거쳐,

1회차 실행
- (id = 1, depth = 0)인 것 찾음
2회차 실행
- model_tree에 (id = 1, depth = 0) 있음 → 다음 JOIN 시 사용되는 id
- parent_model_id = 1인 것 찾기 → (id = 3, depth = 1), (id = 5, depth = 1) 추가
3회차 실행
- model_tree에 (id = 3, depth = 1), (id = 5, depth = 1) 있음
- parent_model_id = 3인 것 찾기 → (id = 4, depth 2) 추가
4회차 실행
- model_tree에 (id = 4, depth 2) 있음
- parent_model_id = 4인 것 찾기 → 없음
- 종료

아래와 같은 결과를 얻게 된다.

id | name            | depth
| yolo-base       | 0
| yolo-traffic    | 1
| yolo-cctv       | 1
| yolo-traffic-v2 | 2

동작 원리

쿼리 실행 핵심은 다음과 같다.

depth 증가: mt.depth + 1 로 각 재귀 단계마다 depth 증가
종료 조건: 더 이상 JOIN되는 행이 없으면 자동 종료
UNION ALL: 여러 쿼리문을 합쳐서 하나의 쿼리문으로 만들어 줌 → Base Case와 Recursive Case의 결과를 모두 포함하게 됨
참고: UNION vs. UNION ALL
- UNION의 경우, 중복 체크를 위한 정렬 및 비교 과정이 들어가서 느림
- 재귀 쿼리의 경우, 하나의 트리 구조에서 한 모델은 한 번만 나타나기 때문에, 중복 체크는 불필요한 오버헤드임
- 따라서 UNION ALL을 사용하는 것이 일반적

UNION ALL을 통해 모든 쿼리 결과를 위아래로 합쳐 주는 게 핵심인데, 살펴 보면 다음과 같다.

1회차 실행(Base Case)

id	name	depth
1	yolo-base	0

2회차 실행(Recursive)

id	name	depth
3	yolo-traffic	1
5	yolo-cctv	1

3회차 실행(Recursive)

id	name	depth
4	yolo-traffic-v2	2

최종 결과(UNION ALL 병합)

id	name	depth
1	yolo-base	0
3	yolo-traffic	1
5	yolo-cctv	1
4	yolo-traffic-v2	2

활용

시작 레코드와 JOIN 조건만 바꾸면, 상향, 하향 탐색이 가능하다.

하향식 탐색
상향식 탐색

하향식 탐색

특정 모델의 모든 자식 모델을 찾기 위해, 아래와 같은 쿼리를 사용하면 된다.

WITH RECURSIVE tree AS (
    SELECT id, name, parent_model_id, 0 AS depth
    FROM model
    WHERE id = 1  -- 부모(루트)에서 시작
    
    UNION ALL
    
    SELECT m.id, m.name, m.parent_model_id, tree.depth + 1
    FROM model m
    JOIN tree ON tree.id = m.parent_model_id -- tree의 각 행에 대해, model에서 그것을 부모로 가진 행을 찾음 
)
SELECT * FROM tree;

상향식 탐색

특정 모델의 모든 부모 모델을 탐색할 때, 아래와 같은 쿼리를 사용하면 된다.

WITH RECURSIVE tree AS (
    SELECT id, name, parent_model_id, 0 AS depth
    FROM model
    WHERE id = 4  -- 자식(리프)에서 시작
    
    UNION ALL
    
    SELECT m.id, m.name, m.parent_model_id, tree.depth + 1
    FROM model m
    JOIN tree ON tree.parent_model_id = m.id -- tree의 각 행에 대해, 그것이 model의 부모가 되는 행을 찾음
)
SELECT * FROM tree;

말장난 같아 이해하기 힘들 수도 있는데, CTE tree를 나라고 생각하고 보면 좀 이해할 수 있다. 내가 모델의 부모가 되느냐, 내 부모가 모델이 되느냐의 차이(?)이다.

요소	하향식	상향식
시작점 (WHERE)	`WHERE id = 1` (부모)	`WHERE id = 4` (자식)
JOIN 조건	`tree.id = m.parent_model_id`	`tree.parent_model_id = m.id`
의미	“자식의 부모가 나”	“나의 부모가 상대방”

트리 탐색

상향식 탐색과 하향식 탐색을 응용하면, 특정 모델 id를 가지고 트리 탐색도 가능하다.

WITH RECURSIVE 
-- 조상 찾기 (위로 올라가기)
ancestors AS (
    SELECT 
        id, 
        name, 
        parent_model_id,
        0 AS depth  -- 시작점은 0
    FROM model
    WHERE id = $1
    
    UNION ALL
    
    SELECT 
        m.id,
        m.name,
        m.parent_model_id,
        a.depth - 1  -- 위로 갈수록 depth 줄이기: -1, -2, -3, ...
    FROM model m
    JOIN ancestors a ON a.parent_model_id = m.id  -- 부모 찾기
),
-- 후손 찾기 (아래로 내려가기)
descendants AS (
    SELECT 
        id,
        name,
        parent_model_id,
        0 AS depth  -- 시작점은 0
    FROM model
    WHERE id = $1
    
    UNION ALL
    
    SELECT 
        m.id,
        m.name,
        m.parent_model_id,
        d.depth + 1  -- 아래로 갈수록 depth 늘리기: +1, +2, +3, ...
    FROM model m
    JOIN descendants d ON d.id = m.parent_model_id  -- 자식 찾기
)
-- 합치기
SELECT DISTINCT 
    id,
    name,
    parent_model_id,
    depth
FROM (
    SELECT * FROM ancestors
    UNION
    SELECT * FROM descendants
) AS full_tree
ORDER BY depth ASC, id ASC; 

주의

재귀 쿼리를 사용할 때, 아래의 점에 주의하면 좋다.

인덱스 사용: 재귀 탐색 시 JOIN 대상이 되는 컬럼에 인덱스 생성
깊이 제한: 무한 루프 방지
- WHERE depth < 10 등 최대 깊이 제한
순환 참조 방지

순환 참조

데이터에 순환 구조가 있으면 재귀 쿼리는 무한 루프에 빠져 버리게 된다.

위에서 말한 테이블의 순환 참조 구조와는 다른 의미의 순환 참조이다!

예컨대 아래와 같은 데이터가 있는 경우다.

(1, 'model-a', 2),  -- 1의 부모가 2
(2, 'model-b', 3),  -- 2의 부모가 3
(3, 'model-c', 1);  -- 3의 부모가 1 

재귀 쿼리를 실행하면, 불행히도 무한 루프에 빠진다.

1회차: id=1, depth=0
2회차: id=2, depth=1
3회차: id=3, depth=2
4회차: id=1, depth=3
5회차: id=2, depth=4
6회차: id=3, depth=5
7회차: id=1, depth=6

순환 참조를 막기 위한 방법으로 아래와 같은 것들이 있음을 알아 두자.

쿼리 깊이 제한

WITH RECURSIVE tree AS (
    SELECT id, name, parent_model_id, 0 AS depth
    FROM model WHERE id = 1
      
    UNION ALL
      
    SELECT m.id, m.name, m.parent_model_id, tree.depth + 1
    FROM model m
    JOIN tree ON tree.id = m.parent_model_id  -- 하향식 탐색
    WHERE tree.depth < 10  -- 최대 10단계
)
SELECT * FROM tree;

PostgreSQL CYCLE 옵션: PostgreSQL 14 이상만 지원됨

WITH RECURSIVE tree AS (
    SELECT id, name, parent_model_id, 0 AS depth
    FROM model WHERE id = 1
      
    UNION ALL
      
    SELECT m.id, m.name, m.parent_model_id, tree.depth + 1
    FROM model m
    JOIN tree ON tree.parent_model_id = m.id
)
CYCLE id SET is_cycle USING path  -- 순환 감지
SELECT * FROM tree
WHERE NOT is_cycle;  -- 순환 발생 전까지만

방문한 노드 추적: ~~그래프 탐색할 때 나오는 visited 와 닮은 방식~~

WITH RECURSIVE tree AS (
    SELECT 
        id, 
        name, 
        parent_model_id,
        ARRAY[id] AS path,  -- 경로 추적
        0 AS depth
    FROM model WHERE id = 1
      
    UNION ALL
      
    SELECT 
        m.id,
        m.name,
        m.parent_model_id,
        path || m.id,  -- 경로에 추가
        tree.depth + 1
    FROM model m
    JOIN tree ON tree.parent_model_id = m.id
    WHERE NOT (m.id = ANY(tree.path))  -- 이미 방문한 노드면 제외
)
SELECT * FROM tree;

애초에, 어플리케이션 레벨에서 자기 참조 컬럼 값을 설정할 때, 순환 참조가 발생하는지 확인하는 것도 답이다.

func (r *Repository) CreateModel(req *CreateModelRequest) (*domain.Model, error) {
    // parent 설정하려고 한다면 순환 체크
    if req.ParentModelID != nil {
        if err := r.validateParentChain(*req.ParentModelID); err != nil {
            return nil, fmt.Errorf("invalid parent: %w", err)
        }
    }
    
    // INSERT 쿼리 실행
    query := `
        INSERT INTO model (name, parent_model_id, type, ...)
        VALUES ($1, $2, $3, ...)
        RETURNING id
    `
    var newID int64
    err := r.db.QueryRow(query, req.Name, req.ParentModelID, req.Type).Scan(&newID)
    // ...
}

// 부모 체인이 유효한지 체크 (순환 없는지)
func (r *Repository) validateParentChain(parentID int64) error {
    visited := make(map[int64]bool)
    currentID := parentID
    
    for currentID != 0 {
        if visited[currentID] {
            return errors.New("parent chain has circular reference")
        }
        visited[currentID] = true
        
        var nextParentID sql.NullInt64
        err := r.db.QueryRow(
            "SELECT parent_model_id FROM model WHERE id = $1",
            currentID,
        ).Scan(&nextParentID)
        
        if err != nil {
            return fmt.Errorf("parent model not found: %w", err)
        }
        
        if !nextParentID.Valid {
            break
        }
        currentID = nextParentID.Int64
    }
    
    return nil
}

결론

자기 참조와 재귀 쿼리를 잘 이용하면, DB 쿼리만으로 트리 탐색을 쉽게 할 수 있다! 어플리케이션 코드에서 힘들게 연결하지 않아도 된다.
보다 보니까 드는 생각인데, 그래프 탐색과 참 닮았다. 순환 참조 방지하려면 방문 체크를 해야 한다는 것까지..!

Twitter Facebook LinkedIn

Eraser

[PostgreSQL] 재귀 쿼리

개요

재귀 쿼리

동작 원리

활용

하향식 탐색

상향식 탐색

트리 탐색

주의

순환 참조

결론

공유하기

댓글남기기

참고

[Kubernetes] Kubernetes 환경에서 GPU Time Slicing 사용하기 - 1. 개념

[Go] Closure Capture - 2. Closure Capture

[Go] Closure Capture - 1. Closure

[H264] 영상 업로드 실패 사태 분석 - 2. YUV 색공간과 영상 압축