Buffer pages required for external sorting of a file in database

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₂⌈8500/3⌉⌉+1

                                                                   = ⌈log₂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_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 8500 pages in the file, N_b = 93 satisfies both inequalities, but N_b = 92 does not. So we need 93 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

Find the number of disk blocks in a given hard disk in dbms data storage

Find the number of disk blocks in a given hard disk in DBMS data storage

Question:

Following are the characteristics of a hard disk; Sector size of 512 bytes, 16 sectors per track, 16384 tracks per surface, 4 double sided platter, and 4096 bytes per block. Find the number of blocks in that disk.

Solution:

Let us find the total capacity of given disk in bytes.

A track has 16 sectors each of which is 512 bytes in size.

Capacity of a track      = Sector size * Number of sectors

= 512 * 16 = 8192 bytes.

There are 16384 tracks in a surface of a disk platter.

Capacity of one surface of disk platter = No. of tracks * Capacity of a track

                                      = 16384 * 8192 = 134217728 bytes

Capacity of one double sided platter = 134217728 * 2 (2 sides per disk)

                                                                   = 268435456 bytes

There are 4 double sided platters.

Capacity of the hard disk = Capacity of one disk platter * No. of disk platters

                                                = 268435456 * 4

                                                = 1073741824 bytes

It is given that the block size is 4096.

The number of blocks = (capacity of the hard disk) / (block size)

                                      = 1073741824/4096 = 262144 blocks

The hard disk with the given characteristics will have 262144 blocks.

*************

Go to Solved Exercises in DBMS page

find number of blocks in a hard disk drive

calculate the size of hard disk in bytes

find the capacity of a disk platter

 

find the disk capacity, rotational latency, and number of cylinders

Find the disk capacity, rotational latency, and number of cylinders, how to calculate the disk capacity, how to calculate the number of cylinders if number of tracks are known, how to compute the rotational latency

Question:

Consider a disk with a sector size of 512 bytes, 1000 tracks per surface, 25 sectors per track, 5 double-sided platters, and average seek time of 10 msec. Choose the correct answer for the following;

(i) capacity of tracks in bytes,

(ii) number of cylinders the disk has,

(iii) the average rotational latency if disk rotates at 5400 rpm.

(a) 12.5 K, 1000, 5.5 msec

(b) 25 K, 2000, 11 msec

(c) 12.5 K, 1000, 11 msec

(d) 25 K, 1000, 100 msec

Answer:

(a) 12.5 K, 1000, 5.5 msec

Given,

Sector size (minimum storage unit of a hard drive) – 512 bytes

Number of double sided disk platters - 5

(One can read/write on both sides in a Double sided platters unlike DVD for example)

Number of tracks per each side of each disk platter – 1000

Number of sectors per track – 25

Average seek time – 10 msec

The time needed for moving head of a disk drive from one track to another is the seek time. The average of many seeks is average seek time.

(i) Capacity of track can be calculated as follows;

Capacity of track = bytes/track = bytes/sector * sectors/track

                   = 512 bytes/sector * 25 sectors/track = 12800 bytes

                   = 12800/1024 KB = 12.5 KB

(ii) The number of cylinders is the same as the number of tracks on each platter.

Number of cylinders = Number of tracks = 1000

(iii) Maximum rotational delay can be calculated as follows;

Maximum rotational delay = (1/rpm) * 60

                                      = (1/5400) * 60 = 0.011 seconds or 11 msec

Average rotational latency is half of the rotation time, ie., 5.5 msec

Previous Question                                                                                Next Question

Go to Multiple Choice Questions / Solved Exercises page

Find the number of records and record size for storing data in one disk block

Find the number of records and record size for storing data in one disk block, How to calculate block size, How to calculate record size, calculate the number of records fit in one disk block in database management system

Question:

6. Suppose blocks of 1024 bytes are used to store variable-length records. The fixed part of the block header is 24 bytes, and includes a count of the number of records. In addition, the header contains a 4-byte pointer (offset) to each record in the block. The first record is placed at the end of the block, the second record starts where the first one ends, and so on. The size of each record is not stored explicitly, since the size can be computed from the pointers.

(i) How many records of size 50 bytes could we fully fit (no spanning) in such a block? (The block is designed to hold variable size records, but these records by coincidence happen to be all the same size.)

(ii) Suppose we want to store 20 records in the block, all of the same fixed size. What is the size of such records?

(iii) Now assume the block layout is changed to accommodate only fixed size records. In this case, the block header is still 24 bytes and contains the common length of the records in the block.

How many records of size 50 bytes could we fully fit in such a block?

(a) 20 records, 50 bytes, 20 records

(b) 18 records, 46 bytes, 20 records

(c) 20 records, 46 bytes, 25 records

(d) 50 records, 50 bytes, 20 records

Answer:

(b) 18 records, 46 bytes, 20 records

(i) Given,

Block size – 1024 bytes

Block header size – 24 bytes

Record size – 50 bytes

Pointer to each record – 4 bytes

Number of records = floor {Block size / records} ----- Eq. 1

But in the given case, we need to consider the block size after deducting the header size. And for each record we need to add 4 bytes pointer size because it is given that pointer for each record. Hence Eq 1 is now as follows;

Number of records = floor {(Block size – Header size) / (Record size + Pointer size)}

Number of records = floor { (1024 – 24) / (50 + 4)} = 18 records

(ii) For finding the size of record, we need to find the size left with us in each block. When we deduce the block header size and the size required for 20 pointers from block size, what we get is the size completely available for storing records.

(Block size – Header size – 4*20) will give us the available block space

Number of records = floor { (1024 – 24 – 4 * 20) / x}

20 = floor { (1024 – 24 – 4 * 20) / x}

x = floor { (1024 – 24 – 4 * 20) / 20} = floor{980/20} = 46 bytes

(iii) In this case, the record size becomes fixed. Hence, we do not need pointers to each record. The extra memory 4 bytes can be saved. The number of records can be calculated using Eq. 1 as follows;

Number of records = floor {(Block size – Header size) / Record size}

Number of records = floor { (1024 – 24) / 50} = 20 records

         Previous Question                                                                                Next Question

Go to Multiple Choice Questions / Solved Exercises page