## Buffer pages required for external sorting of a file in database

__Question:__
Let us suppose that you have a file
with 8500 pages and 3 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}= 8500
Number of available buffer pages, N

_{b}= 3
The number of sorted runs in the first
pass =

**⌈8500****/3****⌉ = 2834 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**_{2}⌈8500**/3****⌉⌉+1****= ⌈log**

_{2}2834⌉+1 = 9 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 * 8500 * 9 = 1,53,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**must at least be large enough to satisfy_{b}**N*** (_{b}**N**− 1) ≥_{b}**N**; this can be used to guess at_{f}**N**, and the guess must be validated by checking the first inequality. Thus;_{b}
with 8500 pages in the file,

**N**satisfies both inequalities, but_{b}= 93**N**does not. So we need 93 buffer pages to sort the entire file in just two passes._{b}= 92
[

*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}^{2}-N_{b}-N_{f}= 0. The equation to be solved is N_{b}^{2 }- N_{b }- 8500 = 0
*********

Go to Solved Exercises in DBMS 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

## No comments:

## Post a Comment