Part 6 of 7 · 5 min read
Sorting, compression and writes in a column store
Choosing a sort order, the compression it brings, and how updates reach column files.
Sorting, compression and writes in a column store
Think of a library shelf sorted by subject. If the shelf is also sorted by year inside each subject, a reader after the books on one subject from 2020 to 2025 reads a short stretch.
The book explains that in a column store the order of rows does not matter by default, and appending is easiest. But a sort order can serve as an index, as with SSTables. The sort is applied to whole rows, never to one column alone, because otherwise the 5th value of one column would no longer belong to the same row as the 5th value of another.
The administrator picks the sort columns from the common queries. If queries often target a date range, the date is the first sort key. A second sort key, such as product, groups the sales of one product on one day, helping queries that group or filter by product within a date range.
Sorting also helps compression. If the first sort column has few distinct values, after sorting it has long runs of the same value. Run-length encoding can shrink it to a few kilobytes, even for billions of rows.
A worked example. The table has 1 billion rows and is sorted by date_key, with 1,000 days in the data.
- Unsorted, a 4-byte column: 1,000,000,000 × 4 = 4 GB.
- Sorted and run-length encoded: 1,000 runs, each with a value (4 bytes) and a count (8 bytes): 1,000 × 12 = 12,000 bytes, 12 KB.
- A reduction from 4 GB to 12 KB.
- The second and third sort keys have shorter runs, so they compress less. The first key gives the largest gain.
A query for "the last 30 days" reads only the 30 runs at the end of the sorted date column, and the matching stretch of the other columns. It skips the other 970 days.
The book mentions an extension from C-Store and Vertica: store the same data several times, each sorted in a different way. Data is copied to several machines for safety anyway, so each copy can have a different order, and the query uses the copy that fits best. This resembles having several secondary indexes, but with no pointers to data elsewhere: each copy holds the values itself.
Writes. The book warns that these tricks make writes harder. A compressed, sorted column cannot be updated in place. Inserting a row in the middle would rewrite all column files. The answer is the LSM-tree idea of module 4. Writes go first to an in-memory store, sorted and ready. When enough have gathered, they are merged with the column files on disk and written out in bulk as new files. Queries look at both the files and the recent in-memory writes and combine them, so an analyst sees new data at once.
Materialized aggregates. The book ends with a trick for repeated queries. If many queries compute the same totals, it is wasteful to scan the raw data each time. A materialized view keeps the results of a query as a real table on disk.
Materialized view
A materialized view is a stored copy of the result of a query, which the database refreshes when the source data changes. A normal (virtual) view is only a saved query that runs each time.
Example: a table daily_sales_by_store holds one row for each store and day, filled by a job. A report reads 2,000 stores × 365 days = 730,000 rows instead of scanning 22 billion.
A grid of such totals is sometimes called a data cube. The book notes the trade-off: reads of those totals are very fast, but the cube is less flexible than raw data, since it can answer only questions built from the dimensions it has summed. Raw data stays for the other questions.
| Technique | Helps | Costs |
|---|---|---|
| Column storage | Scans that read few columns | Slower single-row writes |
| Compression | Less disk and memory use | CPU to decode |
| Sort order | Range scans and compression | Choose carefully, one main order |
| Materialized view | Repeated aggregates | Refresh work, less flexible |
Interview angle
Answer in your head first, then open it.
Where do the reports and dashboards read from?
Not from the live database. A pipeline copies data to a warehouse or a column store, shaped as a fact table with dimensions.
Why columns for analytics?
A query touches a few of many columns, so reading only those cuts bytes read, and similar values compress well.
How do you keep dashboards fast for popular questions?
Pre-aggregate into materialized views or summary tables, and keep raw data for ad hoc questions.
How fresh is the warehouse?
State it: nightly batch, minutes with a change stream, or seconds with a streaming pipeline (Level 6).
Check yourself:
- Why can a column not be sorted on its own?
- What does a materialized view trade away for speed?
Words you will meet
| Word | Plain meaning |
|---|---|
| OLTP | Many small reads and writes by key, for an interactive app |
| OLAP | Few big queries that scan and total many rows |
| Data warehouse | A separate read-only copy of data, shaped for analysis |
| ETL | Extract from sources, transform, load into the warehouse |
| Fact table | One row for each event, with amounts and keys |
| Dimension table | A table that describes who, what, where or when |
| Star schema | A fact table in the middle with dimension tables around it |
| Snowflake schema | A star schema with dimensions split further |
| Row store | Stores all values of a row together |
| Column store | Stores all values of a column together |
| Bitmap index | One bit per row for each distinct value |
| Run-length encoding | Storing a repeated value once with a count |
| Materialized view | A stored copy of a query result |
| Data cube | A grid of pre-computed totals |