[응용디비] 외부 정렬

0. 개요

1GB data를 정렬하고자 한는데 RAM이 1MB뿐이라면 정렬을 어떻게 해야할까?
=> 흔히 알고 있는 내부 정렬로는 해결할 수 없음
=> 외부 정렬을 사용

• 내부 정렬(Internal sorting)
  : 모든 데이터가 주기억장치(RAM)에 한번에 올라와서 정렬 (주로 작은 크기의 데이터를 처리할 때 사용)
  e.g Quick Sort, Merge Sort, Heap Sort, etc.

• 외부 정렬(External sorting)
  : 대용량의 데이터를 정렬( 메인 메모리의 용량을 넘어서는 데이터를 정렬할 때 사용)

  • 대부분의 경우 하드 디스크를 이용하여 정렬을 수행
  • 일반적으로 분산 데이터 처리나 데이터베이스 등에서 사용

※ 메모리의 사용 여부 차이
내부 정렬은 모든 데이터가 메모리에 올라와서 정렬되지만, 외부 정렬은 데이터를 작은 조각으로 나누어 메모리에 올리고, 이를 정렬한 후 다시 병합하는 과정을 거쳐 정렬을 수행합니다. 이러한 과정에서 하드 디스크에 대한 입출력(I/O)이 필요하므로 내부 정렬에 비해 느린 속도를 보입

1. External merge sort

• Two-way sort requirese 3 buffers
  : 입력 데이터(비정렬 파일)를 2개의 파일로 분할한 후 병합하여 하나의 출력 버퍼로 내보낸다. 따라서 main memory 에서 3개의 버퍼를 사용

1) Two-way External Merge Sort 예시

• 'merge' 키워드가 붙는 이유?
  한 번에 모든 데이터를 정렬할 수 없으므로 여러번 쪼개서 main memory에서 정렬한 후 이를 합치는 방식이기 때문에
  

• 4단계를 거침 (divide & conquer)
  ① N(7)개의 page를 각각의 부분 리스트로 분할
  ② 2개씩 병합 (4개의 부분리스트)
  ③ 2개씩 병합(2개의 부분리스트)
  ④ 2개씩 병합
• number of pass = $\lceil \log_2(N) \rceil$
• total cost = 2xNx$\lceil \log_2(N) \rceil$
  (∵ 매 단계 마다 N개의 page를 READ/WRITE 연산)

2) General External Merge Sort

• buffer의 개수가 3개 이상이라면 어떻게 일반화 할 수 있나?

e.g. N(108)개의 page를 B(5)개의 buffer page로 외부 병합 정렬을 수행하고자 한다.
① $\lceil N/B \rceil$ 개의 sorted runs를 생성
=>e.g 5개의 buffer page가 main memory에 존재하므로 매번 5개의 page를 disk에 읽어와 main memory에서 5개의 page를 정렬한 sorted runs가 22개 생긴다. 이떄 마지막 sorted runs는 3개의 page로 sorted run이 생긴다.
② buffer가 5개이므로 4 way merge sort(1개는 output buffer, 4개가 input buffer로 사용)
$\lceil 22/4 \rceil$ = 6
6 sorted runs of 4x5 pages (last runs with 2x4 pages)
③ 4-way merge sort
=> $\lceil 6/4 \rceil$ = 2
2 sorted runs of 4X20pages (last runs with 2x28 pages)
④ merge 2 sorted runs
=> 4단계
=> cosst = 2 X 108 X 4 = 864 pages

cost = 2 X N X # of pass