Chapter 16. Query Optimization

한 줄 핵심: 하나의 SQL 질의는 논리적으로 같은 결과를 내는 등가 표현식과 연산별 알고리즘의 조합만큼 많은 실행 방법을 가지며, 계획에 따라 실행 시간이 수 초 vs 수 일까지 벌어진다. 그래서 옵티마이저는 (1) 등가 규칙으로 표현식을 생성하고, (2) 알고리즘을 붙여 evaluation plan들을 만들고, (3) 통계 기반 추정 비용으로 가장 싼 것을 고른다 — 같은 목적지로 가는 여러 경로 중 가장 빠른 길을 고르는 내비게이션과 같다.

이 챕터가 답하는 핵심 질문

Q1. 같은 질의를 실행하는 방법이 왜 여러 개인가? (등가 표현식)

Q2. Evaluation plan이란 무엇인가?

Q3. 비용 기반 최적화(cost-based optimization)는 어떻게 동작하고 비용은 무엇으로 추정하는가?

Q4. 실행 계획은 어떻게 확인하는가(explain)?

이 슬라이드 분량의 범위

전체 outline은 ① Introduction ② Transformation of Relational Expressions ③ Catalog Information ④ Statistical Information ⑤ Cost-based optimization ⑥ Dynamic Programming for Choosing Plans ⑦ Materialized views이지만, 이 자료(7페이지)는 Introduction과 실행 계획 확인(explain) 까지를 다룬다. 등가 규칙·통계·DP의 상세는 후속 범위.

Q1. 같은 질의를 실행하는 방법이 왜 여러 개인가?

A. 두 축에서 대안이 생긴다 — 결과가 같은 등가 표현식(equivalent expressions)이 여럿이고, 같은 연산이라도 쓸 수 있는 알고리즘(merge join, hash join 등)이 여럿이기 때문이다.

등가 표현식: 관계대수 식을 다르게 써도 결과가 같을 수 있다(예: 필터를 join 전에 거느냐 후에 거느냐).
연산별 알고리즘 선택: 같은 join도 merge join·hash join 등 여러 방식.

표현식과 알고리즘을 분리해서 보기

“서울→부산”이라는 목적지가 질의 결과라면, 경로는 표현식이고 교통수단은 알고리즘이다.

경로 선택: 대전 경유 vs 강릉 경유 = join 순서/selection 위치 선택

교통수단 선택: 자동차 vs 기차 = nested-loop join vs hash join 같은 알고리즘 선택

같은 목적지라도 경로 × 교통수단 조합이 많아지므로, 옵티마이저는 이 조합들 중 예상 비용이 낮은 것을 고른다.

등가 표현식 예시 — “Music 학과 교수가 가르치는 과목”:

$Π_{nam e, t i tl e} (σ_{d e pt_nam e = "Music"} (in s t r u c t or ⋈_{in s t r u c t or . I D = t e a c h es . I D} (t e a c h es ⋈_{t e a c h es . co u rse_i d = co u rse . co u rse_i d} (Π_{co u rse_i d, t i tl e} co u rse))))$

같은 질의를 두 표현식 트리로 그릴 수 있다:

(a) Initial tree	(b) Transformed tree
전체를 join한 뒤 $σ_{d e pt_nam e = Music}$ 적용	$σ_{d e pt_nam e = Music}$ 를 instructor에 먼저 적용 후 join

(b)처럼 selection을 instructor 쪽으로 미리 내려보내면(push down) join에 들어가는 데이터가 줄어 보통 훨씬 싸다.
직관: “전국 식당을 합쳐놓고 ‘서울’만 거르기”보다 “처음부터 서울 식당만 가져와 합치기”가 빠르다.

before → after 를 식과 숫자로 — 왜 push down이 싼가
instructor 2,000명 중 Music 학과는 단 10명이라 하자.
(a) 나중에 거르기:  σ_Music( instructor ⋈ teaches )
       ① instructor(2000) ⋈ teaches 를 먼저 다 join  → 중간 결과 수천 행
       ② 그 큰 결과에서 Music만 골라냄

(b) 먼저 거르기(push down):  ( σ_Music(instructor) ) ⋈ teaches
       ① instructor에서 Music 10명만 추림  → 작은 중간 결과
       ② 10명만 teaches와 join          → join 입력이 200배 작음
두 식은 결과가 완전히 동일(등가 규칙: selection을 join 안으로 밀어넣기)하지만, join이 처리하는 데이터량이 2000 → 10으로 줄어 (b)가 압도적으로 싸다. 옵티마이저가 자동으로 하는 대표적 변환이 바로 이 selection push-down이다.

자주 쓰는 등가 규칙(equivalence rules) 맛보기

“결과는 같으니 더 싼 형태로 바꿔도 된다”를 보장하는 규칙들. 옵티마이저는 이것들을 조합해 가능한 표현식들을 만든다.

규칙 before after 효과
selection push-down $σ_{θ} (r ⋈ s)$ $(σ_{θ} (r)) ⋈ s$ ( $θ$ 가 $r$ 만 관련 시) join 입력 축소
projection push-down $Π_{L} (r ⋈ s)$ 필요한 열만 미리 $Π$ 후 join 중간 결과 폭 축소
join 교환/결합 $r ⋈ s$ = $s ⋈ r$ , $(r ⋈ s) ⋈ t = r ⋈ (s ⋈ t)$ 순서 자유 작은 것부터 join
selection 분해 $σ_{θ_{1} \land θ_{2}} (r)$ $σ_{θ_{1}} (σ_{θ_{2}} (r))$ 각 조건을 적절한 위치로 이동

규칙	before	after	효과
selection push-down	$σ_{θ} (r ⋈ s)$	$(σ_{θ} (r)) ⋈ s$ ( $θ$ 가 $r$ 만 관련 시)	join 입력 축소
projection push-down	$Π_{L} (r ⋈ s)$	필요한 열만 미리 $Π$ 후 join	중간 결과 폭 축소
join 교환/결합	$r ⋈ s$ = $s ⋈ r$ , $(r ⋈ s) ⋈ t = r ⋈ (s ⋈ t)$	순서 자유	작은 것부터 join
selection 분해	$σ_{θ_{1} \land θ_{2}} (r)$	$σ_{θ_{1}} (σ_{θ_{2}} (r))$	각 조건을 적절한 위치로 이동

Q2. Evaluation plan이란 무엇인가?

A. 표현식 트리(논리적 “무엇을”)에 ① 각 연산이 쓸 알고리즘과 ② 연산 실행을 조율하는 방법(물리적 “어떻게”)을 정확히 못 박은 작업 지시서다.

Evaluation plan은 정확히 정의한다: (1) 각 연산에 어떤 알고리즘을 쓸지, (2) 연산 실행을 어떻게 조율할지.
요리에 비유하면 “무엇을 만들지”에 더해 “어떤 도구로, 어떤 순서로 조리할지”까지 못 박은 것.

평가 계획 예시 (위 질의의 트리에 알고리즘 주석):

트리 위치	연산	선택된 알고리즘
최상단	$Π_{nam e, t i tl e}$	sort to remove duplicates(정렬로 중복 제거)
상단 join	$⋈$	merge join — 양쪽을 $sort_{I D}$ 후 병합
왼쪽 입력	$σ_{d e pt_nam e = Music} (in s t r u c t or)$	use index 1 후 $sort_{I D}$
하단 join	$t e a c h es ⋈ Π_{co u rse_i d, t i tl e} (co u rse)$	hash join, 결과를 $sort_{I D}$

한 트리에 여러 알고리즘이 섞인다

같은 질의 안에서도 join마다 다른 알고리즘(merge join vs hash join)을 쓸 수 있고 selection도 인덱스를 탈 수 있다. 평가 계획은 이런 모든 물리적 선택의 조합 하나를 가리킨다.

Q3. 비용 기반 최적화는 어떻게 동작하고 비용은 무엇으로 추정하는가?

A. ① 등가 규칙으로 표현식 생성 → ② 알고리즘 주석으로 대안 계획 생성 → ③ 추정 비용으로 가장 싼 계획 선택의 3단계로 동작하며, 비용은 릴레이션 통계·중간 결과 추정·알고리즘 비용 공식으로 추정한다.

왜 필요한가: 계획 간 비용 차이가 enormous — 같은 질의가 어떤 계획은 수 초, 다른 계획은 수 일이 걸릴 수 있어 비용을 따져 골라야 한다.

3단계 (cost-based query optimization):

등가 표현식 생성: 등가 규칙(equivalence rules) 으로 논리적으로 동등한 표현식 생성. — 가능한 경로 나열.
주석 달기(annotate): 각 표현식에 알고리즘을 붙여 대안 질의 계획 생성. — 각 경로에 교통수단 배정.
최저 비용 선택: 추정 비용(estimated cost) 으로 가장 싼 계획 선택. — 예상 소요시간 최소 경로.

비용 추정 재료:

재료	내용	예시/목적
릴레이션 통계	DB가 보관하는 테이블 통계	튜플 수, 속성의 distinct 값 개수
중간 결과 통계 추정	join 등 중간 산출물 크기 추정	복잡한 표현식 비용 계산에 필요
알고리즘별 비용 공식	통계로부터 각 알고리즘 비용 계산	통계를 입력으로 계획 전체 비용 산출

왜 "중간 결과" 추정이 따로 필요한가

A ⋈ B ⋈ C처럼 여러 단계면 두 번째 join의 입력은 첫 join의 중간 결과다. 이 크기는 카탈로그에 없으므로 원본 통계로부터 추정해야 다음 단계 비용을 계산할 수 있다. 추정이 빗나가면 엉뚱한 계획을 고른다.

join 순서 하나로 "수 초 vs 수 일"이 갈리는 예
$A (1 만 행) ⋈ B (1 만 행) ⋈ C (10 행)$ 를 join할 때, 결합 법칙으로 순서를 바꿔도 결과는 같다.
계획 ①  (A ⋈ B) ⋈ C
    A⋈B 가 먼저 → 중간 결과가 수백만 행으로 폭발 → 그 큰 걸 다시 C와 join  → 느림

계획 ②  A ⋈ (B ⋈ C)
    B⋈C 가 먼저 → C가 10행뿐이라 중간 결과 작음 → 작은 걸 A와 join        → 빠름
옵티마이저는 ①②의 중간 결과 크기를 통계로 추정해 ②가 훨씬 싸다고 판단하고 ②를 고른다. “어떤 순서로 합치느냐”만으로 비용이 수백~수천 배 차이 나는 게 cost-based optimization이 존재하는 이유다.

distinct 값 개수가 왜 통계로 중요한가 — selectivity(선택도)

where dept_name='Finance' 가 몇 행을 남길지 추정하려면, dept_name의 서로 다른 값이 몇 개( $V$ ) 인지가 필요하다. 값이 고르게 퍼졌다고 가정하면 매칭 행 ≈ 전체행 / $V$ . 학과가 50개라면 2,000명 중 한 학과는 평균 $2000/50 = 40$ 행 → “이 selection은 40행쯤 남긴다”고 추정해 다음 단계 비용을 계산한다. 이래서 카탈로그가 튜플 수뿐 아니라 distinct 값 개수까지 보관한다.

Q4. 실행 계획은 어떻게 확인하는가?

A. 대부분의 DBMS가 explain <query>로 옵티마이저가 고른 계획과 비용 추정치를 보여준다 — 문법은 DB마다 조금씩 다르다.

explain <query> 출력: 옵티마이저가 고른 계획 + 비용 추정치.

DBMS	문법
Oracle	`explain plan for <query>` 후 `select * from table (dbms_xplan.display)`
SQL Server	`set showplan_text on`
SQLite	`EXPLAIN QUERY PLAN <query>`

SQLite 예시:

EXPLAIN QUERY PLAN select name from student
-- 결과: SCAN student  (테이블 전체 스캔)

EXPLAIN QUERY PLAN
select name, title
from student natural join takes, course
where takes.course_id = course.course_id;

id	detail
6	SCAN takes USING COVERING INDEX sqlite_autoindex_takes_1
8	SEARCH student USING INDEX sqlite_autoindex_student_1 (ID=?)
14	SEARCH course USING INDEX sqlite_autoindex_course_1 (course_id=?)

읽는 법: takes를 커버링 인덱스로 SCAN(주 구동 테이블)하며, 각 행마다 student·course를 인덱스로 SEARCH(점 조회). 즉 옵티마이저가 Q2의 평가 계획(어떤 테이블을 어떤 인덱스/알고리즘으로 접근할지)을 실제로 출력한 것.

실전 팁 (슬라이드 권고)

“Find out how to view query execution plans on your favorite database” — explain 보는 법을 익혀두면 느린 질의가 왜 느린지(풀스캔? 잘못된 join 순서?)를 직접 진단할 수 있다.

Juhyeon's Blog

탐색기

Ch16_Query_Optimization

Chapter 16. Query Optimization

Q1. 같은 질의를 실행하는 방법이 왜 여러 개인가?

Q2. Evaluation plan이란 무엇인가?

Q3. 비용 기반 최적화는 어떻게 동작하고 비용은 무엇으로 추정하는가?

Q4. 실행 계획은 어떻게 확인하는가?

그래프 뷰

목차

Properties