Column-oriented database: Introduction (Part 1)

What is a column-oriented database and where can I use it? Before we answer those questions we have a look at traditional databases and the row-oriented approach.

row-oriented approach

If we instantiate an object or save a tuple we use a row-oriented approach.

row-oriented approach

We will use an example of persons in the following post. Each person has the attributes name, sex and age. Our data set looks like this:

name          sex       age
==============================
Alex male 26
Bettina female 22
Clara female 23
Dieter male 28
Emil male 29
Frederike female 27

How is this data represented in memory? Each character is 1 byte (simplified!)

address 00 |  A l e x \0 m a l e \0 26
address 11 | B e t i n a \0 f e m a l e \0 22
address 26 | C l a r a \0 f e m a l e \0 23
address 40 | D i e t e r \0 m a l e \0 28
address 53 | E m i l \0 m a l e \0 29
address 64 | F r e d e r i k e \0 f e m a l e \0 27

\0 is the Null character and terminates a string.

Let’s focus on two aspects. Predictability and Locality.

Predictability

Can we predict the address for each tuple? Can we predict the address within a tuple for each attribute? In our example we can’t predict the address where we will find Dieter without looking at all the data. Tuples with a variable length prevent such predictions.

Locality

Are the attributes of two tuples next to each other? Computing the average age of our persons we need to look at address 10, 25, 39, 52 and 63. That’s a problem because we reduce the probability to read the data from memory cache or the same block on disk. We further complicate any forecasts of the CPU what memory area we need next.

On-Disk representation

File data.txt
Alex;male;26
Betina;female;22
Clara;female;23
Dieter;male;28
Emil;male;29
Frederike;female;27

To calculate the average age we need to read the complete file data.txt. Although we are only interested in the age attribute.

column-oriented approach

A different approach is column-oriented. You can compare the approach with an array holding the data for each attribute (column).

column-oriented approach

How is our data represented in memory now?

address 00 |  A l e x \0 B e t i n a \0 C l a r a \0 D i e t e r \0 E m i l \0 F r e d e r i k e \0
address 40 | m a l e \0 f e m a l e \0 f e m a l e \0 m a l e \0 m a l e \0 f e m a l e \0
address 77 | 26 22 23 28 29 27

Predictability

We still can’t guess the address where we find Dieter. But if we have found Dieter (Dieter is at array index 3) we can easily calculate where we can find his age by adding 77 + 3= 80 => 28. If we deal with fixed length types (integer, float, boolean) we can predict exactly where we find our data.

Locality

To calculate the average age we only need to look at the memory block 77–82. The probability to hit the cache (or block) is very high during iteration.

On-Disk representation

The data set can be persisted to disk like this:

File name.txt
Alex
Betina
Clara
Dieter
Emil
Frederike
File sex.txt
male
female
female
male
male
female
File age.txt
26
22
23
28
29
27

To calculate the average age we only need to read file age.txt. We only read data that we need to calculate our result!

Summary

A column-oriented approach increases performance. We need to read less. The probability of cache hits are higher. If we are dealing with fixed length types we can easily combine multiple attributes.

Part 2

In part 2 we will create a draft for a column-oriented time series database (TSDB).

Show your support

Clapping shows how much you appreciated Michael Wittig’s story.