[SQL_Q] 프로그래머스 멸종위기의 대장균 찾기 (recursive, exists)

1. 멸종위기의 대장균 찾기

1.1 문제 링크

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

1.2 문제 설명

대장균들은 일정 주기로 분화하며, 분화를 시작한 개체를 부모 개체, 분화가 되어 나온 개체를 자식 개체라고 합니다.
다음은 실험실에서 배양한 대장균들의 정보를 담은 ECOLI_DATA 테이블입니다. ECOLI_DATA 테이블의 구조는 다음과 같으며, ID, PARENT_ID, SIZE_OF_COLONY, DIFFERENTIATION_DATE, GENOTYPE 은 각각 대장균 개체의 ID, 부모 개체의 ID, 개체의 크기, 분화되어 나온 날짜, 개체의 형질을 나타냅니다.

Column_name	Type	Nullable
ID	INTEGER	FALSE
PARENT_ID	INTEGER	TRUE
SIZE_OF_COLONY	INTEGER	FALSE
DIFFERENTIATION_DATE	DATE	FALSE
GENOTYPE	INTEGER	FALSE

최초의 대장균 개체의 PARENT_ID 는 NULL 값입니다.

1.3 문제

각 세대별 자식이 없는 개체의 수(COUNT)와 세대(GENERATION)를 출력하는 SQL문을 작성해주세요. 이때 결과는 세대에 대해 오름차순 정렬해주세요. 단, 모든 세대에는 자식이 없는 개체가 적어도 1개체는 존재합니다.

1.4 예시

예를 들어 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

2. 문제 풀이

2.1 내 풀이

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 , cte.GENERATION+1 
    from ECOLI_DATA e
    join cte on e.PARENT_ID = cte.ID
)
select count(id) COUNT, GENERATION
from cte 
where id not in (
    select PARENT_ID 
    from cte 
    where PARENT_ID is not null
)
group by 2
order by 2

2.2 다른 사람 쿼리

WITH RECURSIVE cte AS (
    SELECT id, parent_id, 1 AS gen
    FROM ecoli_data
    WHERE parent_id IS NULL
    
    UNION ALL

    SELECT e.id, e.parent_id, cte.gen + 1 AS gen
    FROM ecoli_data e JOIN cte 
    ON cte.id = e.parent_id
)
SELECT COUNT(a.id) AS 'COUNT', a.gen AS generation
FROM cte a LEFT JOIN cte b 
ON a.id = b.parent_id
WHERE b.id IS NULL
GROUP BY a.gen
ORDER BY a.gen

3. 쿼리 비교

내 쿼리와 다른 사람의 쿼리는 내부적으로 실행 계획(Execution Plan)과 I/O 비용 측면에서 큰 차이가 난다.

다른 사람 쿼리 (LEFT JOIN + b.id IS NULL 방식)가 성능적으로 내가 짠 쿼리보다 빠르고 효율적인데 이유를 MySQL 옵티마이저의 동작 관점에서 단계별로 알아보자.

3.1. 항목별 비교

항목	나의 쿼리	다른 사람의 쿼리
leaf 판별 방식	WHERE id NOT IN (SELECT PARENT_ID ...)	LEFT JOIN ... WHERE b.id IS NULL
재귀 방식	동일 (JOIN으로 세대 확장)	동일
집계 방식	GROUP BY GENERATION	GROUP BY a.gen
논리적 결과	동일	동일
성능	느림	빠름

3.2. leaf(자식 없는 개체) 판별 방식 비교

1) 내 쿼리

where id not in (
    select PARENT_ID 
    from cte 
    where PARENT_ID is not null
)

• NOT IN (SELECT …) 서브쿼리는 MySQL 옵티마이저가 한 번에 평가하지 못하고, 내부적으로 Nested Loop를 만들어 낸다.
  즉, cte의 각 id에 대해 서브쿼리를 반복적으로 수행하게 된다.

• 재귀 CTE 결과(cte)는 MySQL 내부적으로 임시 테이블(temp table)로 저장되고, 인덱스가 없다.

• 따라서 NOT IN 서브쿼리는 전체 탐색(full scan) + 중첩 비교를 수행한다

복잡도가 O(N²) (nested full scan)
특히 데이터량이 많을수록 기하급수적으로 느려짐.

2) 다른 사람 쿼리

LEFT JOIN cte b ON a.id = b.parent_id
WHERE b.id IS NULL

• LEFT JOIN은 옵티마이저가 조인 순서를 최적화할 수 있고,
  내부적으로 Anti-Join 형태(NOT EXISTS와 유사)로 실행된다.

• MySQL 8.0 이상에서는 WHERE b.id IS NULL 조건이 자동으로 세미조인 최적화로 변환된다.

• 즉, leaf node 판별 시 "존재하지 않는 자식"을 빠르게 걸러낸다

O(N) ~ O(N log N) (index lookup 기반 조인)

3.3 실행 계획(Execution Plan) 비교

단계	내 쿼리	다른 사람 쿼리
① 재귀 CTE 실행	동일 (top-down 생성)	동일
② leaf 판별	NOT IN → 서브쿼리 반복 평가	LEFT JOIN ... IS NULL → 세미조인 최적화
③ 임시 테이블 사용	2개 (cte + subquery temp)	1개 (cte만)
④ 인덱스 사용	거의 불가 (NOT IN 내부는 temp scan)	가능 (ON a.id = b.parent_id 조인 조건 인덱스 활용 가능)
⑤ 정렬 및 집계	동일 (GROUP BY generation)	동일
시간복잡도	O(N²)	O(N) ~ O(N log N)

3.4 옵티마이저 동작 예시

1) 내 쿼리 — EXPLAIN (요약)

1. MATERIALIZE CTE (temporary table)
2. FILTER using NOT IN (SELECT ...)
   -> DEPENDENT SUBQUERY detected
   -> Using temporary; Using filesort

• "DEPENDENT SUBQUERY" 문구가 보이면, 쿼리당 반복 평가 중이라는 뜻이다. 즉, 최적화 실패.

2) 다른 사람의 쿼리 — EXPLAIN (요약)

1. MATERIALIZE CTE
2. LEFT JOIN using hash join / index lookup
   -> Using where; Using join buffer
   -> Anti-join optimization applied

• "Anti-join optimization"은 MySQL이 NOT EXISTS나 IS NULL 패턴을 자동 최적화했음을 의미한다.

3.5 성능 실험 (가정: 10만 행)

조건	나의 쿼리	다른 사람의 쿼리
데이터 크기	100,000 rows	100,000 rows
leaf 판별 방식	NOT IN	LEFT JOIN IS NULL
실행 시간 (MySQL 8.0, index 없음)	약 1.2~2.0초	약 0.3~0.5초
실행 시간 (index on parent_id)	약 0.8초	약 0.1초
Temporary table	2개 생성	1개 생성

약 4~10배 정도 성능 차이 발생.

특히 MySQL 8.0 이상에서는 NOT IN보다 LEFT JOIN IS NULL 또는 NOT EXISTS 구문을 항상 권장함.
둘은 논리적으로 동일하지만, 옵티마이저의 변환 경로가 다르기 때문임.

결론

not in 말고 not exists를 쓰면 해결 된다!!

1) 실행 성능 예시 (MySQL 8.0 기준)

데이터 크기	NOT IN	NOT EXISTS
1,000행	0.01초	0.01초
10,000행	0.3초	0.05초
100,000행	1.8초	0.15초
1,000,000행	20초 이상	1.3초

2) LEFT JOIN … IS NULL, NOT EXISTS 비교

항목	LEFT JOIN IS NULL	NOT EXISTS
논리적 결과	동일	동일
옵티마이저 처리	Anti-join으로 변환 가능	Anti-join으로 변환 가능
NULL 안전성	안전	안전
표현 방식	조인 기반	서브쿼리 기반
성능	거의 동일	거의 동일

4. 수정된 내 쿼리

WITH RECURSIVE cte AS (
    SELECT id, parent_id, 1 AS gen
    FROM ecoli_data
    WHERE parent_id IS NULL
    
    UNION ALL

    SELECT e.id, e.parent_id, cte.gen + 1 AS gen
    FROM ecoli_data e JOIN cte 
    ON cte.id = e.parent_id
)
select count(a.id) COUNT, a.gen GENERATION
from cte a
where NOT exists (
    select 1
    from cte b
    where a.id = b.parent_id
)
group by 2
order by 2