19. 13장 : EXTERNAL SORTING (2) - sorting

Formal Specification

파라미터가 어떻게 정의되는지 정리한다.

• F : N 블록의 저장공간을 차지하는 파일

  이 때 파일은 multiset of resords R을 포함한다.

• 여유공간 : 최소 N 블록 이상의 여유공간을 가진 두개의 Scratch Disk가 주어짐

  == 충분한 여유공간이 있다고 가정함!!

• RAM : 고정된 B 블록의 메모리공간이 주어짐 (B < N)

  == RAM 공간은 파일크기보다 작음!

• Fs : 정렬된 파일. 즉 디스크 자체에 정렬된 상태로 저장된다.

• Fh : hash된 파일. 동일한 해시값을 가진 레코드끼리는 반드시 연속적으로저장됨.

  이 때 Fh는 정렬되지 않을 수 있다는 점 주의 (단순히 동일한 해시값을 가진 레코드는 연속되어 저장되는것)

Sorting : two-way sorting

분할정복을 사용한다

Pass0

데이터를 작은 batch로 나누어서 처리한다. 버퍼에 올라가는 사이즈 (보통 한 페이지 단위로) 배치를 정한다.

1. 하나의 배치를 I/O 버퍼로 읽어오고 (메모리로 올린것)

2. 메모리에서 정렬을 사용한다. (퀵소트를 보통 사용하는듯!)

3. 이걸 디스크에 저장한다 -> 이후 정렬된 블록들의 run이라고 부름

4. 파일의 모든 페이지에 대해 시행한다.

pass0이 끝나면, 디스크에는 1블록씩 정렬된 데이터가 저장되어 있다 (하나의 블록에서는 정렬된것!!)

하나의 I/O 버퍼만 사용함

Pass1, 2, 3....

이전 단계의 pass에서 만든 정렬된 run을 merge해준다.

1. 이전 단계에서 생성된 정렬된 run 두개를 디스크에서 읽어와 buffer에 저장한다.

   즉 각 버퍼에는 값들이 정렬된채로 들어갔음

2. 두 입력버퍼에서 가장 작은 값을 선택하여 출력버퍼에 넣는다.

3. 출력버퍼가 가득찰때까지 반복한다..

4. 출력버퍼가 가득차면, 이걸 디스크에 기록한다.

5. 입력버퍼가 빌때까지 반복한다.

6. 끝나면... 디스크에는 두개의 블록 길이를 가진 정렬된 run이 생기게 된다! (이전단계가 pass0라고 생각함ㄴ)

   즉, 이전단계의 run길이의 두배가 되는 정렬된 run이 생기게 되는것

7. 모든 파일이 하나의 run에 들어갈때까지 merge를 반복한다.

3개의 버퍼를 사용한다.

하지만 하나의 스레드를 사용하기 떄문에 double buffering은 아님!!

Cost

분할정복의 cost와 같다!

1. I/O 개수 생각하기

   각각의 pass마다, 파일 전체를 "읽고" 정렬해서 "쓰기" 를 반복한다

   == 한번의 pass에 2N번의 I/O 발생

2. 몇번의 pass가 존재하는지 생각하기

   분할정복!! 파일 전체를 반씩 나눠가며 하므로,, $\lceil \log_2 N \rceil$이 된다.

   근데, Pass0이라는 추가작업이 있으니까 (여기서는 run개수에 변화가 없음) 1을 추가한다

결론 : $2N \cdot (\lceil \log_2 N \rceil + 1 )$

General External Merge Sort

2 way sort보다 더 효율적인 방법이다.

=> B개의 메모리 버퍼를 모두 사용하겠다는 전략!! (2 way sort는 버퍼를 3개밖에 안씀)

B가 3보다 클 때 (버퍼가 많이 있을 떄) 잘 활용하려고 한다.

=> 더 큰 배치를 처리하고, 여러 스트림을 동시에 병합할 수 있다.

Pass0

1. B개의 버퍼를 모두 이용하기 위해, B개의 페이지를 전부 RAM에 올린다.

2. 버퍼에 퀵정렬을 실행해서, 정렬된 RUN을 생성한다.

   이 때, 퀵정렬이 버퍼에 따로 적용되는게 아니라, 모든 버퍼에 통합으로 사용한다

   == 즉, 버퍼에 있는걸 다 합쳐서 하나의 정렬된 B 블럭 크기를 가진 RUN을 만들 수 있는것!

3. 파일 전체에 대해 수행한다.

=> 2 way sort와 다르게, pass0에서 생성되는 하나의 RUN의 크기가 달라졌다.

버퍼를 전부다 이용해서 B블럭 크기를 가진 커다란 RUN을 만들어준다.

최종적으로 $\lceil \frac{N}{B} \rceil $ 개의 RUN이 디스크에 저장된다.

Pass1, 2, 3...

B개의 버퍼중 한개를 출력버퍼로, B-1개를 입력버퍼로 사용해 merge한다.

• 여러개의 페이지로 구성된 RUN을 어떻게 읽어와서 merge하는가?

  하나의 버퍼에는 한개의 페이지만 들어갈 수 있으므로

  각 RUN의 첫번째 페이지부터 RUN에 올린다.

  만약 입력버퍼 한개가 비면, 해당 버퍼에 할당된 RUN의 다음 페이지를 읽어온다.

pass1이 지나갔다고 생각하면

이전 단계에서 생성된 RUN은 B 페이지 길이를 가지고 있었다.

그리고 B-1개의 버퍼에 불러와서 전부 합쳐줬으니까....

=> 결과적으로 B * (B-1) 길이의 RUN이 생성된다.

Cost

똑같이, 한번의 pass에 전체 파일을 읽고 쓰기를 하므로 한번의 pass에서 I/O 개수는 2N이다.

한번의 Pass에서 merge를 할 때, 위에서랑 다르게 B-1개의 입력버퍼를 사용하니까...... $\lceil \log_{B-1} N \rceil + 1$가 된다.

결론 : $2N \cdot (\lceil \log_{B-1} N \rceil + 1 )$

B, N에 따라 몇번의 pass가 존재하는지 정리한 표이다!

앞에서 B tree를 할때처럼, 높은 fan-out을 가질수록 (여기서는 높은 B를 가질수록) 전체 pass의 개수가 줄어들게 된다.

Memory 효율성

두번의 pass만으로 정렬을 마무리하고 싶으면 얼만큼의 메모리공간이 필요할까?!?!

일단 pass0, pass1 이 지난 다음에 생기는 RUN 하나의 크기는 B(B-1)이다.

즉 B(B-1)이, 파일의 크기 (N) 와 같으면 된다!!!

대충 생각하면 N = $B^2$라고 생각할 수 있다.

결론 : B = $\sqrt{N}$