Technical Report 94-16

TITLE:

An Analysis of Schedules for Performing Multi-Page Requests

DATE:

August 1994

AUTHORS:

Bernhard Seeger <seeger@informatik.uni-muenchen.de>

Institut für Informatik

Universität München

Leopoldstr. 11B

D-80802 München (Germany)

KEYWORDS:

I/O performance, multi-page requests, magnetic disk modelling, cost functions, query optimization, throughput

ABSTRACT:

In this paper, we address the problem of efficiently reading a set of pages from a file which is kept on some cylinders of a magnetic disk. It is assumed that several pages can be read from disk in a single multi-page request without interfering of other requests. First, a simple algorithm is presented for computing a schedule how the required pages are read from disk. Then, the expected cost of the schedules is analyzed by using a pure analytical model. In addition to the disk geometry, the analysis takes into account the three major cost components (seek time, rotational delay and transfer time) which occur when pages are retrieved from magnetic disk. % Moreover, only the transfer time is assumed to be constant for all pages. The derived cost function depends on two parameters: disk geometry, the analysis takes into account the three major cost components (seek time, rotational delay and transfer time) which occur when pages are retrieved from magnetic disk. The derived cost function depends on two parameters: the number of required pages and the degree of clustering of the underlying file. The cost function demonstrates that significant performance improvements can be achieved by using multi-page requests when the required pages are read according to a well-computed schedule. In addition to the response time of an individual query, we also examine the impact of multi-pages request on the throughput. Results of an experimental performance comparison demonstrate that the throughput can be improved considerably by several factors when multi-page requests are used in comparison to reading the required pages one at a time. performance comparison demonstrate that the throughput can be improved considerably by several factors when multi-page requests are used in comparison to reading the required pages one at a time.