1 Cache Management Policies for Semantic Caching

Commercial database systems make extensive use of caching to speed up query execution. Semantic caching is the idea of caching actual query results in the hope of being able to reuse them to speed up subsequent queries. This paper deals with cache management policies, which refer to policies for admission into the cache and eviction from the cache. When a query is executed, we must decide what part, if any, of the query result to add to the cache. If the cache is full, we must also decide which, if any, of the currently cached results to evict from the cache. The objective of these policies is to minimize the cost of executing the current and future queries or, phrased differently, maximize the benefit of the cache. The main difficulty is predicting the cost savings of future queries. In this study we present a family of cache admission and eviction policies, named RECYCLE, specifically designed for semantic caching within a relational database server. Our policies were designed to be both effective (high reuse ratio) and efficient (low overhead). The policies make use of a novel type of statistics, called access statistics. These statistics are easy to gather and maintain, yet, they offer a solid and flexible framework for dealing with the complexity of the problem. The decision whether to cache a query result takes into account the current content of the cache and the estimated benefit of the result during its lifetime. We experimentally compare the effectiveness of our policies with several other caching policies, and show the superiority of our solution. 1