옵티마이저(Optimizer)

SQL공부를 해보려고 이것저것 찾아보던 중에, SQL을 제대로 이해하려면 옵티마이저가 어떻게 동작하는지 먼저 알아두는 것이 좋다는 영상을 보았다. 옵티마이저는 SQL을 데이터가 어떻게 처리할 지 결정해주는 역할을 한다고 한다. 뭔지 잘 모르겠지만, 일단 정리.

 

1. 개요

옵티마이저(Optimizer)란 주어진 목적 함수(Objective Function)를 최소화하거나 최대화하기 위해 변수(파라미터)를 체계적으로 조정하는 알고리즘 또는 시스템을 말합니다. 이 개념은 데이터베이스, 머신러닝, 컴파일러, 수학적 최적화, 운영 연구(Operations Research) 등 거의 모든 컴퓨터 과학 및 공학 분야에서 핵심적인 역할을 합니다.

---

2. 데이터베이스 옵티마이저 (Query Optimizer)

2.1. 정의와 역할

데이터베이스 옵티마이저는 사용자가 작성한 SQL 쿼리를 분석하여 가장 효율적인 실행 계획(Execution Plan)을 생성하는 DBMS의 핵심 구성 요소입니다. 동일한 결과를 반환하는 쿼리라도 내부 실행 방식에 따라 성능 차이가 수십, 수백 배에 달할 수 있기 때문에 옵티마이저의 역할은 매우 중요합니다.

2.2. SQL 처리 과정에서의 위치

SQL 입력 → 파서(Parser) → 옵티마이저(Optimizer) → 실행 엔진(Execution Engine) → 결과 반환

단계	설명
파싱(Parsing)	SQL 문법 검증, 구문 트리(Parse Tree) 생성
변환(Transformation)	쿼리를 논리적으로 동등한 더 효율적인 형태로 변환
최적화(Optimization)	여러 실행 계획 후보를 생성하고 비용을 추정하여 최적 계획 선택
실행(Execution)	선택된 실행 계획에 따라 데이터 접근 및 결과 반환

2.3. 옵티마이저의 유형

2.3.1. 규칙 기반 옵티마이저 (RBO, Rule-Based Optimizer)

미리 정해진 우선순위 규칙에 따라 실행 계획을 결정합니다.

우선순위	접근 방식
1 (최고)	ROWID에 의한 단일 행 접근
2	유니크 인덱스를 통한 단일 행 접근
3	클러스터 조인
4	해시 클러스터 키에 의한 단일 행
5	인덱스 클러스터 키에 의한 단일 행
...	...
N (최저)	풀 테이블 스캔 (Full Table Scan)

장점: 예측 가능하고 일관된 실행 계획
단점: 데이터의 실제 분포나 양을 고려하지 않아 비효율적인 계획 수립 가능

2.3.2. 비용 기반 옵티마이저 (CBO, Cost-Based Optimizer)

테이블 및 인덱스의 통계 정보를 기반으로 각 실행 계획의 비용(Cost)을 추정하고, 가장 낮은 비용의 계획을 선택합니다.

비용 추정에 사용되는 주요 통계 정보:

통계 항목	설명
카디널리티(Cardinality)	테이블의 총 행(Row) 수
선택도(Selectivity)	조건에 의해 선택되는 행의 비율 (0~1)
밀도(Density)	특정 컬럼 값의 분포 밀도
히스토그램(Histogram)	컬럼 값의 분포를 구간별로 저장
클러스터링 팩터	인덱스 순서와 테이블 데이터의 물리적 정렬 일치도
평균 행 길이	테이블 행의 평균 바이트 크기

비용 계산 공식 (단순화):

총 비용 = (I/O 비용) + (CPU 비용) + (네트워크 비용)
       = (단일 블록 읽기 횟수 × 단일 블록 읽기 비용)
       + (다중 블록 읽기 횟수 × 다중 블록 읽기 비용)
       + (CPU 연산 비용)

2.4. 주요 최적화 기법

2.4.1. 접근 경로 최적화 (Access Path Optimization)

접근 방식	적합한 경우	비용
풀 테이블 스캔	대량 데이터 조회, 선택도가 낮은 경우	테이블 전체 블록 수에 비례
인덱스 범위 스캔	선택도가 높은 조건 (소량 데이터)	인덱스 깊이 + 리프 블록 + 테이블 블록
인덱스 유니크 스캔	유니크 키로 단일 행 접근	인덱스 깊이 + 1
인덱스 풀 스캔	인덱스만으로 결과 반환 가능 (커버링 인덱스)	인덱스 전체 리프 블록 수
인덱스 스킵 스캔	복합 인덱스의 선두 컬럼 조건이 없는 경우	선두 컬럼의 고유 값 수에 따라 변동

2.4.2. 조인 최적화

조인 방법:

조인 방법	원리	적합한 경우
Nested Loop Join	외부 테이블의 각 행에 대해 내부 테이블을 반복 탐색	소량 데이터, 내부 테이블에 인덱스 존재
Sort Merge Join	양쪽 테이블을 정렬 후 병합	대량 데이터, 동등 조인, 이미 정렬된 데이터
Hash Join	작은 테이블로 해시 테이블 생성 후 큰 테이블 탐색	대량 데이터의 동등 조인, 인덱스 없는 경우

조인 순서 최적화:

N개의 테이블을 조인할 때 가능한 조인 순서는 N!(팩토리얼)가지입니다. 테이블 수가 많아지면 모든 경우를 탐색하는 것이 불가능하므로, 옵티마이저는 다음과 같은 전략을 사용합니다:

• 동적 프로그래밍(Dynamic Programming): 소규모 테이블 집합에 대해 최적 해를 점진적으로 구축
• 탐욕 알고리즘(Greedy Algorithm): 각 단계에서 가장 비용이 낮은 조인을 선택
• 유전 알고리즘: PostgreSQL에서 테이블 수가 12개 이상일 때 사용 (GEQO)

2.4.3. 쿼리 변환 (Query Transformation)

변환 기법	설명	예시
서브쿼리 Unnesting	상관 서브쿼리를 조인으로 변환	WHERE id IN (SELECT ...) → JOIN
뷰 병합(View Merging)	뷰의 쿼리를 외부 쿼리와 통합	뷰 내부의 조건을 외부로 푸시
조건 푸시다운(Predicate Pushdown)	필터 조건을 가능한 한 하위 단계로 이동	조인 전에 필터링하여 데이터 양 감소
공통 부분식 제거	중복 계산을 제거하여 효율화	동일 서브쿼리의 결과 재사용
OR Expansion	OR 조건을 UNION ALL로 변환	각 조건에 대해 별도의 인덱스 활용 가능

2.5. 실행 계획 분석

실행 계획을 확인하는 방법:

-- Oracle
EXPLAIN PLAN FOR SELECT * FROM employees WHERE dept_id = 10;
SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY);

-- PostgreSQL
EXPLAIN ANALYZE SELECT * FROM employees WHERE dept_id = 10;

-- MySQL
EXPLAIN SELECT * FROM employees WHERE dept_id = 10;

실행 계획에서 확인해야 할 핵심 항목:

항목	의미
Operation	수행되는 작업 (TABLE ACCESS, INDEX SCAN, HASH JOIN 등)
Rows	예상 반환 행 수
Cost	추정 비용 (상대적 수치)
Bytes	예상 데이터 크기
Time	예상 실행 시간
Actual Rows	실제 반환 행 수 (ANALYZE 옵션 사용 시)

2.6. 옵티마이저 힌트

옵티마이저의 판단을 개발자가 직접 제어할 수 있는 방법입니다:

-- Oracle 힌트 예시
SELECT /*+ INDEX(e idx_dept_id) */ *
FROM employees e
WHERE dept_id = 10;

SELECT /*+ FULL(e) */ *
FROM employees e
WHERE dept_id = 10;

SELECT /*+ USE_HASH(e d) */ *
FROM employees e, departments d
WHERE e.dept_id = d.dept_id;

-- MySQL 힌트 예시
SELECT /*+ NO_INDEX(e idx_dept_id) */ *
FROM employees e
WHERE dept_id = 10;

주요 힌트 종류:

힌트	설명
FULL(table)	풀 테이블 스캔 강제
INDEX(table index)	특정 인덱스 사용 강제
USE_NL(table)	Nested Loop 조인 강제
USE_HASH(table)	Hash 조인 강제
USE_MERGE(table)	Sort Merge 조인 강제
LEADING(table ...)	조인 순서 지정
PARALLEL(table, degree)	병렬 처리 수준 지정

---

3. 머신러닝/딥러닝 옵티마이저

3.1. 기본 원리

머신러닝 옵티마이저의 목표는 손실 함수 L(θ)를 최소화하는 파라미터 θ를 찾는 것입니다.

θ(t+1) = θ(t) - η · ∇L(θ(t))

여기서 η는 학습률(Learning Rate), ∇L은 손실 함수의 그래디언트입니다.

3.2. 주요 옵티마이저 상세 설명

3.2.1. SGD (Stochastic Gradient Descent)

θ(t+1) = θ(t) - η · g(t)

• g(t)는 미니배치에서 계산된 그래디언트
• 장점: 구현이 간단하고, 일반화(Generalization) 성능이 우수한 경우가 많음
• 단점: 수렴 속도가 느리고, 학습률 설정에 민감하며, 안장점(Saddle Point)에서 정체될 수 있음

3.2.2. SGD with Momentum

v(t) = β · v(t-1) + g(t)
θ(t+1) = θ(t) - η · v(t)

• β는 모멘텀 계수 (일반적으로 0.9)
• 과거 그래디언트의 지수 이동 평균을 누적하여 일관된 방향으로의 업데이트를 가속화
• 장점: 진동 감소, 수렴 속도 향상, 지역 최소값(Local Minimum) 탈출 가능성 증가
• 단점: 추가 하이퍼파라미터(β) 필요

3.2.3. Nesterov Accelerated Gradient (NAG)

θ_lookahead = θ(t) - β · v(t-1)
v(t) = β · v(t-1) + η · ∇L(θ_lookahead)
θ(t+1) = θ(t) - v(t)

• Momentum의 개선 버전으로, 미래 위치를 예측하여 그래디언트를 계산
• 오버슈팅(Overshooting)을 줄이고 더 정확한 수렴 가능

3.2.4. AdaGrad (Adaptive Gradient)

G(t) = G(t-1) + g(t)²
θ(t+1) = θ(t) - η / √(G(t) + ε) · g(t)

• 각 파라미터별로 누적된 그래디언트 제곱합에 반비례하여 학습률을 조정
• 장점: 희소(Sparse) 데이터에 효과적, 자주 업데이트되는 파라미터는 학습률 감소
• 단점: 학습이 진행될수록 학습률이 지속적으로 감소하여 학습이 조기 중단될 수 있음

3.2.5. RMSProp (Root Mean Square Propagation)

E[g²](t) = γ · E[g²](t-1) + (1-γ) · g(t)²
θ(t+1) = θ(t) - η / √(E[g²](t) + ε) · g(t)

• γ는 감쇠율(Decay Rate, 일반적으로 0.9)
• AdaGrad의 학습률 감소 문제를 해결하기 위해 지수 이동 평균 사용
• Geoffrey Hinton이 제안

3.2.6. Adam (Adaptive Moment Estimation)

m(t) = β1 · m(t-1) + (1-β1) · g(t)          # 1차 모멘트 (평균)
v(t) = β2 · v(t-1) + (1-β2) · g(t)²          # 2차 모멘트 (분산)
m̂(t) = m(t) / (1 - β1^t)                     # 편향 보정
v̂(t) = v(t) / (1 - β2^t)                     # 편향 보정
θ(t+1) = θ(t) - η · m̂(t) / (√v̂(t) + ε)

• 기본 하이퍼파라미터: β1=0.9, β2=0.999, ε=1e-8, η=0.001
• 장점: 대부분의 문제에서 좋은 성능, 하이퍼파라미터 튜닝에 덜 민감
• 단점: 일부 경우 SGD+Momentum 대비 일반화 성능이 떨어질 수 있음

3.2.7. AdamW (Adam with Decoupled Weight Decay)

θ(t+1) = θ(t) - η · (m̂(t) / (√v̂(t) + ε) + λ · θ(t))

• Adam에서 L2 정규화와 가중치 감쇠가 혼동되는 문제를 해결
• 가중치 감쇠를 그래디언트 업데이트와 분리(Decouple)하여 적용
• 현재 Transformer 기반 모델(BERT, GPT 등)의 사실상 표준 옵티마이저

3.2.8. 기타 최신 옵티마이저

옵티마이저	특징
LAMB	대규모 배치 학습(Large Batch Training)에 최적화, 레이어별 적응적 학습률
LARS	LAMB과 유사, SGD 기반의 레이어별 적응적 학습률
RAdam	Adam의 초기 학습 불안정성을 개선, 워밍업 불필요
Lookahead	기존 옵티마이저를 래핑하여 탐색과 활용의 균형을 개선
AdaFactor	메모리 효율적인 Adam 변형, 대형 모델에 적합
Lion	Google에서 발견한 진화 기반 옵티마이저, Adam보다 메모리 효율적
Sophia	2차 미분 정보를 활용하는 경량 옵티마이저, LLM 학습에 효과적

3.3. 학습률 스케줄링 (Learning Rate Scheduling)

옵티마이저와 함께 사용되는 학습률 조정 전략:

스케줄러	설명
Step Decay	일정 에폭마다 학습률을 고정 비율로 감소
Exponential Decay	매 에폭/스텝마다 지수적으로 감소
Cosine Annealing	코사인 함수를 따라 학습률을 주기적으로 변화
Warmup + Decay	초기에 학습률을 점진적으로 증가 후 감소 (Transformer에서 널리 사용)
Cyclic LR	학습률을 주기적으로 증감하여 지역 최소값 탈출
One Cycle Policy	단일 주기로 학습률을 증가 후 감소
ReduceLROnPlateau	검증 손실이 개선되지 않을 때 학습률 감소

3.4. 옵티마이저 선택 가이드

                    시작
                     │
            ┌────────┴────────┐
            │ 문제 유형은?      │
            └────────┬────────┘
         ┌───────────┼───────────┐
         ▼           ▼           ▼
    컴퓨터 비전    NLP/LLM    일반/추천 시스템
         │           │           │
    SGD+Momentum  AdamW       Adam
    + Cosine LR   + Warmup    + ReduceLR
         │           │
    일반화 성능    빠른 수렴
    우수          + 안정적

---

4. 컴파일러 옵티마이저

4.1. 최적화 수준

대부분의 컴파일러(GCC, Clang 등)는 최적화 수준을 플래그로 지정할 수 있습니다:

플래그	설명
-O0	최적화 없음 (디버깅용)
-O1	기본 최적화 (컴파일 시간과 성능의 균형)
-O2	중간 수준 최적화 (대부분의 프로덕션 코드)
-O3	공격적 최적화 (루프 벡터화, 인라이닝 확대)
-Os	코드 크기 최적화 (임베디드 시스템)
-Ofast	표준 준수를 희생한 최대 성능 최적화

4.2. 주요 최적화 기법 상세

4.2.1. 기계 독립적 최적화 (중간 코드 수준)

기법	설명	예시
상수 폴딩	컴파일 시점에 상수 연산 사전 계산	x = 3 * 4 → x = 12
상수 전파	알려진 상수 값을 사용처에 대입	a=5; b=a+1 → b=6
데드 코드 제거	실행되지 않거나 결과가 사용되지 않는 코드 제거	도달 불가 분기 제거
공통 부분식 제거(CSE)	동일 연산의 중복 계산 방지	a*b+c*d 에서 a*b 재사용
루프 불변 코드 이동	루프 내 불변 연산을 루프 밖으로 이동	루프 내 상수 계산 외부 이동
강도 감소	비용 높은 연산을 저비용 연산으로 대체	곱셈 → 비트 시프트
꼬리 호출 최적화	꼬리 재귀를 반복문으로 변환	스택 오버플로 방지

4.2.2. 루프 최적화

기법	설명
루프 언롤링	반복문 본체를 여러 번 복제하여 분기 오버헤드 감소
루프 퓨전	동일 범위의 인접 루프를 하나로 병합
루프 피싱	하나의 루프를 여러 루프로 분할하여 캐시 활용 개선
루프 타일링	루프를 블록 단위로 분할하여 캐시 지역성 향상
루프 벡터화	SIMD 명령어를 활용한 병렬 연산

4.2.3. 기계 종속적 최적화 (코드 생성 수준)

기법	설명
레지스터 할당	변수를 CPU 레지스터에 효율적으로 매핑 (그래프 컬러링 알고리즘)
명령어 선택	타겟 아키텍처에 최적인 명령어 선택
명령어 스케줄링	파이프라인 스톨을 최소화하도록 명령어 순서 재배치
피홀 최적화	짧은 명령어 시퀀스를 더 효율적인 시퀀스로 대체

---

5. 수학적 최적화 (Mathematical Optimization)

5.1. 분류 체계

최적화 문제
├── 연속 최적화 (Continuous Optimization)
│   ├── 제약 없는 최적화 (Unconstrained)
│   │   ├── 1차 방법: 경사 하강법, 켤레 경사법
│   │   └── 2차 방법: 뉴턴법, 준뉴턴법(BFGS, L-BFGS)
│   ├── 제약 있는 최적화 (Constrained)
│   │   ├── 선형 계획법 (LP): 심플렉스법, 내부점법
│   │   ├── 이차 계획법 (QP)
│   │   └── 비선형 계획법 (NLP): SQP, 내부점법, 페널티법
│   └── 볼록 최적화 (Convex Optimization)
│       └── 전역 최적해 보장
│
├── 이산 최적화 (Discrete / Combinatorial)
│   ├── 정수 계획법 (IP): 분지 한정법
│   ├── 혼합 정수 계획법 (MIP)
│   └── NP-Hard 문제: TSP, 배낭 문제 등
│
└── 메타휴리스틱 (Metaheuristics)
    ├── 유전 알고리즘 (GA)
    ├── 시뮬레이티드 어닐링 (SA)
    ├── 입자 군집 최적화 (PSO)
    └── 개미 군집 최적화 (ACO)

5.2. 주요 알고리즘 비교

알고리즘	수렴 속도	메모리	적용 범위
경사 하강법	선형	낮음	대규모 문제
뉴턴법	이차	높음 (Hessian 저장)	소규모 문제
L-BFGS	초선형	중간	중대규모 문제
심플렉스법	다항 시간 (실제)	중간	선형 계획
내부점법	다항 시간	높음	대규모 LP/QP

---

6. 분야 간 공통 개념

6.1. 탐색(Exploration) vs 활용(Exploitation)

모든 옵티마이저는 다음 두 가지 사이의 균형을 고려합니다:

• 탐색(Exploration): 넓은 범위의 해 공간을 탐색하여 전역 최적해를 찾으려는 시도
• 활용(Exploitation): 현재까지 발견된 좋은 해 근처를 집중적으로 탐색

6.2. 수렴성(Convergence)

• 전역 수렴(Global Convergence): 임의의 초기점에서 시작해도 최적해에 도달
• 지역 수렴(Local Convergence): 최적해 근처에서 시작했을 때의 수렴 속도
• 수렴 속도: 선형(Linear) < 초선형(Superlinear) < 이차(Quadratic)

6.3. 하이퍼파라미터 최적화

옵티마이저 자체의 설정값을 최적화하는 메타 최적화:

방법	설명
그리드 서치	모든 조합을 체계적으로 시도
랜덤 서치	무작위 조합 시도 (그리드 서치보다 효율적인 경우 많음)
베이지안 최적화	이전 결과를 바탕으로 다음 시도점을 지능적으로 선택
Hyperband	조기 종료(Early Stopping)를 활용한 효율적 탐색
Population-Based Training	여러 설정을 동시에 학습하며 진화적으로 최적화

---

7. 요약 및 결론

분야	최적화 대상	핵심 옵티마이저	핵심 고려 사항
데이터베이스	쿼리 실행 계획	CBO (비용 기반)	통계 정보의 정확성, 힌트 활용
딥러닝	모델 파라미터	Adam, AdamW, SGD	학습률, 수렴 속도, 일반화 성능
컴파일러	코드 실행 효율	다단계 최적화 패스	최적화 수준, 타겟 아키텍처
수학적 최적화	목적 함수	문제 특성에 따라 선택	볼록성, 제약 조건, 문제 크기

옵티마이저는 분야에 관계없이 "제한된 자원(시간, 메모리, 계산량) 내에서 최선의 결과를 도출"한다는 공통 목표를 공유합니다. 각 분야의 특성에 맞는 옵티마이저를 이해하고 적절히 선택하는 것이 시스템 성능 향상의 핵심입니다.

---