[Database] DBA급 개발자로 - #9 Sorting & Aggregation

이전 포스팅에서 인덱스의 동시성 처리를 어떻게 수행하는지 살펴봤습니다. 이번 포스팅에서는 sorting과 aggregation이 어떻게 처리되는지 살펴보겠습니다. 

Sorting 

쿼리의 결괏값은 기본적으로 정렬되지 않습니다. 쿼리의 결과를 정렬시키기 위해서는 정렬 작업이 필요합니다. 명시적으로 정렬을 수행(ORDER BY)하거나 쿼리 특성상 정렬이 필요한 경우가 존재합니다(DISTINCT, GROUP BY).

만약 쿼리 결과 전체를 메모리에 올릴 수 있는 크기라면 일반적인 정렬 알고리즘을 사용할 수 있습니다(Quick sort 등). 하지만 쿼리 결과 전체가 메모리에 로드할 수 없는 상황이 존재하므로 중간 결과를 디스크에 저장할 수 있는 정렬 알고리즘이 필요합니다. 

External Merge Sort 

정렬 대상의 데이터를 "run" 단위로 분리해서 각각 정렬하고, 정렬된 "run"을 합쳐서 더 큰 "run"을 만드는 과정을 재귀적으로 수행합니다(Divide-and-Conquer). "run" 단위로 분리할 때 몇 개로 분리하냐에 따라 N-way external merge sort라고 부르기도 합니다. 

2 Way External Merge Sort

그럼 2-Way external merge sort의 I/O 비용에 대해 자세히 살펴보겠습니다. 

2 way external merge sort

2 way external merge sort가 진행되면서 수행되는 pass(정렬 + 병합)의 수는 다음과 같습니다(N은 페이지의 수입니다).

$$ N * (1 + log_{2}N) $$

정렬과 병합이 진행되는 과정에서 I/O는 각각 페이지의 데이터를 읽어올 때 1번 그리고 디스크에 저장하는데 1번씩 발생하기 때문에 총 I/O 비용은 다음과 같습니다. 

$$ 2N * (pass의 수) = 2N * (1 + log_{2}N) $$ 

 

위에서 설명한 2 way external merge sort는 총 3개의 버퍼만을 활용했을 때의 I/O 비용입니다. 만약 3개 이상의 버퍼, 즉 B개의 버퍼를 사용할 수 있다고 가정하면 나중에 사용할 페이지를 미리 버퍼에 가져올 수 있습니다. 정렬 대상인 페이지를 미리 버퍼에 저장할 수 있기 때문에 버퍼가 3개일 때와 달리 디스크로부터 페이지를 메모리에 로드할 때 대기하는 시간을 줄일 수 있습니다. B개의 버퍼를 사용하는 경우 총 pass의 수는 다음과 같습니다. 

$$ 1 + log_{B-1}(N/B)) $$

따라서 총 I/O 비용은 다음과 같습니다. 

$$ 2N * (pass의 수) = 2N * (1 + log_{B-1}(N/B)) $$ 

Aggregations 

Aggregation 함수를 활용해 다수의 값을 하나의 값으로 집계할 수 있습니다. Aggregation을 구현하기 위한 방법으로는 sorting과 hashing이 있습니다. 

Sorting을 통한 Aggregation은 데이터를 정렬 후 집계하는 방식입니다. 만약 데이터가 정렬될 필요가 없이 결과만 필요한 작업이라면(DISTINCT, GROUP BY) 불필요한 정렬 오버헤드가 발생합니다. 이때는 hashing 방법을 사용해 불필요한 정렬 오버헤드를 제거할 수 있습니다. Hashing은 정렬 없이 중복 값을 제거할 수 있기 때문입니다. 

 

마무리 

이번 포스팅을 통해 Sorting과 Aggregation이 어떻게 수행되는지 간략히 살펴봤습니다. 다음 포스팅에서는 Join에 대해 살펴보겠습니다.