[Database] Query Processing

Basic Steps in Query Processing

 

일반적으로 DBMS에서 Query를 처리하는 과정은 다음과 같습니다:

Basic Steps in Query Processing

 

(1) Parsing and translation - SQL을 구문 검사한 후 관계 대수식(Relational Algebra)의 형태로 변환하는 과정입니다.

(3) Evaluation - 선택된 계획을 query-excution engine이 실제로 실행해 결과를 반환하는 과정입니다. 

 

Basic Steps in Query Processing: Optimization

 

relational algebra는 정말 많은 수의 같은 의미를 갖는 표현들을 가질 수 있습니다:

ex

 

따라서 어떤 순서로 primitive operation들을 실행시킬 것인지를 평가해야하며, 이 과정을 통해 결과적으로 실행해야하는 operation들의 sequence를 query-evaluation-plan이라고 합니다:

ex (above)

 

이때 Optimization이란, 이 동일한 plans들 중 가장 적은 cost를 갖는 plan을 찾는 과정을 말합니다.

 

Measures of Query Cost

 

Query의 cost를 계산하는 데에는 많은 요소들이 필요합니다(예를 들어, disk accesses, CPU, or even network communication). 이들 중 Disk accesses는 가장 중요하며, 예측하기 쉽기 때문에 해당 교재에서는 이를 중심으로 cost를 계산합니다. *일반적으로 쓰기 블록은 읽기 블록보다 시간이 더 걸리지만, 교재에서는 동일 가중치로 단순화합니다.

 

간단하게 하기 위해 그냥, number of block transfer와 number of seeks을 이용해서 cost를 측정하겠습니다. 따라서 b block을 전송하고, S번 찾는 경우 다음과 같은 cost가 계산됩니다:

ex

 

Algorithm A1 (Linear Scan)

 

인덱스가 없거나 너무 다양해서 그냥 선형으로 탐색해야하는 경우 사용하는 알고리즘입니다. 이는 선형으로 file block들을 탐색하며 모든 records들을 원하는 조건에 해당하는지 안하는지를 검사하여 원하는 record를 찾아냅니다.

 

relation r에 해당하는 block의 개수가 b라고 했을때, cost는 b*(transfer time) + 1입니다. *마지막 +1은 initial seek에 드는 비용으로 가장 처음 file을 찾을때 드는 비용입니다. 만약 어던 특정한 값을 찾고 scan을 멈추는 경우 평균 cost는 1/2b*(transfer time) + 1입니다.

 

Algorithm A2 (Primary B+-tree index, equality on key)

 

clustered b+-tree를 사용하며, unique key를 통해 원하는 record를 찾는 경우 cost = (h + 1) * (transfer time + seek time)입니다. h = height of b+-tree로, 우선 h(transfer time + seek time)을 통해 원하는 record pointer까지 트리를 타며 이동합니다. 그 후 해당 value로 이동하는 비용인 한 번의 transfer와 seek을 더하면 다음과 같은 비용이 계산됩니다.

 

Algorithm A3 (Primary B+-tree index, equality on non unique key)

 

이는 composite key를 search key로 하는 경우 A2와 마찬가지로 leaf node를 찾는 비용 h(transfer time + seek time) 후, leaf node에 해당하는 block으로 이동하는 비용인 한 번의 (seek time)과, 해당 block 근처에서 나머지 key에 해당하는 record들을 찾는 비용인 b*(transfer time)이 소모됩니다. 

 

즉 composite key (n, v)일때, n=k인 record들을 찾으면 되는것이니 우선 n=k인 leaf node를 찾고, 해당 record가 있는 block으로 넘어가 (k, -∞) 부터 (k, ∞)까지의 record들을 찾습니다. 이때 이들은 연속된 block에 저장되어있을테니, 해당 record들이 들어있는 연속된 block의 숫자인 b만큼 transfer를 하면 됩니다.

 

Algorithm A4 (Secondary index, equality on non unique key)

 

만약 검색하고자 하는 key가 candidate key이고, 하나의 record만을 검색하는 것이라면, cost = (h + 1) * (transfer time + seek time)입니다. 하지만 candidate key가 아니고 여러개의 record를 검색하는 것이라면, matching되는 record의 수가 n일 때 cost = (h + n) * (transfer time + seek time)이 됩니다.

 

왜냐하면 우선 트리의 leaf까지 도달한 후, (k, -∞) 부터 (k, ∞)의 RID나 PK같은 정보를 얻습니다. 그 후 해당 RID나 PK를 이용하여 한 번 더 탐색을 수행해야하고, 각각의 record들은 A3와 달리 연속된 block에 있을것이라 보장할 수 없기 때문에 그냥 record의 수 만큼 (transfer + seek)을 수행해야합니다.

 

Algorithm A5 (Primary B+-tree index, comparison, Relation is sorted on A)

 

만약 A>V인 record들을 찾는 경우, cost = h * (transfer time + seek time) + (seek time) + b * (transfer time) 이 됩니다. 하나하나 살펴보면, 우선 b+-tree의 A=V인 leaf node까지 가는데에 h * (transfer + seek)이고, 한 번의 seek을 통해 찾은 leaf node의 block으로 이동합니다. 그 후 해당 record들을 A에 대해 이미 정렬되어있기 때문에 A>V인 record들은 A=V인 record에 인접하게 있을것이라 기대할 수 있습니다. 따라서 matching되는 record들이 존재하는 block의 개수만큼 transfer만 하면 됩니다.

 

만약 A<V인 record들을 찾는 경우 index를 사용하지 않고 file의 처음부터 A=V인 record가 나올때까지 linear scan(A1)하는 것이 더 빠를 수 있습니다.

 

Algorithm A6 (Secondary B+-tree index, comparison)

 

A>V인 record들을 찾는 비용 = (h + n) * (transfer time + seek time)입니다. 우선 A=V인 leaf node까지 이동하는데 h * (transfer + seek)이고, B+-tree에서 leaf node level에서 scan을 통해 A>V인 record들의 RID나 PK 정보를 얻습니다. 이렇게 해서 나온 record의 수가 n개 일때, 그 n개의 RID, PK에 대해서 한 번더 탐색을 수행하기 때문에 n * (transfer + seek)이 추가됩니다. 이때 A5와 달리 인접한 block에 있다고 기대할 수 없기 때문에 record의 수만큼 직접 찾아야합니다.

 

A<V인 경우는 B+-tree의 가장 처음 leaf node부터 A=V까지 RID, PK를 수집한 다음 그 수만큼 탐색하면 됩니다. 혹은 그냥 file들을 linear scan하는 것이 더 빠를 수도 있습니다.

 

Implementation of Complex Selections

 

A7 (conjunctive selection using one index)

 

이는 하나의 index(attr.)만을 사용하여 교집합 조건을 걸며 탐색을 하는 경우에 대한 비용입니다. 이는 임의의 한 조건(가능하면 여로 조건) c_i에 해당하는 record들을 A1-A6까지의 알고리즘 중 가장 싼 알고리즘을 이용하여 뽑아냅니다. 그렇게 메모리에 c_i에 해당하는 record들이 들어오면, 메모리에서 나머지 조건들에 대한 판단을 통해 최종 record들을 뽑아냅니다.

 

A8 (conjunctive selection using composite index)

 

여러 개의 index를 사용하여 교집합 조건을 걸어 선택하는 경우는 복합 인덱스(composite index/key)에 해당하는 tree를 이용하여 처리할 수 있습니다.

 

A9 (conjunctive selection by intersection of identifiers)

 

index를 이용하는 방법으로, 각각의 조건에 해당하는 RID나 PK를 뽑아낸 후, 모든 조건에 대해 모두 있는 RID와 PK를 선택하여 record들을 선택합니다. 만약 몇몇 condition이 RID나 PK가 없다면(tree가 없어서), 일단 있는것끼리 뽑아낸 후 메모리에서 처리합니다.

 

A10 (disjunction selection by union of identifiers)

 

만약 모든 condition들에 대해 RID나 PK가 있는 경우, 모든 조건에 대해 하나라도 있는 RID, PK를 선택합니다. 하지만 이는 A9와 달리 임의의 한 condition이 RID, PK(index)가 없다면 사용할 수 없고 그냥 linear search를 통해 구현됩니다.

 

Negation

 

Linear scan을 사용할 수도 있고, A9, A10처럼 index를 사용할 수도 있습니다.

 

Sorting

 

지금까지는 Selection에 대해 살펴봤습니다. 한편 Sorting은 DBMS에서 매우 중요한 연산들 중 하나입니다. 하지만 데이터가 매우 커서 Quick sort와 같은 알고리즘은 memory에 fit하지 못해 사용할 수 없습니다. 그래서 DBMS에서는 external sort-merge algorithm을 사용합니다.

 

External Sort-Merge

 

우선 run을 생성해야합니다.
메모리 buffer에 들어갈 수 있는 block의 수가 M이라고 했을 때 메모리 block M개를 모두 채울 때까지 relation에 있는 block들을 읽어들입니다(cost = b * (transfer time) + b / M * (seek time)). 그 후 메모리 안에있는 M개의 block들에 대해 quick sort, heap sort 등 sort 알고리즘을 통해 정렬합니다. *이는 값들이 모두 메모리 공간안에 있기 때문에 상관없습니다.

 

그렇게 정렬된 M개의 block들을 다시 Run으로 만들어 disk에 저장합니다(cost = b * (transfer time) + b / M * (seek time)). 이렇게 relation에 해당하는 여러 개의 block들을 run의 형태로 만듭니다. 이때 총 cost = 2 * {b * (transfer time) + b / M * (seek time)}

 

이렇게 만들어진 Run의 개수는 총 b / M 개 입니다. 그 후 run들을 merge하면서 정렬합니다.

 

우선 M개의 memory공간을 merge하는데 모두 사용할 수는 없습니다. 그렇게 되면 최소값 하나 찾고, I/O, 하나 찾고, I/O 해야하기 때문에 output buffer로 사용할 한 칸의 block 공간을 만들어 batch로 처리함으로써 성능을 높입니다.

 

다시 돌아와서 한 칸의 output buffer을 제외한 N개의 buffer 공간에 대해(이때 N = M - 1), N개의 run들의 first record들끼리 비교하며 output buffer에 저장합니다. 그 후 output buffer가 가득차면 disk로 flush하고, input buffer가 empty하면 다음 run을 입력으로 하여 반복하여 수행합니다.

 

만약 run의 개수가 N보다 크다면, 여러번의 pass가 필요합니다. 예를 들어 M=11이고, run의 개수가 90개라면, 한 번의 pass가 지나고 9개의 run들이 남아있습니다. 

M=3, External Sort-Merge

 

External Merge Sort - Cost Analysis

 

우선 transfer먼저 살펴봅니다.

 

가장 처음 run을 초기화하는데 2 * b 만큼의 비용이 들고(이하 * (transfer time)은 생략합니다), 총 pass의 길이, 개수는 ⌈log_{(M-1)}(b/M)⌉입니다. 그리고 각각의 pass동안 I/O가 이뤄지므로 이때의 I/O는 읽기 한 번 쓰기 한 번으로 총 2 * b입니다.

 

만약 마지막 pass의 결과를 disk에 쓰지 않고 processing하는데에만 사용한다면 마지막 pass에 대해서는 읽기 연산 만 수행됩니다. 따라서 P = ⌈log_{(M-1)}(b/M)⌉ 라고 했을때,

 

initialize run: 2 * b

pass: (read) b * P + (write) b * (P - 1)

total: 2 * b + b * P + b * (P - 1) = b * (2P - 1 + 2) = b * (2P + 1) 입니다.

 

이때 output buffer의 크기를 1이 아니라, b_b라고 했다면(단 input buffer의 크기는 유지), M은 M/b_b로 치환되어 cost가 계산됩니다. *output buffer의 크기를 늘림으로써 I/O 성능이 더 좋아질 수 있다. 난 seek에 한해서... transfer는 어짜피 b만큼 transfer해야하는건 똑같기 때문이다.

 

Seek 비용은 다음과 같습니다(이것도 마지막 pass에서는 쓰기 제외).

 

initialize run: 2 * ⌈b / M⌉

pass: (read) ⌈b / b_b⌉ * P + (write) ⌈b / b_b⌉ * (P - 1)

total: 2 * ⌈b / M⌉ + ⌈b / b_b⌉ * P + ⌈b / b_b⌉ * (P - 1) = 2 * ⌈b / M⌉ + ⌈b / b_b⌉ * (2P - 1)

 

Join Operation

 

Join연산에 드는 비용에 대해 살펴보겠습니다.

 

Nested-Loop Join

 

가장 오래걸립니다.

Nested-Loop Join

 

이는 두 relation들의 tuple들을 기준으로 중첩 loop를 통해 하나하나 join합니다. 각각의 relation에 대해 하나씩의 block만을 memory에서 hold하는 최악의 경우 transfer에 드는 비용은 n_r * (b_s) + b_r 입니다. relation r이 outer, relation s가 inner일때, 우선 가장 처음으로 r의 block들을 가져와야하기 때문에, b_r만큼의 비용이 들고, r의 각 튜플마다 s 전체를 스캔하기 때문에, n_r * (b_r) 의 transfer 비용이 듭니다. 

 

seek의 경우는 가장 처음 r의 block들을 찾을때, b_r만큼 seek하고, n_r번 relation s의 block들을 seek하기 때문에 총 seek 비용은 b_r + n_r입니다. 즉 작은 relation을 inner로 두면 b_s와 n_r을 최소화할 수 있습니다.

optimization

 

모든 relation들의 block들을 메모리에 넣을 수 있을때는(best case), transfer는 b_r + b_s, seek에는 2번의 비용이 듭니다. 

 

Block Nested-Loop Join

 

outer와 inner를 block단위로 읽어들여서 효율을 높입니다.

Block Nested-Loop Join

 

각 relation당 하나의 block씩만 memory에 넣을 수 있는 worst case의 경우 transfer에는 b_r * b_s + b_r이, seek에는 2 * b_r이 사용됩니다. Best case는 Nested-Loop Join과 마찬가지로 transfer에 b_r + b_s, seek에는 2번의 비용이 듭니다.

 

이때 memory에 M-2개의 input buffer가 존재하는 경우(아마 나머지 2개는 하나는 output, 하나는 outer relation을 위한 buffer), transfer는 ⌈b_r / (M-2)⌉ * b_s + b_r, seek에는 2 *  ⌈b_r / (M-2)⌉가 사용됩니다.

 

Indexed Nested-Loop Join

 

index를 활용해서 join연산을 수행할 수도 있습니다. 이는 equi-join이나 natural join과 같이 indexing을 활용할 수 있는 condition이 존재하는 join에 대해서 사용해야합니다. 또한 inner relation이 indexing이 되어있는 경우 사용합니다.

 

outer tuple하나 읽을 때마다 index로 relation s의 매칭 튜플을 검색하는 방법입니다. 오직 하나의 buffer만을 memory에 넣을 수 있는 worst case에 대하여(이때 buffer에는 outer relation r의 block이 들어갑니다), b_r * (transfer time + seek time) + n_r * c 의 비용이 들어갑니다.

 

우선 b_r * (transfer time + seek time)은 r의 block을 메모리로 가져오는 비용이고, r의 각 튜플에 대해 index로 s의 매칭 튜플을 검색합니다. 이때 c는 index equality 선택 비용으로 만약 A2를 사용한다면 (h+1)(transfer time + seek time)입니다. 만약 outer에 더 적은 양의 tuple을 갖는 relation을 배치하면 cost가 더 줄어들 수 있습니다(n_r이 줄어들어서).

vs.

 

Sort-Merge Join

 

우선 각각의 relation에 대해 sort-merge 알고리즘을 통해 정렬을 수행합니다. 그 후 병합을 통해 join을 수행합니다. 각각의 relation들의 block들을 한 번씩만 읽으면서 내려가면 되기 때문에 transfer 비용은 b_r + b_s이며, seek 비용은 2입니다(한 번에 쭈욱 읽으면 되니까). 만약 이미 정렬이 되어있는 relation이라면 sort비용은 들지 않습니다.

sort-merge join

 

Hash-Join

 

이는 equi-join이나 natural join에서 사용할 수 있으며, hash function h는 각 relation들의 tuple들을 구분짓든 partition를 만드는데 사용됩니다. Hash-join에서 사용하는 용어들은 다음과 같습니다:

• Build(입력) - 교재에서는 relation s, 메모리에 올려 in-memory hash table을 만드는 relation, 일반적으로 더 작은 relation을 말합니다.
• Probe(입력) - 교재에서는 relation r, Build tabel을 탐색하며 매칭 튜플을 찾는 쪽
• h() - 두 릴레이션을 동일하게 나누는 1차 해시 함수
• partition i(r,s) - h와 같은 번호를 받은 튜플 모음. 같은 i 값끼리만 비교하면 됩니다.

 

Partition Phase

 

디스크를 한 번 훑으며 각 튜플을 h(JoinAttr) 값에 따라 bucket file r0, r1, ..., rn, s0, s1, ..., sn으로 써 넣습니다. 이때 linear scan하며, 읽고 쓰기 때문에 2(b_s + b_r)의 transfer 비용이 듭니다.

 

Build & Probe Phase

 

partition별 s_i 전부를 메모리로 읽어 2차 hash function g로 in-memory hash table을 생성합니다. 그리고 r_i를 한 튜플씩 읽어 g에 검색/매칭을 진행하여 결과를 출력합니다. 각각의 tuple들을 block단위로 읽고 쓰기 때문에 (b_s + b_r)의 transfer 비용이 듭니다.

Hash join

cost of hash join

ex

 

Complex Join

 

Conjunctive Join

 

이는 여러 조건들 모두를 만족해야하는(and) join입니다. 이는 (1) NLJ/blocked NLJ를 사용하거나, (2) 조건 중 하나의 condition만 적용해 작은 중간 결과를 만들고, 메모리에서 나머지 조건을 필터링하는 방법을 사용합니다. 

 

Disjunctive Join

 

이는 여러 조건들 중 하나라도 맞으면(or) join하는 연산입니다. 이는 (1) NLJ/blocked NLJ를 사용하거나, (2) 각 조건별 단순 join을 수행한 후 결과 relation들의 union으로 합치는 방법을 사용할 수 있습니다:

(2)

 

Duplicate elimination(distinct)

 

(1) external sort-merge연산을 통해 같은 값을 가지는 record들을 가깝게 붙여놓은 다음 인접 중복을 하나만 남기는 방식을 사용합니다. (2) 혹은 hash방식을 이용하여, 동일 키기 같은 bucket으로 같은 값을 가지는 record들이 모이는 성질을 이용하여, bucket마다 중복을 제거하는 방법을 사용합니다.

 

Projection

 

각 튜플에서 필요한 속성만 남긴 후 중복 제거 로직을 적용합니다.

 

Aggregation

 

(1) group key로 sort-merge를 진행한 후 같은 키가 연속으로 등장할 때마다 누적/계산을 진행합니다. (2) 혹은 해시 기반으로, group key를 기준으로 파티셔닝 후 각 bucket의 record들을 모아 누적/계산을 진행합니다.

 

Set operation

 

hashing을 이용하는 경우 동일 hash h()로 r, s 파티셔닝을 한 후 r_i를 메모리 hash build하고, s을 probe합니다.

이때 (1) UNION은 s_i의 튜플들을 hash table에 삽입, hash table을 결과로 출력합니다.

(2) INTERSECT는 s_i의 튜플들을 table과 비교하며 같은 값이 있다면 결과로 바로 출력합니다.

(3) EXCEPT는 같은 값이 있다면 결과에서 삭제하고, 남은 r_i만을 결과로 출력합니다.

 

Outer Join

 

(1) Merge-sort join시 tr과 매칭되는 ts가 없다면 null로 채우는 방식을 사용하고, (2) hash-join시 probe중 매칭되는 build가 없다면 null로 채우는 방식을 사용합니다.

 

Evaluation of Expressions

 

Optimizer가 고른 Query-Evaluation Plan을 실행하는데, 크게 두 가지 방식이 있습니다.

 

Materialization

 

중간 결과를 디스크에 저장하는 방식으로 트리의 아래부터 시작하여 결과를 임시 테이블로 디스크에 기록합니다. 그리고 다음 연산자는 해당 파일을 읽어 다음 연산을 수행합니다. 이는 항상 적용가능하다는 장점이 있지만 블럭 전송이 2배로 늘어난다는 단점이 있습니다. 그래서 double buffering을 통해 단점을 완화합니다.

 

double buffering은 출력 버퍼를 2개 두어서 하나는 디스크를 쓰는 동안 다른 하나를 채워서 I/O와 CPU를 겹치는 방식입니다.

 

Pipelining

 

이는 중간 저장 없이 직접 전달하는 방식으로 Materialization에 비해 더 값싼 방식이지만 항상 적용 가능한것은 아닙니다(예를 들어: sort, hash-join에는 사용할 수 없다). 이는 크게 Demand-driven과 Producer-driven으로 나뉩니다.

1. 파이프라이닝(pipelining)이 성립하려면

• “한-튜플씩(streaming) → 바로 상위 연산자로 전달” 이 가능해야 합니다.
• 즉 첫 번째 결과가 나오기 전에 전(前) 입력을 모두 읽을 필요가 없어야 합니다.

유형예첫 결과를 만들기 위한 최소 요구

스트리밍(Non-blocking) 연산자	․ 선택 (σ)  ․ 투영 (π)  ․ 중첩 Loop-Join	한 튜플/한 블록 만 있으면 바로 산출
블로킹(Blocking) 연산자	․ 정렬(Sort)  ․ Hash-Join  ․ Duplicates eliminate	입력 전체(또는 큰 덩어리) 를 모아 놔야 첫 튜플 산출 가능

 

따라서 Sort, Hash-Join은 “첫 결과 전까지 시간이 비어 있는” pipeline breaker가 됩니다.

---

2. 정렬(Sort)의 경우

1. 외부 정렬은
   • (1) run 생성 → (2) run 머지 끝까지 해야 실제 정렬 순서가 결정됩니다.
2. Top-K 같은 특수 모드가 아니면 **첫 튜플 자체가 “정렬 전체 결과의 최소값”**이므로
   • 전체 입력을 읽어 두기 전엔 산출 불가 → 상위 연산자에게 아무 것도 줄 수 없음.
3. 따라서 정렬 노드 위에서 파이프라이닝을 끊고 임시 파일(또는 메모리)로 materialize합니다.

---

3. Hash-Join(Grace / Hybrid)의 경우

단계필요 조건파이프라이닝 가능?

(a) Build 단계 – build 관계를 읽어 해시 테이블/파티션 작성	build 입력 전체를 메모리에(또는 디스크 파티션에) 적재해야 한다.	✖ (blocking)
(b) Probe 단계 – probe 튜플 ↔ 해시 조회	해시 테이블이 이미 완성돼 있어야 한다.	✔ (streaming)

 

• 즉 **build 단계가 끝나기 전까진 probe 결과를 낼 수 없으므로,
  join 연산 전체로 보면 첫 결과 산출 전까지 “반쪽 블로킹”**입니다.
• 옵티마이저는 이를 blocking 연산자로 분류하고, 하위 연산들(특히 sort 등)과 파이프라인을 끊어 둡니다.

메모리 안에 build 관계가 다 들어가도 “일단 다 읽어야” 첫 튜플이 나올 수 있으므로 strict streaming 은 불가.

 

(1) Damand-driven(pull)은 부모 -> 자식 호출 체인으로 부모가 자식에게 "다음 튜플 줘!" 하는 것입니다. 이는 lazy evaluation이라고도 불리며 각 연산자는 상태를 기억하여 부모가 호출시 결과를 줄 수 있어야합니다. 이는 사용하는 메모리가 적지만, 함수 호출 시 오버헤드가 발생합니다.

 

(2) Producer-driven(push)은 자식 -> 부모 호출 체인으로 자식 연산자가 결과를 버퍼에 넣고 부모가 꺼내는 방식입니다. 만약 버퍼가 가득 찬다면 자식을 stop됩니다. 이는 배치로 결과를 전송하기 때문에 throughput이 증가하지만, 버퍼 관리나 스케줄 관리가 필요하다는 단점이 있습니다.

 

이 둘은 디스크에 임시 결과를 쓰지 않음으로써 I/O 비용이 materialization에 비해 적습니다.