External Sort-Merge (Cont.) 2.Merge the runs(N-way merge).We assume(for now)that N< M. 1.Use Nblocks of memory to buffer input runs,and 1 block to buffer output.Read the first block of each run into its buffer page 2.repeat 1.Select the first record(in sort order)among all buffer pages 2.Write the record to the output buffer.If the output buffer is full write it to disk. 3. Delete the record from its input buffer page. If the buffer page becomes empty then read the next block(if any)of the run into the buffer. 3. until all input buffer pages are empty: Database System Concepts-5th Edition,Aug 27,2005. 13.17 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 13.17 ©Silberschatz, Korth and Sudarshan th Edition, Aug 27, 2005. External Sort-Merge (Cont.) 2. Merge the runs (N-way merge). We assume (for now) that N < M. 1. Use N blocks of memory to buffer input runs, and 1 block to buffer output. Read the first block of each run into its buffer page 2. repeat 1. Select the first record (in sort order) among all buffer pages 2. Write the record to the output buffer. If the output buffer is full write it to disk. 3. Delete the record from its input buffer page. If the buffer page becomes empty then read the next block (if any) of the run into the buffer. 3. until all input buffer pages are empty:
External Sort-Merge (Cont.) If N>M,several merge passes are required. In each pass,contiguous groups of M-1 runs are merged. A pass reduces the number of runs by a factor of M-1,and creates runs longer by the same factor. E.g.If M=11,and there are 90 runs,one pass reduces the number of runs to 9,each 10 times the size of the initial runs Repeated passes are performed till all runs have been merged into one. Database System Concepts-5th Edition,Aug 27,2005. 13.18 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 13.18 ©Silberschatz, Korth and Sudarshan th Edition, Aug 27, 2005. External Sort-Merge (Cont.) If N M, several merge passes are required. In each pass, contiguous groups of M - 1 runs are merged. A pass reduces the number of runs by a factor of M -1, and creates runs longer by the same factor. E.g. If M=11, and there are 90 runs, one pass reduces the number of runs to 9, each 10 times the size of the initial runs Repeated passes are performed till all runs have been merged into one
Example:External Sorting Using Sort-Merge a 19 a 19 g 24 d 31 b 14 a 14 a 19 24 a c 33 19 d 31 14 d 31 b 14 b 33 33 e 16 c b 14 d g 24 7 e 16 e 16 d 2 r 16 d 21 d 14 d a 21 3 e 16 m 3 7 16 g 24 d 21 p 2 m 3 d 7 m 3 a 14 2 14 d 7 2 r 16 16 p 2 initial sorted relation runs runs output create merge merge runs pass-1 pass-2 Database System Concepts-5th Edition,Aug 27,2005. 13.19 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 13.19 ©Silberschatz, Korth and Sudarshan th Edition, Aug 27, 2005. Example: External Sorting Using Sort-Merge