Memory required for external sorting in DBMS

Memory required for external sorting in DBMS

Question:

Let us suppose that you have a file with 150000 pages and 45 available buffer pages. If you use external sorting to sort the above said file, answer the following questions;

a) How many runs will you produce in the first pass?

b) To sort the entire file, how many passes do you need?

c) How much is involved in terms of I/O cost to sort the file?

d) If you like to sort the file in just two passes, then what is the number of buffer pages you need?

Solution:

a) If Nf is the number of file pages and Nb is the number of available buffer pages then the first pass requires ⌈N_f/N_b⌉ [ceiling(N_f/N_b)] sorted runs.

For our case,

Number of file pages, N_f = 150000

Number of available buffer pages, N_b = 45

The number of sorted runs in the first pass = ⌈150000/45⌉ = 3334 runs

b) The number of passes required to sort the entire file can be calculated using the equation ⌈log_Nb-1⌈N_f/N_b⌉⌉+1.

Number of passes to sort complete file = ⌈log₂⌈150000/45⌉⌉+1

                                                                   = ⌈log₂3334⌉+1 = 13 passes

c) Since each page is read and written once per pass, the total number of page I/Os for sorting the file is 2 * N_f * (#passes):

Total I/O cost for sorting the file = 2 * 150000 * 13 = 39,00,000

d) In Pass 0, ⌈N_f/N_b⌉ runs are produced. In Pass 1, we must be able to merge this many runs; i.e., N_b − 1 ≥ ⌈N_f/N_b⌉. This implies that N_b must at least be large enough to satisfy N_b * (N_b − 1) ≥ N_f; this can be used to guess at N_b, and the guess must be validated by checking the first inequality. Thus;

With 150000 pages in the file, N_b = 388 satisfies both inequalities, but N_b = 387 does not. So we need 388 buffer pages to sort the entire file in just two passes.

[Note: to find the value of N_b, factorize the equation N_b * (N_b-1) = N_f which can be written as a quadratic equation N_b²-N_b-N_f = 0. The equation to be solved is N_b² - N_b - 8500 = 0]

*********

Go to Solved Exercises in DBMS page

Go to Multiple Choice Questions in Disk Storage and Access page

buffer pages required for external sorting

number of passes required to complete sorting of a file using external sorting

external sorting technique in database 

number of runs required for each pass in external sorting

I/O cost involved in sorting the entire file