Technical Report 94-19

TITLE:

Tuning Access Methods to Supporting Data Intensive Queries

DATE:

November 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:

databases, complexity of access

ABSTRACT:

In this paper, we consider how to improve dynamic access methods which are designed to perform data-intensive selection queries in a dynamic setting. A large number of dynamic access methods have been proposed for supporting such queries. Almost all of them are designed with the primarily goal to reduce the number of page accesses, whereas our main attention is paid to decreasing the cost of individual page requests. There is a great potential for such improvements since the average (page) access time on a magnetic disk drive is typically by a factor of 10 higher than the transfer time.

In our approach, two techniques are jointly used: clustering and multi-page requests. The technique of clustering takes care of storing pages on one cylinder which are frequently required by the same query in common. In contrast to issuing a request for each qualifying page of a query, one multi-page request is used for retrieving all qualifying pages from a cylinder. Due to these techniques, the access time of a qualifying page can be substantially reduced compared to the average (disk) access time. For the sake of concreteness, our discussion is based on the problem of supporting range queries on B+-trees. In an experimental performance study, we show that the response time of a range query can be reduced by several factors if the B+-tree exploits both techniques (clustering and multi-page requests).