[SQL/오답] 재귀 쿼리와 NOT IN의 함정: 멸종위기 개체 수 산출 (프로그래머스 Lv5)

 

1. Problem

대장균 가계도 데이터에서 각 세대별로 '자식이 없는 개체(멸종위기 개체)'를 찾아 세대별 인원수를 집계해야 한다. 단순한 조인으로는 깊이를 알 수 없는 계층 구조를 탐색해야 하며, '부모 목록에 존재하지 않는 ID'를 정확히 필터링하는 것이 과제이다.

2. Solution: 계층 탐색과 존재 여부 검증

WITH RECURSIVE를 통해 전 세대를 탐색하며 세대 번호를 부여하고, NOT IN을 활용해 자식 유무를 판별한다.

3. Takeaway: 쿼리 설계의 정밀도와 성능 최적화

• INNER JOIN을 통한 재귀 제어: 재귀 부분에서의 INNER JOIN은 '부모가 존재하는 자식'만을 유효한 행으로 연결한다. 이는 자식이 없는 리프 노드(Leaf Node)에 도달했을 때 재귀가 무한 루프에 빠지지 않고 자연스럽게 종료되게 만드는 객관적인 논리적 안전장치이다.
• NOT IN의 치명적인 함정, NULL: SQL의 3값 논리(Three-valued Logic)에 따라 NOT IN 서브쿼리 결과에 NULL이 하나라도 포함되면 전체 결과는 언제나 FALSE 또는 UNKNOWN이 된다. WHERE PARENT_ID IS NOT NULL을 명시한 것은 데이터 무결성을 보장하는 가장 중요한 필터이다.
• DISTINCT를 통한 연산 비용 절감: 자식 유무를 확인할 때 수많은 중복 부모 ID를 제거하고 고유값 리스트만 비교 대상으로 전달함으로써, 대규모 데이터셋에서도 효율적인 탐색 성능을 유지하도록 설계했다.

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

프로그래머스

---

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

Column nameTypeNullable

ID	INTEGER	FALSE
PARENT_ID	INTEGER	TRUE
SIZE_OF_COLONY	INTEGER	FALSE
DIFFERENTIATION_DATE	DATE	FALSE
GENOTYPE	INTEGER	FALSE

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

---

문제

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

---

예시

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

IDPARENT_IDSIZE_OF_COLONYDIFFERENTIATION_DATEGENOTYPE

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

 

1. 정답 쿼리

WITH RECURSIVE GENERATION_DATA AS (    
   SELECT ID, PARENT_ID, 1 AS GENERATION
    FROM ECOLI_DATA
    WHERE PARENT_ID IS NULL
    
    UNION ALL
    
    SELECT E.ID, E.PARENT_ID, G.GENERATION + 1
    FROM ECOLI_DATA E
    JOIN GENERATION_DATA G ON E.PARENT_ID = G.ID)   #1세대의 부모와 다음 세대의 자식을 연결
    
SELECT COUNT(*) AS COUNT, GENERATION
FROM GENERATION_DATA
WHERE ID NOT IN (                         # WHERE IN () 안에 NULL이 있으면 연산결과 Unknown이 됨
        SELECT DISTINCT PARENT_ID         # 고유값만 추출 중복 제거
        FROM ECOLI_DATA
        WHERE PARENT_ID IS NOT NULL)
GROUP BY GENERATION
ORDER BY GENERATION ASC;

 

 

재귀 쿼리(WITH RECURSIVE)의 반복 부분에서 INNER JOIN을 사용하는 이유

"부모가 있어야 자식이 존재한다"**는 계층 구조의 논리를 물리적으로 구현

 

1. 세대를 타고 내려가는 '연결 고리' 역할

재귀 쿼리는 한 번에 모든 데이터를 찾는 게 아니라, 한 단계씩 다리를 놓으며 전진합니다.

• 1단계: 부모가 없는 애들(1세대)을 찾습니다.
• 2단계: 1세대 ID를 부모(PARENT_ID)로 둔 자식들을 찾습니다. (JOIN 발생)
• 3단계: 그 자식들을 다시 부모로 둔 그다음 자식들을 찾습니다. (JOIN 발생)

이때 INNER JOIN은 **"직전 단계에서 찾은 부모 ID와 일치하는 PARENT_ID를 가진 자식"**만 정확히 골라내어 다음 세대로 넘겨주는 필터 역할을 합니다.

---

2. 재귀의 '종료 조건' 형성

만약 여기서 LEFT JOIN을 쓰면 어떻게 될까요? 자식이 없는 개체(마지막 세대)에 도달했을 때도 JOIN이 실패하지 않고 NULL을 붙여서 계속 결과를 만들어내려고 할 것입니다.

• INNER JOIN: 더 이상 매칭되는 자식이 없으면 결과가 나오지 않고, 그 지점에서 재귀가 자연스럽게 종료됩니다.
• 논리적 일치: "자식이 없는 개체는 그다음 세대를 생성하지 않는다"는 생물학적(?) 사실을 INNER JOIN이 코드로 보장하는 셈입니다.

 

 

 

SELECT DISTINCT PARENT_ID

 

DISTINCT를 사용하는 이유는 크게 **쿼리의 성능(효율성)**과 논리적인 명확성

NOT IN은 왼쪽에 있는 ID가 괄호 안의 리스트에 있는지 하나하나 비교합니다.

• DISTINCT가 없을 때: ID NOT IN (NULL, 1, 2, 2, 4, 4, 6, 6, 6, ...)
  • 데이터가 100만 건이라면 괄호 안에도 100만 개의 숫자가 들어갑니다. 같은 숫자를 수만 번 중복해서 비교하게 되죠.
• DISTINCT가 있을 때: ID NOT IN (1, 2, 4, 6)
  • 중복을 미리 제거해서 비교 대상을 최소화합니다. 컴퓨터가 훨씬 빠르게 "어, 여기 없네!"라고 결론 내릴 수 있습니다.

 

WHERE PARENT_ID IS NOT NULL

 

NOT IN과 NULL이 만났을 때의 대참사

ID NOT IN (1, 2, NULL) 이라는 조건이 있다고 가정해 봅시다. 이 조건은 내부적으로 다음과 같이 풀어서 해석됩니다.

ID != 1 AND ID != 2 AND ID != NULL

여기서 ID != NULL은 무조건 UNKNOWN이 됩니다. AND 연산에서 하나라도 결과가 확실치 않으면 전체 조건이 만족되지 않기 때문에, ID가 무엇이든 간에 이 조건문은 결코 TRUE가 될 수 없습니다.

결과적으로 PARENT_ID 목록에 NULL이 섞여 있으면, 자식이 없는 개체가 분명히 존재함에도 불구하고 아무것도 조회되지 않는 오답이 나오게 됩니다.