Heap Sort And Oracle Sorting

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 수행 성능이 향상됨을 볼수 있었다.

 

Faster sorting
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. 쉽게 배우는 알고리즘 - 한빛 미디어