C-Store: A Column-oriented DBMS

In one breath — the whole paper, compressed

C-Store is a read-optimized relational DBMS built on the premise that CPU cycles are abundant and disk bandwidth is not. Instead of tables plus indexes it stores only projections: overlapping groups of columns, each group sorted on its own sort key, horizontally partitioned into segments and heavily compressed with an encoding chosen from the column's sort order and cardinality. Updates land in a small B-tree-based Writeable Store and are migrated in bulk into the large Read-optimized Store by an LSM-style tuple mover, while read-only queries run at an epoch timestamp under snapshot isolation and take no locks at all. Full rows are reassembled across differently sorted projections using storage keys and join indices, and the same redundancy delivers K-safety on a shared-nothing grid. On a seven-query TPC-H subset C-Store ran on average 164 times faster than a commercial row store and 21 times faster than a commercial column store, while occupying less disk than either.

Before this paper — the world it landed in

In 2005 every major DBMS vendor shipped a record-oriented storage engine: the attributes of a tuple laid out contiguously so one disk write pushes an entire record out, with B-tree primary and secondary indexes bolted on top. That layout is write-optimized and excellent for OLTP, but warehouses and other read-mostly systems - CRM, electronic library card catalogs, ad-hoc inquiry systems - bulk-load periodically and then scan a few columns of very large tables for a long time. Column stores already existed in the market, notably Sybase IQ, Addamark and KDB, but they typically kept columns in entry sequence, which makes appends cheap at the cost of a retrieval order that suits almost no query. Warehouse operators such as Walmart already maintained two copies of their data because log-based recovery on a terabyte data set was prohibitive, and the OLAP vendors leaned on precomputed data cubes and materialized views, which only pay off when the query set is known in advance. C-Store targeted precisely the case they could not serve: unanticipated ad-hoc queries, with on-line updates, over a shared-nothing grid of commodity blade computers.

The problem — what was actually breaking

A row store must read all the attributes of a tuple even when a query touches only a few of them, so warehouse scans burn the scarcest resource in the machine, which is disk bandwidth rather than CPU.
Conventional engines pad attributes to byte or word boundaries and store values in their native format, a sensible choice when CPU was expensive but a waste now that CPUs are getting faster far more quickly than disk bandwidth is growing.
B-tree primary and secondary indexes are effective in an OLTP write-optimized environment but do not perform well in a read-optimized one, where bitmap indexes, cross-table indexes and materialized views are more advantageous.
Existing column stores such as KDB and Addamark keep columns in entry sequence order, which makes insertion cheap but leaves a less-than-optimal retrieval structure, while storing columns in a non-entry sequence makes insertions very difficult and expensive.
Running many large ad-hoc queries alongside a smaller stream of OLTP-style update transactions under conventional dynamic locking produces substantial read-write conflict, blocking and deadlock.
Recovery by DBMS log processing on a terabyte warehouse is prohibitively expensive, and grids of tens to hundreds of nodes cannot be hand-tuned because there are not enough skilled DBAs to go around.

Core ideas — the contributions, and why they work

Projections instead of tables and indexes

C-Store stores no base tables at all; the only physical objects are projections, each anchored on a logical table and holding one or more of its columns plus, optionally, columns pulled in from other tables along a chain of n:1 foreign-key relationships. A projection retains duplicate rows and therefore has exactly as many rows as its anchor table, is stored column by column, and every one of its columns is laid out in the single order given by the projection's sort key. Because a projection is materialized in sorted order rather than being an unordered heap with indexes bolted on, a predicate over the sort key becomes a range scan and adjacent values become highly compressible. The chosen set of projections must be covering, so that every column of every table lives in at least one projection and any SQL query can be answered.

Overlapping redundancy that pays twice

The same column may exist in several projections, sorted differently in each, which is a deliberate break from the one-physical-copy discipline of row stores. That redundancy buys availability: when the administrator asks for K-safety, projections and join indices are laid out so that after any K node failures a covering set still exists and can be mapped into a common sort order. It also buys speed, because the optimizer's main decision is simply which projection to answer a query from, and a query that matches a projection's sort order avoids sorting and reads less. Aggressive compression is what makes the redundancy affordable, and the paper's own benchmark schema, with five overlapping projections, still fit in under half the space the row store needed for tables plus indexes.

Encoding chosen from order and cardinality

Every RS column is compressed with one of exactly four encodings, selected from two properties: whether the column is sorted on its own values (self-order) or on some other column of the same projection (foreign-order), and how many distinct values it holds. Sorting is what manufactures the redundancy that compression consumes, so the same decision that makes a projection fast for a query also makes it small on disk, and the two design levers reinforce each other instead of competing. That is the argument for supporting many sort orders at once: aggressive coding means extra orderings do not cause an explosion in space. Each encoding keeps a densepack B-tree over the coded objects, so compression never costs the ability to search.

An executor that runs on compressed data

The query executor is built from ten node types whose operands and results are projections, columns and bitstrings, not rows, and its operators are written to consume the compressed representations directly rather than decompressing first. Select does not restrict its input; it emits a bitstring, which Mask applies later, and BAnd, BOr and BNot combine bitstrings so predicates compose without ever materializing tuples. A Select over a Type 2 column can be answered by reading only those bitmaps whose values satisfy the predicate, even though the column is not sorted on that value, which is a plan a row engine has no way to express. The paper is explicit that this ability to process compressed data, not columnar layout alone, is the key to C-Store's performance advantage.

The WS/RS hybrid and the tuple mover

Keeping columns in a sort order other than entry sequence makes in-place insertion ruinous, so C-Store splits storage into two engines: a small Writeable Store architected for high-performance inserts and updates, and a much larger Read-optimized Store that accepts new data only as bulk movement from WS. WS implements the identical logical design - same projections, same sort keys, same join indices - so that only one optimizer has to be written, but it stores uncompressed (value, storage key) pairs in B-trees and is expected to be largely main-memory resident. A background tuple mover performs a merge-out borrowed from the LSM-tree, merging ordered WS objects with large RS blocks into a fresh copy of RS that is installed when the merge completes. Deletes are only marked, updates are an insert plus a delete, and the mover eventually sweeps everything into the compressed side.

Snapshot isolation without locks, redo, or PREPARE

Read-only queries run in historical mode at an effective time no later than a system-wide high water mark, before which no uncommitted transactions remain, so they set no locks whatsoever and never contend with the update stream. Read-write transactions still use strict two-phase locking, but the log carries only UNDO records - REDO is replaced by copying state from surviving projections on other sites - and distributed commit omits the PREPARE phase of two-phase commit entirely. This is safe only because K-safety guarantees another copy of the data already exists: a site told to commit that crashes before writing anything durable rebuilds its state by querying other projections. C-Store is therefore trading the generality of a redo log and 2PC against redundancy it is already paying for on availability grounds.

How it works — the mechanism, concretely

Projections, sort keys and segments

A projection is written as its columns followed by a vertical bar and its sort key, for example EMP2(dept, age, DEPT.floor | DEPT.floor), and tuples are sorted on the key columns in left-to-right order while each of the K columns becomes its own data structure. Every projection is horizontally partitioned into one or more segments carrying a segment identifier Sid greater than zero, and C-Store supports only value-based partitioning on the projection's sort key, so each segment owns a key range and the set of ranges partitions the key space. Segments are also the unit of placement on the grid: all columns of a segment are co-located, a join index is co-located with its sending segment, and each WS segment sits with the RS segments covering the same key range. Choosing the projections, segments, sort keys and join indices is the C-Store physical design problem, to be solved automatically against a training workload and a space budget B while meeting the required K-safety.

Storage keys and join indices

Inside a segment every value of every column is associated with a storage key, and values in different columns of the same segment carrying the same storage key belong to one logical row. In RS the storage key is simply the ordinal number of the record in the segment and is never stored, only calculated; in WS it is stored explicitly as an integer larger than the largest RS storage key, drawn from a node-local counter with the site id appended so that nodes never have to synchronize to allocate keys. A join index from projection T1 to T2 is a collection of per-segment tables of rows (s: Sid in T2, k: storage key in segment s), one row per tuple, and since both projections are anchored at the same table the mapping is always one-to-one; equivalently it re-sorts T1's order into T2's order. Reconstructing a table requires a path of join indices carrying every attribute into some common sort order, and the paper deliberately stores each column in several projections so that few join indices are needed, because each one must be updated whenever either side is modified.

The four RS encodings

Type 1, self-order with few distinct values, is a sequence of triples (v, f, n) giving the value, the position where it first appears and its run length, so a group of 4s in positions 12 through 18 is (4, 12, 7), with one triple per distinct value and a clustered B-tree over the value field. Type 2, foreign-order with few distinct values, is a sequence of pairs (v, b) where b is a bitmap of the positions holding v, so the column 0,0,1,1,2,1,0,2,1 becomes (0, 110000100), (1, 001101001) and (2, 000010010); the sparse bitmaps are themselves run-length encoded and offset-index B-trees map positions back to values. Type 3, self-order with many distinct values, is block-oriented delta coding in which the first entry of each block is a value with its storage key and every later entry is a delta from its predecessor, turning 1,4,7,7,8,12 into 1,3,3,0,1,4. Type 4, foreign-order with many distinct values, is left unencoded; because RS has no on-line updates all of these B-trees can be densepacked with no empty space, and with 64 to 128K disk blocks their height stays at two or less.

WS: an updatable column store

WS is also a column store implementing exactly the same physical design as RS, but nothing is compressed because WS is assumed trivial in size relative to RS, and WS is partitioned the same way so there is a 1:1 mapping between WS and RS segments. Each column is a collection of (v, sk) pairs held in a conventional B-tree keyed on the storage key, and the sort key of each projection is additionally represented by (s, sk) pairs in a B-tree on the sort key field, where sk is the storage key at which sort-key value s first appears. A search by sort key therefore consults the latter B-tree to find the storage keys of interest and then the per-column B-trees to fetch the remaining fields of those records. An insert becomes one physical insert per column per projection plus the sort-key entry, all sharing a single storage key, which is why the design is built on BerkeleyDB B-trees with a very large main-memory buffer pool so hot WS structures stay resident.

Snapshot isolation: epochs, HWM and LWM

Time is divided into coarse epochs, expected to be many seconds each, and one site is designated the timestamp authority. To advance the high water mark the TA broadcasts an end-of-epoch message; each site increments its current epoch from e to e+1 so newly arriving transactions run with timestamp e+1, waits for every transaction that began in epoch e or earlier to complete, then replies epoch complete; once all sites have replied the TA sets the HWM to e and broadcasts it, after which read-only transactions may read data from epoch e or earlier with no locks and a guarantee that it is committed. Visibility is computed record by record from an insertion vector, holding the insertion epoch of each WS record, and a deleted record vector, holding 0 or the deletion epoch for each record; the DRV is kept in WS because it must be updatable and is compressed with the Type 2 bitmap scheme since it is mostly zeros, and RS needs no insertion vector because the tuple mover guarantees nothing in RS was inserted after the LWM. A low water mark bounds how far into the past a query may reach, avoiding the onerous cost of general time travel, and epoch numbers are meant to wrap like TCP sequence numbers once no DRV entry still refers to them.

Tuple mover and the merge-out process

The tuple mover runs as a background task looking for worthy (RS, WS) segment pairs and performs a merge-out process, MOP, on one pair at a time. MOP finds all records in the chosen WS segment with an insertion time at or before the LWM and splits them: records also deleted at or before the LWM are discarded outright, since no user query can run as of a time when they existed, and the rest are moved to RS. It creates a new segment RS', reads in blocks from the columns of the old RS segment, drops any RS item whose DRV value is at or below the LWM, merges in the WS column values and writes the result into RS' as it grows; the most recent insertion time in RS' becomes the segment's new tlastmove, always at or below the LWM. Because records receive new storage keys in RS' every join index that points at the segment must be maintained, and only once RS' and its indices are complete does the system cut over from RS to RS' and free the old disk space - an old-master/new-master scheme chosen because essentially every data object moves anyway.

Transactions, commit and recovery

Read-write transactions set read and write locks under strict two-phase locking, implementing a distributed lock table across sites, with deadlock resolved by timeout and abort of one participant. Logging is NO-FORCE and STEAL but only UNDO records are written, and they are logical, as in ARIES, because physical logging over the WS B-trees would produce far too many records; rollback scans that UNDO log backwards. Each transaction has a master that assigns work to sites and decides the outcome; when it receives COMMIT it waits for all workers to finish outstanding actions and then sends commit or abort with no PREPARE phase, so a site can be told to commit and crash before any update or log record reaches stable storage. Recovery handles three cases: a site with no data loss rolls forward updates queued for it elsewhere; a catastrophic loss of both RS and WS is rebuilt from other projections and join indices; and the common case of WS damage with RS intact is repaired by querying remote projections for tuples with insertion_epoch above the local tlastmove and at or below the HWM, whose deletion_epoch is 0 or at or above the LWM, followed by the queued updates.

What the paper showed — measurements and proofs

The benchmark is a simplified TPC-H at scale 10 - lineitem, orders and customer reduced to INTEGER and CHAR(1) columns, 60,000,000 line items totalling 1.8 GB - run on a single 3.0 GHz Pentium under RedHat Linux with 2 GB of memory and 750 GB of disk, against a commercial row store and a commercial column store with locking and logging turned off.
Under a 2.7 GB storage budget, roughly 1.5 times the raw data size, C-Store's five projections occupied 1.987 GB and the column store 2.650 GB, while the row store could not fit at all and was given 4.480 GB; C-Store thus used 40 percent of the row store's space despite being the only system storing redundant copies.
Across the seven queries C-Store was on average 164 times faster than the commercial row store and 21 times faster than the commercial column store in the space-constrained case; the widest gap was Q4, a lineitem-orders join with a MAX aggregate, at 2.09 seconds against 722.90 for the row store and 22.23 for the column store.
When both competitors were additionally given materialized views corresponding to C-Store's projections their times improved but their footprints exploded: the row store grew to 11.900 GB and was still 6.4 times slower on average, and the column store grew to 4.090 GB and was still 16.5 times slower.
Simple aggregation shows the compression effect most sharply: Q1, a COUNT grouped by l_shipdate, ran in 0.03 seconds against 6.80 for the row store and 2.24 for the column store, and Q5 ran in 0.31 seconds against 116.56 for the row store.
The paper decomposes the advantage into four named causes - column representation, storing overlapping projections rather than whole tables, better compression, and operators that run on the compressed representation - and notes that only the first was shared with the competing commercial column store.

Limits and trade-offs — conceded and discovered

The paper concedes the evaluation is incomplete: only the RS storage engine and executor were running, the WS and tuple mover were too early to benchmark and were not integrated, and RS supported neither segments nor multiple grid nodes, so every number is single-site and read-only and the overhead of updates is unmeasured.
The paper concedes join indices are very expensive to store and maintain in the presence of updates, because every modification to a projection requires updating every join index that points into or out of it, and its own mitigation - storing each column in several projections - buys fewer indices with yet more space.
The paper concedes Type 4 columns, foreign-ordered with many distinct values, are simply left unencoded with compression for that case still under investigation, and that operators consuming Type 2 data need one page of memory for each possible value in the column, which constrains the plans the optimizer can choose.
The paper concedes its snapshot isolation is not general time travel: a read-only query must fall between the low and high water marks, epoch numbers have to be wrapped like TCP sequence numbers to stay bounded, and if WS recovery cannot find a remote cover with an early enough tlastmove the tuple mover must additionally log a storage-key remapping for every tuple it moves.
Later work exposed the fragility of join indices in practice: Vertica, the commercial descendant, abandoned them and instead requires every table to carry a super projection containing all of its columns, and the automatic physical design tool the paper promised proved to be a substantial research problem of its own.

What it became — the systems that inherited it

C-Store was commercialized almost immediately as Vertica, and the 2012 VLDB paper on that system reads as a report on which C-Store ideas survived contact with customers: projections with explicit sort orders, K-safety through redundant differently-sorted copies, and the write-optimized store plus read-optimized store split with a tuple mover all shipped, while join indices were dropped in favor of super projections holding every column of a table. The compression work grew into Abadi's line of papers on compression-aware execution and late materialization, and into the 2008 comparison showing that simulating a column store inside a row store recovers only a fraction of the benefit. The idea that operators should consume compressed, block-at-a-time column data converged with MonetDB/X100 and VectorWise into the vectorized execution model now used by DuckDB, ClickHouse, Redshift and Snowflake. The columnar file formats of the Hadoop and lakehouse era - Parquet, ORC, Arrow, Snowflake's micro-partitions, BigQuery's Capacitor - inherit the run-length, dictionary and delta encodings and the immutable, densepacked block layout that C-Store's RS defined. The RS/WS pattern reappears wherever an analytic store must absorb writes: Vertica's ROS and WOS, Druid's real-time versus historical segments, and merge-on-read tables in Hudi and Iceberg. Finally, the epoch-timestamp snapshot mechanism prefigures the snapshot and time-travel semantics that Snowflake, Delta Lake and Iceberg now expose as a user-facing feature.

In the paper’s words — verbatim

“CPUs are getting faster at a much greater rate than disk bandwidth is increasing. Hence, it makes sense to trade CPU cycles, which are abundant, for disk bandwidth, which is not.”

§1

“As will be shown in Section 9, the ability to process compressed data is the key to the performance benefits of C-Store.”

§8.2

“In summary, for this seven query benchmark, C-Store is on average 164 times faster than the commercial row-store and 21 times faster than the commercial column-store in the space-constrained case.”

§9

Vocabulary — as this paper uses it

Projection: A stored, column-wise, sorted materialization anchored on one logical table, containing some of its columns plus any columns reachable through a chain of n:1 foreign-key relationships. C-Store stores only projections and never the base tables from which they are derived.
Sort key: The column or columns a projection is sorted on, applied left to right and written after a vertical bar. It fixes the segment partitioning, determines which encoding each column of the projection can use, and decides which queries that projection is good for.
Segment: A horizontal partition of a projection carrying an identifier Sid greater than zero and covering one key range of the sort key, with the set of ranges partitioning the key space. Segments are the unit of allocation to grid nodes and the unit the tuple mover works on.
Storage key (SK): The identifier tying values in different columns of the same segment to a single logical row. In RS it is the record's ordinal position and is calculated rather than stored; in WS it is an explicitly stored integer larger than any RS storage key.
Join index: A per-segment table of (Sid, storage key) entries mapping each tuple of one projection to the same logical row in another projection anchored at the same table, always a one-to-one mapping. A path of join indices lets C-Store reassemble a full table in some common sort order.
RS and WS: The Read-optimized Store holds the bulk of the data, compressed and admitting only bulk insertion from the tuple mover; the Writeable Store is a small uncompressed B-tree-based column store with the identical logical design that absorbs all inserts and deletes.
Merge-out process (MOP): The tuple mover's LSM-style operation on an (RS, WS) segment pair: take WS records inserted at or before the LWM, discard those already deleted, merge the rest with old RS blocks into a new segment RS', maintain the affected join indices and DRV, then cut over.
K-safety: The configurable property that the loss of any K nodes still leaves a covering set of projections and join indices from which every table can be reconstructed in a common sort order. After a failure C-Store simply continues at K-1 safety until the node is repaired.
Epoch, high water mark, low water mark: Timestamps are coarse epoch numbers handed out by a designated timestamp authority. The HWM is the most recent epoch every site has finished, so read-only queries at or below it see only committed data; the LWM is the earliest epoch they may use, bounding history and WS size.

On the timeline — where this sits in the story

Year2005

MilestoneC-Store and Vertica-style column stores

Problem solvedRow stores wasted I/O for analytical queries that scanned a few columns across many rows.

How it solved itColumnar storage improved compression, column pruning, vectorized scans, and analytical performance.

Why it matteredInfluenced modern cloud warehouses and analytical engines.

DDIACh. 4: Storage & Retrieval

View on the timeline