CSE Roadmap

Common tier · about 3 hours · 7 parts

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