Why are column oriented databases so much faster than row oriented databases?

I have been playing around with Hybrid Word Aligned Bitmaps for a few weeks now, and they turn out to be a rather remarkable data structure.  I believe that they are utilized extensively in modern column oriented databases such as Vertica and MonetDB.

Essentially HWABs are a data structure that allows you to represent a sparse bitmap (series of 0's and 1's) really efficiently in memory.  The key trick here is the use of run length encoding to compress the bitmap into fewer bits while still allowing for lightening fast operations.  

They key operation from my perspective is the "AND" operation.  "Why is that useful?" I hear you ask.  Well, imagine we have the following query:

SELECT Animal, Colour, COUNT(*) 
FROM AnimalDetails 
WHERE City='Melbourne'
GROUP BY Animal, Colour

On a table that looks like:

Animal, Colour, City
Dog, White, Melbourne
Cat, Black, Sydney
Cat, White, Melbourne
Dog, Black, Melbourne

In order for me to process the query, I need first to calculate the WHERE condition, which is to say find all the rows that satisfy the condition "City='Melbourne'".  

Then, given those rows (a list of row ids) I need to group the results to Animal and then by Colour.

Imagine for a moment that our data for "Animal", "Colour" and "City" are all stored as simple arrays, with the array index 0 for all arrays creating row 0, so Animal[0] = Dog, Colour[0] = White, City[0] = Melbourne, forming the first row.

That would work well, but its a bit clunky since I have to visit every row in the table to satisfy the query.  What I really want to do is to index the data, so I change the structure of the data, such that each Array is now a map using the distinct values as keys and a list of the row_ids that the value is found in.  Then my "Animal" column can be represented as:

Animal["Dog"] = {1, 4}
Animal["Cat"] = {2, 3}

Indicating that for the column "Animal" the value "Dog" can be found at rows 1, 4.  This is repeated for all the other columns.

This means that satisfying my WHERE condition means I only need to seek to the "Melbourne" value in my City structure, and read off the list of row_ids {1, 3, 4}.  Awesome!

It then also means that for my group by conditions I can do the same thing, but a little differently.  Since I have a list of all the distinct values, I can just walk through the list of distinct values and collect the list of row ids, then Intersect it with the result of the WHERE condition.

So to find the Distinct values of "Animal" that satisfy the condition I end up with:

Seek for "Dog" in Animals, return {1, 4} then INTERSECT {1, 3, 4} = {1, 4}
Seek for "Cat" in Animals, return {2, 3} INSERSECT {1, 3, 4} = {3}

I can then take those results and intersect them with the results of "Colour":

Dogs
"White" {1, 2} INSERSECT {1, 4} = {1} (White Dog)
"Black" {3, 4} INSERSECT {1, 4} = {4} (Black Dog)

Cats
"White" {1, 3} INTERSECT {3} = {3} (White Cat)
"Black" {2, 4} INSERSECT {3} = {} (No Black Cats)

The problem here is all these INTERSECT operations are really expensive, especially when the conditions end up producing a lot of rows.  

On my test data set (a million rows), a similar query to this took about 4000ms, with the vast majority of time being taken up in calculating the intersections.

Now, if you structure the data a little bit differently you can represent the values as bitmaps.

Animal["Dog"] = 1001
Animal["Cat"] = 0110

Here, "Dog" can be found at row id 1 and 4.  Therefore we set the value of the bit at rows 1 and 4 to 1, and 0 elsewhere.

Now my first index seek to satisfy my WHERE Condition is just a matter of looking up the Bitmap for "City = Melbourne", which I see is 1011.

I can then find my bitmaps for "Animal" and do the AND operation on the bitmaps rather than the intersection, giving me:

"Dog" 1001 AND 1011 = 1001 (rows {1,4})
"Cat" 0110 AND 1011 = 0010 (rows {3})

In my example, running the query using Bitmaps now takes in the order of 40ms, or about 100 times faster.

My next post will probably go into a bit more detail about how Hybrid Word Aligned Bitmaps actually work.  But if you are curious have a look at: 

https://sdm.lbl.gov/fastbit/

Or a pretty good .Net implementation:

http://softwarebotanysun.codeplex.com/

 

Cheers!

 

 

 

14 responses
Postgres will automatically bitmap combine indexes. This isn't only column oriented database feature.
Yes that is true, many row oriented databases also support bitmap indexes (even building them dynamically for certain query operations).

The benefit of column oriented is that the bitmap index can be the data representation, so its not an additional index.

Kind of like how in SQL Server you get one free index for each table (the clustered index - how the data is physically stored), but each additional index means increased data storage requirements.

Column-oriented databases are faster for low selectivity queries (where you might need to access most tuples). They can be slower to update and may be slower at high selectivity queries.

Another important element is that column-oriented designs allow better compression. This compression can even be enhanced if you sort the tables (or projections) in the right way before compressing the columns.

You should watch out though because several techniques are actually patented. This is true of bitmap index formats like WAH that you are using. Fastbit is great, but make sure you acquire a license before you use it in your project. Or you can use alternatives such as EWAH which are not patented.

References:

EWAH implementation in Java:
http://code.google.com/p/javaewah/

EWAH implementation in C++:
http://code.google.com/p/lemurbitmapindex/

Daniel Lemire and Owen Kaser, Reordering Columns for Smaller Indexes, Information Sciences 181 (12), 2011.
http://arxiv.org/abs/0909.1346

Unfortunately, HWAB are protected under one or more patents.
Hmm, wonder if the GPU (cuda) could be used to increase the performance even more. The combination of arrays can basically be seen as arrays, which GPU's really like.

Just a (stupid) idea...

lemire is on right track.

Column-oriented databases are faster for low selectivity queries (where you might need to access most tuples). They can be slower to update and may be slower at high selectivity queries.
Another important element is that column-oriented designs allow better compression. This compression can even be enhanced if you sort the tables (or projections) in the right way before compressing the columns.

You should watch out though because several techniques are actually patented. This is true of bitmap index formats like WAH that you are using. Fastbit is great, but make sure you acquire a license before you use it in your project. Or you can use alternatives such as EWAH which are not patented.

References:

EWAH implementation in Java:
http://code.google.com/p/javaewah/

EWAH implementation in C++:
http://code.google.com/p/lemurbitmapindex/

Daniel Lemire and Owen Kaser, Reordering Columns for Smaller Indexes, Information Sciences 181 (12), 2011.
http://arxiv.org/abs/0909.1346

Awesome posting! Can I translate this into Korean and share it with my colleague? if you don't mind?
@Seongsik, go for it (just include a link back here if that's ok)
@Nasrullah Thanks for that. Do you have any information on the relative performance between EWAH and WAH (HWAB in my post for god knows what reason!)?

Thanks

Do you have a link or any more information on Vertica's use of WAH bitmaps?
thank you so much...! i have understood your idea but generally ... if the number of rows in a table are less enough to be fit in a hard drive block, then a row-oriented dbms would place all the rows of our tables in single row with the row id's like below 001:Dog, White, Melbourne;002:Cat, Black, Sydney;003:Cat, White, Melbourne;004:Dog, Black, Melbourne and a column-oriented dbms will store like below 001:dog,002:cat,003:cat,004:dog;001:white,002:black,003:white,004:black;001:Melbourne........ but why did you ask to assume them as array..so iam bit confused..can you help me..?
Interesting article as it shows the difference on real example. Thanks to the author for explanation.
1 visitor upvoted this post.