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 × pricefor 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?