15.1 질의 처리 개요 (Query Processing Overview)
사용자가 던진 질의(query)는 크게 3단계를 거쳐 결과(query output)가 된다.
① Parsing & translation
파싱 및 변환
parser가 질의의 syntax(구문)를 검사하고, 참조한 relation(릴레이션)이 존재하는지 검증한 뒤, 질의를 relational algebra(관계 대수) 표현식으로 변환한다.
② Optimization
최적화
동등한(equivalent) 여러 표현식과 각 연산의 여러 알고리즘 중에서 가장 비용이 낮은 evaluation plan(평가 계획)을 고른다.
③ Evaluation
평가
execution engine(실행 엔진)이 선택된 plan을 실제로 실행하여 질의에 대한 답(answer)을 반환한다.
인터랙티브: 질의 처리 흐름도
각 단계를 클릭하면 오른쪽 패널에 설명이 나타납니다. 마름모=엔진(engine), 박스=데이터, 실린더=디스크(통계·데이터)를 뜻합니다.
Relational Algebra 기호
| 기호 | 연산 | 의미 |
|---|---|---|
| σ | Select (선택) | 조건을 만족하는 행(tuple)을 고른다. |
| Π | Project (추출) | 지정한 열(attribute)만 남긴다. |
| ∪ | Union (합집합) | 두 릴레이션의 합집합. |
| ∩ | Intersection (교집합) | 두 릴레이션의 교집합. |
| − | Difference (차집합) | 한 릴레이션에서 다른 릴레이션을 뺀다. |
| × | Cartesian product (곱집합) | 두 릴레이션의 모든 행 조합. |
| ⋈ | Join (조인) | 조건을 만족하는 행끼리 결합. |
| ρ | Rename (이름 변경) | 릴레이션/속성의 이름을 바꾼다. |
15.2 질의 최적화 (Query Optimization)
같은 결과를 내는 표현식·알고리즘은 여러 개다. 그 중 가장 싼 것을 고르는 일이 최적화다.
Equivalent expressions (동등 표현식)
하나의 질의는 결과가 같은 여러 relational algebra 표현식으로 쓸 수 있다. 예를 들어 다음 둘은 동등하다.
≡ (동등)
Πsalary( σsalary<75000(instructor) )
결과는 같지만 연산 순서에 따라 처리 비용이 달라진다.
Evaluation plan (평가 계획)
각 연산(σ, Π, ⋈ …)은 여러 알고리즘으로 구현할 수 있다. 어떤 알고리즘으로 어떤 순서로 연산을 수행할지 명시한 것이 evaluation plan(=연산의 시퀀스)이다.
Query optimization = 동등한 여러 plan 중 예상 비용이 가장 낮은 plan을 선택하는 과정. 비용 추정에는 catalog 통계(튜플 수, 튜플 크기 등)를 사용한다.
옵티마이저는 데이터를 직접 실행해 보지 않고, catalog(시스템 카탈로그)에 저장된 통계 — 각 릴레이션의 튜플 수(number of tuples), 튜플/블록 크기 등 — 로 각 plan의 비용을 추정한다. 그래서 통계가 부정확하면 나쁜 plan이 선택될 수 있다.
15.3 비용 측정 (Measures of Query Cost)
질의의 비용은 여러 자원의 시간으로 나뉘지만, 실무에서는 디스크 비용이 지배적이다.
⏱️ Disk access
디스크 접근 시간. 보통 가장 큼 → 비용을 지배한다.
🧠 CPU
연산·비교 등 CPU 시간. 디스크에 비해 작아 보통 무시한다.
🌐 Network
분산/병렬 환경의 통신 비용. 기본 모델에서는 무시한다.
전체 시간은 disk access + CPU + network 로 볼 수 있고, 보통 response time(응답 시간)을 기준으로 한다. 단, response time을 정확히 추정하기는 어려워, 디스크 비용을 두 가지 척도로 단순화한다: block transfer 수와 seek 수.
디스크 비용의 구성
- tT
- 블록 1개를 transfer(전송)하는 데 걸리는 시간.
- tS
- seek 1회에 걸리는 시간.
- b
- 총 block transfer 수.
- S
- 총 seek 수.
block transfer 수 × 블록 전송 시간 + seek 수 × seek 시간. CPU·network는 무시한다.
tS · tT 대표값 (4KB 블록 기준)
| 매체 | tS (seek 시간) | tT (블록 전송 시간) |
|---|---|---|
| HDD (자기 디스크) | 4 ms | 0.1 ms |
| SSD (플래시) | 20 ~ 90 µs | 2 ~ 10 µs |
SSD는 seek가 사실상 없어 tS·tT가 HDD보다 수십~수백 배 작다.
비용 추정은 보통 worst case(최악 상황)를 가정한다: 시작 시 buffer(버퍼)가 비어 있고, 연산에 최소한의 메모리만 주어진다고 본다. 실제로는 buffer에 이미 블록이 있으면 비용이 더 작아질 수 있다.
인터랙티브: 질의 비용 계산기
15.4 External Sort-Merge (외부 정렬-병합)
데이터가 메모리에 다 들어가면 quicksort로 끝나지만, 들어가지 않으면 디스크를 오가는 external sort-merge가 필요하다.
Stage 1 — Create runs (run 생성)
메모리 M 블록만큼 읽어 정렬한 뒤 정렬된 run(런)으로 디스크에 쓴다. 입력을 다 읽을 때까지 반복한다. M=3(=6 records)이면 18개 입력은 6개씩 잘려 3개의 run이 만들어진다.
Stage 2 — Merge (N-way 병합)
N < M: N개 input buffer + 1개 output buffer로 모든 run을 한 번에 병합. 각 run의 첫 블록을 적재 → 정렬순으로 가장 작은 record를 output에 보냄 → output이 full이면 write, input page가 비면 그 run의 다음 블록을 읽음.
N ≥ M: 한 번에 못 합치므로 여러 pass로 나눈다. 각 pass는 M−1개씩 병합하여 run 개수를 (M−1)배 줄인다. 예: M=11, 90 runs → 9 runs(각 10개 병합).
page = 2 records, M = 3 블록(= 6 records). 입력 18 records:
[18,24,13,21,26,5,28,7,22,10,9,4,2,11,39,8,3,31].
6개씩 잘라 정렬 → 3개의 run, 이후 2번의 merge pass로 최종 정렬을 완성한다. 아래 애니메이션이 정확히 이 과정을 보여준다.
인터랙티브: External Sort-Merge 애니메이션
"다음 ▶"으로 ① run 생성 → ② merge pass 1 → ③ merge pass 2 를 단계별로 따라가세요.
15.5 정렬 비용 분석 (Cost of External Sort-Merge)
seek를 줄이기 위해 run당 buffer block bb을 두면, pass 수·block transfer·seek 수가 다음 공식으로 정해진다.
- br
- 릴레이션 전체의 블록 수.
- M
- 정렬에 쓸 수 있는 메모리 블록 수.
- bb
- run 하나당 할당하는 buffer block 수(seek를 줄이기 위해). 한 pass는 ⌊M/bb⌋ − 1 개의 run을 병합한다.
① Merge pass 수
② Total block transfers
공식의 +1은 run 생성 시의 write를 반영하고, 마지막 merge pass의 output write는 비용에 넣지 않는다 — 정렬 결과는 디스크에 쓰지 않고 곧바로 부모 연산(parent operation)으로 파이프(pipe)되기 때문이다. (read만 br회 계산.)
③ Total seeks
앞 항 2⌈br/M⌉ = run 생성(읽기+쓰기) seek, 뒷 항 = merge seek(마지막 pass의 write seek 제외).
인터랙티브: Sort-Merge 비용 계산기
15.6 선택 연산 (Selection Operations) 보충
σθ(r) — 조건 θ를 만족하는 튜플을 고른다. 어떤 알고리즘이 싼지는 조건의 종류(equality/comparison, key/nonkey)와 인덱스 유무에 달렸다.
강의 슬라이드(Query Processing 1)는 cost model + sorting까지만 다뤘다. 이 절은 후속 차시·교재(Silberschatz 7e §15.3) 보충이지만 시험·학습 핵심이다. 표기: br=릴레이션 블록 수, nr=튜플 수, hi=B+트리 인덱스 높이, tT=블록 전송 시간, tS=seek 시간. 비용은 block transfer (+ seek) 단위.
기본 선택 알고리즘 (A1 ~ A6)
| 약칭 | 방식 | 조건 | 비용 (block transfer + seek) |
|---|---|---|---|
| A1 | Linear search 선형 탐색 |
임의(항상 적용 가능) | tS + br·tTkey에 대한 equality면 찾는 즉시 종료 → 평균 br/2 블록 |
| A2 | Primary B+-tree index, equality on key 기본 인덱스 · 키 동등 |
단일 레코드 반환 | (hi + 1)·(tT + tS)트리 hi레벨 + 레코드 1블록 |
| A3 | Primary index, equality on nonkey 기본 인덱스 · 비키 동등 |
연속한 b개 블록 | hi·(tT + tS) + tS + b·tT정렬되어 있어 매칭 b블록이 연속 → seek 1회로 순차 읽기 |
| A4 (key) |
Secondary index, equality on key 보조 인덱스 · 키 동등 |
단일 레코드 | (hi + 1)·(tT + tS) |
| A4 (nonkey) |
Secondary index, equality on nonkey 보조 인덱스 · 비키 동등 |
n개 레코드 | (hi + n)·(tT + tS)매칭 n개가 제각기 다른 블록에 흩어짐 → 매우 비쌈. n이 크면 A1(linear scan)이 더 쌀 수 있다. |
| A5 | Primary index, comparison 기본 인덱스 · 비교 |
σA≥v, σA>v | 인덱스로 첫 ≥v 튜플을 찾고 그 지점부터 파일 끝까지 순차 스캔. σA≤v·σA<v는 파일 처음부터 v까지 스캔하면 되므로 인덱스 불필요. |
| A6 | Secondary index, comparison 보조 인덱스 · 비교 |
σA≥v 등 | 인덱스 leaf를 스캔해 매칭 포인터를 얻고 각 레코드를 따로 fetch → 레코드마다 1 I/O. 매칭이 많으면 매우 비쌈(보통 linear scan이 낫다). |
A1 linear: tS + br·tT (key equality면 평균 br/2). A2/A4key equality on key: (hi+1)(tT+tS). A3 primary nonkey: hi(tT+tS)+tS+b·tT. A4nonkey secondary nonkey: (hi+n)(tT+tS) — 흩어진 n블록이라 비쌈. 핵심 직관: primary(=정렬됨) index는 매칭이 연속이라 싸고, secondary index는 매칭이 흩어져 레코드마다 I/O가 든다.
복합 조건: Conjunction(∧) · Disjunction(∨) · Negation(¬)
Conjunction (∧) σθ1∧θ2∧…
A7 — 한 조건에 인덱스가 있으면 가장 선택적(selective)인 조건을 인덱스로 처리하고, 나머지 조건은 그 결과 튜플에 대해 in-memory 필터로 검사.
A8 — 여러 속성을 묶은 composite(복합) 인덱스가 있으면 그것으로 직접 처리.
A9 — 각 조건의 record pointer/bitmap을 인덱스로 구한 뒤 교집합(intersection), 남은 포인터로 레코드 fetch.
Disjunction (∨) σθ1∨θ2∨…
A10 — 모든 조건에 인덱스가 있을 때만 인덱스 활용 가능. 각 조건의 record pointer를 구해 합집합(union)한 뒤 레코드 fetch. 하나라도 인덱스가 없으면 linear scan이 불가피하다.
Negation (¬) σ¬θ
조건을 만족하지 않는 튜플을 찾는다. 보통 인덱스가 도움이 안 되어 linear scan으로 처리한다(만족하지 않는 튜플이 드물고 인덱스로 식별 가능한 특수한 경우 제외).
br=10,000, hi=3, tT=0.1ms, tS=4ms 라고 하자.
A1 linear = tS + br·tT = 4 + 10000·0.1 = 1,004 ms.
A2 equality on key = (hi+1)(tT+tS) = 4·(0.1+4) = 16.4 ms — 인덱스가 압도적으로 싸다.
A4nonkey, 매칭 n=100 = (hi+n)(tT+tS) = 103·4.1 = 422.3 ms — 흩어진 100블록이라 비싸지만 아직 A1보다 싸다. n=300이면 403·4.1=1652.3ms로 A1보다 비싸진다.
인터랙티브 (A): 선택 비용 계산기
15.7 조인 연산 (Join Operations) 보충
r ⋈ s — 두 릴레이션을 조인 조건으로 결합한다. 알고리즘마다 비용이 크게 다르며, 선택은 메모리(M)·인덱스·정렬·조건 종류(equi/non-equi)에 좌우된다.
Silberschatz 7e §15.5 보충. 예제 릴레이션: student (nr=5,000, br=100 블록), takes (ns=10,000, bs=400 블록). 비용은 block transfer (+ seek). r=outer(외부), s=inner(내부).
① Nested-loop join (중첩 루프 조인)
for each tuple tr in r: for each tuple ts in s: if (tr, ts) 조인 조건 만족 → 결과에 추가. 인덱스 불필요·조건 무관(임의 θ에 적용 가능)하지만 가장 비싸다.
- 최악 (버퍼=각 1블록)
nr·bs + br전송,nr + brseek. (r의 튜플마다 s를 통째로 다시 읽음.)- 최적 (작은 릴레이션이 메모리에 다 들어감)
br + bs전송,2seek.- 규칙
- 작은 릴레이션을 outer로 두면 더 싸다.
예) r=student outer: 5000·400 + 100 = 2,000,100 전송. r=takes outer: 10000·100 + 400 = 1,000,400 전송 (더 쌈). 한 릴레이션이 메모리에 다 들어가면: 100 + 400 = 500 전송.
② Block nested-loop join (블록 중첩 루프 조인)
튜플 단위가 아니라 블록 단위로 짝짓는다: outer의 각 블록마다 inner 전체를 스캔. outer 블록의 모든 튜플을 한 번의 inner 스캔에서 처리하므로 nested-loop보다 inner 재읽기가 크게 준다.
- 최악 (버퍼=각 1블록)
br·bs + br전송,2·brseek.- 최적
br + bs전송,2seek.- outer에 (M−2) 블록 할당
⌈br/(M−2)⌉·bs + br전송,2·⌈br/(M−2)⌉seek. (output·inner용으로 2블록 예약.)
예) r=student outer, M=2: 100·400 + 100 = 40,100 전송 (nested-loop의 2,000,100보다 50배↓). M=27 (outer 25블록): ⌈100/25⌉·400 + 100 = 4·400+100 = 1,700 전송.
③ Indexed nested-loop join (인덱스 중첩 루프 조인)
inner(s)의 조인 속성에 인덱스가 있으면, outer의 각 튜플에 대해 inner 전체를 스캔하는 대신 인덱스로 매칭 튜플만 조회(selection)한다. equi-join / natural join에 적합.
c = 인덱스로 s에서 한 건을 selection하는 비용 (예: equality on key면 c=(hi+1)(tT+tS)). r의 br 블록을 읽고, r의 각 튜플(nr개)마다 인덱스 조회 c를 더한다.
④ Merge join / Sort-merge join (병합 조인)
두 입력이 조인 속성으로 정렬되어 있으면, 두 정렬 목록을 동시에 훑으며 한 번씩만 스캔해 매칭한다(external sort-merge의 merge 단계와 동일한 발상). equi-join에 적합.
- 이미 정렬됨
br + bs전송 (+ seek). 각 블록을 한 번씩만 읽는다.- 정렬 안 됨
- 위 비용에 r·s 정렬 비용(§15.5 external sort-merge)을 더한다.
예) student·takes가 조인 속성으로 정렬되어 있으면 100 + 400 = 500 전송.
⑤ Hash join (해시 조인)
조인 속성에 해시 함수 h를 적용해 r·s를 같은 파티션끼리만 묶는다. build(작은 쪽으로 in-memory 해시 테이블 구성) → probe(다른 쪽으로 매칭 조회). equi-join 전용.
- 재귀 분할 불필요 (한 파티션이 메모리에 들어감)
3·(br + bs)전송. (분할 시 읽기+쓰기 2회 + probe 읽기 1회.)- 재귀 분할 필요
2·(br + bs)·⌈logM−1(bs) − 1⌉ + br + bs전송.
build relation은 작은 쪽을 쓴다. 주의점: hash table overflow / skew(편향) → 일부 파티션이 너무 커지면 recursive partitioning 필요. hybrid hash join은 메모리에 여유가 있으면 첫 파티션을 디스크에 쓰지 않고 메모리에 유지해 I/O를 줄인다.
예) 재귀 분할 불필요 시 student·takes: 3·(100+400) = 1,500 전송.
조인 알고리즘 비교
| 알고리즘 | 정렬 필요 | equi-only | 메모리 의존 | 언제 최적 / 비용 |
|---|---|---|---|---|
| Nested-loop | 아니오 | 아니오 | 큼 | 임의 θ, 작은 릴레이션. nr·bs+br (최악) |
| Block nested-loop | 아니오 | 아니오 | 큼(M↑ 유리) | 인덱스 없고 정렬 안 됨. br·bs+br (최악) |
| Indexed nested-loop | 아니오 | equi/θ(인덱스 가능 조건) | 작음 | inner 조인속성에 인덱스, outer 작음. br(tT+tS)+nr·c |
| Merge join | 예(또는 정렬 비용) | 예 | 중간 | 두 입력 정렬됨. br+bs |
| Hash join | 아니오 | 예 | 중간 | equi-join, 정렬 안 됨, 인덱스 없음. 3(br+bs) |
Nested-loop: 최악 nr·bs+br 전송 / nr+br seek, 최적 br+bs 전송 / 2 seek (작은 쪽 outer). Block nested-loop: 최악 br·bs+br, M−2 할당 시 ⌈br/(M−2)⌉·bs+br. Indexed nested-loop: br(tT+tS)+nr·c. Merge join: 정렬 전제로 br+bs. Hash join: 3(br+bs) (재귀 분할 없을 때).
인터랙티브 (B): 조인 비용 계산기 ★
Nested-loop vs Block nested-loop (전송 수 비교)
15.8 기타 연산 (Other Operations) 보충
나머지 관계 연산들의 구현은 대부분 정렬(sort) 또는 해시(hash) 기법을 재사용한다 — 비용도 그에 준한다.
Silberschatz 7e §15.6. 핵심은 “sort 기반 ↔ hash 기반 두 갈래”라는 점이다.
Duplicate elimination (중복 제거)
정렬 후 인접한 같은 튜플 제거, 또는 해시로 같은 버킷에 모아 제거. 비용은 external sort-merge / hash와 유사.
Projection (Π)
각 튜플에서 속성을 추린 뒤(저렴), 중복 제거가 필요하면 위 sort/hash 비용이 추가된다.
Aggregation (집계: sum/avg/count…)
group by 키로 정렬하거나 해시하여 그룹을 모은다. 그룹별 running aggregate(누적값)를 유지하면 모든 튜플을 메모리에 둘 필요가 없다.
Set operations (∪ ∩ −)
union·intersection·difference 모두 정렬 기반(merge하며 처리) 또는 해시 기반(같은 버킷에서 처리)으로 구현. merge join과 유사한 비용.
Outer join (외부 조인)
left/right/full outer join은 nested-loop 변형(매칭 없는 튜플도 null 채워 출력) 또는 merge/hash join 변형으로 구현. 기반 조인 비용에 준한다.
15.9 표현식 평가 (Evaluation of Expressions) 보충
질의는 여러 연산이 트리로 묶인 표현식이다. 중간 결과를 저장하느냐(materialization) 아니면 바로 흘려보내느냐(pipelining)가 비용을 가른다.
Silberschatz 7e §15.7.
Materialization (구체화)
하위(자식) 연산의 결과를 임시 릴레이션(temporary relation)에 디스크로 저장한 뒤, 상위(부모) 연산이 그것을 읽어 들인다. 트리를 한 레벨씩 평가하는 단순한 방식이지만, 임시 결과를 쓰고 다시 읽는 추가 I/O가 든다.
Pipelining (파이프라이닝)
하위 연산이 튜플을 만들 때마다 임시 저장 없이 상위 연산으로 즉시 전달한다. 디스크 I/O를 줄여 보통 더 싸다. 두 방식:
- Demand-driven (pull)
- iterator / lazy. 상위가 필요할 때 하위에서 끌어온다.
open–next–close인터페이스. - Producer-driven (push)
- 하위가 튜플을 만들어 상위로 밀어 올린다.
정렬(sort)이나 hash join의 build 단계처럼 입력 전체를 다 받아야 첫 결과를 낼 수 있는 연산은 파이프라인의 끝에서 막힌다(blocking). 이런 지점은 materialization이 불가피하다. 한편 double-pipelined hash join은 양쪽 입력을 동시에 받아 들어오는 대로 양방향으로 probe하여, 스트리밍 입력에서도 결과를 흘려보낼 수 있다.
인터랙티브: Materialization vs Pipelining 데이터 흐름
15.10 핵심 정리 (Exam Cheatsheet)
시험 직전 한 번 더. 공식과 단계 위주로.
| 주제 | 꼭 기억할 것 | 핵심도 |
|---|---|---|
| 처리 3단계 | Parsing & translation → Optimization → Evaluation. parser가 syntax·relation 검증 후 relational algebra로 변환, 엔진이 plan 실행. | 🎯 핵심 |
| 흐름도 | query → [parser&translator] → relational-algebra → [optimizer]←statistics → execution plan → [evaluation engine]←data → output. 마름모=엔진, 박스=데이터, 실린더=디스크. | 🎯 핵심 |
| 최적화 | 동등 표현식·여러 알고리즘 중 최저비용 plan 선택. 비용 추정은 catalog 통계(튜플 수·크기). | 🎯 핵심 |
| 비용 공식 | Cost = b·tT + S·tS. disk 지배적, CPU·network 무시. worst case 가정. | 🎯 최빈출 |
| tS·tT | HDD 4ms / 0.1ms, SSD 20~90µs / 2~10µs (4KB). | 🎯 핵심 |
| Sort-Merge | Stage1 create runs(M블록 정렬→write), Stage2 N-way merge. N≥M이면 pass당 M−1 run 병합. | 🎯 핵심 |
| 정렬 block transfer | br(2⌈log⌊M/bb⌋−1(br/M)⌉+1). 최종 pass write 미포함(부모로 pipe). | 🎯 최빈출 |
| 정렬 seek | 2⌈br/M⌉ + ⌈br/bb⌉(2⌈log…⌉−1). | 🎯 핵심 |
| 선택 σ 보충 | A1 linear tS+brtT; A2/A4key (hi+1)(tT+tS); A3 primary nonkey hi(tT+tS)+tS+b·tT; A4nonkey (hi+n)(tT+tS); A5/A6 comparison. ∧=A7~A9, ∨=A10(모두 인덱스), ¬=linear. | 🎯 핵심 |
| 조인 ⋈ 보충 | Nested-loop 최악 nr·bs+br(작은쪽 outer); Block n.l. 최악 br·bs+br, M−2 할당 ⌈br/(M−2)⌉·bs+br; Indexed n.l. br(tT+tS)+nr·c; Merge join br+bs(정렬 전제); Hash join 3(br+bs). | 🎯 최빈출 |
| 기타 연산 보충 | 중복제거·projection·aggregation·set·outer join 모두 sort 또는 hash 기반(비용 유사). | 보충 |
| 표현식 평가 보충 | Materialization(임시 저장, 추가 I/O) vs Pipelining(즉시 전달). Demand-driven(pull, iterator open-next-close) / Producer-driven(push). sort·hash build는 blocking → pipeline 불가. | 보충 |