CSE Roadmap

Common tier · about 3 hours · 7 parts

Part 5 of 7 · 4 min read

Rows or columns

Why storing each column together makes a scan read far fewer bytes.

Think of a stack of forms against a set of lists. A stack of forms has one sheet per customer, with all the fields on it. To total the amounts, the clerk must turn over every sheet. A set of lists has one list for each field: all names, all cities, all amounts. To total the amounts, the clerk reads one list.

The book describes the difference. Most OLTP databases store data row by row: all the values of one row sit together on disk. A document database also keeps a whole document together. This is good when the program needs the whole row. But a typical warehouse query reads only a few of the many columns. The fact table in the book's retail example has over 100 columns, and a query touches 4 or 5.

In a row store, the engine must still load every row from disk and parse it, then throw most of it away.

Column-oriented storage

Column-oriented storage keeps all the values of each column together in one file, in the same row order in every file.

Example: one file holds all quantity values, another all price values. The 5th item in each file belongs to the 5th row.

Because every file has the same row order, a row is rebuilt by taking the same position from each file.

A worked example. The fact table has 1 billion rows and 100 columns of about 4 bytes each.

  • Row size: 100 × 4 = 400 bytes. Table size: 1,000,000,000 × 400 = 400 GB.
  • Query: total of quantity × price for one product. It reads 3 columns: product_key, quantity, price.
  • Row store: reads all 400 GB. At 1 GB per second, 400 seconds.
  • Column store: reads 3 columns × 4 bytes × 1 billion = 12 GB. At 1 GB per second, 12 seconds.
  • The column store reads 100 ÷ 3, about 33 times less data.

Column files also compress very well. The book says the number of distinct values in a column is often small compared with the number of rows: a retailer might have billions of sales but only 100,000 products.

Bitmap encoding. For a column with n distinct values, make n bitmaps, one for each value, with one bit per row. A bit is 1 if the row has that value.

A worked example. Eight rows, with product_key: 30, 31, 30, 68, 31, 30, 69, 68.

Value Bitmap (rows 1 to 8)
30 1 0 1 0 0 1 0 0
31 0 1 0 0 1 0 0 0
68 0 0 0 1 0 0 0 1
69 0 0 0 0 0 0 1 0

The query WHERE product_key IN (30, 68, 69) loads three bitmaps and takes the bitwise OR:

30: 1 0 1 0 0 1 0 0
68: 0 0 0 1 0 0 0 1
69: 0 0 0 0 0 0 1 0
OR: 1 0 1 1 0 1 1 1   -> rows 1, 3, 4, 6, 7, 8

The query product_key = 31 AND store_key = 3 takes the AND of two bitmaps. Say the store column has the bitmap 1 1 0 1 0 1 1 0 for store 3.

product 31: 0 1 0 0 1 0 0 0
store 3:    1 1 0 1 0 1 1 0
AND:        0 1 0 0 0 0 0 0   -> row 2

This works since the kth bit in each bitmap is the same row. When n is large, most bitmaps are mostly zeros, so they are stored using run-length encoding, which records only how long each run of equal bits is.

Run-length encoding

Run-length encoding stores a repeated value once with a count, instead of every repetition.

Example: the sequence 7, 7, 7, 7, 9, 9 is stored as (7 × 4), (9 × 2).

The book adds a caution. Cassandra and HBase have "column families" inherited from Bigtable, but they are not truly column-oriented: within a family, they store all columns of a row together and do not use column compression. They are still mostly row-oriented.

Check yourself:

  • A table has 50 columns and a query reads 2. About how many times less data does a column store read?
  • Why can a bitmap AND combine conditions on two different columns?