一种基于访问图优化的缓存替换算法

A BUFFER REPLACEMENT ALGORITHM BASED ON CALL GRAPH OPTIMISATION

针对目前数据库缓存替换算法替换策略单一,无法预测即将执行SQL语句的不足,提出了一种基于访问图优先的缓存替换算法CG-ABR(CallGraph Optimizing Adaptive Buffer Replacement)。该算法通过查询优化器获得当前数据访问类型,自动调整缓存替换算法以适应实时变化的访问类型,改进了缓存访问的管理方法,并根据SQL语句的应用逻辑执行顺序来构造访问图CallGraph,基于CallGraph以预测将要执行的SQL语句,替换出未来不会被访问的页面缓存,以达到缓存空间优化的目的。实验结果与分析表明,CG-ABR算法是有效的,对实时变化的访问类型有较好的缓存命中率,具有良好的应用价值。

Aiming at existing problems of single buffer replacement policy and the inability in predicting future SQL sentences execution of which the current database buffer replacement algorithm has, this paper proposed a new database buffer replacement algorithm CG-ABR （Call graph optimising adaptive buffer replacement）. CG-ABR automatically adjusts butter replacement algorithm in order to adapt to data access types with timely variation by obtaining current type through query optimiser, this has optimised the management method of buffer access infor- mation. For achieving the goal of optimising the buffer space, this algorithm constructs Call Graph according to the applied logic execution or- der of SQL sentences,predicts future SQL sentences to be executed based on the Call Graph, and replaces the pages which might not be ac- cessed afterwards. Experiment results and analyses show that the CG-ABR algorithm is effective in buffer replacement with high hit ratio on timely varying access types and has good applicable value.