Notesstorage🌱 seedling

Column-Oriented Storage

Also: Columnar Storage · Column Store · Columnar Database · Column-Oriented Database

Store each column of a table contiguously instead of each row, all in the same row order. Scans read only the columns a query needs, compress far better, and can skip blocks by their min/max statistics.

Why it exists

Analytic queries read a few columns of billions of rows. In a row store those values are interleaved with every other column, and disks read whole pages, so a scan reads everything.

How it works

  • Same order everywhere: the k-th value of each column belongs to row k; a row is rebuilt by taking position k from each column.
  • Sort key: the table is sorted by chosen columns, which lengthens runs for Columnar Compression and narrows each block's min/max range so queries skip blocks. Like a Clustered Index, there's one per copy.
  • Projections: storing the data again in another sort order serves filters on other columns, at the cost of space and write work.
  • Writes: batches are sorted and written as immutable parts, then merged in the background, the LSM-Tree pattern; deletes are marks until the next merge.
  • Vectorized execution: operators process batches of ~1,000 values of one column in tight, cache-resident, SIMD-friendly loops.

Trade-offs

Gains Costs
reads only referenced columns rebuilding a whole row needs one read per column
high compression single-row inserts and updates are expensive
block skipping on the sort key little skipping on columns outside the key

In practice

  • ClickHouse sorts each table by its ORDER BY key and keeps a sparse index entry per granule of up to 8,192 rows.
  • Apache Parquet is a column store per row group, readable by almost every engine.
  • Dremel's 2010 paper reported a query reading 0.5 TB from compressed columns that read 87 TB in row form.

Pitfalls

  • SELECT * throws the advantage away.
  • Streams of tiny inserts create too many small parts for merges to keep up with.

Recall

These cards are also in your review deck, scheduled with spaced repetition.