Storage and access in relational data bases

Results indicate that physical clustering of logically adjacent items is a critical performance parameter for relational query evaluation and methods that depend on sorting the records themselves seem to be the algorithm of choice.

Abstract

Using the observations in this paper, a query translator could operate in the following manner. From the available access paths, determine the applicable methods and cases, eliminate any obviously bad methods, discard any methods that fail to pass certain simple tests (such as, for example, F 1 1 ) , and then evaluate the cost estimates for the remaining methods. Choose the method with minimum cost. A query evaluator based on these principles of simple analytic calculations and numeric cost computations could be part of relational data base query systems or other system that uses indexes. A complete model to analyze the cost of various methods that apply to any given situation has been implemented in APL. The time to analyze a particular situation is of the order of a few milliseconds.