F. Grandi et Mr. Scalas, BLOCK ACCESS ESTIMATION FOR CLUSTERED DATA USING A FINITE LRU BUFFER, IEEE transactions on software engineering, 19(7), 1993, pp. 641-660
Data access cost evaluation is fundamental in the design and managemen
t of database systems. When some data items have duplicates, a cluster
ing effect which can heavily influence access costs is observed. The a
vailability of a finite amount of buffer memory in real systems has an
even more dramatic impact. In this paper a comprehensive cost model f
or clustered data retrieval by an index using a finite buffer is prese
nted. Our approach combines and extends previous models based either o
n finite buffer or on uniform data clustering assumptions. The computa
tional cost of the formulas we propose in this work is independent of
the data size or of the query cardinality and need only a single stati
stics per search key, the clustering factor, to be maintained by the s
ystem. The predictive power and the accuracy of the model are shown in
comparison with actual costs resulting from simulations.