Sequentiality and prefetching in database systems

摘要: Sequentiality of access is an inherent characteristic many database systems. We use this observation to develop algorithm which selectively prefetches data blocks ahead the point reference. The number prefetched chosen by using empirical run length distribution and conditioning on observed sequential block references immediately preceding reference current block. optimal prefetch estimated as a function “costs,” including cost accessing not resident in buffer (a miss), fetching additional at fault times, that are never referenced. estimate latter cost, described memory pollution, two ways. consider treatment (in replacement algorithm) blocks, whether they treated referenced or not, find it makes very little difference. Trace taken from operational IMS system analyzed results presented. show how determine sizes. anticipatory can lead significant improvements operation.