[DB] 4. 외부 정렬(External Sorting)

이번 글에서는 DB에서 자주 사용되고, 비용이 비싼 연산인 정렬에 대해 알아볼 것이다.

탐색 키를 기준으로 한 정렬은 DBMS에서 자주 사용되는 연산이다. 대표적으로, 1. 인덱스 생성 시, 2. sort-merge 조인 시, 3. 중복 제거 시에 사용된다.

1. 외부 합병 정렬(External Merge Sort)

외부 합병 정렬은 이름에서 알 수 있듯이 합병 정렬 알고리즘의 아이디어(divide-and-conquer)를 기반으로 한 기법이다.

외부 합병 정렬 알고리즘은 다음과 같다.

1. 파일을 $N$개의 부분 파일로 분할한다.

2. 부분 파일을 $b$개 씩 묶어 내부 정렬을 수행해 총 $\lceil N/b \rceil$개 부분 파일로 재구성한다.

3. 부분 파일을 $b-1$개씩 묶어 정렬해 수행해 총 $\lceil N/b \rceil /( b-1)$개 부분 파일로 재구성한다.

($b$개의 입력 페이지와 1개의 출력 페이지가 필요하다.)

4. 부분 파일 개수가 1이 될 때까지 세 번째 과정을 반복한다.

 

이 과정에서, 부분 정렬은 패스(pass), 정렬된 부분 파일은 런(run)이라 부른다. 또한 두 번째 과정에서 레코드 정렬할 때 아무 내부 정렬 알고리즘(퀵 정렬)을 사용해도 된다.

쉽게 말해, 외부 합병 정렬은 합병 정렬의 CPU와 메모리 간의 데이터 이동 과정 관계를 메모리와 디스크로 확장한 것으로 보면 된다.

 

$N$개 페이지로 구성된 파일을 정렬할 때, 필요한 페이지 입출력 비용은 다음과 같다.

$b+1$개 버퍼 페이지를 사용할 경우, 총 $\log_b lceil N/b \rceil$번의 패스를 수행해야 한다. 그리고, 각 패스마다 $2N$번의 입출력을 수행해야 한다. (모든 페이지를 한번씩 읽고 써야 하기 때문이다.) 그러므로, 총 $2N\log_b(N/b)$의 입출력이 필요하다.

 

왼쪽 그림은 0번째 패스, 오른쪽 그림은 i(>0)번째 패스

3. B+ Tree 기반 정렬

정렬 기준이 되는 탐색 키에 대해 B+ 트리 인덱스가 존재할 경우, 외부 병합 정렬 대신 B+ 트리 인덱스의 데이터 엔트리를 순회함으로써, 탐색 키 순서대로 레코드를 검색할 수 있다.

 

인덱스가 클러스터링된 경우라면 데이터 엔트리를 순회하는 것은 매우 효과적이다. 

클러스터 B+ 트리 인덱스에서 탐색 키 순서로 데이터 레코드를 모두 검색하는 비용은 트리 루트(root)부터 최촤단 데이터 엔트리까지 이동하는 비용, 데이터 엔트리의 모든 페이지 검색 비용($f \cdot N$), 데이터 레코드를 포함하고 있는 모든 페이지 검색 비용($N$)의 합($(f + 1) \cdot N$)이다. ($f$는 데이터 레코드 크기에 대한 데이터 엔트리 크기의 비율)

참고로, 데이터 레코드는 데이터 엔트리는 데이터 레코드보다 훨씬 작기 때문에, 데이터 엔트리 페이지 수는 데이터 레코드 페이지 수보다 작다.

 

하지만, 클러스터링이 되어 있지 않은 경우라면, 비효율적일 가능성이 높다. 

최악의 경우 데이터 레코드마다 한번의 입출력을 요청할 수 있다. 즉, 전체 입출력 비용이 데이터 레코드 수($p$)와 동일하다는 것이다.

비용은 트리 루트(root)부터 최촤단 데이터 엔트리까지 이동하는 비용, 데이터 엔트리의 모든 페이지 검색 비용($f \cdot N$), 데이터 레코드를 포함하고 있는 모든 페이지 검색 비용($p \cdot N$)의 합($(f + p) \cdot N$)이다.

물론, 데이터 엔트리 페이지에 속한 몇 rid가 동일한 데이터 레코드 페이지를 참조할 수 있기 때문에, 총 비용은 이것보다 작을 것이다.

왼쪽: 군집 인덱스, 오른쪽: 비군집인덱스