Terence Siganakis:

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.  

The comment thread discusses a couple of reasons for column databases being faster than row-oriented databases and some scenarios where this is not happening.

Terence Siganakis links to FastBit: An efficient compressed Bitmap index technology :

FastBit is an open-source data processing library following the spirit of NoSQL movement. It offers a set of searching functions supported by compressed bitmap indexes. It treats user data in the column-oriented manner similar to well-known database management systems such as Sybase IQ, MonetDB, and Vertica.

Original title and link: Hybrid Word Aligned Bitmaps: Why are column oriented databases so much faster than row oriented databases? - (NoSQL database©myNoSQL)

via: http://siganakis.com/using-bitmap-indexes-in-query-processing