재귀쿼리에 대해 알아보자

어떤 객체가 다른 객체에 속하는 경우가 있다. 댓글과 대댓글, 상위조직과 하위조직 등 각종 Tree 구조가 그렇다. 데이터 베이스에 Tree형식으로 데이터를 삽입하는 방법은 간단하다. parent_Id 라는 컬럼을 만들어 부모의 pk값을 저장하고 있으면 된다. 단일한 부모찾기는 쉽다. 그냥 자식에게 적혀있는 부모의 번호를 부르면 된다. 하지만 할머니를 찾고 싶다면...? 증조할머니를 찾고싶다면..?

코드단에서는 이런일을 그래프 탐색, DFS나 BFS로 해결한다. 즉 테이블을 통째로 꺼내서 코드단에서 그래프 탐색을 통해 트리를 만들어줘도 된다는 말이다! 하지만 이런 방법은 DB 성능적으로 반갑지 않은 일이다. 그래서 우리는 처음부터 쿼리로 트리를 예쁘게 꺼내오는 방법을 생각해볼 수 있다. 

 

MySql로 트리 꺼내오기

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

프로그래머스

WITH RECURSIVE TREE AS(
    SELECT ID, PARENT_ID, 1 AS DEPTH
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NULL
    
    UNION ALL 
    
    SELECT E.ID, E.PARENT_ID, T.DEPTH+1
    FROM ECOLI_DATA E JOIN TREE T ON E.PARENT_ID=T.ID
    
)

SELECT ID
FROM TREE
WHERE DEPTH = 3
ORDER BY ID ASC;

 

다음 문제는 내가 이 글을 쓰게 된 계기이다. 전형적인 부모찾기트리문제이다. 

 

재귀적 CTE (Common Table Expression) 을 사용해 쿼리안에서 재귀호출을 통해 트리를 구성할 수 있다.

CTE는 두 가지 부분으로 구성된다.

• 앵커(Anchor) 부분: 재귀 쿼리의 시작점을 정의합니다.
• 재귀 부분: 앵커에서 찾은 데이터를 바탕으로 재귀적으로 호출하여 더 깊은 레벨의 데이터를 찾습니다.

앵커 쿼리는 트리의 루트노트를 찾는다. WHERE 절에서 PARENT_ID 가 NULL인 데이터를 찾고 이 노드의 깊이를 1로 설정한다.

SELECT ID, PARENT_ID, 1 AS DEPTH
FROM ECOLI_DATA
WHERE PARENT_ID IS NULL

 

 

재귀 쿼리는 앵커쿼리에서 반환된 결과를 기반으로 자식 노드를 찾아서 다시 재귀적으로 처리한다. TREE CTE에서 반환된 노드 T.ID를 기준으로 자식 노드(E.PARENT_ID = T.ID)를 찾아서 JOIN 한다. 자식 노드의 깊이는 부모 노드의 깊이 +1로 계산한다. 

SELECT E.ID, E.PARENT_ID, T.DEPTH+1
FROM ECOLI_DATA E JOIN TREE T ON E.PARENT_ID=T.ID

 

 

재귀의 과정

 

1. PARENT_ID가 NULL인 루트 노드를 찾는다. 이때 DEPTH는 1이다.
2. 1번에서 호출에서 반환된 루트 노드의 ID를 기준으로, 자식 노드를 찾습니다. 자식 노드가 있으면, 이 자식 노드의 DEPTH는 부모의 DEPTH + 1 로 계산된다. 
3. 2번 호출에서 반환된 자식 노드를 기준으로 다시 그 자식 노드를 찾는다.
4. 이러한 과정이 반복되면서 트리의 모든 자식 노드를 찾을 때까지 재귀가 이어진다.

UNION ALL

UNION ALL 은 앵커 쿼리와 재귀 쿼리의 결과를 결합하는 역할을 한다. UNION과 UNION ALL은 두 쿼리 결과를 합치는 데 사용되지만, UNION은 중복된 행을 제거하고, UNION ALL은 중복을 허용하여 모든 행을 그대로 반환한다. 이 쿼리에서는 중복된 행을 제거하지 않고 재귀적으로 모든 자식 노드를 찾는 것이 목적이므로 UNION ALL을 사용한다.

앵커 쿼리의 결과가 반환되면 재귀 쿼리에서 UNION ALL을 통해 루트 노드의 자식 노드들이 반환된다. 재귀 쿼리는 이전 단계에서 반환된 TREE를 참조하여 자식 노드를 찾는다. 이 과정을 반복하면서 자식 노드들이 계속 반환된다. 

 

 

 

재귀에 대해 완.전.히. 알아버렸다. 이젠 어떤 재귀가 와도 두렵지 않다!