Ch15_Query_Processing

Chapter 15. Query Processing

한 줄 핵심: SQL 질의는 파싱 → 최적화 → 실행의 3단계로 처리되며, 옵티마이저는 동치 표현·알고리즘 조합(= evaluation plan) 중 비용(cost) 이 가장 낮은 것을 고른다. 이 장의 비용 모델은 디스크 I/O만 본다: $b\cdot t_T+S\cdot t_S$ (블록 전송 × 전송시간 + seek × seek시간). 이 잣대로 selection(A1~A10), external sort-merge, join(nested-loop 계열)의 비용을 “블록을 몇 번 읽고 헤드를 몇 번 옮기는지” 직접 세어 유도한다.

이 챕터가 답하는 핵심 질문

• Q1. 질의 처리는 어떤 단계로 이뤄지고 왜 최적화가 필요한가?
• Q2. 질의 비용은 무엇으로 어떻게 측정하는가? ($t_T$, $t_S$)
• Q3. Selection은 어떤 알고리즘(A1~A10)으로, 각각 비용은 얼마인가?
• Q4. 메모리에 안 들어가는 데이터는 어떻게 정렬하는가(external sort-merge)? 비용은?
• Q5. Join은 어떤 알고리즘으로 구현하고 비용은 어떻게 비교되는가?

---

Q1. 질의 처리는 어떤 단계로 이뤄지고 왜 최적화가 필요한가?

A. SQL 문장은 ① Parsing & translation → ② Optimization → ③ Evaluation의 3단계로 처리되며, 같은 질의에 대해 동치 표현과 알고리즘 조합이 여러 개라서 비용이 가장 낮은 evaluation plan을 골라야 한다.

1. Parsing and translation — 질의를 내부 형태로 번역 후 관계대수로 변환. 파서는 문법 검사·릴레이션 존재 확인.
2. Optimization — 동치인 여러 방법 중 최저 비용을 골라 execution plan 생성.
3. Evaluation — execution engine이 plan을 실행해 답 반환.

query → [parser/translator] → relational-algebra expr → [optimizer] → execution plan
query output ← [evaluation engine] ←────────────────────────────────────┘

SQL 처리 과정을 내비게이션으로 보면

“서울→부산 가줘”가 SQL이라면, parser는 목적지를 좌표로 바꾸고, optimizer는 고속도로·국도·기차 같은 여러 경로 중 예상 시간이 가장 짧은 것을 고른다. evaluation engine은 그 경로대로 실제로 이동한다.

중요한 점은 사용자가 “어느 길로 가라”고 말하지 않아도 된다는 것이다. SQL은 원하는 결과를 말하고, DBMS가 어떻게 실행할지를 고른다.

왜 동치 표현이 여러 개인가:

select salary from instructor where salary < 75000;

${\sigma }_{salary<75000}({\Pi }_{salary}(instructor))\equiv {\Pi }_{salary}({\sigma }_{salary<75000}(instructor))$

또 각 연산마다 여러 알고리즘이 있다(위 selection: index로 75000 미만을 찾거나, 전체 스캔하며 버리거나). “어떤 표현을 + 어떤 알고리즘으로” 실행할지 명시한 것이 evaluation plan.

• Query Optimization: 모든 동치 plan 중 최저 비용 선택. 비용은 database catalog 통계(튜플 수·튜플 크기 등)로 추정. (연산 조합으로 전체 표현을 평가하는 법은 슬라이드 회색 처리 = 미강의.)

---

Q2. 질의 비용은 무엇으로 어떻게 측정하는가?

A. 비용 척도로 total resource consumption을 쓰고, CPU·결과 쓰기 비용은 무시한 채 디스크의 블록 전송 횟수와 seek 횟수만으로 $b\cdot t_T+S\cdot t_S$로 계산한다.

• 시간 비용 요인: disk access, CPU, network. 측정 기준은 response time(총 경과시간) 또는 total resource consumption(총 자원 소비).
• 이 장은 total resource consumption을 사용(response time은 추정 어렵고, 공유 DB에선 자원 최소화가 합리적).
• 단순화 가정: CPU 비용 무시(실제 시스템·병렬 시스템은 고려), 결과를 디스크에 쓰는 비용 미포함(출력은 상위 연산으로 바로 전달 가능).

디스크 비용 모델:

기호	의미	직관
$t_T$	블록 1개 전송 시간	책 한 권 꺼내 옮기는 시간(읽기=쓰기 가정)
$t_S$	seek 1회 시간(block-access time)	디스크 헤드를 이동시키는 시간

$\text{Cost}=b\cdot t_T+S\cdot t_S(b\text{개 블록 전송}+S\text{회 seek})$

매체별 실제 값(4KB 블록): HDD $t_S=4$ msec, $t_T=0.1$ msec / SSD $t_S=20$–90 μsec, $t_T=2$–10 μsec.

왜 seek가 따로 비싼가

HDD는 헤드를 물리적으로 움직여야($t_S=4ms$) 위치에 도달하고, 도착 후 연속 블록은 술술 읽힌다($t_T=0.1ms$, seek의 1/40). 그래서 “연속으로 한 번에”(seek 1회) vs “흩어진 곳 띄엄띄엄”(seek 여러 회)의 차이가 크고, 이것이 모든 비용 공식에서 ”$+t_S$ 항이 몇 개 붙는가”로 나타난다.

버퍼와 worst-case 가정: 데이터가 버퍼에 상주하면 I/O를 피할 수 있으나 반영이 어렵고, 가용 메모리는 실행 시점에만 안다 → worst-case 추정: 버퍼에 아무것도 없고 최소 메모리만 가용이라 가정(실무는 더 낙관적).

---

Q3. Selection은 어떤 알고리즘(A1~A10)으로, 각각 비용은 얼마인가?

A. 인덱스 없이 전체를 훑는 file scan(A1)부터, 클러스터링/보조 인덱스 + 등호/비교 조건(A2A6), 복합 조건의 AND/OR 처리(A7A10)까지 있으며, 핵심은 “매칭 레코드가 연속 블록에 모여 있으면 seek 1회, 흩어져 있으면 레코드당 seek”라는 점이다.

예시: ${\sigma }_{salary<75000}(instructor)$. 가정: 튜플은 한 파일에, 블록은 연속(contiguously) 저장. File scan=인덱스 없이 / Index scan=인덱스 사용(조건이 그 인덱스 search-key에 대한 것이어야 함).

A1 — Linear Search: 모든 블록 스캔하며 검사.

• 비용 = $b_r$ block transfers + 1 seek (블록이 연속이라 시작 위치로 헤드 1번만 이동 후 쭉 읽음).
• key 등호면 찾는 순간 멈춤 → 평균 $(b_r/2)$ + 1 seek. 조건 형태·정렬·인덱스 유무와 무관하게 항상 적용 가능(만능이지만 느림).

A2 — Clustering index, equality on key (레코드 1건):
$\text{Cost}=(h_i+1)(t_T+t_S)$

• $h_i$=인덱스 높이. 루트→리프 하강 노드마다 seek+전송($h_i$회) + 레코드 블록 1번(+1). 내부 노드가 버퍼에 있는 흔한 경우 $h_i=1$로 둘 수 있음.

A3 — Clustering index, equality on non-key (여러 건, 연속 블록):
$\text{Cost}=h_i(t_T+t_S)+t_S+t_T\cdot b(b=\text{매칭 블록 수})$

• 인덱스 하강 + 첫 데이터 블록 seek 1회 + 연속 $b$블록 쭉 읽기. 연속 저장 덕에 seek 한 번.

A4 — Secondary index, equality on key/non-key:

• candidate key(1건): $(h_i+1)(t_T+t_S)$ — A2와 동일.
• non-key($n$건): 매칭 레코드가 서로 다른 블록에 흩어질 수 있음
  $\text{Cost}=(h_i+n)(t_T+t_S)$
• 레코드 하나당 seek+전송 1회씩 → 매우 비쌀 수 있음($n$이 크면 A1보다 못함). (bucket 접근 비용은 미고려 — 시스템이 record-id로 non-unique key를 unique하게 만들기 때문.)

A5 — Clustering index, comparison(릴레이션이 $A$로 정렬):

• ${\sigma }_{A\ge v}$: 인덱스로 첫 $\ge v$ 찾고 끝까지 순차 스캔 → $h_i(t_T+t_S)+t_S+t_T\cdot b$.
• ${\sigma }_{A\le v}$: 인덱스 안 씀! 파일 처음부터 첫 $>v$까지 순차 스캔($\le v$인 것은 어차피 맨 앞에 모여 있음).

A6 — Secondary index, comparison:

• ${\sigma }_{A\ge v}$: 인덱스 첫 $\ge v$ 엔트리부터 리프 순차 스캔하며 포인터 수집. ${\sigma }_{A\le v}$: 리프 처음부터 첫 $>v$까지.
• 포인터가 가리키는 레코드 fetch에 레코드당 I/O 1번 → 선형 스캔이 더 쌀 수 있음. $\text{Cost}=(h_i+n)(t_T+t_S)$.

복합 조건 A7~A10:

알고리즘	조건	방법
A7	AND, one index	${\theta }_i$ + A1~A6 중 ${\sigma }_{{\theta }_i}$ 비용 최소인 것 실행, 나머지 조건은 메모리 버퍼에서 검사
A8	AND, composite index	적절한 복합(multiple-key) 인덱스 사용
A9	AND, intersection of identifiers	각 조건 인덱스로 포인터 집합 → 교집합 → 레코드 fetch (인덱스 없는 조건은 메모리 검사)
A10	OR, union of identifiers	모든 조건에 인덱스가 있어야 적용(없으면 linear scan). 포인터 집합들의 합집합 → 레코드 fetch

AND vs OR의 비대칭

AND는 인덱스 하나로 후보를 좁힌 뒤 나머지를 메모리에서 걸러도 된다. OR은 인덱스 없는 조건이 하나라도 있으면 그 조건 만족 튜플을 찾으러 어차피 전체를 훑어야 해서 인덱스 전략이 무의미해진다.

숫자로 느끼는 selection 비용 — "흩어지면 seek가 폭발한다"

$instructor$가 블록 $b_r=500$개, 인덱스 높이 $h_i=2$, HDD($t_S=4ms$, $t_T=0.1ms$)라 하자. dept_name='Finance' 조건에 맞는 교수가 100명, 그 100개 레코드가 100개의 서로 다른 블록에 흩어져 있다고 가정.

방법	식 대입	I/O 시간
A1 linear scan	$500t_T+1t_S=50+4$	54 ms (블록은 연속이라 seek 단 1회)
A3 clustering index (매칭 100건이 연속 5블록에)	$h_i(t_T+t_S)+t_S+5t_T=2(4.1)+4+0.5$	약 12.7 ms (연속이라 seek 거의 없음 → 최고)
A4 secondary index (매칭 100건이 흩어짐)	$(h_i+100)(t_T+t_S)=102\times 4.1$	약 418 ms (레코드마다 seek 1회 → linear보다 8배 느림!)

교훈: 같은 100건을 찾아도 연속이면 seek 1번, 흩어지면 100번. 이래서 “secondary index가 너무 많은 레코드를 매칭하면 차라리 linear scan(A1)이 낫다”는 말이 나온다 — 위에서도 A4(418ms) > A1(54ms).

---

Q4. 메모리에 안 들어가는 데이터는 어떻게 정렬하는가? 비용은?

A. External sort-merge로 정렬한다 — ① $M$블록씩 읽어 메모리 내 정렬 후 run으로 쓰고(create runs), ② run들을 $M-1$-way로 반복 병합(merge)한다. 비용은 transfers $b_r(2\lceil {\log }_{M-1}(b_r/M)\rceil +1)$, seeks $2\lceil b_r/M\rceil +b_r(2\lceil {\log }_{M-1}(b_r/M)\rceil -1)$.

정렬이 필요한 이유: 결과 정렬 출력, merge join 같은 연산의 전처리. 메모리에 다 들어가면 quicksort, 안 들어가면 external sort-merge. (인덱스로 정렬 순서 읽기는 튜플마다 블록 접근 1번 발생 가능.)

알고리즘 ($M$=메모리 페이지 수):

• 1단계 Create sorted runs: 릴레이션 끝까지 반복 — (a) $M$블록 읽기 (b) 메모리 내 정렬 (c) run $R_i$로 쓰기. → 크기 $M$짜리 정렬 조각 $N=\lceil b_r/M\rceil$개 생성.
• 2단계 Merge (N-way merge, $N<M$ 가정): 입력 run 버퍼 $N$개 + 출력 버퍼 1개. repeat: 모든 버퍼 페이지 중 가장 앞선 레코드를 골라 출력 버퍼에 쓰고(가득 차면 디스크로), 그 레코드를 삭제, 버퍼 페이지가 비면 그 run의 다음 블록 읽기. until 모든 입력 버퍼가 빌 때까지.

비유: 정렬된 카드 더미 $N$개에서 매번 맨 위 카드 중 가장 작은 것을 뽑아 새 더미에 쌓기.

$N\ge M$이면 여러 pass: 연속 $M-1$개 run씩 병합. 한 pass는 run 수를 $M-1$배 줄이고 run 길이를 $M-1$배 늘린다. (예: $M=11$, run 90개 → 한 pass 후 9개, 각 10배 길이.)

작은 숫자로 전 과정 따라가기 ( $b_r=12$블록, $M=3$)

메모리에 3블록만 올릴 수 있는데 정렬할 데이터는 12블록.

[1단계 run 생성] 3블록씩 읽어 메모리 내 정렬 → run 4개 (각 3블록)
   R1[정렬됨] R2[정렬됨] R3[정렬됨] R4[정렬됨]

[2단계 merge] M-1 = 2-way merge (입력 버퍼 2 + 출력 버퍼 1)
  pass 1: (R1,R2)→A,  (R3,R4)→B     ← run 4개 → 2개, 각 길이 2배(6블록)
  pass 2: (A,B)→최종 정렬 결과       ← run 2개 → 1개 (완료!)

매 merge는 “정렬된 더미들의 맨 위 카드 중 가장 작은 것을 뽑아 쌓기”의 반복. pass 수 $=\lceil {\log }_{M-1}(b_r/M)\rceil =\lceil {\log }_2(12/3)\rceil =\lceil {\log }_{2}4\rceil =2$ 와 정확히 일치 → 공식의 ${\log }_{M-1}$이 “몇 번 더 병합해야 1개로 합쳐지나”임을 알 수 있다.

비용 — Block Transfers:

단계	transfers	왜?
Run 생성	$2b_r$	전체 읽고($b_r$) 정렬해 쓰기($b_r$)
Merge pass 수	$\lceil {\log }_{M-1}(b_r/M)\rceil$	pass마다 run 수가 $M-1$분의 1로
각 pass	$2b_r$	전체 읽고 다시 쓰기
마지막 쓰기	$-b_r$ 제외	최종 출력은 상위 연산에 직접 전달 가능 → 모든 연산에서 최종 쓰기 비용 무시

$\boxed{\text{Total transfers}=b_r\left(2\lceil {\log }_{M-1}(b_r/M)\rceil +1\right)}$

비용 — Seeks:

단계	seeks	왜?
Run 생성	$2\lceil b_r/M\rceil$	run당 읽기 seek 1 + 쓰기 seek 1 (run 내부는 연속)
각 merge pass	$2b_r$	여러 run을 번갈아 읽고/쓰므로 블록마다 헤드 이동
마지막 pass	쓰기 seek 제외	최종 쓰기 안 함

$\boxed{\text{Total seeks}=2\lceil b_r/M\rceil +b_r\left(2\lceil {\log }_{M-1}(b_r/M)\rceil -1\right)}$

두 공식이 닮은 이유

둘 다 “pass 수 × pass당 비용 − 마지막 쓰기” 구조. 차이는 run 생성뿐: transfer는 $2b_r$이지만 seek는 run 단위라 $2\lceil b_r/M\rceil$로 훨씬 적다. merge는 읽기가 여러 run에 흩어져 보수적으로 블록마다 seek로 잡는다.

---

Q5. Join은 어떤 알고리즘으로 구현하고 비용은 어떻게 비교되는가?

A. Nested-loop(튜플 쌍 전부) → Block nested-loop(inner를 블록 단위로 재스캔) → Indexed nested-loop(인덱스로 매칭 튜플만 콕 집음) 순으로 개선되며, 공통 원리는 “디스크에서 같은 데이터를 다시 읽는 횟수를 줄이는 것”이다.

기호: $b_r,b_s$=릴레이션 블록 수, $n_r$=레코드 수. 예제 수치: student(record 5,000 / block 100), takes(record 10,000 / block 400). (Merge-join은 슬라이드 회색 = 미강의.)

Nested-Loop Join

이중 for문: outer $r$의 각 튜플마다 inner $s$ 전체를 검사. 인덱스 불필요, 어떤 조건에도 가능, 매우 비쌈.

for each tuple t_r in r:          ← outer를 한 번 훑음
    for each tuple t_s in s:      ← 그때마다 inner를 통째로 다시 읽음(!)
        if (t_r, t_s) 조건 만족: 결과에 추가

왜 이렇게 비싼가 — "outer 튜플 한 개당 inner 전체를 다시 읽는다"

outer 튜플이 $n_r$개면 inner 전체 스캔($b_s$블록)을 $n_r$번 반복한다. student를 outer로 두면 student 튜플 5,000개 × takes 400블록 = 2,000,000 블록 전송. 도서관에서 학생 명단의 한 명마다 수강기록 책 전체를 처음부터 다시 펼쳐 보는 격이다 → 다음 BNLJ가 “책을 블록 단위로 본다”로 이걸 고친다.

$\text{worst: }{n}_r\cdot b_s+b_r\text{ transfers},n_r+b_r\text{ seeks}$

• outer 튜플마다 inner 전체($b_s$) 재읽기 → $n_r\cdot b_s$, outer 1회 → $+b_r$. seek: inner 스캔마다 1회($n_r$) + outer 블록마다($b_r$).
• 작은 릴레이션이 메모리에 통째 들어가면 그것을 inner로 → $b_r+b_s$ transfers + 2 seeks.
• 예제: student outer = $5000\times 400+100=2,000,100$ transfers, 5,100 seeks / takes outer = 1,000,400 transfers, 10,400 seeks / student가 메모리에 다 들어가면 500 transfers.

Block Nested-Loop Join

블록 단위로 짝짓는 변형 — inner의 각 블록을 outer의 모든 블록과 짝.

for each block B_r in r:          ← outer를 블록 단위로
    for each block B_s in s:      ← inner도 블록 단위로
        for each t_r in B_r, t_s in B_s:   ← 메모리에 올라온 두 블록 안에서만 짝짓기
            if 조건 만족: 결과에 추가

무엇이 좋아졌나 — 재읽기 단위가 "튜플마다"→"블록마다"

NLJ는 inner를 outer 튜플 수($n_r$)만큼 재스캔했지만, BNLJ는 outer 블록 수($b_r$)만큼만 재스캔한다. student 예: 재스캔 횟수가 $5,000\to 100$으로 50배 감소, 지배항이 $n_r{b}_s\to b_r{b}_s$로 줄어든다. 같은 책을 “학생 한 명마다” 다시 펴는 대신 “한 페이지(블록)에 적힌 학생들을 한꺼번에 처리하고” 다음 페이지로 넘어가는 셈.

$\text{worst: }{b}_r\cdot b_s+b_r\text{ transfers}+2b_r\text{ seeks},\text{best: }{b}_r+b_s\text{ transfers}+2\text{ seeks}$

• inner 전체 재스캔 횟수가 $n_r$회 → $b_r$회로 감소(5000→100!)가 핵심. seek: outer 블록당 (자기 읽기 1 + inner 스캔 시작 1) = $2b_r$. best = inner가 메모리에 통째.

Indexed Nested-Loop Join

inner join 속성에 인덱스가 있으면 file scan을 index lookup으로 대체.

• 적용 조건: ① equi-join/natural join, ② inner의 join 속성에 인덱스(join용으로 새로 만들 수도).
• 동작: outer $r$의 각 튜플 $t_r$마다 인덱스로 $s$의 매칭 튜플을 찾음.

$\text{Cost}=b_r(t_T+t_S)+n_r\cdot c$

• $c$ = $t_r$ 1개에 대해 인덱스를 타고 매칭 $s$ 튜플을 모두 가져오는 비용 = $s$에 대한 단일 selection 비용(A2~A4 등)으로 추정.
• 양쪽 다 인덱스가 있으면 튜플 수가 적은 쪽을 outer로($n_r$ 줄이기).

비용 총정리

알고리즘	Block transfers	Seeks	비고
Nested-loop (worst)	$n_r\cdot b_s+b_r$	$n_r+b_r$	인덱스 불필요, 매우 비쌈
NL/BNL (best: 작은 쪽 메모리에)	$b_r+b_s$	$2$	작은 릴레이션을 inner로
Block nested-loop (worst)	$b_r\cdot b_s+b_r$	$2b_r$	inner 재스캔이 튜플당→블록당
Indexed nested-loop	$b_r(t_T+t_S)+n_r\cdot c$	(식 포함)	equi/natural + inner 인덱스 필요

예제 비교 — $student\bowtie takes$, student outer. takes는 ID에 primary B⁺-tree(노드당 엔트리 20개), 10,000 튜플 → 높이 4 + 데이터 접근 1 → $c=5$. student 5,000 튜플.

알고리즘	계산	비용
Block nested-loop	$400\times 100+100$ / $2\times 100$	40,100 transfers + 200 seeks
Indexed nested-loop	$100+5000\times 5$	25,100 transfers & seeks (+ CPU도 더 낮을 가능성)

한눈에 보는 직관

• NLJ → BNLJ: inner 재읽기 단위가 “outer 튜플마다”→“outer 블록마다”로 바뀌어 지배항 $n_r\cdot b_s\to b_r\cdot b_s$.
• BNLJ → INLJ: inner 전체 스캔 대신 인덱스로 필요한 튜플만 집음. $n_r\cdot c<b_r\cdot b_s$면 이득.
• 공통 원칙: 디스크에서 같은 데이터를 다시 읽는 횟수를 줄이는 것이 본질.