Query Processing
Query processing(질의 처리)은 사용자가 작성한 고수준 쿼리(SQL 등)를 내부적으로 효율적으로 실행할 수 있는 저수준 연산으로 변환하고, 최적의 실행 계획을 선택하여 실제로 결과를 산출하는 일련의 과정을 의미한다. 이 과정은 데이터베이스 시스템의 성능과 효율성에 직접적으로 영향을 미친다.
Query Processing의 3단계
1. Parsing and Translation
- 사용자가 입력한 쿼리의 문법(syntax)과 의미(semantics)를 검사한다.
- 쿼리를 내부 표현(주로 relational algebra expression, 관계 대수식)으로 변환한다.
- 파서는 SQL 문법 오류를 체크하고, 존재하지 않는 relation이나 attribute가 사용되었는지 검증한다.
- view가 사용된 경우 정의로 치환하고, 쿼리를 관계 대수식으로 변환한다.
2. Optimization
- 동일한 의미의 여러 관계 대수 표현식(equivalent expressions) 중에서 가장 효율적인 실행 계획(execution plan)을 선택한다.
예시:
- 두 표현식은 결과가 같지만, 실제 실행 비용은 다를 수 있다.
- 각 관계 대수 연산은 다양한 알고리즘으로 수행될 수 있다.
- 이들 연산의 조합(primitive operations sequence)이 query-evaluation-plan(질의 평가 계획)이 된다.
- 예: 인덱스를 사용할 수도 있고, 전체 relation scan 후 조건에 맞지 않는 튜플을 버릴 수도 있다.
3. Evaluation
- 선택된 query-evaluation-plan을 실제로 실행한다.
- evaluation engine이 실행 계획을 받아, 데이터에 접근하여 쿼리 결과를 반환한다.
Query Optimization의 세부 내용
- Query Optimization은 여러 가능한 평가 계획 중에서 비용(cost)이 가장 낮은 계획을 선택하는 과정이다.
- 비용은 데이터베이스 카탈로그의 통계 정보(예: relation의 튜플 개수, 튜플 크기 등)를 활용하여 추정한다.
- 주요 내용:
- 쿼리 비용 측정 방법
- 관계 대수 연산별 다양한 평가 알고리즘
- 전체 표현식 평가를 위한 조합 최적화 방법
요약
- Query processing은 parsing & translation, optimization, evaluation의 3단계로 구성된다.
- 각 단계는 데이터베이스 시스템의 효율적이고 정확한 질의 처리를 위해 필수적이다.
- 특히 optimization 단계에서 다양한 실행 계획 중 최적의 계획을 선택하는 것이 시스템 성능에 큰 영향을 미친다.
데이터베이스 쿼리 비용 측정 및 선택 연산 최적화
쿼리 비용 측정 방법
주요 비용 요소
- 디스크 접근: 가장 지배적인 비용 요소
- Seek 횟수 × 평균 seek 시간
- 블록 전송 횟수 × 평균 블록 전송 시간($$t_T$$)
CPU 및 네트워크 통신 비용은 일반적으로 무시(단순화 목적)
비용 계산 공식
- Tt: 전송된 블록 수
- Ts : seek 연산 횟수
선택 연산(Selection) 최적화 기법
1. 파일 스캔 (Algorithm A1)
- Linear Search 방식
- 적용 조건: 모든 유형의 선택 조건, 인덱스 없을 때
- 비용 계산: Cost estimate = br block transfers + 1 initial seek
- br : 관계(relation)의 전체 블록 수
- 최적화: cost = (0.5 br) block transfers + 1 seek
2. 인덱스 스캔 (B+-Tree 활용)
A2: 기본 B+-트리 (고유 키 검색)
- 조건: 기본 키(primary key) equality 검색
- seek한다음에 trans 해야되므로 tT + tS이다.
- 이 과정을 B+트리구조에서 탐색하는데 leaf노드까지 가는데 h(트리높이) (tT + Ts)가 걸리고, leaf노드에서 실제 데이터를 보는데 1 (tT + Ts) 추가로 걸린다.
A3: 기본 B+-트리 (비고유 키 검색)
- 특징: 연속 블록에 저장된 레코드 접근
- b: 일치 레코드가 포함된 블록 수
- h * (tT + tS)로 leaf 포인터까지 도달한다.
- A2에서는 tT + Ts으로 끝날텐데, 비 고유키이 때문에 여러개를 transfer해야될수도 있다.
- leaf포인터로 실제 데이터를 조회하는데 tS가 걸리고 b개의 블록을 옮기는데 b*tT가 걸린다.
3. 보조 인덱스 활용 (A4)
- 후보 키 검색
- 비후보 키 검색
- secondary index는 연속적으로 저장하지 않기 때문에 일일히 seek후 tranfer를 해야된다.
비교 조건이 포함된 Selection 연산
비교 연산(예: σ{A ≤ v}(r), σ{A ≥ v}(r))이 포함된 selection은 다음과 같은 방식으로 구현할 수 있다.
- Linear file scan: 전체 relation을 순차적으로 스캔하며 조건을 만족하는 튜플을 찾는다.
- Index 활용: 인덱스를 사용하는 경우, primary index와 secondary index에 따라 접근 방식과 비용이 다르다.
A5. Primary B+-tree index, comparison
- relation이 A 속성 기준으로 정렬되어 있고 primary B+-tree index가 존재할 때 사용한다.
- σ{A ≥ v}(r): 인덱스를 사용해 첫 번째 tuple(튜플) ≥ v를 찾고, 그 이후 relation을 순차적으로 스캔한다.
- σ{A ≤ v}(r): relation을 처음부터 순차적으로 스캔해 첫 번째 tuple > v가 나올 때까지 탐색한다. 인덱스를 사용하지 않는다.
A6. Secondary B+-tree index, comparison
- secondary index가 존재할 때 사용한다.
- σ{A ≥ v}(r): 인덱스를 사용해 첫 번째 인덱스 엔트리 ≥ v를 찾고, 인덱스를 순차적으로 스캔하며 record pointer를 찾는다.
- σ_{A ≤ v}(r): 인덱스 리프 페이지를 순차적으로 스캔하며 pointer를 찾는다.
- 각 pointer로 실제 레코드를 파일에서 읽어야 하므로, 각 레코드마다 I/O가 발생한다.
- 조건에 따라 linear file scan이 더 효율적일 수 있다.
복합 Selection 구현
Conjunction (AND 조건, 교집합)
- σ_{θ1 ∧ θ2 ∧ ... ∧ θn}(r) 형태의 selection
- A7. 하나의 인덱스를 활용한 conjunction:
- 조건 중 하나(혹은 여러 개)에 인덱스가 있으면, 해당 인덱스를 사용해 후보 레코드를 찾고, 나머지 조건은 메모리에서 검사한다.
- A8. 복합 인덱스를 활용한 conjunction:
- 복합(다중 키) 인덱스가 있으면 이를 사용한다.
- A9. 여러 인덱스의 교집합을 활용한 conjunction:
- 각 조건마다 인덱스를 사용해 record pointer 집합을 얻고, 이들의 교집합을 구해 파일에서 레코드를 읽는다.
- 일부 조건에 인덱스가 없으면, 파일에서 읽은 후 메모리에서 조건을 검사한다.
Disjunction (OR 조건, 합집합)
- σ_{θ1 ∨ θ2 ∨ ... ∨ θn}(r) 형태의 selection
- A10. 여러 인덱스의 합집합을 활용한 disjunction:
- 모든 조건에 인덱스가 있을 때, 각 인덱스로부터 pointer를 얻어 합집합(union)을 구한 뒤, 해당 레코드를 파일에서 읽는다.
- 일부 조건에 인덱스가 없으면 linear scan이 더 효율적일 수 있다.
Negation (NOT 조건)
- σ_{¬θ}(r) 형태의 selection
- 파일 전체를 linear scan하며 조건을 만족하지 않는 레코드를 찾는다.
- θ에 대해 일치하는 레코드가 매우 적고, 인덱스가 적용 가능하다면 인덱스를 사용할 수도 있다.
External Sort-Merge 정렬 알고리즘 동작 과정
1. 정렬된 Run 생성 단계 (Run Creation Phase)
- 메모리 크기 M(page 단위)만큼 relation(릴레이션)에서 데이터를 읽어온다.
- 읽어온 M block을 메모리 내에서 정렬한다(예: quicksort 등 사용 가능).
- 정렬된 데이터를 디스크에 임시 파일로 저장한다. 이 임시 파일을 run이라 부른다(R0, R1, R2, ...).
- relation의 모든 데이터를 처리할 때까지 위 과정을 반복한다.
- 이 단계가 끝나면 여러 개의 정렬된 run이 생성된다.
2. Run 병합 단계 (Merge Phase)
(1) N < M인 경우 (run 개수 < 메모리 블록 수)
- 각 run마다 1 block씩 메모리에 buffer로 할당한다.
- 추가로 1 block은 output buffer로 사용한다.
- 각 run의 첫 block을 메모리로 읽어온다.
- 모든 buffer page에서 정렬 순서상 가장 앞선 record를 선택한다.
- 선택한 record를 output buffer에 쓴다. output buffer가 가득 차면 디스크에 쓴다.
- 해당 record는 input buffer page에서 삭제한다. buffer page가 비면 그 run의 다음 block을 읽어온다.
- 모든 input buffer page가 빌 때까지 이 과정을 반복한다.
(2) N ≥ M인 경우 (run 개수 ≥ 메모리 블록 수)
- 한 번에 모든 run을 병합할 수 없으므로 여러 번의 merge pass가 필요하다.
- 각 pass마다 연속된 (M-1)개의 run을 그룹으로 묶어 병합한다.
- 병합된 결과는 더 긴 새로운 run으로 저장된다.
- 예를 들어, M=11이고 run이 90개라면, 한 pass에서 10개씩 묶어 9개의 run으로 줄어든다. 각 run의 길이는 10배가 된다.
- 모든 run이 하나로 합쳐질 때까지 pass를 반복한다.
이렇게 External Sort-Merge 알고리즘은 메모리에 적합하지 않은 대용량 relation을 효율적으로 정렬하기 위해, 데이터를 여러 번에 걸쳐 읽고, 정렬된 작은 단위(run)로 쪼갠 뒤, 단계적으로 병합하여 최종적으로 하나의 정렬된 결과를 만들어낸다.
핵심은 메모리 크기에 맞게 데이터를 나누고, 여러 번의 병합을 통해 점진적으로 정렬을 완성하는 점이다.
External Merge Sort – Cost analysis
External Merge Sort에서 relation r이 차지하는 block 수를 br이라고 한다.
- 초기 run 생성 단계에서는 relation 전체를 한 번 읽고(1회), 정렬된 run을 디스크에 한 번 쓴다(1회). 따라서 총 2br block transfer가 발생한다.
- 초기 run의 개수는 ⎡br/M⎤이다. (M: 메모리 크기, 페이지 단위)
- 이후 merge 과정에서는, run의 개수가 매 pass마다 M-1배씩 감소한다.
- 총 merge pass의 수는 ⎡log_{M-1}(br/M)⎤이다.
- 각 merge pass마다 relation 전체를 한 번 읽고(1회), 한 번 쓴다(1회). 즉, 2br block transfer가 필요하다.
- 단, 마지막 pass에서는 결과가 바로 parent operation으로 전달되므로 write cost를 계산하지 않는다.
따라서 전체 block transfer는 다음과 같다:
block의 갯수(초기에 읽을때 필요) + block의 갯수 * merge pass의 횟수(logm-1(br/m))
merge 과정에서 run마다 1 block씩만 buffer로 쓰면, 디스크 seek가 너무 많이 발생한다.
따라서, run마다 bb(buffer block) 단위로 buffer를 할당하여, bb block씩 read/write하는 것이 바람직하다.
이 경우, 위의 M을 ⎣M/bb⎦로 대체하여 계산한다.
Seek cost
- run 생성 단계: 각 run을 한 번 읽고, 한 번 쓸 때마다 seek가 발생한다. 총 2 ⎡br / M⎤ seek.
- merge 단계: 각 merge pass마다 2 ⎡br / bb⎤ seek가 필요하다. 마지막 pass는 write가 필요 없다.
- 전체 seek 수는 다음과 같다:
- 2 ⎡br / M⎤ + ⎡br / bb⎤ × (2 ⎡log_{⎣M/bb⎦}(br/M)⎤ - 1)
Join Operation 구현 방법 종류
DBMS에서 join 연산을 구현하는 방법에는 여러 가지가 있다.
- Nested-loop join
- Block nested-loop join
- Indexed nested-loop join
- Merge-join
- Hash-join
적절한 알고리즘 선택은 cost estimate(비용 추정)에 따라 결정된다.
예시 데이터:
- student relation: 5,000 tuples, 100 blocks
- takes relation: 10,000 tuples, 400 blocks
Nested-Loop Join
r ⋈θ s (theta join)을 계산할 때,
for each tuple tr in r:
for each tuple ts in s:
if (tr, ts) satisfy θ:
결과에 추가- r: outer relation, s: inner relation
- index가 필요 없고, 어떤 join 조건에도 사용 가능하다.
- 모든 tuple 쌍을 검사하므로 비용이 크다.
Worst case: 메모리에 relation 각각 1 block만 적재 가능할 때
- outer block r을 읽는다(br) + r의 레코드당 bS blocker을 읽는다.(nr + bs) - 이중 반복문
- outer block 한번 seek(br) + inner block iteration마다 seek(nr)
- inner는 interation다 돌리면, 다시 그때 맨 처음을 다시 seek 하므로 nr이다.
- outer는 one block만 저장하므로 총 block의 갯수만큼(br) seek이 걸린다
- 작은 relation이 메모리에 모두 적재 가능하다면, 그 relation을 inner로 사용해 비용 감소
- br + bs block transfers, 2 seeks
예시:
- student를 outer로 할 때: 5,000 × 400 + 100 = 2,000,100 block transfers, 5,100 seeks
- takes를 outer로 할 때: 10,000 × 100 + 400 = 1,000,400 block transfers, 10,400 seeks
- student가 메모리에 모두 적재 가능하면, 비용은 500 block transfers
Block Nested-Loop Join
block 단위로 outer/inner relation을 처리하는 nested-loop join의 변형이다.
for each block Br of r:
for each block Bs of s:
for each tuple tr in Br:
for each tuple ts in Bs:
if (tr, ts) satisfy θ:
결과에 추가
r block당 s전체를 읽으므로 br * bs이고, r 전체를 불러오므로 br을 더한다.
br번 s를 seek하고 br번 r을 seek 하므로 : br + br = 2*br이다.
개선 방법:
- outer relation을 M-2 block 단위로 묶어서 처리(M=메모리 크기)
- inner relation과 output에 2 block buffer 사용
- inner relation의 scan 횟수를 br → ⎡br / (M-2)⎤로 줄임
- 비용: ⎡br / (M-2)⎤ × bs + br block transfers + 2 ⎡br / (M-2)⎤ seeks
Indexed Nested-Loop Join
inner relation의 join attribute에 index가 있을 때 사용
- join이 equi-join 또는 natural join이고, inner relation에 index가 있으면 file scan 대신 index lookup 가능
- outer relation의 각 tuple마다, index를 사용해 inner relation에서 조건을 만족하는 tuple을 찾음
Worst case: buffer에 outer relation 1 page만 적재 가능할 때, outer의 각 tuple마다 inner에 대해 index lookup
- c: index traversal 및 matching tuple fetch 비용(보통 selection 비용과 유사)
- 양쪽 relation 모두 index가 있으면, tuple 수가 더 적은 쪽을 outer로 선택
Nested-Loop Join Cost 예시
- student ⋈ takes (student를 outer로)
- takes에 primary B+-tree index(ID 속성, index node 당 20 entry)
- takes: 10,000 tuples, B+-tree height 4, 실제 data 접근 1회 추가 필요
- student: 5,000 tuples
Block nested-loops join:
- 400 × 100 + 100 = 40,100 block transfers + 2 × 100 = 200 seeks (worst case)
Indexed nested-loops join:
- 100 + 5,000 × 5 = 25,100 block transfers 및 seeks
Sort-Merge-Join
- 두 relation을 join attribute로 정렬(sort)한 뒤, merge 단계에서 join 수행
- merge 단계는 sort-merge의 merge와 유사
- join attribute 값이 중복될 경우, 같은 값에 대해 모든 tuple 쌍을 매칭해야 함
- equi-join, natural join에 사용 가능
- 모든 join attribute 값에 대한 tuple이 메모리에 적합할 경우, 각 block은 한 번만 읽으면 됨
- 비용: br + bs block transfers + (정렬 비용, 만약 relation이 미정렬 상태라면)
Hash-Join
- equi-join, natural join에 사용
- hash function h를 사용해 두 relation을 partition
- r, s의 각각의 tuple을 join attribute 값에 따라 동일한 hash partition에 배치
- r의 ri와 s의 si만 서로 비교하면 됨(다른 partition은 비교 불필요)
- partition 단계: relation을 hash function h로 분할, 각 partition마다 1 block output buffer 사용
- build phase: s의 각 partition을 메모리에 적재해 in-memory hash index 생성(다른 hash function 사용)
- probe phase: r의 각 partition을 디스크에서 읽어와, build된 hash index로 join 수행
비용(재귀적 partitioning 필요 없는 경우):
- bb: input/output buffer에 할당된 block 수
- partitioning: 2(br + bs)
- build/probe: br + bs
- α: 부분적으로 채워진 block 처리 오버헤드build input 전체가 메모리에 적합하면 partitioning 불필요, 비용은 br + bs로 감소
Hash-Join Cost 예시
- instructor(br=100), teaches(bs=400), memory size=20 blocks
- instructor를 build input으로, 20 block씩 5개 partition
- teaches도 80 block씩 5개 partition
- partitioning: 각 relation 1 pass
- 총 비용(부분 block 무시): 3(100+400) = 1,500 block transfers 2(⎡100/3⎤ + ⎡400/3⎤) = 336 seeks (input buffer 3 block, output buffer 5 block)
복합 Join
conjunction(AND) 조건: r θ1∧θ2∧...∧θn s
- nested loop, block nested loop 사용 가능
- 또는 r θi s로 단순 join 결과를 구한 뒤, 나머지 조건을 추가로 필터링
disjunction(OR) 조건: r θ1∨θ2∨...∨θn s
- nested loop, block nested loop 사용 가능
- 또는 개별 join 결과의 union으로 처리: (r θ1 s) ∪ (r θ2 s) ∪ ... ∪ (r θn s)
Duplicate Elimination (distinct)
구현 방법:
- Sorting 기반
- 데이터를 정렬하면 중복 레코드가 인접하게 배치됩니다.
- 인접한 중복 레코드 중 하나만 남기고 삭제합니다.
- Hashing 기반
- 동일한 hash bucket에 중복 레코드가 모이도록 합니다.
- 각 bucket 내에서 중복을 제거합니다.
Projection
- 특정 컬럼만 선택하는 연산입니다.
- 프로젝션 수행 후 위의 Duplicate Elimination 방법으로 중복을 제거합니다.
Set Operations (집합 연산)
종류: Union(∪), Intersection(∩), Difference(−)
구현 방법:
- Sort-Merge 변형 또는 Hash-Join 변형 사용
Hash-Join 기반 구현 예시:
- 두 relation을 동일한 hash function으로 partition합니다.
- 각 partition i에 대해:
- ri에 대해 in-memory hash index를 구축합니다.
- si를 처리하며 연산 수행:
- Union: si의 튜플을 hash index에 없을 때만 추가 → 최종 index의 튜플을 결과로 출력
- Intersection: si의 튜플이 hash index에 있으면 결과로 출력
- Difference: si의 튜플이 hash index에 있으면 삭제 → 남은 튜플을 결과로 출력
Outer Join
목적: Non-matching tuples를 null로 채워 결과에 포함시킵니다.
구현 방법:
- Join 후 Non-matching Tuples 추가
- Inner Join 결과에 null-padded된 non-participating tuples를 추가합니다.
- Merge Join 수정
- Merge 중에 s와 매칭되지 않는 r의 튜플을 null로 채워 출력합니다.
- Hash Join 수정
- Probe 단계에서 매칭되지 않는 r 튜플을 null로 채워 출력합니다.
Aggregation (집계 연산)
예시:
SELECT dept_name, AVG(salary)
FROM instructor
GROUP BY dept_name구현 방법:
- Sorting 또는 Hashing으로 그룹화합니다.
- 그룹 생성 시 집계 함수를 실시간 적용합니다.
- count, sum, min, max: 그룹별로 누적 계산
- avg: sum과 count를 유지한 후 최종적으로 나눔
Evaluation of Expressions
1. Materialization (구체화)
방식:
- 연산을 단계별로 수행하며, 중간 결과를 디스크에 저장합니다.
- 예: σ(building="Watson")(department) → ⋈(instructor) → π(name)
단점:
- 중간 결과를 디스크에 쓰고 읽는 오버헤드가 큽니다.
- 최적화: Double Buffering: 출력 버퍼를 2개 사용해 디스크 쓰기와 연산을 병행합니다.
2. Pipelining (파이프라이닝)
방식:
- 여러 연산을 동시에 수행하며, 중간 결과를 직접 전달합니다.
- 예: σ → ⋈ → π를 디스크 저장 없이 연속 처리
장점:
- 디스크 I/O가 없어 비용이 낮습니다.
- 제약: Sort, Hash-Join과 같은 blocking operation에는 적용 불가능합니다.
이처럼 DBMS는 쿼리 최적화를 위해 Materialization과 Pipelining을 상황에 따라 선택하며, 집계 및 집합 연산은 정렬/해싱을 활용해 효율적으로 처리합니다.
반응형
댓글