The Role of Data Clustering in High Performance, Scalable Database Systems

 

Background

In the first article in this series we looked at the need to reduce the number of I/Os required to perform database operations and the role of smart caching, including cross-transaction caching. Reducing I/Os improves response times and increases system throughout. In this article we’ll look at the role of data clustering, which aims to reduce I/Os by physically grouping together data that is frequently accessed together.

 

Fine Grain Clustering

Caching can dramatically reduce the number of I/Os needed to support some operations. The next line of attack is clustering objects that are generally used together, such as Word objects with the Sentence object that they are a logical part of. You can only cluster things once, unless some of the objects are replicated, but in the example that we used of a document object the number of I/Os will be not much more than the size of the document divided by the I/O size. In ThingSpan the default page size is 16 KB, so reading a 40KB document would require 3 I/Os. If the same document were stored in a classically normalized relational database there would be 1 I/O for the Document table, 1 for each Chapter, 1 for each Paragraph and ( #Sentences / IO_Size) for the sentences etc. It would clearly be more than 3.

 

Objectivity’s ThingSpan allows the application or database designer to cluster objects in two ways, explicitly or using placement directives. The two mechanisms should generally not be mixed, because the placement directives can narrow the scope of a predicate search. With explicit clustering each new object can be placed as close as possible, generally in the same page, to another specified object, e.g. all of the Word objects with their associated Sentence object. With placement directives the application engineer specifies a policy for placing objects, either at the database or container level, or near a related object.

 

There are standard policies for strategies such as sequential placement, clustering, consecutive round robin across servers, random round robin within a group of servers and so on. The round robin strategy helps balance the load across disk drives when an application is handling high velocity ingest streams.

 

Example 1 - Storing a Document

Consider how a document might be stored in a relational or an object database. The relational database would probably have separate tables for Document, Chapter, Section, Paragraph and Sentence entries. In the purest case it should also have Word and Character tables, but we will only cover mapping down to the Word level because of the number of join operations and storage overheads involved.

 

Images or videos would be stored in BLOBs, which can’t be automatically indexed or searched with SQL. We’ll ignore those here as they will be equally I/O intensive in most databases.

Figure 1 - Mapping a Document to a Relational Database

 

Retrieving and displaying a document stored this way in a relational database would involve a complex SQL query that would access many B-Tree indices and join tables in order to finally assemble the viewable document. Have you ever wondered why Microsoft Word doesn’t use SQL Server? The storage overheads would make it too cumbersome and slow.

 

The object database would store a single Document object, a Chapter object for each one, a Paragraph object per paragraph, plus Sentence and Word objects. The overheads for storing a single character make that impracticable. There would also be Image and Video objects, which could be searchable by content. The objects are connected together with 1:many or many:many relationships, like this:

Figure 2 - Mapping a Document to ThingSpan

 

Retrieving the document is now a matter of looking up the Document object, probably by its title or ISBN. That command then issues open() commands for each Chapter and so on down the hierarchy as directed by the viewer application. It is much faster and simpler to code than the SQL queries used above.

 

Furthermore, the overheads for the relational database indices and join tables typically triple the amount of disk storage needed for a given dataset, i.e. the expansion factor is around 3x. The overhead on each object in ThingSpan is 14 bytes and each bidirectional link can be stored in 8 or 16 bytes, so the data expansion factor is typically about 1.2x.

 

In other words, Thingspany requires 60% less storage and takes about 60% fewer I/Os to access the document. If the total number of Document, Chapter, Paragraph, Sentence and Word objects is X, the unit of I/O is 16KB and the total document size is 160 KB, the numbers of lookup and read operations are summarized in the table below:

 

RANK TECHNOLOGY KEY LOOKUPS INDEX LOOKUPS LOGICAL READS PHYSICAL READS
1 ThingSpan 1 0 X 10 or 11
2 Relational Database 0 X 3 * X Approx X/2 to
3 * X

 

Example 2 - Handling Class Inheritance

Inheritance is difficult to implement efficiently in a relational database. There are three simple ways to manage it:

  1. A table per class with columns for the unique attributes, plus join tables.
  2. A table per class with replicated columns.
  3. A single table with columns for every attribute type in the class hierarchy and a class name column.

 

Consider this class hierarchy and how it would be mapped in each of the above ways:

Figure 3 - Class Hierarchy (Primate inherits from Animal etc.)

 

Example 2.1 - One Table Per Class

Figure 4 - One Table Per Class

 

The main problem with the above mapping is that the query to assemble a document is clumsy and the number of index, join and read operations is prohibitive. The query has to have knowledge of the class hierarchy that isn’t in the relational schema (dictionary).

 

Example 2.2 - Replicated Columns For Each Class

Figure 5 - Replicated Columns for Each Class

 

This solution makes queries easier to write - “Select * From Mammal_Table” only has to access one B-Tree index, no join tables and the requisite number of rows in one table. However, this mapping requires much more storage space and SQL doesn’t support updating replicated columns across multiple tables very well.

 

Example 2.3 - One Large Table with All Class Attributes and Sparse Fields



Figure 6 - One Large Table with Class Attributes and Sparse Fields

 

This uses less space overall than the other two mappings, but traditional relational databases aren’t usually very efficient at handling sparse columns, so a column store would be a better solution. It also needs an additional column to identify the class.

 

Inheritance in ThingSpan

In Objectivity’s ThingSpan each object has the exact attributes defined in the class hierarchy and a Type Number that is unique within a schema. The attributes are tightly clustered.

 

In the above example the object Types (class numbers) might be 100, 101, 102 and 103 for the Animal, Primate, Mammal and Human object classes, respectively. When the Query Manager instructs the Storage Manager to search for Animal objects it tells it to search for objects with Type = 100. If the Query Manager is looking for Human objects, the Storage Manager is told to search for Type = {100 or 101 or 102 or 103}.

Figure 7 - Inheritance in ThingSpan

 

Summary

In this article we looked at ways in which ThingSpan’s data clustering can improve performance and reduce storage requirements by 60% or more without resorting to compression. In the next article we’ll look at data distribution and how it works in ThingSpan.

SHARE THIS POST
Share on FacebookTweet about this on TwitterShare on Google+Share on LinkedIn