Suppose you need to sort a relation of 40 gigabytes, with 4 kilobyte blocks, usi

Question

Suppose you need to sort a relation of 40 gigabytes, with 4 kilobyte blocks, using a memory size of 40 megabytes. Suppose the cost of a seek is 5 milliseconds, while the disk transfer rate is 40 megabytes per second.

a. Find the cost of sorting the relation, in seconds, with bb = 1 and with bb = 100.

b. In each case, how many merge passes are required?

c. Suppose a flash storage device is used instead of a disk, and it has a seek time of 1 microsecond, and a transfer rate of 40 megabytes per second. Recompute the cost of sorting the relation, in seconds, with bb = 1 and with bb = 100, in this setting.

Explanation / Answer

b)

br = 40GB / 4KB = 10,000,000 blocks
M = 40MB / 4KB = 10,000 blocks
The initial number of runs = (br / M) = 1,000

The number of merge passes required = logM-1(br / M) = log99991000 = 1
Block transfers = br(2*1 + 1) = 30,000,000 blocks
Seeks = 2[br / M] + [br / bb] (2*1 – 1)
if bb = 1, 2000 + 10,000,000 = 10,002,000 seeks
bb = 100, 2000 + 100,000 = 102,000 seeks

c)
Total sorting cost in seconds = (# of block transfers) * 4KB / 40MB + (# of seeks) * 5/1000

a)

if bb = 1,

=>30,000,000 * 4KB / 40MB + 10,002,000 * 5/1000 = 3000 + 50010 = 53010 sec.
bb = 100,

=>30,000,000 * 4KB / 40MB + 102,000 * 5/1000 = 3000 + 510 = 3510 sec.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.