1. Heap Sort
Simple Code
void heapsort(int arr[], unsigned int N)
{
int t; /* the temporary value */
unsigned int n = N, parent = N/2, index, child; /* heap indexes */
/* loop until array is sorted */
for (;;) {
if (parent > 0) {
/* first stage - Sorting the heap */
t = arr[--parent]; /* save old value to t */
} else {
/* second stage - Extracting elements in-place */
n--; /* make the heap smaller */
if (n == 0) return; /* When the heap is empty, we are done */
t = arr[n]; /* save lost heap entry to temporary */
arr[n] = arr[0]; /* save root entry beyond heap */
}
/* insert operation - pushing t down the heap to replace the parent */
index = parent; /* start at the parent index */
child = index * 2 + 1; /* get its left child index */
while (child < n) {
/* choose the largest child */
if (child + 1 < n && arr[child + 1] > arr[child]) {
child++; /* right child exists and is bigger */
}
/* is the largest child larger than the entry? */
if (arr[child] > t) {
arr[index] = arr[child]; /* overwrite entry with child */
index = child; /* move index to the child */
child = index * 2 + 1; /* get the left child and go around again */
} else {
break; /* t's place is found */
}
}
/* store the temporary value at its new location */
arr[index] = t;
}
}
Heap Sort 는 Heap 자료구조를 이용한 Sorting 기법이다.
오라클은 Sort Join 시에 Heap Sort 를 사용한다. (CBO 책에 근거), 따라서 각 Sub List 의 크기, 즉 한번에 정렬해야될 Row 의 수에 따라서, 성능에 차이가 존재한다.
Heap 자료구조는 이진트리 형태를 가진다. 만약 부모의 노드의 키 값이 항상 자식 노드의 키값보다 크거나 같다면 max-heap 이라고 하고, 반대로 부모 노드의 키값이 자식노드의 키값보다 항상 작거나 같다면 min-heap 이라고 한다.
heap 구조는 이진트리의 형태로 구성되며, 배열로 구현한다. 따라서 K[n] 의 child node 는 K[2n], K[2n+1] 이되며, K[n] 의 parent node는 K⌊n/2⌋ 가 된다.
Heap 구조로 Bulid 하는것이 O(n) 의 시간이 걸린다.
n-1 번 실행하는것이 각각 O(log n) 의 시간이 걸리므로 총 수행시간은 O(nlogn) 이다.
2. ORACLE SORT
오라클은 Sort 시에 PGA(또는 UGA) 영역에서 사용하는 정렬 메커니즘은 Heap Sort 를 사용한다. ( 또는 유사한? ) 따라서 정렬메모리 공간에 이진트리를 위한 공간이 따로 마련되어야 한다.
이진트리의 높이는 예를 들어 8개의 로우가 정렬되기 위해서는 log2(n) = 3 인 이진트리가 만들어진다.
1. Merge 시의 비교 횟수는 로우개수 * log2(sort run 개수) 로 추정된다.
2. 메모리 정렬을 위한 비교 횟수는 로우개수 * log2(로우 개수) 로 추정된다.
In-Memory Sort 의 경우 정렬해야 할 로우의 개수가 많다면, 트리의 높이가 log2(로우 개수) 만큼 높아지기 때문에, 탐색하는 시간이 오래 걸리게 되고, 결국 더 많은 CPU 를 소비하게 된다.
sort_area_size 가 높아짐에 따라서 initial Runs 의 개수가 적어지게 된다. 따라서 Disk I/O 도 줄어들게 되며, Merge 시의 비교 횟수 또한 일정 값까지 줄어들게 된다.
하지만 각각의 Run 의 크기가 커짐에 따라서 트리의 높이가 높아져 그만큼 메모리내에서의 비교 횟수 또한 증가하게 된다. ( Trade off 가 존재함 )
성능 저하의 원인이 Disk 가 아니라면 One-Pass Sort 로 수행되도록 하여, 트리의 높이를 줄여 성능을 향상 시킬수도 있을것이다.
위의 내용은 CBO 책에 기반한 것으로써 9i ~ 10g r1 버전을 기반으로 하고 있다.
하지만 10g r2 버전부터 Sort 알고리즘이 수정된것으로 보인다. 실제로 수행되는 것을 보면 10g r2 의 sort 수행 성능이 향상됨을 볼수 있었다.
Starting in 10gr2 we see an improved sort algorithm, Oracle10gRw introduced a new sort algorithm which is using less memory and CPU resources. A hidden parameter _newsort_enabled = {TRUEFALSE} governs whether the new sort algorithm will be used
Heap Sort 를 사용하면 CPU 오버헤드가 많이 발생한다. 따라서 많은 데이터 처리가 가능한 요즘 컴퓨팅 환경으로 접어듬에 따라, DISK I/O 에 집중되었던 COST 방식이 CPU 기반 COST 로 변화하였고,
따라서 메모리 내에서 CPU COST 많이 발생하는 알고리즘에 대해서도 변화가 필요하지 않을까 생각한다.
그런 맥락에서 오라클도 CPU 자원을 아끼기위해 다른 알고리즘으로 변경한것으로 추측한다.
Reference :
1. http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Heapsort
2. Cost Based Oracle Fundamentals Book
3. Introduction to ALGORITHMS
4. 쉽게 배우는 알고리즘 - 한빛 미디어
