176. 조인 순서 (Join Order) 최적화

핵심 인사이트: 조인할 테이블이 5개면, 가능한 순서의 조합은 120가지(5!)나 된다. 옵티마이저는 제한된 시간 안에 이 수많은 경우의 수 중 가장 싼 비용(Cost)을 내는 조합을 찾아내기 위해 '동적 계획법(DP)'과 '탐욕 알고리즘'이라는 수학적 무기를 꺼내 든다.

Ⅰ. 조인 순서(Join Order) 최적화의 개념

관계형 데이터베이스에서 3개 이상의 다중 테이블 조인이 발생할 때, 어느 테이블을 먼저 조인하고 어떤 순서로 엮어 나갈 것인가를 결정하는 비용 기반 옵티마이저(CBO)의 핵심 작업입니다. 조인 순서에 따라 처리해야 할 중간 결과물(Intermediate Result)의 크기가 수만 배 차이 날 수 있으므로 성능에 결정적인 영향을 미칩니다.

Ⅱ. 가능한 조인 조합의 수 폭발 (Search Space Explosion)

조인할 테이블이 늘어날수록 가능한 순서의 경우의 수(순열)는 팩토리얼($N!$)로 기하급수적으로 폭발합니다.

• 테이블 3개 (A, B, C): $3! = 6$ 가지
• 테이블 5개: $5! = 120$ 가지
• 테이블 10개: $10! \approx 362만$ 가지 옵티마이저는 사용자가 질의를 날렸을 때 1초도 안 되는 찰나의 시간에 실행 계획(Execution Plan)을 세워야 하므로, 이 모든 조합을 무식하게 다 계산해 볼 수 없습니다.

Ⅲ. 조인 순서 최적화 알고리즘

1. 동적 계획법 (Dynamic Programming, DP)

• System R 시대부터 IBM이 개발한 전통적이고 가장 완벽한 방식입니다.
• 작은 부분의 최적 해(예: A와 B 조인의 최소 비용)를 먼저 구해서 메모리에 저장해 두고, 테이블 수가 하나씩 늘어날 때마다 이전에 구한 결과를 재사용하여 최종 최적 해를 찾습니다.
• 장점: 항상 최적의 조인 순서를 보장합니다.
• 단점: 조인할 테이블이 6~7개를 넘어가면 동적 계획법조차 계산 시간이 너무 오래 걸리는 한계에 부딪힙니다.

2. 탐욕 알고리즘 (Greedy Algorithm) / 휴리스틱

• 조인할 테이블이 많아 동적 계획법으로 풀기 버거울 때 옵티마이저가 사용하는 방식입니다.
• 전체 그림을 보지 않고, 매 순간(단계)마다 가장 행(Row) 수가 적게 반환될 것 같은 최선의 조인 짝을 선택하여 순서를 엮어 나갑니다.
• 장점: 실행 계획 수립 속도가 매우 빠릅니다.
• 단점: 항상 전역 최적 해(Global Optimum)를 보장하지는 못하며, 때로는 지역 최적 해(Local Optimum)의 함정에 빠져 비효율적인 조인 순서를 만들 수 있습니다.

Ⅳ. 옵티마이저의 최적화 한계와 DBA의 개입

옵티마이저가 통계 정보의 오류나 탐욕 알고리즘의 한계로 인해 엉뚱한 테이블을 먼저 읽어 쿼리가 몇 시간씩 도는(Hang) 경우가 실무에서 자주 발생합니다. 이 경우 DBA나 튜닝 전문가는 힌트(Hint) 를 사용하여 옵티마이저의 결정을 무시하고 조인 순서를 강제 지정합니다.

• 예: /*+ ORDERED */ (FROM 절에 나열된 순서대로 무조건 조인해라)

📢 섹션 요약 비유: 서울에서 부산까지 5개 도시를 거쳐서 가는 최단 코스를 짤 때, 내비게이션(옵티마이저)이 모든 길을 다 계산해보는 것(DP)이 제일 정확하지만 시간이 너무 걸린다면, 그냥 현재 위치에서 당장 눈앞에 보이는 제일 안 막히는 길(Greedy)만 계속 골라서 달려가는 원리입니다.