External Sort-Merge Let M denote memory size (in pages). 1.Create sorted runs.Let i be 0 initially. Repeatedly do the following till the end of the relation: (a)Read M blocks of relation into memory (b)Sort the in-memory blocks (c)Write sorted data to run Ri;increment i. Let the final value of i be N 2.Merge the runs (next slide)..... Database System Concepts-6th Edition 12.17 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 12.17 ©Silberschatz, Korth and Sudarshan th Edition External Sort-Merge 1. Create sorted runs. Let i be 0 initially. Repeatedly do the following till the end of the relation: (a) Read M blocks of relation into memory (b) Sort the in-memory blocks (c) Write sorted data to run Ri ; increment i. Let the final value of i be N 2. Merge the runs (next slide)….. Let M denote memory size (in pages)
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-6th Edition 12.18 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 12.18 ©Silberschatz, Korth and Sudarshan th Edition 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-6th Edition 12.19 @Silberschatz,Korth and Sudarshan
Database System Concepts - 6 12.19 ©Silberschatz, Korth and Sudarshan th Edition 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 吕 24 d 31 a 14 b 14 a 19 24 33 a 19 d 31 b d 31 14 b 14 33 33 33 e 16 b 14 e 16 24 d 7 e 16 d 21 16 d 21 d 31 a 14 d 21 m 3 e 16 d 7 m 3 r 16 24 d 21 p 2 m 3 m 3 d 7 a 14 p 2 p 2 a 14 d > 16 2 16 initial sorted relation runs runs output create merge merge runs pass-1 pass-2 Database System Concepts-6th Edition 12.20 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 12.20 ©Silberschatz, Korth and Sudarshan th Edition Example: External Sorting Using Sort-Merge g a d 31 c 33 b 14 e 16 r 16 d 21 m 3 p 2 d 7 a 14 a 14 a 19 b 14 c 33 d 7 d 21 d 31 e 16 g 24 m 3 p 2 r 16 a 19 b 14 c 33 d 31 e 16 g 24 a 14 d 7 d 21 m 3 p 2 r 16 a 19 d 31 g 24 b 14 c 33 e 16 d 21 m 3 r 16 a 14 d 7 p 2 initial relation create runs merge pass–1 merge pass–2 runs runs sorted output 24 19