Opportunistic prioritised clustering framework for improving OODBMS performance

Abstract

In object oriented database management systems, clustering has proven to be one of the most effective performance enhancement techniques. Existing clustering algorithms are mainly static, that is re-clustering the object base when the database is off-line. However, this type of re-clustering cannot be used when 24-h database access is required. In such situations dynamic clustering is necessary, since it can re-cluster the object base while the database is in operation. We find that most existing dynamic clustering algorithms do not address the following important points: the use of opportunism to impose the smallest I/O footprint for re-organisation; the re-use of prior research on static clustering algorithms; and the prioritisation of re-clustering so that the worst clustered pages are re-clustered first. Our main achievement in this paper is to create the Opportunistic Prioritised Clustering Framework (OPCF). The framework allows any static clustering algorithm to be made dynamic. Most importantly it allows the created algorithm to have the properties of I/O opportunism and clustering prioritisation which are missing in most existing dynamic clustering algorithms. We have used OPCF to make the static clustering algorithms "Graph Partitioning" and "Probability Ranking Principle" into dynamic algorithms. In our simulation study we found these algorithms outperformed two existing highly competitive dynamic algorithms in a variety of situations.