Temporal Join Processing with the Adaptive Replacement Cache - Temporal Data Policy

Management of data with a time dimension increases the overhead of storage and query processing in large database applications especially with the join operation, which is a commonly used and expensive relational operator. The join evaluation can be time consuming because temporal data are intrinsically multidimensional. The problem can be even harder since tuples with longer life spans tend to overlap a greater number of joining tuples thus; they are likely to be accessed more often. The proposed Adaptive Replacement CacheTemporal Oata (ARC-TO) buffer replacement policy is built upon the Adaptive Replacement Cache (ARC) policy by favoring the cache retention of data pages in proportion to the average life span of the tuples in the buffer. By giving preference to tuples having long life spans, a higher cache hit ratio can be achieved. The caching priority is also balanced between recently and frequently accessed data.

An evaluation and comparison study of the proposed ARC-TO algorithm determined the relative performance with respect to a nested-loop join, a sort-merge, and a partition-based join algorithm. The metrics include the processing time (disk 110 time plus CPU time), cache hit ratio, and index storage size. The study was conducted with comparisons in terms of the Least Recently Used (LRU), Least Frequently Used (LFU), ARC, and the new ARC-TO buffer replacement policy.