I. Shin and K. Koh (Korea)
cache, replacement, database, re cency, frequency, block group.
In order to exploit various reference patterns of applica tions, several local replacement policies have appeared in operating systems, which operate a replacement policy on the application level. Also for databases, researchers have proposed several policies that manage cache on the query level. However, as some researches show, these policies have a problem in a multi-user situation where query optimizer plans can overlap in complicated ways, making it difficult to manage such an overlap. Then, which policy should be used for databases? This paper proposes the use of RCB, an alternative pol icy. RCB classifies all the blocks into several groups that have different reference characteristics and operates the proper replacement policies on the block group level. RCB overcomes several LRU drawbacks by operating the adequate replacement policy per block group and thereby delivering a superior performance compared to the exist ing replacement policies. In trace-driven simulations with realistic database workloads, RCB surpasses the conven tional replacement policies (LRU, 2Q, LRU-K, LRFU) for all the cache sizes. Additionally, time complexity of RCB is O (1), which means RCB performs block re placement very quickly in on-line. This study shows that RCB is an effective and efficient cache replacement pol icy superseding the conventional global replacement po lices.∗
Important Links:
Go Back
