Why analytics databases store data by column

Why row storage becomes wasteful in analytics

The first time I compared OLTP and OLAP, the workload split made sense but the storage split did not. This section filled in the missing piece. A warehouse may hold very wide fact tables, while an analytical query often needs only four or five columns from millions or billions of rows.

A row-oriented database keeps every value for one record together. That is a sensible layout when an application reads or updates one order, user, or payment. For a broad analytical scan, however, it means loading, parsing, and discarding most of every wide row.

ROW-ORIENTED STORAGE
row 1: date | product | store | customer | quantity | price | ...
row 2: date | product | store | customer | quantity | price | ...

Analytical query needs only:
date | product | quantity

All other values still get read and parsed.

A column store keeps related values together

A column-oriented database stores all values from one column together instead. A query can load only the column files it uses, which removes a large amount of disk I/O and parsing work. The idea applies outside relational databases too. Parquet is a columnar format that can represent document-like data.

The entries in every column file must remain in the same order. The 23rd date, 23rd product, and 23rd quantity form the logical 23rd row. This gives a column store its ability to reconstruct a full record when needed.

COLUMN-ORIENTED STORAGE
date:     [Jan 1, Jan 1, Jan 2, ...]
product:  [42,    17,    42,    ...]
quantity: [2,     1,     4,     ...]

entry 23 in every column
= values for logical row 23

Compression works better when one column has one kind of value

A column often contains repeated or similar values. That makes it easier to compress than a mixed row of IDs, dates, text, prices, and unrelated attributes. Compression means less data needs to move from disk into memory.

It also helps the CPU. More values fit in the same cache space, so the query engine can do useful work with less memory traffic.

ROW DATA
date | ID | text | price | quantity
mixed values, weaker repetition

COLUMN DATA
quantity: 1, 1, 1, 2, 2, 2, ...
repeated patterns, better compression

Bitmap indexes make common filters very cheap

When a column has far fewer distinct values than rows, a warehouse can build one bitmap for each value. Each bitmap has one bit per row. A 1 means that row contains the value, while a 0 means it does not.

With many possible values, most bits in a particular bitmap are zero. These sparse bitmaps compress well with run-length encoding. The result can be compact even for a table with an enormous number of rows.

product = 30:  0 1 0 0 1 0
product = 68:  1 0 0 1 0 0
product = 69:  0 0 1 0 0 1

one bit position
= one logical row

OR and AND answer filters without touching every row

For a condition such as product IN (30, 68, 69), the engine loads those three bitmaps and applies a bitwise OR. A result bit of 1 marks a row where any selected product appears.

For product = 31 AND store = 3, it loads one bitmap from each column and applies a bitwise AND. This only works because the same bit position refers to the same logical row in both columns.

product IN (30, 68, 69)
bitmap 30 OR bitmap 68 OR bitmap 69
-> rows matching any chosen product

product = 31 AND store = 3
bitmap product 31 AND bitmap store 3
-> rows matching both conditions

Column families are not automatically column stores

Cassandra and HBase use the term column family, which can be confusing. Within a column family, they still keep a row key and several values from that row together, and they do not use this style of column compression.

Their layout is therefore mostly row-oriented. The name describes a data-model grouping, not the analytical column-store layout discussed here.

COLUMN FAMILY
row key + values from that row together

ANALYTICAL COLUMN STORE
all values for one column together
column compression and scan-oriented processing

Column storage also matches how CPUs work

Analytical scans can bottleneck not only on disk reads, but also on memory bandwidth, CPU cache misses, branch mispredictions, and the processor instruction pipeline. Column layouts help because the engine can work through a compact chunk of one column in a tight loop.

The engine can operate on many values at once using CPU SIMD instructions, and even apply operations such as bitmap AND or OR directly to compressed chunks. This style is called vectorized processing.

COMPRESSED COLUMN CHUNK
-> fits in CPU cache
-> tight loop over many values
-> SIMD and bitwise operations
-> less branch and function-call overhead

Sort order can narrow scans and improve compression

A column store may keep rows in insertion order, but it can also sort complete rows by columns that common queries use. It cannot sort every column separately, because that would break the row alignment needed to reconstruct records.

If analysts often query recent dates, sorting first by date lets the database scan a smaller section of the table. A second sort key, such as product, groups related values within each date. Sorting can also create long runs of identical values, which improves run-length compression, especially for the first sort key.

SORT KEY: date, then product

same date values stay together
same product values within a date stay together

smaller date-range scan
and longer repeated-value runs

Multiple copies can use different sort orders

Different analytical queries benefit from different sort orders. C-Store and Vertica use replicated copies of data sorted in different ways, so the query optimizer can choose the version that best fits a query.

This resembles having several secondary indexes in a row store, but the mechanics differ. A row-store secondary index usually points to a row elsewhere. A column-store copy keeps the values directly in its own columns, so there is usually no pointer chase.

COPY 1: sorted by date, product
COPY 2: sorted by customer, store
COPY 3: sorted by store, date

query optimizer
-> choose layout matching query

What I will carry forward

A column store is a direct answer to a familiar warehouse problem: wide tables, huge scans, and queries that need only a few attributes. It avoids reading irrelevant fields, compresses repetitive data well, and gives the CPU a compact layout for fast scans.

Those benefits come with a trade-off. Sorted, compressed columns are harder to update in place. The next part explains how column-oriented systems deal with recent writes.

WIDE FACT TABLE
-> read only needed columns
-> compress repeated values
-> scan in CPU-friendly chunks
-> sort for common filters

Read performance improves.
Writes need a different strategy.

These are my personal learning notes from Designing Data-Intensive Applications by Martin Kleppmann.