On estimating cost of accessing records in blocked database organizations

The estimation of the cost of processing a query using a particular access path under a given physical organization has important applications in integrated database environments. When records in a file are stored in fixed-length physical blocks in secondary storage, and mechanisms are available whereby a query can be resolved without the accessing of all of the records, an important measure of the cost of using a particular access path is the number of blocks that have to be accessed in referencing the records of interest. In this paper, a general formula is derived for the expected number of blocks on which a random sample of r records from a file containing n records (which may be of arbitrary lengths, and which may extend across block boundaries) will reside. The specialization of this formula to the case of fixed-length records is discussed. An approximation to this formula which is highly accurate for a wide range of parameters and which can be computed very efficiently is also provided