[SQL] 멸종위기의 대장균 찾기

비슷한 쿼리를 작성할 일도 있고, CTE에 대한 개념을 정리할 겸 작성하게 되었습니다.

CTE

CTE(Common Table Expression)은 단일 쿼리 내부에서 임시로 쿼리 결과를 저장하고, 해당 쿼리 내에서 반복적으로 사용 가능한 개념입니다.

이걸 들었을 때 가장 먼저 생각나는건 아무래도 가상 테이블 VIEW 인데, 차이점이 있습니다.

• VIEW 는 만들기 위해서 특별한 권한이 필요하고, 쿼리 실행 전 사전에 정의 되어 있어야 하며, 쿼리문이 끝나도 사용 가능합니다.
• 반면 CTE는 특별한 권한은 필요 없고, 쿼리가 끝나면 사라지는 임시 테이블입니다.

이를 쓰는 이유는 서브 쿼리와 달리 동일 쿼리 내에서 재사용이 가능하고, 또 자체 참조로 재귀 쿼리를 작성할 수 있음에 있습니다.

활용

기본 활용

기본적인 문법은 아래와 같습니다. WITH 절을 사용하여 정의합니다.

WITH cte_name AS (
    SELECT column1, column2, ...
    FROM table_name
    WHERE condition
)
SELECT *
FROM cte_name
WHERE additional_condition;

테이블명 옆에 컬럼명을 새로 지정하여 사용할 수도 있습니다.

WITH cte_name (column1, column2, ...) AS (
    SELECT column1, column2, ...
    FROM table_name
    WHERE condition
)
SELECT *
FROM cte_name
WHERE additional_condition;

여러 개 만들기

여러 개를 만드는 것은 단순히 , 로 이어주면 됩니다.

WITH 
    cte1 AS (
        SELECT column1, column2
        FROM table1
        WHERE condition1
    ),
    cte2 AS (
        SELECT column3, column4
        FROM table2
        WHERE condition2
    )
SELECT c1.column1, c2.column3
FROM cte1 c1
JOIN cte2 c2 ON c1.column2 = c2.column4;

재귀 쿼리

재귀 쿼리는 재귀 CTE를 사용하여 구현합니다. 재귀 CTE는 자기 자신을 참조하여 반복적으로 실행되는 임시 결과 집합입니다. 쿼리로 알고리즘 문제 풀 듯 DFS가 가능합니다.

가장 대표적으로 쓰이는 사례는 트리 형태로 되어있는 자료 검색입니다.

보통 부서도를 볼 때 다음과 같은 형태로 되어 있는 걸 볼 수 있습니다. 보통 이런 스키마의 경우 ID 와 PARENT_ID 를 따로 두는 편입니다.

CEO 김대표
├── 부장 이부장
│   └── 과장 최과장
│       └── 사원 정사원
└── 부장 박부장

여기서 최과장을 검색한다고 생각해보면, 아래와 같이 검색 결과가 나오는 것이 자연스럽습니다. 즉 계층 관계를 모두 표현해야 됩니다. 이럴 때 사용하는 것이 바로 재귀 쿼리입니다.

CEO 김대표
└── 부장 이부장
    └── 과장 최과장
        └── 사원 정사원

문법은 WITH RECURSIVE 를 사용하여서 표현합니다.

WITH RECURSIVE recur_cte AS (
    -- 1. Anchor Member (기준점)
    SELECT 초기값들...,
    	1 AS DEPTH -- 시작 깊이는 1
    FROM 테이블
    WHERE 시작조건
    
    UNION ALL
    
    -- 2. Recursive Member (재귀 부분)
    SELECT 계산값들...,
    	R.DEPTH + 1 -- 기존 깊이에 1 추가
    FROM 테이블 T
    JOIN recur_cte R ON 조인조건
    WHERE 종료조건
)
SELECT * FROM recur_cte;

문법을 보시면 아시겠지만, 호출을 위해 recur_cte 내부 본인을 재귀적으로 호출하고 있습니다.

기준점과 재귀 파트가 있는데, 이 둘을 UNION ALL 연산을 통해 모두 합치는 과정을 거칩니다. 합치는 것이 종료되는 시점은 바로 재귀 파트에서 더이상 새로운 row가 없을 때 종료됩니다.

또한 재귀 깊이는 SQL이 아닌 알고리즘 문제에서도 dfs할 때 depth 형태로 많이 쓰이는 만큼 쿼리를 짤 때도 해당 칼럼은 추가해주는 편이 좋습니다.

멸종위기의 대장균 찾기

[PRG] 멸종위기의 대장균 찾기

문제에서 요구하는 것은 다음과 같습니다.

• 각 대장균들의 세대를 파악해야 됩니다.
• 각 대장균들 중 자식이 없는 대장균을 파악해야 됩니다.
• 각 세대별 자식이 없는 개체의 수(COUNT)와 세대(GENERATION)를 출력합니다.

CTE 생성

각 세대를 마킹하기 위해서는 알고리즘 문제 풀 듯 dfs 진행하면 됩니다. 즉 재귀 쿼리가 적절한 선택입니다.

WITH RECURSIVE CTE AS (
    SELECT ID,
        PARENT_ID,
        1 AS GENERATION
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NULL
    UNION ALL
    SELECT E.ID,
        E.PARENT_ID,
        C.GENERATION + 1
    FROM ECOLI_DATA E
    JOIN CTE C ON (E.PARENT_ID = C.ID)
)

여기서 depth 역할을 하는 것이 바로 GENERATION 칼럼입니다.

쿼리

자식이 없다라는 말은 해당 대장균과 연결된 PARENT_ID 가 없다는 말과 동일합니다.

이를 구현하는 방법은 크게 두 가지가 있습니다.

• CTE 에 원래 테이블(ECOLI_DATA) 을 LEFT JOIN 을 걸어서 ECOLI_DATA 의 ID가 NULL 인 것이 바로 자식이 없는 대장균입니다.

  SELECT 
      COUNT(C.GENERATION) AS COUNT,
      C.GENERATION
  FROM CTE C
  LEFT JOIN ECOLI_DATA E ON (E.PARENT_ID = C.ID)
  WHERE E.ID IS NULL
  GROUP BY GENERATION

• NOT EXISTS 로 ECOLI_DATA 의 PARENT_ID 에 매핑되는 CTE의 ID 를 제외해줍니다.

  SELECT 
      COUNT(GENERATION) AS COUNT,
      GENERATION
  FROM CTE
  WHERE NOT EXISTS (
      SELECT 1 FROM ECOLI_DATA E WHERE E.PARENT_ID = CTE.ID
  )
  GROUP BY GENERATION

해당 상황은 NOT EXISTS 가 더 적합합니다. 해당 주제로 추후 포스팅 예정이지만, NOT EXISTS 의 동작은 중간에 EXISTS 조건을 만족하는 행을 찾으면 즉시 중단하기에 수행 횟수 측면에서 이득이 있습니다.

전체 예시 답안

WITH RECURSIVE CTE AS (
    SELECT ID,
        PARENT_ID,
        1 AS GENERATION
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NULL
    UNION ALL
    SELECT E.ID,
        E.PARENT_ID,
        C.GENERATION + 1
    FROM ECOLI_DATA E
    JOIN CTE C ON (E.PARENT_ID = C.ID)
) 

-- NOT EXIST 활용
SELECT 
    COUNT(GENERATION) AS COUNT,
    GENERATION
FROM CTE
WHERE NOT EXISTS (
    SELECT 1 FROM ECOLI_DATA E WHERE E.PARENT_ID = CTE.ID
)
GROUP BY GENERATION