As a system administrator for the accounting firm AFS, you are usually asked to
ID: 3672315 • Letter: A
Question
As a system administrator for the accounting firm AFS, you are usually asked to import data from a regular source and upload the records to a heap file that needs to be sorted after the import. You want to write a script that will do that automatically, so you need to estimate the cost of the sort operation. Your DBMS uses external sort and makes efficient use of the available buffer space when it sorts a file. Information about the newly loaded file and the DBMS software available to operate on it are as follows:
The number of records in the file is 4500. The sort key for the file is 4 bytes long. You can assume that rids are 8 bytes long and page ids are 4 bytes long. Each record is a total of 48 bytes long. The page size is 512 bytes. Each page has 12 bytes of control information on it. Four buffer pages are available.
How many sorted subfiles will there be after the initial pass of the sort, and how long will each subfile be?
How many passes (including the initial pass just considered) are required to sort this file?
What is the total I/O cost for sorting this file?
Explanation / Answer
Assuming that the general external merge-sort algorithm is used, and that the available space for storing records in each page is 512 12 = 500 bytes, each page can store up to 10 records of 48 bytes each. So 450 pages are needed in order to store all 4500 records, assuming that a record is not allowed to span more than one page. Given that 4 buffer pages are available, there will be (450/4) = 113 sorted runs (sub-files) of 4 pages each, except the last run, which is only 2 pages long. The total number of passes will be equal to log113(base 3) + 1 = 6 passes. The total I/O cost for sorting this file is 2 450 6 = 5400 I/Os
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.