SQL) 재귀 CTE

프로그래머스 SQL 고득점 kit를 풀던 중 재귀 CTE를 사용하는 문제가 있어 공부한 내용을 정리해보고자 한다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/301651

해당 문제이다.

 

프로그래머스

 

CTE란?

WITH 키워드로 선언하는 나타내는 재사용 가능한 서브쿼리로 프로그래밍 언어로 따지면 일종의 메서드로 볼 수 있다.

CTE는 FROM절, JOIN 절, WHERE 절 등 다양한 위치에서 쿼리의 일부처럼 사용할 수 있다.

또한 쿼리 내에서 여러번 참조할 수 있어 중복을 피하는데 유용하다.

 

CTE의 기본 구문

WITH CTE_name AS (
    -- CTE를 정의하는 쿼리
    SELECT column1, column2
    FROM table_name
    WHERE condition
)
-- CTE를 참조하는 쿼리
SELECT *
FROM CTE_name;

 

재귀 CTE란?

자기 참조적 쿼리를 작성할 때 사용하는 CTE로 주로 부모-자식 관계를 처리하는데 사용한다.

예를 들어 직원 중 상사-부하 관계가 트리 구조로 이루어져 있을 때 특정 직원의 밑에 있는 모든 직원을 찾을 수 있다.

WITH RECURSIVE CTE_name AS (
    -- 기본 CTE (시작 테이블)
    SELECT ...
    FROM ...
    WHERE ...

    UNION ALL

    -- 재귀 CTE (이전 CTE 결과를 바탕으로 추가 테이블)
    SELECT ...
    FROM ...
    JOIN CTE_name ON ...
    WHERE END_CONDITION
)
SELECT * FROM CTE_name;

 

여기서 기본 CTE는 트리 구조에서 가장 상위에 있는 root 노드를 의미하고 재귀 CTE는 각 리프를 타고 점진적으로 데이터를 확장한다.

중요한 것은 기본 CTE는 시작 데이터를, 재귀 CTE에는 종료 조건을 걸어줘야 한다는 것이다.

 

이제 재귀 CTE에 대해 알아보았으니 문제를 살펴보자.

 

조건은 ECOLI_DATA 테이블이 주어지며 구조는 다음과 같다.

ID, PARENT_ID, SIZE_OF_COLONY, DIFFERENTIATION_DATE, GENOTYPE 은 각각 대장균 개체의 ID, 부모 개체의 ID, 개체의 크기, 분화되어 나온 날짜, 개체의 형질을 나타낸다.

 

각 세대별 자식이 없는 개체의 수(COUNT)와 세대(GENERATION)를 출력하는 SQL문을 작성해달라는 문제다.

이때 결과는 세대에 대해 오름차순 정렬해야한다.

(단, 모든 세대에는 자식이 없는 개체가 적어도 1개체는 존재한다)

 

예를 들어 ECOLI_DATA 테이블이 다음과 같다면

ID PARENT_ID SIZE_OF_COLONY DIFFERENTIATION_DATE GENOTYPE
1 NULL 10 2019/01/01 5
2 NULL 2 2019/01/01 3
3 2 100 2020/01/01 4
4 2 16 2020/01/01 4
5 2 17 2020/01/01 6
6 4 101 2021/01/01 22
7 4 101 2022/01/01 23
8 6 1 2022/01/01 27
각 세대별 대장균의 ID는 다음과 같다.

1 세대 : ID 1, ID 2
2 세대 : ID 3, ID 4, ID 5
3 세대 : ID 6, ID 7
4 세대 : ID 8

이 때 각 세대별 자식이 없는 대장균의 ID는 다음과 같다.

1 세대 : ID 1
2 세대 : ID 3, ID 5
3 세대 : ID 7
4 세대 : ID 8

따라서 결과를 세대에 대해 오름차순 정렬하면 다음과 같아야 한다.

COUNT GENERATION
1 1
2 2
1 3
1 4

 

 

풀이는 다음과 같다.

WITH RECURSIVE GENERATION_CTE AS (
    SELECT ID, PARENT_ID, 1 AS GENERATION
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NULL
    
    UNION ALL
    
    SELECT E1.ID, E1.PARENT_ID, GC.GENERATION + 1 AS GENERATION
    FROM ECOLI_DATA E1
    JOIN GENERATION_CTE GC ON E1.PARENT_ID = GC.ID
)

SELECT 
    COUNT(*) AS COUNT,
    GC.GENERATION
FROM GENERATION_CTE GC
LEFT JOIN ECOLI_DATA E1 ON GC.ID = E1.PARENT_ID
WHERE E1.ID IS NULL
GROUP BY GC.GENERATION
ORDER BY GC.GENERATION

 

ECOLI_DATA의 세대를 중심으로 출력해야 하므로 각 세대를 나타낼 수 있는 재귀 CTE가 필요하다.

재귀 CTE 내에 부모의 ID와 일치하는 ID를 찾아서 자식 데이터를 구하고 GENERATION이라는 COLUMN을 만들어 세대 데이터를 추가한다.

그 다음 자식이 없는 개체를 조건으로 뒀으므로 LEFT JOIN을 통해 자식이 NULL인 세대 데이터를 구한다.

GROUP BY를 통해 세대에 따른 집계함수를 쓸 수 있도록 그룹화 한다.