Showing posts with label Disk Storage Access Exercises. Show all posts
Showing posts with label Disk Storage Access Exercises. Show all posts

Wednesday, 28 March 2018

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 Nf/Nb [ceiling(Nf/Nb)] sorted runs.
For our case,
Number of file pages, Nf = 150000
Number of available buffer pages, Nb = 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 ⌈logNb-1Nf/Nb⌉⌉+1.
Number of passes to sort complete file = ⌈log2⌈150000/45⌉⌉+1
                                                                   = ⌈log23334⌉+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 * Nf * (#passes):
Total I/O cost for sorting the file = 2 * 150000 * 13 = 39,00,000

d) In Pass 0, Nf/Nbruns are produced. In Pass 1, we must be able to merge this many runs; i.e., Nb − 1 ≥ Nf/Nb. This implies that Nb must at least be large enough to satisfy Nb * (Nb − 1) ≥ Nf; this can be used to guess at Nb, and the guess must be validated by checking the first inequality. Thus;
With 150000 pages in the file, Nb = 388 satisfies both inequalities, but Nb = 387 does not. So we need 388 buffer pages to sort the entire file in just two passes.
[Note: to find the value of Nb, factorize the equation Nb * (Nb-1) = Nf which can be written as a quadratic equation Nb2-Nb-Nf = 0. The equation to be solved is Nb2 - Nb - 8500 = 0]

*********




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
 




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 Nf/Nb [ceiling(Nf/Nb)] sorted runs.
For our case,
Number of file pages, Nf = 8500
Number of available buffer pages, Nb = 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 ⌈logNb-1Nf/Nb⌉⌉+1.
Number of passes to sort complete file = ⌈log2⌈8500/3⌉⌉+1
                                                                   = ⌈log22834⌉+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 * Nf * (#passes):
Total I/O cost for sorting the file = 2 * 8500 * 9 = 1,53,000

d) In Pass 0, Nf/Nbruns are produced. In Pass 1, we must be able to merge this many runs; i.e., Nb − 1 ≥ Nf/Nb. This implies that Nb must at least be large enough to satisfy Nb * (Nb − 1) ≥ Nf; this can be used to guess at Nb, and the guess must be validated by checking the first inequality. Thus;
with 8500 pages in the file, Nb = 93 satisfies both inequalities, but Nb = 92 does not. So we need 93 buffer pages to sort the entire file in just two passes.

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

*********

 


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








Friday, 23 March 2018

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.

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



find number of blocks in a hard disk drive
calculate the size of hard disk in bytes
find the capacity of a disk platter
 



Saturday, 10 February 2018

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









Important properties of two phase locking protocol and its variants

Important properties of two phase locking protocol and its variants Properties of     2PL Serializability  2PL ensures co...