[SQL] MySQL 재귀 쿼리 (Recursive Common Table Expressions)

목차

재귀 쿼리
어디에 사용할까?

아래 글은 MySQL 버전 8.0 이상을 기준으로 작성하였습니다. 5.x 버전에서 재귀쿼리(Recursive CTE)를 사용하는 방법은 스택오버플로우 문서를 참고하시길 바랍니다.

---

재귀 쿼리

재귀 쿼리는 자기 자신을 참조하여 쿼리를 실행하는 것이다. 바로 예시를 확인해보자.

WITH RECURSIVE cte AS
(
  SELECT 1
  UNION ALL
  SELECT n + 1 FROM cte WHERE n < 5 -- FROM절에 자신이 참조됨.
)
SELECT * FROM cte;

위의 예시에서 with문의 테이블 명으로 사용한 CTE는 Common Table Expression의 약자이다. CTE는 WITH문을 사용하여 만든 임시 테이블을 말한다. 재귀 쿼리는 영어로 Recursive CTE이다. 즉 WITH문을 사용할 때 FROM절에서 자기 자신을 참조하여 것이다. 재귀 쿼리를 사용할 때에는 WITH 뒤에 RECURSIVE를 사용한다.

재귀 쿼리는 두개의 SELECT절로 이루어지며 각 SELECT절은 UNION으로 구분된다. 첫번째 SELECT절은 Non-Recursive한 부분이고 두번째 SELECT절은 Recursive한 부분이다. 두번째 SELECT절이 반복적으로 자기자신을 참조하여 쿼리를 실행한다.

위의 예시 쿼리를 실행했을 때의 결과이다.

+------+
| n    | 
+------+
|    1 | -> 첫번째 SELECT 절이 반환한 행
|    2 | -> 첫 행을 기반으로 두번째 SELECT 절이 반환한 행 (1 + 1 = 2)
|    3 |
|    4 |
|    5 | -> n < 5 일 때까지 반복. n = 5에 반복 종료.
+------+

첫번째 SELECT 절은 반복을 시작할 첫번째 행을 만드는 역할이고, 두번째 SELECT 절은 첫번째 SELECT절이 만든 행을 기반으로 반복적으로 행을 만들어낸다. 그리고 WHERE 절에 명시된 조건에 의해 n=5가 되었을 때 반복은 종료된다.

기본적인 구조이다.

-- WITH 절 뒤에 RECURSIVE  
WITH RECURSIVE cte AS
(
  -- Non-Recursive : 반복을 진행하기 위한 행 세팅
  SELECT 1  
  UNION ALL
  -- Recursive : 위의 SELECT절에서 세팅된 행을 기반으로 반복을 진행.
  SELECT n + 1 
  FROM cte -- 자기자신 참조 명시
  WHERE n < 5 -- 반복 종료 조건
)
SELECT * FROM cte;

---

어디에 사용할 수 있을까?

연속적인 값을 생성할 때, 계층 구조를 탐색하기 위한 용도로 사용된다.

연속적인 값 생성

아래와 같은 A라는 이름의 테이블이 있고, 해당 데이터를 가지고 시간대별로 ID갯수를 카운트해야 한다.

CREATE TABLE A (
  time int,
    id char(10)
);

INSERT INTO A (time, id) 
VALUES
  (1, "id0"),
  (2, "id1"),
  (2, "id2"),
  (2, "id3"),
  (7, "id4"),
  (8, "id5"),
  (8, "id6"),
  (11, "id7"),
  (11, "id8"),
  (12, "id9")
;

아래 테이블 같이 결과를 요약한 테이블을 만들어 내고 싶다고 할때 사용할 수 있다. 아래 테이블은 0부터 23까지의 모든 데이터를 포함하고 있다.

time	count_id
0	0
1	1
2	3
...	...
22	0
23	0

A라는 테이블을 이용하여 단순히 시간대별 ID 갯수를 카운트하면 다음과 같이 쿼리를 작성할 수 있다.

SELECT 
  time,
  COUNT(ID) AS count_id
FROM A
GROUP BY time

결과는 다음과 같이 나올 것이다. 하지만, 원하는 결과와는 차이가 있다. 테이블 시간 컬럼에 0~23시를 모두 포함해야하기 때문이다. 위의 쿼리로는 갯수가 0인 시간을 출력할 수 없다.

time	count_id
1	1
2	3
7	1
8	2
11	2
12	1

이때 재귀 쿼리를 사용하여 문제를 해결할 수 있다.

WITH RECURSIVE time_table AS (
    SELECT 0 AS 'time'

    UNION ALL

    SELECT time + 1 AS 'time'
    FROM time_table
    WHERE time < 23
), count_A AS (
    SELECT
        time,
        COUNT(id) AS count_id
    FROM A
    GROUP BY time
)

SELECT
    time_table.time,
    IFNULL(count_A.count_id, 0) AS count_id -- A 테이블에 없는 시간대는 NULL로 표시되기 때문에 0으로 치환
FROM time_table
LEFT JOIN count_A
    ON time_table.time = count_A.time

계층 구조 탐색

다음과 같은 계층적 구조가 있다고 한다.

계층구조를 나타낸 B라는 이름의 테이블은 다음과 같다.

CREATE TABLE B (
    id int,
    parent_id int
);

INSERT INTO B (id, parent_id) 
VALUES
    (1, null),
    (2, null),
    (3, 2),
    (4, 2),
    (5, 2),
    (6, 4),
    (7, 4),
    (8, 6)
;

이 테이블 이용해 위 그림처럼 세대를 구분하는 쿼리를 작성해야 한다. 출력 예시는 다음과 같다. gen이라는 컬럼을 생성해야 한다.

id	parent_id	gen
1	null	1
2	null	1
3	2	2
4	2	2
5	2	2
6	4	3
7	4	3
8	6	4

이를 위해 재귀 쿼리를 사용한다.

WITH RECURSIVE B_GEN AS (
    SELECT
        id, 
        parent_id,
        1 AS GEN
    FROM B
    WHERE parent_id IS NULL

    UNION ALL

    SELECT
        B.id, 
        B.parent_id,
        GEN + 1 AS GEN
    FROM B_GEN
    INNER JOIN B
        ON B_GEN.id = B.parent_id
)

SELECT *
FROM B_GEN

위 쿼리 실행과정을 나타내면 다음과 같다.

1. 처음에 첫번째 SELECT 절이 실행된다.

첫번째 iteration 실행 결과   

id	parent_id	GEN
1	null	1
2	null	1

2. 위의 결과를 기반으로 두번째 재귀 쿼리를 실행한다.

두번째 iteration 실행 결과

id	parent_id	GEN
3	2	2
4	2	2
5	2	2

3. 두번째 재귀 쿼리 실행 결과가 나오지 않을때까지 반복.

세번째 Iteration 실행결과

id	parent_id	GEN
6	4	3
7	4	3

네번째 iteration 실행 결과

id	parent_id	GEN
8	6	4

다섯번째 iteration 실행 결과

없음

4. 반복이 종료 된 후, 실행 결과를 모두 UNION 한다.

UNION 결과

id	parent_id	gen
1	null	1
2	null	1
3	2	2
4	2	2
5	2	2
6	4	3
7	4	3
8	6	4

 

---

참고

MySQL 공식 문서
프로그래머스 문제 : 멸종 위기의 대장균 찾기