Sorting We may build an index on the relation,and then use the index to read the relation in sorted order.May lead to one disk block access for each tuple. For relations that fit in memory,techniques like quicksort can be used. For relations that don't fit in memory,external sort-merge is a good choice. Database System Concepts-7th Edition 15.17 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 15.17 ©Silberschatz, Korth and Sudarshan th Edition Sorting ▪ We may build an index on the relation, and then use the index to read the relation in sorted order. May lead to one disk block access for each tuple. ▪ For relations that fit in memory, techniques like quicksort can be used. • For relations that don’t fit in memory, external sort-merge is a good choice
Example:External Sorting Using Sort-Merge a 19 a 19 g 24 d 31 b a 14 19 1 a 24 a 19 d 31 d 31 b 14 b 14 33 33 33 e 16 b 14 e 16 g 24 d 7 e 16 d 21 r 16 21 d 31 d 21 a 14 m 3 e 16 d 7 m 3 r 16 g 24 d 21 2 m 3 14 m 3 d 7 a 2 2 a 14 16 2 r 16 initial sorted relation runs runs output create merge merge runs pass-1 pass-2 Database System Concepts-7th Edition 15.18 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 15.18 ©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
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-7th Edition 15.19 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 15.19 ©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 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: Database System Concepts-7th Edition 15.20 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 15.20 ©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: