176. 조인 순서 (Join Order) 최적화 - 동적 계획법 (Dynamic Programming), 탐욕 알고리즘

핵심 인사이트 (3줄 요약)

1. 본질: 조인 순서 (Join Order) 최적화는 같은 SQL (Structured Query Language) 의미를 유지한 채, 어떤 테이블을 먼저 묶어 중간 결과를 가장 작게 만들지 결정하는 문제다.
2. 가치: 좋은 조인 순서는 조인 알고리즘 자체보다 더 큰 비용 차이를 만들 수 있으며, 특히 다중 조인에서 메모리 사용량, 디스크 I/O (Input/Output), 응답시간을 좌우한다.
3. 판단 포인트: 옵티마이저는 동적 계획법 (Dynamic Programming)으로 부분 최적해를 축적하거나, 탐욕 알고리즘 (Greedy Algorithm)으로 계획 수립 시간을 줄인다. 성패는 결국 기수성 (Cardinality) 추정 정확도에 달린다.

Ⅰ. 개요 및 필요성

조인 순서 최적화는 비용 기반 옵티마이저 (CBO, Cost-Based Optimizer)가 다중 테이블 질의에서 가장 먼저 고민하는 핵심 문제다. 관계대수 관점에서는 조인이 결합법칙과 교환법칙을 어느 정도 만족하므로 여러 순서가 같은 결과를 낼 수 있다. 그러나 물리 실행에서는 "같은 결과"와 "같은 비용"이 결코 동의어가 아니다. 먼저 묶는 집합이 달라지면 중간 결과 크기와 이후 조인 반복 횟수가 크게 바뀐다.

예를 들어 ORDERS, CUSTOMERS, REGIONS 세 테이블을 조인한다고 하자. REGIONS = 'SEOUL' 조건이 매우 선택적이라면, 지역 정보를 먼저 적용해 고객 집합을 줄인 뒤 주문과 조인하는 편이 자연스럽다. 반대로 큰 주문 테이블과 고객 테이블을 먼저 조인하면 아직 필요 없는 수많은 행을 들고 다음 단계로 넘어가야 한다. 즉 조인 순서 최적화의 본질은 정답 계산을 시작하기 전에, 계산량부터 줄이는 전략 수립이다.

아래 그림은 왜 조인 순서가 실행시간을 좌우하는지 보여 준다. 핵심은 최종 결과 건수보다 중간 결과 건수가 시스템 자원을 먼저 태운다는 점이다.

┌────────────────────────────────────────────────────────────────────┐
│ Same logical answer, different work                               │
├────────────────────────────────────────────────────────────────────┤
│ Path A                                                            │
│   ORDERS(100M) join CUSTOMERS(10M) -> 100M rows                   │
│   then REGION='SEOUL' filter -> 200K rows                         │
│                                                                    │
│ Path B                                                            │
│   CUSTOMERS join REGIONS filter -> 20K rows                       │
│   then join ORDERS -> 200K rows                                   │
│                                                                    │
│ Final answer same / memory, I/O, spill risk very different        │
└────────────────────────────────────────────────────────────────────┘

테이블 수가 늘어나면 문제는 더 커진다. 3개 조인은 사람이 감으로도 볼 수 있지만, 8개 조인은 가능한 결합 순서와 트리 구조가 급격히 늘어난다. 그래서 옵티마이저는 "최적의 순서"를 찾는 동시에 "계획을 찾는 비용"도 함께 통제해야 한다.

• 📢 섹션 요약 비유: 같은 장보기 목록이라도 어떤 가게부터 들르느냐에 따라 동선이 완전히 달라진다. 최종적으로는 같은 물건을 사더라도, 돌아다닌 거리와 힘든 정도는 순서가 결정한다.

Ⅱ. 아키텍처 및 핵심 원리

조인 순서 최적화는 보통 네 단계를 거친다. 첫째, 질의에서 조인 그래프와 선택 조건을 뽑아낸다. 둘째, 통계 정보와 히스토그램을 바탕으로 각 테이블의 필터 후 기수성을 추정한다. 셋째, 가능한 조인 부분집합에 대해 비용을 계산한다. 넷째, 그중 가장 싼 계획을 채택하고 각 단계에 NL Join (Nested Loop Join), Hash Join, Sort Merge Join 같은 물리 조인 방식을 결합한다.

동적 계획법의 핵심은 부분집합별 최적 계획 저장이다. 예를 들어 {A,B}의 최저 비용 계획을 한 번 구해 두면, {A,B,C}를 탐색할 때 다시 처음부터 계산하지 않는다. 이 방식은 System R 계열 옵티마이저의 고전적 아이디어이며, 특히 좌심 트리 (Left-Deep Tree) 중심 탐색과 결합될 때 효율적이다.

아래 그림은 동적 계획법이 "작은 조합의 최적해"를 쌓아 올리는 방식을 보여 준다.

┌────────────────────────────────────────────────────────────────────┐
│ Dynamic Programming by subsets                                     │
├────────────────────────────────────────────────────────────────────┤
│ size 1 : {A} {B} {C} {D} -> best access path per table            │
│ size 2 : {A,B} {A,C} ...  -> cheapest join plan per pair          │
│ size 3 : {A,B,C} ...      -> reuse best size-2 plan               │
│ size 4 : {A,B,C,D}        -> final cheapest global plan           │
│                                                                    │
│ memo key = joined table set / memo value = cheapest known plan    │
└────────────────────────────────────────────────────────────────────┘

반면 탐욕 알고리즘은 "지금 가장 작아 보이는 조합"을 먼저 선택한다. 예를 들어 가장 선택도가 높은 조건이 걸린 테이블과 가장 싼 조인 상대를 먼저 묶고, 그 결과에 다음 후보를 붙여 나간다. 이 방식은 빠르지만, 초반 선택이 뒤쪽 전체 구조를 고정해 버릴 수 있다. 그래서 어떤 데이터 분포에서는 초기에 작아 보였던 선택이 결국 더 비싼 전체 계획으로 이어질 수 있다.

실무 DBMS (Database Management System)는 둘 중 하나만 순수하게 쓰기보다, 좌심 트리 제한, 부시 트리 (Bushy Tree) 일부 허용, 탐색 시간 제한, 휴리스틱 가지치기를 조합한다. 결국 조인 순서 최적화는 알고리즘 교과서 문제가 아니라, 최적성·탐색 시간·통계 품질을 절충하는 엔진 설계 문제다.

• 📢 섹션 요약 비유: 동적 계획법은 여행 코스를 짤 때 "도시 두 개씩 묶은 최적 경로"를 메모해 두었다가 재사용하는 방식이고, 탐욕 알고리즘은 그때그때 가장 가까운 다음 도시부터 찍는 방식이다.

Ⅲ. 비교 및 연결

조인 순서 최적화를 이해할 때 가장 자주 생기는 혼동은 조인 순서, 조인 방식, 액세스 경로를 하나로 보는 것이다. 하지만 셋은 서로 연결되면서도 다른 결정을 뜻한다. 조인 순서는 "누구를 먼저 묶을까"의 문제이고, 조인 방식은 "그 둘을 어떤 알고리즘으로 결합할까"의 문제이며, 액세스 경로는 "각 테이블을 인덱스로 읽을까 풀스캔할까"의 문제다.

또 하나의 비교 축은 좌심 트리 vs 부시 트리다. 좌심 트리는 (A join B) join C처럼 결과를 한쪽으로 계속 누적하는 구조여서 탐색 공간이 비교적 작고 파이프라이닝에 유리하다. 반면 부시 트리는 (A join B) join (C join D)처럼 양쪽 부분결과를 독립적으로 먼저 줄일 수 있어 특정 스타 스키마나 서브그래프 구조에서 더 유리할 수 있다. 다만 그만큼 탐색 공간이 커지므로 동적 계획법의 부담도 함께 커진다.

조인 순서 최적화는 분산 데이터 처리와도 바로 연결된다. 단일 서버에서는 메모리와 디스크 I/O가 핵심이지만, 분산 SQL 엔진에서는 네트워크 셔플 비용까지 들어온다. 이때 잘못된 순서는 단순히 "느린 실행"을 넘어서 대규모 데이터 이동을 유발한다. 즉 조인 순서 문제는 전통적 RDBMS (Relational Database Management System) 튜닝을 넘어, 현대 분산 질의 처리의 핵심 설계 변수이기도 하다.

결국 동적 계획법과 탐욕 알고리즘의 차이는 계산 방식 차이이면서, 동시에 전역 최적성 vs 신속한 계획 수립의 철학 차이다. 어떤 엔진이 어느 쪽으로 기울었는지 이해해야 실행 계획을 해석할 때 "왜 완벽한 정답 대신 괜찮은 답을 골랐는가"가 보인다.

• 📢 섹션 요약 비유: 식당, 카페, 은행을 들르는 순서를 정하는 것과, 각 장소에서 계산을 어떻게 할지 정하는 것은 다른 문제다. 방문 순서를 잘못 잡으면 카드 결제가 아무리 빨라도 하루가 비효율적으로 꼬인다.

Ⅳ. 실무 적용 및 기술사 판단

실무에서 조인 순서 문제는 대개 "왜 같은 SQL이 어떤 날은 0.2초, 어떤 날은 20초가 되는가"로 드러난다. 대부분의 원인은 오래된 통계, 편향된 데이터 분포, 조건 푸시다운 실패, 혹은 과도하게 복잡한 조인 그래프다. 즉 옵티마이저가 나빠서라기보다, 옵티마이저가 보고 있는 세계 모델이 틀려서 잘못된 순서를 택하는 경우가 많다.

예를 들어 OLTP (Online Transaction Processing) 질의에서 5개 테이블 정도를 조인하고, 특정 고객이나 특정 주문일자처럼 선택도가 높은 조건이 있다면 동적 계획법 기반 탐색만으로도 충분히 좋은 계획이 나오는 경우가 많다. 반면 데이터 웨어하우스에서 사실 테이블 1개와 차원 테이블 10개 이상을 묶는 질의는 탐색 공간이 너무 커져 휴리스틱이나 탐욕적 가지치기가 개입할 가능성이 높다. 이때는 차원 필터를 먼저 강하게 걸 수 있도록 통계, 파티션, 사전 집계 구조를 정리해 두는 것이 중요하다.

기술사 판단 체크리스트

1. 가장 선택적인 조건이 어느 테이블에 있으며, 필터 후 예상 행 수는 얼마인가?
2. 통계 정보와 히스토그램이 현재 데이터 분포를 반영하는가?
3. 좌심 트리만으로 충분한가, 아니면 독립 서브그래프를 먼저 줄이는 부시 트리가 필요한가?
4. 조인 순서 문제를 조인 방식 문제로 오진하고 있지 않은가?
5. 분산 환경이라면 네트워크 셔플 비용이 메모리 비용보다 더 크지 않은가?
6. 힌트 사용 전에 통계 갱신, 조건 재작성, 불필요 조인 제거를 먼저 검토했는가?

자주 나오는 안티패턴

• SQL FROM 절 순서가 곧 실제 조인 순서라고 믿는 경우
• 실행계획의 비용 숫자만 보고 추정 행 수 오류를 보지 않는 경우
• 오래된 통계 상태를 그대로 둔 채 힌트로만 순서를 강제하는 경우
• 12개 이상 조인을 한 번에 묶어 두고 탐색 공간 폭발을 방치하는 경우

힌트는 마지막 수단이어야 한다. ORDERED, LEADING처럼 조인 순서를 강제하는 힌트는 일시적으로 문제를 덮을 수 있지만, 데이터 분포가 바뀌면 곧 고정된 족쇄가 된다. 기술사 답안에서는 "옵티마이저의 잘못"보다 통계 정확도, 질의 구조 단순화, 탐색 공간 관리, 필요 시 제한적 힌트 순으로 판단하는 흐름이 더 설득력 있다.

• 📢 섹션 요약 비유: 내비게이션이 길을 잘못 고를 때는 기계가 멍청해서라기보다 지도 정보가 낡았거나 도로 공사 정보가 빠진 경우가 많다. 길을 고치기 전에 지도를 먼저 최신으로 바꾸는 것이 순서다.

Ⅴ. 기대효과 및 결론

조인 순서 최적화가 잘 되면 효과는 단순한 속도 향상에 그치지 않는다. 중간 결과가 줄어들수록 메모리 사용량이 안정되고, 디스크 스필이 감소하며, 동시 실행 질의 간 자원 경쟁도 줄어든다. 특히 분석형 질의나 분산 처리에서는 올바른 순서 하나가 네트워크 비용과 임시 저장 공간을 함께 절약한다.

하지만 한계도 분명하다. 아무리 좋은 동적 계획법도 잘못된 기수성 추정 위에서는 틀린 방향으로 최적화될 수 있고, 아무리 빠른 탐욕 알고리즘도 데이터 왜곡이 심하면 지역 최적해에 갇힐 수 있다. 그래서 최근에는 적응형 질의 처리 (Adaptive Query Processing), 실행 중 재최적화, 학습 기반 기수성 추정 같은 보완 기법이 함께 논의된다.

결론적으로 조인 순서 최적화는 "어떤 테이블부터 읽을까"라는 단순한 순서 놀이가 아니다. 중간 결과를 최소화하기 위해 탐색 공간과 계획 수립 비용까지 함께 관리하는 비용 모델의 핵심 문제다. 이 관점으로 기억해야 동적 계획법과 탐욕 알고리즘의 차이도 단순 암기가 아니라 설계 철학으로 남는다.

• 📢 섹션 요약 비유: 잘 짠 이사 동선은 박스를 어떻게 들지보다 먼저, 어느 방부터 비울지를 결정한다. 순서를 잘 잡으면 같은 힘으로도 훨씬 적게 오르내리게 된다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

Query graph construction
        │
        ▼
Selectivity / cardinality estimate
        │
        ├──────────────► Dynamic Programming: best plan per subset
        │
        └──────────────► Greedy search: cheapest next join first
        ▼
Join method + access path selection
        │
        ▼
Intermediate result minimization
        │
        ▼
Adaptive re-optimization / feedback stats

이 흐름도는 "질의 구조 파악 → 행 수 추정 → 탐색 전략 선택 → 물리 계획 결합 → 실행 중 보정"으로 이어지는 조인 최적화의 사고 순서를 보여 준다.

👶 어린이를 위한 3줄 비유 설명

1. 친구 집 여러 곳을 들를 때 어디부터 갈지 잘 정하면 덜 걷고 더 빨리 끝나요.
2. 컴퓨터도 표 여러 개를 합칠 때 먼저 작은 묶음을 만들면 힘을 훨씬 덜 써요.
3. 그래서 똑똑한 데이터베이스는 모든 길을 오래 계산하거나, 빨라 보이는 길부터 골라서 일을 시작해요.