Page 209 - DCAP402_DCAO204_DATABASE MANAGEMENT SYSTEM_MANAGING DATABASE

Database Management Systems/Managing Database

Notes 2. Build an index on the relation, and then use the index to read the relation in sorted order.
(Options 1&2 may lead to one block access per tuple).
3. For relations that fit in the memory, techniques like quicksort can be used.

4. For relations that do not fit in the memory, external sort-merge is a good choice.
Let us go through the algorithm for External Sort-Merge.

12.3.1 Create Sorted Partitions

Let i be 0 initially.
Repeat steps (1) to (4) until the end of the relation:
1. Read M blocks of relation into the memory. (Assumption M is the number of available
buffers for the algorithm).
2. Sort these buffered blocks using internal sorting.
3. Write sorted data to a temporary file – temp (i)

4. i = i + 1;
Let the final value of i be denoted by N;

Notes Each temporary file is a sorted partition.

12.3.2 Merging Partitions (N-way Merge)

// We assume (for now) that N < M.

// Use N blocks of memory to buffer temporary files and 1 block to buffer output.
Read the first block of each temporary file (partition) into its input buffer block;
Repeat steps (1) to (5) until all input buffer blocks are empty;
1. Select the first record (in sort order) among all input buffer blocks;
2. Write the record to the output buffer block;

3. If the output buffer block is full then write it to disk and empty it for the next set of data.
This step may be performed automatically by the Operating System;
4. Delete the record from its input buffer block;

5. If the buffer block becomes empty then read the next block (if any) of the temporary file
into the buffer.
If N M, several merge passes are required, in each pass, contiguous groups of M × 1 partitions
are merged and a pass reduces the number of temporary files temp (i) by a factor of M –1. For
example, if M=11 and there are 90 temporary files, one pass reduces the number of temporary
files to 9, each temporary file begin 10 times the size of the earlier partitions.
Repeated passes are performed till all partitions have been merged into one.

Figure 12.2 shows an example for external sorting using sort-merge.

202 LOVELY PROFESSIONAL UNIVERSITY