데이터베이스의 Sorting(정렬) 알고리즘 (External Sort-Merge)
알고리즘 중에는 다양한 정렬 알고리즘들이 있다.
데이터베이스에서는 일반적인 정렬 알고리즘을 사용하기에는 데이터베이스의 데이터의 크기가 너무 크다.
그래서 데이터베이스에서는 메모리에 데이터를 다 못 올릴 것이다. 그럼 어떻게 정렬을 해야 할까??
데이터베이스에서 정렬은 어떤 방식으로 이루어지는지 알아보자.
데이터베이스에서는 External Sort-Merge 알고리즘을 사용한다.
그럼 External Sort-Merge 알고리즘에 대해 알아보자.
일어나는 과정은 크게 두 단계로 이루어진다.
첫 번째로 'runs'라고 하는 것으로 분할을 하고, 두 번째로 merge하는 두 단계이다.
(메모리에 한 번에 올려서 정렬할 수 없기 때문에 runs로 나누는 것이다)
첫 번째 runs를 생성하는 과정을 살펴보자
(1) relation의 M(메모리의 블럭의 개수, 메모리 사이즈)개의 block을 읽어서 메모리로 불러온다.
(참고로, 메모리와 디스크 사이의 data transfer는 block 단위로 이루어진다.)
(2) 메모리에서 정렬한다.
(3) 다시 디스크 파일에 정렬된 runs를 저장한다.
(즉, relation의 size만큼의 block의 개수 / M = runs의 개수가 된다.)
위의 (1), (2), (3) 과정을 relation 전체에 대해서 수행한다.
즉, run0, run1, run2 ... run N 까지 디스크에 저장이 되는 것이다.
두 번째로 merge하는 과정을 살펴보자
merge는 두 가지 경우로 나누어서 생각해봐야한다.
1) N < M (run의 개수 N이 M(메모리의 블럭의 개수, 메모리 사이즈)보다 작은 경우)
이 경우엔 merge 과정이 한 단계로 끝난다.
각 runs의 첫 번째 record를 골라서 메모리에 올린 다음에 record들을 비교해서 제일 작은 값(오름차순 정렬일 경우)을 output으로 저장하는 것이다.
(runs들은 이미 위의 과정에서 정렬된 상태로 저장되어 있기 때문에 각 run들의 첫 번째 record들 중에 제일 작은 값이 전체에서 제일 작은 값임이 당연하다)
그리고 output으로 나간 record의 run에서 그 다음 값을 메모리로 불러오면 된다.
2) N >= M (run의 개수 N이 M(메모리의 블럭의 개수, 메모리 사이즈)보다 크거나 같은 경우)
이 경우엔 merge 과정이 두 단계 이상해야한다.
이 과정은 글보단 사진을 보고 이해하는 편이 낫다고 생각하여 아래 예시 사진을 보고 이해해보자.
가정은 다음과 같다.
1개의 record가 1개의 block이다.
메모리에는 최대 3개의 record가 들어갈 수 있다.
3개 중에 2개의 block은 input용이고 나머지 1개의 block은 output용이다.
다시 N >= M에 대해 설명하자면,
만약 N < M이라면 merge pass-1 단계에서 끝날 것이다.
하지만 N >= M에서는 merge pass-2 단계까지 가야한다.
위의 사진에서는 메모리는 3개고, runs의 개수는 4개이기 때문에
N >= M 케이스이다.
merge-pass1이 지나면 runs가 4개였다가 2개가 된다.
이것은 4(runs의 개수) / (3(메모리의 block 개수) - 1(output용)) = 2
runs의 개수가 2개가 되었다.
아직 1개의 runs로 병합되지 않았기 때문에 merge pass를 한 단계 더 거쳐야한다.
(과정을 더 자세히 설명하면,
a 19 record와 b 14 record를 메모리에 올리고 (메모리엔 최대 2개의 input만 들어감) 알파벳이 더 낮은
a 19 를 output으로 저장하고 다음 runs에 저장하는 것이다.
그리고 a 19 record가 있던 runs 의 다음인 d 31을 가져온다.
그리고 다시 b 14 record와 d 31을 비교한다.
이 과정을 반복한다.)
merge-pass2가 지나면 runs가 2개였다가 1개가 된다.
이것은 2(runs의 개수) / (3(메모리의 block 개수) - 1(output용)) = 1
이렇게 병합된 runs 하나가 생성되었기 때문에 sorting 과정은 종료되게 된다.
Cost를 계산해보자.
Block Transfer Cost
먼저 block 간의 transfer cost를 먼저 계산해보자
위에서 설명했듯이 br(relation의 size만큼의 block의 개수) / M = runs의 개수가 된다.)
(따라서 br(relation의 size만큼의 block의 개수)는 M * runs의 개수다.)
(1)
맨 처음에 runs를 만드는 cost는 2br이다.
왜냐하면 block 전체 만큼 메모리에 올리고 내려야 하기 때문이다.
(2)
merge pass의 cost를 알아보자.
위의 예시에서 merge pass 과정이 몇 번 이루어져야 하는지 생각해보자.
2^(merge pass 횟수) = 4 로 2번 이루어졌다.
이것을 일반화 해보면
(메모리의 블럭의 개수(M) -1 ) ^ (merge pass 횟수) = br / M(runs의 개수)이다.
이 식을 풀어보면
merge pass 횟수는 아래 식과 같다.
근데 여기서 merge pass 돌 때마다 읽고 쓰는 비용이 있기 때문에
2br *
이다.
(3) 근데 여기서 write 비용은 다시 빼도 되는데 disk로 쓰지 않는 경우가 있을 수 있기 때문이다.
따라서 -br이다.
(1), (2), (3)을 다 더해보면
2br + 2br*
-br이고 정리해보면
아래 사진과 같다. 아래가 block transfer cost이다.
Seek Cost
그럼 이제 찾는 비용, Seek Cost에 대해 알아보자.
(1) run 생성 단계에서는 run의 개수만큼 찾을 것이고 읽고 쓰기 때문에 2를 곱해준다.
따라서
이다.
(2) merge 단계에서는
버퍼 사이즈를 bb라고 할 때
(bb = 위의 예시에서 메모리에 record 1개를 올릴 수 있음을 의미)
br/bb만큼 읽는 곳과 쓰는 곳을 찾는 과정이라 * 2 기 때문에
2 br / bb이고
이것이 각 merge pass마다 이루어지기 때문에
이다
따라서 (1)과 (2)를 더하면 아래와 같다.
이렇게 데이터베이스에서 sorting이 이루어지는 과정을 알아보았다.
참고 :
Database System Concepts 7th edition