C-Store: A Column-oriented DBMS

In one sentence

C-Store flips a relational database's physical storage from rows to columns, and redesigns everything around that choice: heavy compression with operators that work directly on the compressed form, the same data stored as several overlapping "projections" in different sort orders (sorted redundant copies that serve as index and as fault-tolerance replica), and a write-optimized store + read-optimized store + background tuple mover hybrid that absorbs the writes a column store hates. It marks the generational turn in analytical (OLAP) databases and was commercialized as Vertica.

Glossary

Where it sits

The authors are Michael Stonebraker (MIT), Daniel Abadi, Samuel Madden, Mitch Cherniack (Brandeis), Elizabeth and Patrick O'Neil (UMass Boston), Stan Zdonik (Brown) and others — about a dozen in all — publishing at VLDB 2005. Storing by column was not their invention: the decomposition storage model (1985), the commercial Sybase IQ, and the academic MonetDB all came earlier. C-Store's contribution is placing column storage inside one complete, workable database design — compression, sorted redundancy, a hybrid write path, replica-based recovery and snapshot reads, each leaning on the others. It launches Vertica, and together with the contemporaneous Dremel (columnar storage plus a multi-level execution tree — see that paper here) forms one of the two headwaters of today's warehouses.

The problem and the motivation

The mainstream relational systems of 2005 (Oracle, DB2, SQL Server) all descended from the OLTP world of the 1970s and 80s, and their physical storage was write-optimized: a whole row placed contiguously, so inserting a record writes one place. But the market's center of gravity had moved to the data warehouse — bulk-loaded, rarely modified, repeatedly scanned and aggregated.

On that workload the row store wastes work structurally: disks read in blocks, and a block is packed with whole rows. A query that rolls up sales by year touches two or three fields, yet the disk is forced to drag every row's dozens of fields into memory; the wider the table, the worse the waste. The remedy of the day was piles of indexes and materialized views, which cost space, slowed writes, and only ever covered the queries somebody anticipated.

The authors' judgment is blunt: the problem is not insufficient tuning, it is a physical layout on the wrong side of the trade. If reads vastly outnumber writes, design a read-optimized store from scratch — and pay back the harder writes by other means.

Core idea and method

1. Store by column: haul only the columns you use

C-Store stores each column contiguously on its own. A query reads exactly the columns it needs and never touches a byte of the rest; on wide tables, analytical queries routinely cut an order of magnitude of I/O this way.

The cost is tuple reconstruction: a query usually has to stitch several columns back into one record. C-Store's answer is position alignment — within a set of columns, the i-th value belongs to the i-th row by construction, so stitching is just indexing by ordinal and no row id is stored alongside each value. That "position is identity" convention became table stakes for every columnar engine since.

2. Compress — and compute on the compressed form

A column holds values of one type and one meaning, often in sorted order, so it repeats itself far more than a row does and compresses far better. C-Store picks an encoding along two axes: is this column the sort key of the projection it lives in (ordered or not) × does it have few or many distinct values:

• Ordered, few distinct values: run-length encoding — a run becomes the triple (value, start position, run length), squeezing thousands of rows into one entry.
• Unordered, few distinct values: bitmap encoding — each value gets a bit string saying which rows hold it, and the bitmaps themselves are run-length compressed.
• Ordered, many distinct values: store block-wise deltas from the previous value; ascending dates and ids flatten right down.
• Unordered, many distinct values: little structure to exploit, so essentially left unencoded.

The decisive step is that operators eat the compressed representation directly rather than decompressing first. Counting one store's sales against a run-length encoding means reading the phrase "5,000 rows in a row" — the answer is 5,000. What that saves is not only disk I/O but the CPU of decoding and touching rows one at a time. Compression stops being a "space for CPU" trade and starts saving both.

3. Projections: the same data in several sort orders

C-Store does not store "tables"; it stores projections: a set of columns taken from a table (possibly pulling in columns of another table through a foreign key), sorted as a whole on some sort key. One column may appear in several projections, each sorted differently. As long as every column is covered by some projection, any query can be answered.

Why design it this way? Once data is columnar and heavily compressed, keeping one more sorted copy becomes cheap — and a sorted copy does three jobs at once: it acts as an index (range queries on that key can skip whole segments); it acts as a compression multiplier (the sort key's own column is ordered, so run-length encoding takes it to the floor); and it acts as a fault-tolerance replica (see K-safety below). Base table, index and materialized view — three separate things in a classical database — collapse into one kind of object.

Each projection is then partitioned horizontally into segments by ranges of the sort key and spread across machines; each row within a segment has a storage key, simply its ordinal position, which the read-optimized copy never stores at all and computes from position instead. Different projections sort differently, so their row orders do not line up, which is what join indices are for: for each row of a "sending" projection they record the (segment id, storage key) of the matching row in the "receiving" projection, stitching the two orders back into one logical record.

4. The WS / RS hybrid: peel writes off reads

Columnar plus sorted plus heavily compressed amounts to welding the data into a slab — inserting a row in the middle nearly means rewriting a stretch of it. So C-Store splits the database in two:

• RS (read-optimized store): the big one — columnar, compressed, sorted on the sort key, storage keys implicit; only fit to be rewritten in bulk.
• WS (writeable store): the small one, logically identical to RS (same projections, same sort keys) but uncompressed, organized as B-trees on the sort key with explicit storage keys, and therefore able to take scattered inserts.

Inserts go only to WS; a delete marks the row (recorded in a deleted-record vector); an update is a delete plus an insert. A background tuple mover periodically runs a bulk merge, folding WS data that is old enough into RS in blocks, rewriting compressed blocks and updating join indices as it goes. Queries read WS and RS together and merge the results, so freshly written data is never missed. "Small fast write area + big tidy read area + background merge" recurs later in LSM trees, in ClickHouse's part merging, and in Vertica's own WOS/ROS.

5. Read-only queries take no locks: epochs and snapshot isolation

Warehouse queries are long and heavy; fighting writers for locks would strangle both. C-Store lets read-only transactions run as of a slightly earlier instant: timestamps are coarse-grained epochs (a few seconds each) and a timestamp authority advances a high water mark. A read-only query picks an epoch no later than that mark and uses each row's insertion and deletion times to decide whether it was visible then — so readers take no locks and never block writers, at the price of seeing data a few seconds stale. Read-write transactions use ordinary two-phase locking.

6. Replicas instead of a log: K-safety

RS is huge and rewritten in bulk, so write-ahead logging it would be absurdly expensive. C-Store's trade: log only the small WS and let replication carry the fault tolerance — keep enough projections that any K simultaneous machine failures still leave every column covered (K-safety). When a crashed machine restarts, the data it missed is not replayed from a log but queried back out of the other replicas and loaded into its WS. The elegance is that those replicas already exist for query performance; the fault tolerance is nearly free.

Key results

The paper reports a preliminary experiment: a TPC-H-derived warehouse schema, seven queries, against a popular commercial row store and a popular commercial column store (both anonymized). In the configuration that limited each system's disk budget, the same data took 1.987 GB in C-Store versus 4.480 GB in the commercial row store (about 40%), and on the queries C-Store averaged roughly 164× faster than the commercial row store and 21× faster than the commercial column store. The authors attribute the gain to three effects stacking: reading only the needed columns, scanning projections rather than whole tables, and better compression.

They are notably restrained about the numbers themselves: the prototype implemented only part of the design — WS and the tuple mover were not yet fully working — so what was measured is essentially the read-optimized half, and they say plainly that a thorough study must wait for the rest. Read it as directional evidence, not as a product comparison.

Why it matters

After this paper, columnar storage went from a niche option to the assumed baseline for analytical databases. C-Store was commercialized as Vertica (acquired by HP in 2011), and its combination — columnar layout, per-column encoding chosen for heavy compression, computing on the compressed form, sorted redundant copies doubling as indexes, a split write/read path with background merging — was inherited by nearly every analytical engine since: Redshift, ClickHouse, Snowflake, BigQuery, and the Parquet / ORC columnar file formats. The lakehouse queries that scan billions of rows in seconds today are living off that dividend.

It also made Stonebraker's slogan concrete: one size does not fit all — OLTP and OLAP deserve engines of different shape, not one engine with different knobs (the same group's H-Store / VoltDB is the other half of that argument). Academically it opened a whole line of work on how compression and execution should cooperate and on when to stitch columns back into rows (late materialization).

Limitations and criticism

• A prototype measured against commercial products is not an even match: tuning, maturity and feature completeness are in different leagues, and the authors call the results preliminary. Wisconsin's DeWitt and Halverson later redid the comparison inside one common framework and found the gap far narrower, with a good share of the gain coming from physical design (narrow tables / vertical partitioning) rather than from "column storage" as such.
• The sources of the gain were not yet separated: Abadi et al.'s 2008 "how different are they really?" showed that emulating a column store inside a row store by vertical partitioning is often slower, and that the real wins come from compression, late materialization and block iteration — execution-layer techniques that were only embryonic in the 2005 version.
• The write path is the weakest and least-built part: WS and the tuple mover are exactly what the paper implemented least, and exactly what decides whether a column store can go to production.
• Engineering did not adopt all of it: the Vertica team's seven-years-later retrospective admits join indices proved complex and expensive and were essentially never used in the product, replaced by pre-join projections and similar devices.
• Physical design becomes the new burden: which projections to build, in what sort order, with how much redundancy, decides performance outright; the paper hands that hard problem to an automatic design tool, and a bad choice degrades into "bulky and still slow."
• Not for OLTP: changing one row touches several projections and several encodings, and read-only queries see a snapshot seconds old — a deliberate trade, not an oversight.

Takeaways