On using cache conscious clustering for improving OODBMS performance

The two main techniques of improving I/O performance of Object Oriented Database Management Systems (OODBMS) are clustering and buffer replacement. Clustering is the placement of objects accessed near to each other in time into the same page. Buffer replacement involves the selection of a page to be evicted, when the buffer is full. The page evicted ideally should be the page needed least in the future. These two techniques both influence the likelihood of a requested object being memory resident. We believe an effective way of reducing disk I/O is to take advantage of the synergy that exists between clustering and buffer replacement. Hence, we design a framework, whereby clustering algorithms incorporating buffer replacement cache behaviour can be conveniently employed for enhancing the I/O performance of OODBMS. We call this new type of clustering algorithm, Cache Conscious Clustering (C3). In this paper, we present the C3 framework, and a C3 algorithm that we have developed, namely C3-GP. We have tested C3-GP against three well known clustering algorithms. The results show that C3-GP out performs them by up to 40% when using popular buffer replacement algorithms such as LRU and CLOCK. C3-GP offers the same performance as the best existing clustering algorithm when the buffer size compared to the database size is very small.