쿼리 프로세싱(Query processing)
쿼리 프로세싱(Query Processing)이란?
데이터베이스에서 데이터를 가져오거나 데이터를 삽입할 때 사용하는 언어를 Query라고 한다.
Query Processing이란 우리가 보낸 Query를 데이터베이스가 처리하는 과정을 말한다.
기본적인 쿼리 프로세싱 과정
1. 입력받은 Query(SQL)를 parser and translator(Compiler)가 relational-algebra expression 형태로 변환한다.
Query(SQL) 예시
SELECT balance FROM account WHERE blanace < 2500;
Relational-algebra expression 예시
parser and translator의 결과가 1개 이상일 수 있다.
2. optimizer가 데이터의 통계 정보를 바탕으로 query 실행 계획을 세운다.
Optimizer는 query를 실행 가능한 계획 중 가장 cost가 낮은 계획을 선택하는 작업이다.
Optimizer 예시
1. balance가 2500보다 작은 값을 Full scan
2. B-Tree Index를 통해 2500의 leat subtree에 있는 값을 반환
1번은 O(N)의 시간 복잡도를 가지고 2번은 log(N)의 시간 복잡도를 가진다.
3. evaluation engine이 세워진 계획을 바탕으로 query를 실행하여 반환한다.
Query-excution cost(쿼리 실행 비용)
디스크에 접근하는 수, cpu에서 처리하는 시간, 분산 시스템끼리 통신하는 비용 등을 종합적으로 계산하여 cost를 산출한다.
많은 상업적 시스템이 오직 디스크에 접근하는 수만 고려한다. (그만큼 디스크 접근의 비용 가장 많은 영향을 준다)
그러면 실제로 cost가 어떻게 계산되는지 알아보겠습니다.
b : 디스크에서 보낸 블록의 수
S : 디스크 탐색의 수
t(T) : 하나의 블록을 보내는데 걸리는 평균 시간
t(S) : 하나의 블록에 접근하는데 걸리는 평균 시간
b개의 block을 전송하고 S개를 탐색하는데 드는 비용
Cost = b * t(T) + S * t(S)
Selection(Linear Search) - A1
블록이 흩어져 있지 않고 순차적으로 저장되어 있다고 가정
Selection을 시행할 때 디스크에 측면에서 살펴보자 (Linear Search)
디스크에 한 번 접근하고 그 뒤로 블록의 개수만큼 전송이 필요하므로
Cost = t(S) + b(r) * t(T)
Select a row where sid(primary key) is equal is 1234 (sid가 1234인 row에 대하여 Select하라)
Best Case
디스크에 접근하고 메모리에 던져 검사했을 때 바로 그 블록이 1234인 경우
t(S) + t(T)
Average Case
t(S) + (b(r) * t(T)) / 2
디스크에 접근하고 순차적으로 메모리에 던져 검사했을 때 가운데에 위치한 블록이 평균으로 걸리는 시간이므로 나누기 2
Worse Case
t(S) + b(r) * t(T)
디스크에 접근하고 순차적으로 메모리에 던져 검사했을 때 마지막 블록이 1234인 경우
Selection(Binary Search) - A2
블록이 흩어져 있지 않고 순차적으로 저장되어 있다고 가정
블록이 정렬되어 있다고 가정
처음에 디스크의 절반(1)에 접근하고 블록을 메모리에 던져 검사한다. ( Binary Search)
찾는 값보다 작은경우 절반 아래의 절반(2)에 접근하여 블록을 메모리에 던져 검사한다.
찾는 값보다 큰 경우 절반 아래의 절반 위의 절반(3)에 접근하여 블록을 메모리에 던져 검사한다.
이를 반복하므로 최악의 경우 log2(b(r))이 수행된다.
따라서 cost = log2(b(r)) * ( t(T) + t(S) )
Selection(Primary Index, Equality check to a key) - A3
A relation이 key에 의해 정렬된 상태
B+tree라고 가정해보자
왼쪽 B+tree도 파일이고 오른쪽 디스크도 파일이다.
B+tree는 leafNode가 순차적으로 정렬되어 있기 때문에 leafNode를 순차적으로 탐색해도 됨 하지만 효율적이지 못함.
트리의 높이(h) 마다 t(S) + t(T)가 발생한다.
또한 진짜 데이터에 대해 메모리 버퍼까지 던지는 것 까지 t(S) +t(T)가 한번 더 발생하므로
cost = (h + 1 ) * ( t(S) + t(T) )
Selection(Primary Index, Comparison) - A6
A relation이 key에 의해 정렬된 상태
어떤 값 v에 대하여
A < v 라면 굳이 index로 탐색할 필요 없이 0번째부터 시작한 뒤 v값을 만날 때까지 메모리로 전송하면 된다.
초기 탐색 t(S) + v값을 만날 때 까지 블록 전송 ( b(r) * t(T) )
최악의 경우는 블록을 모두 전송해야 하므로
cost = t(S) + b(r) * t(T)
A > v 라면 index로 탐색이 필요 하다. 탐색은 A4에서 했듯이 트리의 높이 (h) 만큼 (t(T) + t(S))가 발생한다.
index 탐색 h * (t(T) + t(S)) + 디스크에서 index값 탐색 t(S)) + 블록이 끝날 때까지 블록 전송 ( b * t(T))
최악의 경우 v가 작은값이여서 블록을 모두 전송해야 한다.
cost = (h * (t(T) + t(S))) + t(S) + (b(r) * t(T) )
Selection(conjunction using one primary index)
만약에 어떤 배열에 대하여 세가지 Conjunction을 한다고 가정
세모 = 중간보다 큰 값
네모 = 짝수
동그라미 = key가 7인 값
동그라미를 가장 먼저해야 범위가 많이 줄어들어서 효율적일 것임
즉 Conjunction을 할때는 index를 먼저하는 것이 좋음
Selection(conjunction using one multiple indices)
index가 한 개가 아니라 여러 개일 가능성이 있음
그럴 때는을 index들끼리 먼저 해서 교집합을 찾음
Selection(Negation)
Negation x!= 7
Use linear scan
처음부터 쭉 순회해면서 그냥 7이 아닌것들만 메모리에 던져줌
Selection에 대해 어느 정도 알아보았고 이제 Sorting에 대하여 알아보겠습니다
Sorting
b-Tree에서 정렬된 값을 얻고 싶다.
블록이 퍼져있다면 계속하여 디스크에 접근해야 한다.
계속 디스크에 접근하는게 비 효율적인데 어떻게 해야 할까?
메모리에 모두 던지고 메모리에서 Quick-sort 해버림
하지만 일반적으로 디스크(파일시스템)에 비해 메모리는 작기 때문에 메모리가 초과될 수 있다
그러면 어떻게 해야할까?
External sort-merge algorithm을 사용한다.
External sort-merge algorithm
메모리의 사이즈가 M개의 블록을 감당할 수 있다고 가정합니다.
1. 블록의 개수가 b(r) 개 라면 [b(r) / M ]만큼의 Runs들이 만들어집니다.
블록의 개수는 b(r) = 12개, M = 4이므로 3개의 Runs들이 만들어집니다.
2. Merge the Runs
Runs들의 포인터가 가리키는 값을 비교해 가면서 merge
초기의 포인터는 Runs들의 맨 위 값을 가리킴
값이 쓰이면 포인터의 위치는 바로 아래를 가리키게 함.
R0에서 A값이 쓰이고 포인터의 위치는 C로 이동됨(R1, R2(R1,R2 포인터 값(B, A)과 비교)
R2에서 A값이 쓰이고 포인터의 위치는 D로 이동됨(R0, R1(R0,R1 포인터 값(C, B)과 비교)
R1에서 B값이 쓰이고 포인터의 위치는 D로 이동됨(R0, R2(R0,R2 포인터 값(C, D)과 비교)
이것을 반복하면서 정렬
External sort-merge algorithm은 아래와 같은 수식들을 갖는다.
pass
pass의 경우에는 1의 결과가 나올 때까지 반복하는데
따라서 n pass = [ [b(r)/M] / (M-1)^n ] = 1
양변에 (M-1)^n을 곱하면
[ b(r)/M ]= (M-1)^n
양변에 Log(M-1)을 취하면
[ Log(M-1) b(r)/M] = n
따라서 n번 반복했을 때
[Log(M-1) b(r)/M ]의 수식이 도출된다.
block transfers
블록의 개수 b(r) * pass의 수만큼 read, write 되고 마지막에는 Read만 하여 메모리에 올림
b(r) * ( 2* [log(M-1) b(r)/M ] + 1)
Disk seek
Runs의 개수만큼 Read File에 Write 하기 때문에
2 * [ b(r) / M] 만큼 발생합니다.
한 번에 b(b) 만큼 읽을 수 있다고 하면 Merge 하는 과정에서
한번에 b(b) 만큼 읽을 수 있으므로 [b(r) / b(b) ] 번 읽어야 함
1번 pass 할 때 read, write가 발생한다.
마지막에는 read만 발생하기 때문에 -1
따라서 [b(r) / b(b) ] * ( 2 * [ log(m-1) b(r)/M ] - 1 )
따라서 두 과정을 모두 합하면
2 * [b(r) / M ] + [b(r) / b(b) ] * ( 2 * [ log(m-1) b(r)/M ] - 1 )
Join
depositor와 customer를 join 한다고 가정하겠습니다.
레코드와 블록의 개수는 아래와 같습니다.
n(r) : r의 tuple의 개수
n(s) : s의 tuple의 개수
b(r) : r의 블록의 개수
b(s) : s의 블록의 개수
Nested-loop join
가장 Naive(순진한) 방법
각각의 row에 대하여 2중 포문을 돌리며 join condition에 만족하면 결괏값으로 등록
메모리가 작아서 1개의 블록 쌍만 올릴 수 있는 상황
disk seek
b(depositor) + n(depositor)
block transfer
b(depositor) + n(depositor) * b(customer)
메모리가 충분히 큰 상황
disk seek
2
block transfer
b(depositor) + b(customer)
depositor와 customer의 join 위치를 바꾸게 되면 성능에 차이가 발생하게 됨
disk seek, block transfers가 변화함
Block Nested-loop join
각각의 블록에 대하여 각각의 tuple에 대하여 검사함
Ndested-loop join과 극명한 차이점은 블록 단위로 움직이기 때문에 더 효율적임
메모리가 작아서 1개의 블록 쌍만 올릴 수 있는 상황
disk seek
2 * b(depositor)
block transfer
b(depositor) + b(depositor) * b(customer)
메모리가 충분히 큰 상황
disk seek
2
block transfer
b(depositor) + b(customer)
위 수식을 기반으로 outer relation(외부 relation)을 어떻게 놓는 것이 효과적일까요?
x = b(depositor), y = b(customer)으로 치환한다면
disk seek
2 * x
block transfer
x + x * y
x의 값이 작을수록 절대적으로 좋습니다. ( 블록의 개수가 작은 것을 외부 relation으로 두는 것이 좋다)