CMSC724: Column Stores and Compression

Instructor: Amol Deshpande

This chapter covers C-Store (Stonebraker et al., VLDB 2005) and the assigned reading, “Integrating Compression and Execution in Column-Oriented Database Systems” (Abadi, Madden, Ferreira; SIGMOD 2006). Several figures come from a tutorial on column stores by Harizopoulos, Abadi, and Boncz.

Where the previous chapter’s technique was nearly free, this one is not. Column stores have a much higher upside and a much larger downside than PAX, and most of the chapter is about what that downside costs and how systems pay it.

Passages marked as editorial extensions were written by the notes generator and go beyond the source slides and class discussion.

1. Fractured Mirrors

Fractured mirrors: store the replica in a different format

One idea worth seeing before C-Store, from Ramamurthy, DeWitt, and Su (VLDB 2002).

The observation: replication — mirroring — is already widely used for fault tolerance. You take a relation, make a copy, and store it elsewhere. So why store the copy in the same format?

Their proposal: keep the original as NSM and the replica as DSM, and mix and match. On one disk part of the data is NSM and part DSM; on the other disk the assignment is reversed. A query then reads from whichever copy suits it.

The tradeoffs are what you would expect, and you can read the result either way: the best of both worlds or the worst of both. You get real read benefits, but updates are difficult — now you maintain two formats.

It is a nice idea and a nice paper, and it did not go anywhere, because it is too hard to make work. But the hybrid insight is worth keeping somewhere in mind; it recurs.

2. Row Stores versus Column Stores

Two systems arrived around the same time, in the late 1990s and early 2000s. MonetDB was being built at CWI in Amsterdam. It got less recognition than it deserved — partly a function of how the work was written up — and people have since tried to correct that. But at the time it was Stonebraker’s C-Store paper that set off the work in this area, even though MonetDB had been doing it for five or six years already.

The idea is simple: store data column by column rather than row by row. The tradeoff is symmetric:

	Row store	Column store
Record operations (updates, inserts)	Easy	Very difficult
Reading	May read unnecessary data	Read only the columns you need
Suited to	Transactional workloads	Read-mostly large data warehouses

Most data warehouses today are built as column stores. And the Parquet format we will get to shortly is columnar for exactly this reason — it is essentially a read-only format.

How large is the win?

The Telco experiment: 200 columns, 7 needed

From experiments in Stonebraker’s earlier One Size Fits All work, using a synthetic “Telco” schema. The usage table has 200 columns, of which a given query needs 7.

The results show order-of-magnitude gaps between Vertica (the column store) and a row-oriented data warehouse appliance. Two things to notice in the numbers:

The appliance cost is identical across queries. Every one of them requires a scan, so runtime is dominated by scan time — I/O cost dominates, and the query barely matters. (The row store also was not using indexing here, which is part of why the numbers are flat.)

The gap is almost entirely about how much data is read — 200 columns versus 7. Compression contributes too: Vertica compresses the columns, and while the appliance also compressed, its ratios were much lower, because compressing column by column is much more effective than compressing tuple by tuple.

This is the order-of-magnitude gap that PAX cannot reach. PAX’s changes are local to a page; column stores change how much data comes off disk.

3. C-Store and Projections

C-Store: relational model and SQL on top, everything below redesigned

C-Store keeps the relational model and SQL on top, and rewrites the storage and execution engine entirely underneath.

All data is stored in the form of projections, which are essentially materialized views. This takes some thinking, because it is more general than “one file per column.”

Take an employee table and a department table. Rather than storing the rows, you store a set of projections such as:

M1: (name, age), sorted by age.
M2: (dept, age, dept_floor), sorted by floor — note that dept_floor is not in the employee table at all; it is inferred by joining with department.
M3: the department table itself.

Those projections are all you store. The original tables are not kept — not in NSM, not in DSM. They do not exist.

The extreme case of this design is one projection per column, which is essentially DSM. But projections are more general: they can combine columns across different relations. The motivation is workload-driven — if many queries involve name and age together, storing them together in one projection beats storing them separately and joining.

Reconstruction and join indexes

Join indexes stitch projections back together

The obvious problem: if you only store projections, how do you get a tuple back?

Consider M2 holding (math, 25, floor 1) and (math, 29, floor 1). Nothing in there says which employee the 25 and the 29 belong to, and you cannot use name because it is not a key.

The requirement is simply: you must be able to reconstruct the original tables. If you can, you are correct. C-Store does this with join indexes, which provide a mapping between one projection and another — M1 to M2, M1 to M3. Fundamentally, that is all they are.

Why sort the projections? Partly to make queries more efficient, and partly because sorted data compresses much better — which matters a great deal, as the next section shows. It is a fair question what the cost of reconstructing and un-sorting is; I suspect it is fairly high.

Isn’t this all extremely workload-dependent? Yes. If your query uses dept and age together it is optimized; if it uses something else, it is not. There is a natural question — given a workload, what is the best set of projections? — and there is research on it, though not from these authors, who moved on to something simpler.

Important

My belief is that nobody actually uses anything this complicated. Today’s column stores simply store column by column. The C-Store paper had interesting ideas about more efficient arrangements, but I do not believe modern databases do this.

Worth knowing anyway, both because the paper is influential and because the general move — choosing a physical arrangement to match a workload — keeps coming back.

4. Updates: The Write-Optimized Store

The write-optimized store and the tuple mover

The honest answer to “how do column stores handle updates” is: they don’t. MonetDB never really addressed updates at all. C-Store at least did, and the solution is the one that has stuck:

Maintain two stores:

A write-optimized store (WOS) — memory-based, unsorted, uncompressed, row-oriented. Fast updates.
A read-optimized store (ROS) — everything described above: columnar, sorted, compressed.

A background process, the tuple mover, asynchronously migrates data from the WOS to the ROS.

Updates follow the same principle as everything else here: you do not modify the ROS in place; you record the update in the WOS. The cost is that there are now two copies of a record, one in each store, and queries have to reconcile them. Not a large problem, but a real one.

Is the tuple mover an ETL process? No. It lives inside the database system, and it is a much more deterministic, clearly defined operation — moving between two storage representations. ETL is a far more complex process, and it happens outside and above the system.

5. Compression

Why compression and column stores fit together

Compression is one of the main benefits of columnar layout, and the reason is straightforward:

In a row store, compression benefits are limited because the data on a page is heterogeneous — a string next to an integer next to a date. In a column store, everything in a block is the same type, drawn from the same domain, and often sorted.

The costs are worth stating up front. Compression reduces storage and I/O, but decompression is a significant expense, and it sits in the fast path: as you read data to answer a query, you must decompress it, so the cost lands directly on query latency. And it makes updates considerably more complicated.

The techniques

Run-length encoding. Find the largest contiguous runs of identical values and store each as a triple: (value, start position, run length). So “starting at position 1, 300 of them are Q1; starting at position 301, 350 are Q2; starting at 651, 500 are Q3.”

RLE works well on sorted data, which is why sort order in the projections matters. In a table sorted by quarter then by product ID, you can RLE both of those columns. But price — unsorted, high cardinality — compresses to nothing. Sorting decides what compresses.

Dictionary encoding. If a column has few distinct values, assign each a short codeword. With four quarters you need two bits: 00 for Q1, 01 for Q2, 10 for Q3, 11 for Q4. Instead of storing the string “Q1” you store two bits. This works on unsorted data, unlike RLE.

A fancier variant assigns codewords not to single values but to patterns of consecutive values — Q1,Q2,Q4,Q1 in that order gets one codeword. That trades a larger dictionary for a smaller encoded size, and only pays off if particular patterns are very common. It is essentially how arithmetic coding works. I am not sure it makes sense in practice.

Bit-vector encoding. For each distinct value, store a bit vector marking which positions hold it. Product ID 1 gets a vector with 1s wherever the product is 1, ID 2 its own vector, and so on.

This is an old idea — it was in data warehouses in the 1990s and does not require a column store. And it has a property the others do not:

You can intersect bit vectors to answer queries. A vector for id = 1 and a vector for city = 'College Park' are positionally aligned over the same tuples, so a query asking for both is a bitwise AND.

Bit vectors are extremely cheap to store — it is easy to underestimate how small they get — so you can keep many of them and combine them freely. This is a trick data warehouses have used for a long time.

Frame-of-reference encoding stores values as offsets from a local base value, which works well when values in a block cluster in a narrow range.

6. Operating Directly on Compressed Data

Here is where the assigned paper’s real contribution begins. Much of the work in this space is about avoiding decompression entirely.

The example: for each product, count the entries from quarter 2.

quarter is RLE-encoded, so you immediately know that positions 301–650 are Q2. You do not scan, you index straight in.
product_id is bit-vector encoded, so within that range you count the 1s in each product’s vector.

You never look at the underlying data at all. Three entries for product 1, one for product 2, two for product 3 — the answer comes directly out of the compressed representation.

Even in the simpler case of a selection on Q3, RLE tells you exactly which positions match, so you jump to them and never decompress the quarter column.

The problem this creates

Operating on compressed data works, and it creates a serious software engineering problem.

Consider joining two columns. Is C1 compressed? Is C2? Which scheme each? You end up writing a separate code path for every combination, and the combinations multiply with every operator and every encoding you add. The result is a codebase full of special cases.

The paper’s answer is an abstraction layer over compression — note that this is about writing the code, not about execution. Compressed data is divided into compressed blocks (for RLE, a block is a single triple), and every block, whatever its encoding, must support a small API:

isOneValue() — does this block hold a single repeated value? (True for an RLE block, false for a bit vector.)
isValueSorted() — are the values in order?
isPositionContiguous(), iterators over positions and values, and so on.

Then your operator code stops asking “is this RLE?” and starts asking “is this one value?” The branching survives, but it branches on properties rather than on encodings — so adding a new compression scheme means implementing the API, not editing every operator.

This is a capability interface, and it is worth recognizing the pattern because it is the standard answer to a combinatorial explosion of this shape.

The naive design couples N operators to M encodings, giving N×M code paths, and each new encoding costs N edits scattered across the codebase. The API breaks the coupling by introducing a small vocabulary of properties that operators actually care about — is it one value, is it sorted, are positions contiguous — and having each encoding declare which it has. Operators are written against the properties. The product collapses to N + M.

The reason it works here specifically is that the property set is genuinely small and genuinely stable: the things an operator needs to know about a compressed block in order to shortcut its work turn out to be few, and they do not change when someone invents a new encoding. Where that is not true — where each new implementation brings a genuinely new property — the abstraction leaks and you are back to special cases wearing a thin disguise.

Whether this particular API is what modern column stores use, I do not know; it is the kind of internal engineering that rarely gets written up.

7. What Carried Forward

A closing caution about how to read this line of work.

C-Store and Vertica were built from scratch. Many other data warehouses moved toward column stores without redoing everything — they adopted the parts that pay best and left the rest. So what you find in a given modern system is usually less involved than what C-Store did, and that is an artifact of how those systems were developed rather than a judgment about the ideas.

The durable results from this chapter:

Columnar layout for read-mostly analytical workloads, because you read only the columns you need.
Compression per column, which works far better than compressing heterogeneous rows.
Operating on compressed data wherever possible, keeping decompression off the fast path.
Separating a write path from a read path, with a background process moving data between them.

That last pattern in particular is worth flagging, because it long outlives C-Store: it is essentially what LSM trees do, what Delta Lake does with its log and its compaction, and what nearly every system does when it needs both fast ingest and fast scans out of the same data.