2011-09-07Clustering Data: The Second Power of Indexing

The term “cluster” is used in various fields. A star cluster, for example, is a group of stars. A computer cluster, on the other hand, is a group of computers that work closely together—either to solve a complex problem (high-performance computing cluster) or to increase availability (failover cluster). Generally speaking, clusters are related things that appear together.

But there is one more type of cluster that applies to computing—one that is often misunderstood: data clusters. Clustering data means to store consecutively accessed data closely together, so that accessing them needs less IO operations. Data clusters are a very important database tuning concept. Computer clusters, on the other hand, are also very common in database context—thus, making the term “cluster” very unclear. The sentence “Let’s use a cluster to improve database performance” is just one example that might refer to a computer cluster, but could also mean a data cluster. In this chapter, clusters are generally referring to data clusters.

The simplest data cluster in SQL databases is the row. Databases store all columns of a row in the same database block, if possible. Exceptions occur if a row doesn’t fit into a single block, especially if LOB types are involved.

Indexes allow to cluster data. The concept was already introduced in Chapter 1, “Anatomy of an Index”. The index leaf nodes hold the indexed column in an ordered fashion: similar values are stored next to each other. That means, that indexes build clusters of rows with similar values. This ability—to cluster data—is so important that I refer to it as the second power of indexing.

The following sections explain how to use clustering to improve query performance.