Part 5 of 6 · 2 min read
Writing to a column store
Writing to a column store
Think of inserting a new entry into a sorted, bound ledger. There is no blank space to write into partway through. The only way to insert in the middle is to rewrite every page after that point.
In plain words: Compressed, sorted column files cannot be updated in place the way a B-tree page can, since inserting one row in the middle of a sorted, compressed column would require rewriting the rest of that column's file, and every other column's file in the same way, to keep row positions aligned. The practical fix mirrors the LSM-tree pattern seen earlier in this subject: new writes land first in a small, separate in-memory structure, and only once enough writes accumulate are they merged into new column files on disk in bulk, the same append-and-compact pattern used for write-heavy row stores. A query simply checks both the on-disk column files and the small in-memory structure holding very recent writes, combining the two transparently.
A worked example. A new sale lands first in the bookstore warehouse's in-memory write buffer rather than being spliced directly into the sorted sales_fact column files. Once that buffer accumulates enough rows, it is merged into a new batch of on-disk column files in one bulk operation, exactly as an LSM-tree flushes a memtable into a new SSTable.
The key lines. No new SQL; this describes a write path, not a query.
New sale -> in-memory write buffer (row-oriented, small)
Buffer full -> merged in bulk into new sorted column files on disk
Write buffering (column store)
Write buffering in a column store holds newly arrived rows in a small, separate in-memory structure rather than inserting them directly into the large, compressed, sorted column files, merging them into new files in bulk only once enough have accumulated.
Example: the in-memory write buffer above absorbs new sales until it is full, then is merged into the on-disk column files at once, the same pattern an LSM-tree uses for its memtable.
Quick notes
- Row-oriented storage groups one row's columns together; column-oriented storage groups one column's rows together, letting a query read only the columns it needs.
- A typical analytical query touches only a handful of a wide fact table's columns, which is exactly what column-oriented storage is built to exploit.
- Bitmap encoding represents a column as one bitmap per distinct value; run-length encoding compresses a bitmap's runs of repeated bits.
- Sorting rows by a chosen sort key compresses the first sort column best and speeds up queries that filter on it; later sort keys compress progressively less.
- In-place updates do not work on compressed, sorted columns; writes are buffered in memory and merged into new column files in bulk, an LSM-tree-style pattern.