Basic Idea of External Sorting run 1 run 2 run 3 run 4 run 5 run 6 750 records 750 records 750 records 750 records 750 records 750 records run 1 run 2 run 3 1500 records 1500 records 1500 records run 1 3000 records run 1 4500 records 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 4)
Binary Sort/Merge Sorting Phase 초기 run 들을 sorting 한후, 2 개의외부파일에저장 Merging Phase 각파일에서하나씩 run을선택하여큰 run으로병합하여세번째파일에저장 결과파일을다시 2 개의파일로분배한후병합진행 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 5)
Binary Sort/Merge 의예 Input File (Run = 3) 50 110 95 10 100 36 153 40 120 60 70 130 22 140 80 Sorting Phase의완료후 File 1: (50 95 110) (40 120 153) (22 80 140) File 2: (10 36 100) (60 70 130) 첫번째병합의결과 File 3: (10 36 50 95 100 110) (40 60 70 120 130 153) (22 80 140) 첫번째병합후재분배의결과 File 1: (10 36 50 95 100 110) (22 80 140) File 2: (40 60 70 120 130 153) File 3: 비었음 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 6)
Binary Sort/Merge 의예 - 계속 두번째병합의결과 File 3: (10 40 36 50 60 70 95 100 110 120 130 153) (22 80 140) 두번째병합후재분배의결과 File 1: (10 40 36 50 60 70 95 100 110 120 130 153) File 2: (22 80 140) File 3: 비었음 세번째병합의결과 File 3: (10 22 40 36 50 60 70 80 95 100 110 120 130 140 153) 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 7)
다른 Sort/Merge Algorithm 들 Balanced Binary Sort/Merge 입력파일수 = 출력파일수 = 2 파일수가동일하므로, 파일의재분배필요없음 Balanced k-way Sort/Merge k-way k Sort/Merge 의 Balanced version 파일수가증가하므로더적은수의병합과 run 가짐 k 의값이무한히증가할수있는가? Polyphase Sort/Merge 입력파일수 출력파일수일경우에도, 재분배필요없음 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 8)
Ex: Balanced a Binary Sort/Merge Input File: 50 110 95 10 100 36 153 40 120 60 70 130 22 140 80 Sorting Phase 의완료후 File 1: (50 95 110) (40 120 153) (22 80 140) File 2: (10 36 100) (60 70 130) 첫번째병합의결과 File 3: (10 36 50 95 100 110) (22 80 140) File 4: (40 60 70 120 130 153) 두번째병합의결과 File 1: (10 36 40 50 60 70 95 100 110 120 130 153) File 2: (22 80 140) 세번째병합의결과 File 3: (10 22 36 40 50 60 70 80 95 100 110 120 130 140 153) 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 9)
Ex: Balanced a k-way Sort/Merge Input File: 50 110 95 10 100 36 153 40 120 60 70 130 22 140 80 Sorting Phase의완료후 File 1: (50 95 110) (60 70 130) File 2: (10 36 100) (22 80 140) File 3: (40 120 153) 첫번째병합의결과 File 4: (10 36 40 50 95 100 110 120 153) File 5: (22 60 70 80 130 140) File 6: 두번째병합의결과 File 1: (10 22 40 36 50 60 70 80 95 100 110 120 130 140 153) 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 10)
Ex: Polyphase Sort/Merge Sorting Phase의완료후 File 1: (50 95 110) (40 120 153) (22 80 140) File 2: (10 36 100) (60 70 130) 첫번째병합의결과 File 1: (22 80 140) File 2: 비었음 File 3: (10 36 50 95 100 110) (40 60 70 120 130 153) 두번째병합의결과 File 1: 비었음 File 2: (10 22 36 50 80 95 100 110 140) File 3: (40 60 70 120 130 153) 세번째병합의결과 File 1: (10 22 40 36 50 60 70 80 95 100 110 120 130 140 153) 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 11)
추가적인고려사항 초기 run의수가r인 Binary Sort/Merge Level 의수 = logl 2 R + 1 전체병합단계의수 = log 2 R 초기 run의수가r인 k-way Sort/Merge 전체병합단계의수 = log k R k개의 run에서가장작은 key 값을갖는 run 검색 Linear search: 전체비교수 = n * (k 1) * logg k R Selection tree: 전체비교수 = n * log 2 k * log k R = n * log 2 R Selection Tree? See Section 5.8 of HSF 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 12)
Selection ect Tree for k = 8 6 6 8 9 6 8 17 10 9 20 6 8 9 90 17 15 16 20 38 20 30 15 15 25 50 11 16 100 110 18 20 run 1 run 2 run 3 run 4 run 5 run 6 run 7 run 8 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 13)
3. 2 Phase Multiway Merge/Sort 2PMM의기본개념 2 Phase Sorting Phase + 1번의 Merging Phase 각 phase 마다데이터에대한 read/write 가 1 회수행 Multiway 사용할수있는파일의수는무제한 2PMM으로 sorting 할수있는파일의크기는 Memory 크기 M에의해결정 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 14)
2PMM Algorithm Phase 1 정렬단계 Fill main memory with records. Sort using favorite internal sort. (e.g. Quick Sort) Write sorted sub-list to a specific file. Repeat until all records are put into one of the sorted lists. Phase 2 병합단계 각 sorted-list에서한블록씩판독하여메모리에저장. 가장작은키값을갖는레코드를판단하여, 출력블록에저장. 출력블록이가득찰경우, 출력블록을디스크에기록. 입력블록에레코드가존재하지않을경우, 해당리스트에서다음블록판독하여메모리에저장. 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 15)
2PMM 의동작과정 Source File 21, 37, 40 17, 10, 1 7, 20, 11 31, 27, 30 14, 24, 28 12, 26, 20 9, 25, 16 29, 2, 4 25, 13, 53 23, 15, 45 33, 43, 22 13, 3, 5 Run 0 1, 7, 10 11, 17, 20 21, 27, 30 31, 37, 40 Run 1 2, 4, 9 12, 14, 16 20, 24, 25 26, 28, 29 Run 2 3, 5, 13 13, 15, 22 23, 25, 33 43, 45, 53 Memory 1, 7, 10 1, 7, 10 1, 7, 10 1, 7, 10 2, 4, 9 2, 4, 9 2, 4, 9 2, 4, 9 3, 5, 13 3, 5, 13 3, 5, 13 3, 5, 13 1, 2, 3 4, 5, 7 9 1, 7, 10 11, 17, 20 11, 17, 20 11, 17, 20 12, 14, 16 12, 14, 16 12, 14, 16 12, 14, 16 3, 5, 13 3, 5, 13 3, 5, 13 13, 15, 22 9, 10 9, 10, 11 12, 13 12, 13, 13 Maximum file size = M * ((M / B) - 1) Sorted File 1, 2, 3 4, 5, 7 9, 10, 11 12, 13, 13 정렬단계 병합단계 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 16)
Discussion of 2PMM Analysis Assume blocks are stored at random, so average access time is about 15 ms. File is stored on 250,000000 blocks, read and written once in each phase. 1,000,000 disk I/O s * 15 ms = 15,000 sec = 4+hours. 시간을줄이는방법? 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 17)
4. Optimization k-way Sort/Merge에서 Parallel I/O 기본개념 Buffer 수 : 2k + 2 (double buffering for I/O) 입력, 출력, 병합연산을병렬로처리 Fixed Buffer Allocation 입력파일마다 2개의버퍼를고정할당 입력대기현상발생가능 Dynamic Buffer Allocation Run 들의최대키값을비교 (Selection Tree 이용 ) Algorithm: HSF Section 7.11.3 참조 2PMM 에서 Parallel l I/O 지원방법? Clustering, Double Buffering Data Replication with Multiple Disks 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 18)
Run Generatione 기본개념 Memory 크기이상으로초기 run 의크기를설정 Merge pass의수감소 Algorithm Double buffering을위하여 2개의 I/O 버퍼이용 키값을차례로입력받아 selection tree 구성 Selection tree: 노드수 = (M 4 ) * rec_per_page Tree가 full인경우, 루트레코드출력 출력된레코드보다작은키값을갖는레코드가입력될경우, run number를증가 비교대상 : concatenate(run t number, key value) HSF Section 7.11.4 참조 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 19)
Example Memory 크기 = 3 Input File= (8, 6, 1, 3, 2, 7, 5, 4, 9) 1 st run = (1, 3, 6, 7, 8) 8, 6, 1, 3, 2, 7, 5, 4, 9 1 8, 6, 1, 3, 2, 7, 5, 4, 9 3 8, 6, 1,3,2, 7,5,4,9 6 8, 6, 1, 3, 2, 7, 5, 4, 9 7 8, 6, 1, 3, 2, 7, 5, 4, 9 8 8, 6, 1, 3, 2, 7, 5, 4, 9 done 2 nd run = (2, 4, 5, 9) 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 20)
Optimization - 계속 Optimal Merging of Runs Run generation 에의해생성된 run 의크기는상이 각 run의병합순서에따라실행속도차이발생 External path length 를이용하여비용계산 26 26 11 15 6 20 6 5 2 4 2 4 5 15 Path Length = 52 Path Length = 43 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 21)
최소비용트리 : Huffman Tree void huffman(tree_pointer heap[], int n) { /* heap is a list of n single node binary trees */ int i; tree_pointer tree; initialize(heap, n); /* initialize min heap */ for (i =1;i <n;i++) { tree = (tree_pointer) malloc(sizeof(tree_node)); } } tree->left >left_child = least(heap, n-i+1); tree->right_child = least(heap, n-i); tree->weight = tree->left_child->weight + tree->right_child->weight; insert(heap, n-i-1, tree); 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 22)
Construction o of a Huffman Tree Run: 2, 3, 5, 7, 9, 13 5 10 16 2 3 5 5 7 9 2 3 23 10 13 5 5 2 3 39 16 23 7 9 10 13 5 5 2 3 영남대학교데이터베이스연구실 Algorithm: Chapter 5 (Page 23)