The Vertica Analytic Database: C-Store 7 Years Later

In one breath — the whole paper, compressed

Vertica is C-Store shipped: the same core bets — projections as the only physical structure, total sort order, aggressive per-column encoding, an in-memory write store drained into immutable read-optimised files, epoch snapshots and K-safe replication — rebuilt from scratch with none of the prototype's code. The paper is unusual because it says out loud which research ideas did not survive: join indices were dropped entirely in favour of a mandatory super projection, the B-tree inside the read store became a lightweight position index because ROS containers are never modified, C-Store's time-window epochs became epochs that advance at commit, and C-Store's random join order became three generations of real optimizer. What survived is defended with measurement: on the same single-core Pentium 4, using C-Store's own queries and test harness, Vertica finishes the seven-query set in 9.6 s against C-Store's 18.7 s and uses 949 MB of disk against 1,987 MB — despite adding data types, NULLs, updates, ACID transactions and a query optimizer the prototype never paid for. At publication there were over 500 production deployments, at least three substantially over a petabyte.

Before this paper — the world it landed in

By 2005 the one-size-fits-all row store had been stretched past breaking for analytics: tables had grown to billions of rows, and an engine tuned for thousands of single-row transactions per second spent most of its I/O reading columns no query asked for. C-Store argued that a purpose-built column store could beat those systems by orders of magnitude, and Stonebraker's One Size Fits All made the same case polemically. But C-Store was a research prototype: INTEGER only, no NULLs, no updates, single-threaded, an optimizer that picked join order at random, and a storage allocator for assigning segments to nodes that was described but never built. The real question — the one Vertica's investors asked — was whether the prototype's numbers would survive the addition of everything a shipping product needs. Meanwhile the NoSQL wave was arguing that SQL itself was the problem.

The problem — what was actually breaking

Legacy relational systems were designed for transactional workloads on hardware from forty years earlier, so they cannot serve analytic workloads where tens of transactions per second each touch a significant fraction of a table.
Linear scale-out rules out shared disk or network-attached storage, which becomes a bottleneck almost immediately, and forces the storage layout, optimizer and execution engine to avoid saturating the interconnect.
Analytic systems must ingest rows at enormous rates, because a fast query engine is useless if loading takes days, and bulk load must not stop or unduly slow concurrent queries.
Every operation has to be online: a production cluster cannot suspend queries for storage maintenance, recovery, rebalancing or backup.
C-Store left major pieces unbuilt or unproven — the segment-to-node storage allocator, a real query optimizer, and join indices whose true cost in a distributed engine had never been measured.
Customers will not pay for heroic tuning or for performance that varies unpredictably, so physical design, storage layout and encoding choices have to be automated.

Core ideas — the contributions, and why they work

Projections as the only physical structure

A Vertica table has no heap and no secondary indexes: its data exists solely as projections, each a subset of the table's columns held in a total sort order of its own choosing. Projections resemble materialised views but deliberately exclude aggregation, filtering and general joins, because the paper reports that maintaining such views is impractical in a real distributed system. Total sortedness is what makes the rest work: encodings such as RLE become far more effective than over unsorted data, and the optimizer can rely on order for merge joins, stream aggregation and sort elimination. In practice most customers keep one super projection plus zero to three narrow ones — the engine is fast enough that you do not need a projection per predicate.

Join indices dropped, super projections required

C-Store reconstructed whole tuples from disjoint partial projections using a join index. Vertica does not implement join indices at all, and instead requires every table to have at least one super projection containing all of its columns. The stated reasons are operational rather than theoretical: join indices were complex to implement, reconstructing tuples across nodes during distributed execution was very expensive, and storing explicit row ids consumed significant disk on large tables. Because columnar compression makes a full super projection cheap to store, the trade collapsed in favour of redundancy, and the authors say they have no plans to lift the requirement.

Segmentation for the cluster, partitioning for pruning

Vertica splits what C-Store called horizontal partitioning into two distinct mechanisms. Segmentation is inter-node: each projection declares SEGMENTED BY an integral expression, usually a hash of a high-cardinality key, and nodes own contiguous ranges of the 2^64 value space in a ring, giving a deterministic value-to-node map that enables fully local distributed joins and high-cardinality distinct aggregation. Partitioning is intra-node: PARTITION BY at the table level guarantees each ROS container holds a single partition value, turning bulk deletion of a month into file deletion and sharpening min/max container pruning. C-Store's intra-node partitioning for parallelism was dropped entirely, because the execution engine gets intra-node parallelism by dividing each on-disk structure into logical regions at runtime instead.

Encoding over sorted data, executed encoded

Every column of every projection carries its own encoding — Auto, RLE, Delta Value, Block Dictionary, Compressed Delta Range or Compressed Common Delta — and the same column may be encoded differently in each projection it appears in. The set differs from C-Store's, and the paper argues the same schemes pay off far more here precisely because storage is totally sorted: RLE over a sorted low-cardinality column collapses millions of rows into a handful of pairs. Critically, scans, joins and low-level aggregates operate directly on encoded data rather than decoding first, which the authors admit cost real implementation complexity but is where the speed comes from. Encodings are chosen by empirical experiment in the Database Designer, not by rule of thumb.

WOS, ROS and a strata-bounded tuple mover

Small writes land in an in-memory, uncompressed Write Optimised Store; the read side is a set of immutable ROS containers on an ordinary filesystem. The tuple mover performs moveout (WOS to ROS) and mergeout (small containers into larger ones), and must be neither overzealous, which creates too many tiny containers, nor lazy, which overflows the WOS and also creates tiny containers. Unlike C-Store, it never intermixes WOS and ROS data in a merge, so that a tuple taking part in a mergeout is read from disk once and written once. Containers are quantised into exponentially sized strata capped at 2 TB, which bounds the number of times any tuple is ever rewritten — the same argument that governs LSM compaction.

Epochs as the log

Every tuple is stamped with the epoch in which it committed, as an implicit 64-bit column, and every delete marker with the epoch of its deletion; all nodes agree on the commit epoch, so an epoch boundary is a globally consistent snapshot. Because storage is never modified in place, a query reading the recent past takes no locks at all, which is what lets bulk loads and long analytic scans run concurrently. The consequence is structural: Vertica needs no transaction log, since data plus epoch is the history, and a returning node simply replays the DML it missed from a buddy projection. C-Store's time-window epochs were abandoned because READ COMMITTED users were confused when their own commits were not yet visible; the epoch now advances at commit for DML, which also simplified the tuple mover.

Automatic physical design that calls the optimizer

The Database Designer chooses projections for a workload in two sequential phases. The query-optimization phase enumerates candidate sort orders and segmentations from predicates, group-by, order-by, aggregate and join columns, then invokes the actual query optimizer on each input query with those candidates and reads the resulting plans to pick winners — so the tool cannot drift from the optimizer's cost model as that model evolves. The storage-optimization phase then picks encodings by empirically compressing sample data under the chosen sort orders. The reported outcome is the argument for the design: expert users occasionally hand-adjust segmentation or sort order on their biggest tables, but it is extremely rare for anyone to override the encoding choices, which were measured rather than guessed.

How it works — the mechanism, concretely

ROS container layout and the position index

A ROS container holds complete tuples in the projection's sort order, written as two files per column: the encoded column data, and a position index roughly one thousandth its size. A row's identity inside a container is its position, its ordinal offset in the file, which is implicit and never stored; tuple reconstruction means fetching the same position from each column file. The position index stores per-block metadata including start position, minimum and maximum value, and the min/max lets the planner prune whole containers that cannot satisfy a predicate. Unlike C-Store, there is no B-tree here, because ROS containers are never modified once written; a rarely used hybrid mode can group several columns into one file, at a performance and compression penalty.

Moveout, mergeout and exponential strata

As the WOS fills, moveout asynchronously writes its contents into new ROS containers; if the WOS saturates before moveout finishes, subsequent loads bypass it and go straight to new containers. Mergeout quantises existing containers into exponentially sized strata by file size and plans each merge so its output lands at least one stratum above every input, which is what bounds re-merging. Mergeout is also where space is reclaimed: rows deleted before the Ancient History Mark are elided from the output, since no query can ever reach them again. Merges preserve partition and local-segment boundaries and are deliberately not coordinated across the cluster, so two nodes holding identical tuples routinely have different container layouts.

Deletes as vectors, updates as delete plus insert

Data is never modified in place. A delete produces a delete vector — a list of positions of deleted rows — written first to an in-memory DVWOS and later moved by the tuple mover into compressed DVROS containers, stored in the same format as user data. There may be several delete vectors for the WOS and several for any given ROS container, and every scan must apply them. SQL UPDATE is implemented as a delete of the old row plus an insert of the new values, which is why marking rows deleted is slower than dropping a partition's files, and why deletes temporarily increase storage and degrade queries until the next mergeout.

Commit without two-phase commit

A distributed agreement and group membership protocol carries control messages by broadcast and point-to-point delivery; a node that fails to receive one is ejected and the survivors are informed. Like C-Store, Vertica does not use two-phase commit: once the cluster commit message is sent, each node either completes the commit or leaves the cluster, and the transaction commits if a quorum succeeds. Rollback is just discarding the ROS containers and WOS data the transaction created; nodes that fell out during commit rejoin through recovery. Queries default to READ COMMITTED against the current epoch minus one, and a seven-mode table lock matrix (S, I, SI, X, T, U, O) governs writers — notably the Insert lock is compatible with itself, so many bulk loads run at once while still offering transactional semantics.

K-safety, buddy projections and two-phase recovery

Fault tolerance reuses the projection mechanism: each projection must have at least one buddy with the same columns and a segmentation guaranteeing no row lands on the same node in both, and K-safety means K+1 copies of every segment on distinct nodes. A rejoining node first truncates everything inserted after its Last Good Epoch — the epoch through which its data actually reached ROS, tracked per projection because WOS-only data is lost on failure — then recovers in two phases: a historical phase that copies from the LGE up to some earlier epoch Eh while holding no locks, and a current phase that takes a Shared lock and copies the small remainder. If buddy sort orders match, whole ROS containers and delete vectors are copied verbatim; otherwise an INSERT ... SELECT style plan moves the rows, including deleted ones, with a separate plan for delete vectors. Refresh, rebalance and hard-link-based backup reuse the same historical/current structure, and all of them run online.

Execution engine: vectorised, pipelined, adaptive

Plans are operator trees — Scan, GroupBy, Join, ExprEval, Sort, Analytic, Send/Recv — driven by pull requests from downstream, vectorised so operators exchange blocks of rows, and multithreaded, with a StorageUnion dispatching threads over non-overlapping regions of ROS containers and resegmenting locally so parallel GroupBys can compute complete groups. Sideways Information Passing builds filters during planning and places them in the Scan, which consults the join's hash table at runtime and drops outer rows that cannot match before they enter the pipeline. The engine adapts while running: a hash join whose table will not fit memory becomes a sort-merge join, and cheap L1-cache-sized prepass aggregations are abandoned if they stop reducing row counts. Memory is budgeted per operator at compile time under a workload policy, plans are cut into zones that cannot run concurrently so downstream operators reclaim upstream memory, every operator can externalise to disk, and type-specific expression evaluation is JIT-compiled to remove branching.

Three generations of query optimizer

C-Store's optimizer took the first projections it reached and ordered joins at random. StarOpt, the first Vertica optimizer, was Kimball-style: it assumed a star or snowflake schema, joined the fact table to its most selective dimensions first, and required co-located projections, meaning every joined projection had to be replicated everywhere or segmented on the same range of the join key. StarifiedOpt rewrote non-star queries so they looked like stars and could be fed to the StarOpt algorithm — a bridge the authors say worked far better than they had any right to expect. V2Opt, the current one, is distribution-aware and built as extensible modules: it classifies physical properties (column selectivity, sort order, segmentation, prejoin and constraint availability), prunes with a cost model pricing compression-aware I/O, CPU and network transfer, and enumerates bushy plans with data movement permitted. When nodes go down the optimizer replans, re-costing against buddy projections, which can produce an entirely different join order.

What the paper showed — measurements and proofs

On identical single-node Pentium 4 hardware, running the C-Store paper's own queries and test harness, Vertica's total query time is 9.6 s against C-Store's 18.7 s, and its disk footprint is 949 MB against 1,987 MB (Table 3) — roughly twice as fast on a single core.
The per-query gains are very uneven: Q7 falls from 2,540 ms to 161 ms and Q4 from 2,090 ms to 280 ms, while Q3 barely moves (4,900 ms to 4,833 ms), and all of this is despite Vertica adding FLOAT and VARCHAR types, NULL handling, updates and deletes, multiple ROS and WOS stores, ACID transactions, optimization and 64-bit integers that C-Store never paid for.
One million random integers between 1 and 10 million take 7.5 MB as text; gzip yields 3.6 MB (2.1x), sorting before gzip yields 2.3 MB (3.3x), and Vertica stores them in 0.6 MB — 12.5x, or 0.6 bytes per row (Table 4).
On 200 million real customer meter readings (metric, meter, collection timestamp, float value), 6,200 MB of CSV gzips to 1,050 MB (5.9x) but stores in Vertica in 418 MB (14.8x, about 2.2 bytes per row); sorting on metric, meter and time lets RLE reduce the metric column to 5 KB and the meter column to 35 MB, timestamps to 20 MB, leaving 363 MB in the float values.
Several guarantees are structural rather than measured: the position index is about 1/1000 the size of the raw column data, ROS containers are capped at 2 TB so the exponential strata bound how many times a tuple is rewritten, and a tuple participating in a mergeout is read from disk once and written once.
Deployment evidence stands in for a cluster benchmark: over 500 production deployments at the time of writing, at least three substantially over a petabyte, and the authors explicitly decline to compare a modern multicore cluster against C-Store because the prototype is single-threaded and the comparison would be unfair.

Limits and trade-offs — conceded and discovered

Conceded: the super projection requirement means every column is stored in full at least once per table, and again in every buddy projection, so K-safety multiplies the base footprint — the paper accepts this because compression makes it cheap and states there are no plans to lift the requirement.
Conceded: two shipped features are nearly dead in practice. Prejoin projections are used far less than expected because the engine's hash and merge joins already handle small dimension tables well and customers will not slow their loads to precompute joins, and the hybrid row-column file mode is very rarely used because of its performance and compression penalty.
Conceded: special-case optimizations (transitive predicates for inner but not outer joins, filters for hash but not merge joins) caused almost as many problems as they solved, because users would not accept unpredictable performance; resource management is admitted to have been under-appreciated early and is called an understudied problem in academic research.
Conceded: availability has hard edges — losing K+1 nodes may shut the database down, losing N/2 nodes forces a safety shutdown to avoid split brain, and the Ancient History Mark normally stops advancing while a node is down, so history that would otherwise be purged accumulates for the whole outage.
Exposed later: the only head-to-head measurement is a single-core Pentium 4 run of 2005-vintage queries, with no cluster scaling, concurrency or ingest-rate numbers reported at all; and the tightly coupled shared-nothing design with node-local storage was later displaced by separated storage and compute (Snowflake, Redshift RA3, and Vertica's own Eon mode).

What it became — the systems that inherited it

Vertica is the bridge between C-Store's prototype and the modern analytic stack, and much of what it settled is now invisible default practice. Per-block minimum and maximum metadata for pruning containers became zone maps in Amazon Redshift and min/max statistics per row group and stripe in Apache Parquet and ORC; immutable data files plus positional delete vectors are exactly the mechanism Apache Iceberg v2 and Delta Lake later adopted, under the same name; and mergeout's exponentially sized strata are the same bounded-rewrite argument that governs ClickHouse's MergeTree and LSM compaction generally. Vectorised execution directly over encoded data, paired with a compression-aware cost model, reappears in DuckDB, ClickHouse, StarRocks and Apache DataFusion, a project this paper's lead author Andrew Lamb went on to help lead. Snowflake and BigQuery inherited the columnar, heavily encoded, no-indexes-just-sorted-storage worldview while replacing node-local disks with object storage, a split Vertica itself later adopted as Eon mode. Its most durable contribution may be negative: an explicit, reasoned record of which research ideas — join indices, B-trees inside the read store, time-window epochs, WOS/ROS intermixing, random join orders — did not survive contact with customers, and why.

In the paper’s words — verbatim

“In practice and experiments with early prototypes, we found that the costs of using join indices far outweighed their benefits.”

§3.2

“Vertica has no need of traditional transaction logs because the data+epoch itself serves as a log of past system activity.”

§5.2

“To our surprise, such special case optimizations caused almost as many problems as they solved because certain user queries would go super fast and some would not in hard to predict ways, often due to some incredibly low level implementation detail.”

§7

Vocabulary — as this paper uses it

Projection: A sorted materialisation of a subset of a table's columns, and the only physical data structure Vertica has. A table's data lives exclusively in its projections, each with its own sort order, encodings and segmentation.
Super projection: A projection containing every column of its anchoring table. Vertica requires at least one per table, precisely because it dropped C-Store's join indices and must be able to reconstruct whole tuples inside a single projection.
Segmentation: The inter-node assignment of tuples to machines, declared per projection as SEGMENTED BY an integral expression whose 2^64 value space is split into ring ranges owned by nodes. It gives a deterministic value-to-node mapping, which is what makes local joins and distributed distinct aggregation possible.
Partitioning: Intra-node physical separation, declared per table with PARTITION BY, ensuring all tuples in a ROS container share one value of the partition expression. Its purposes are instant bulk deletion by removing files and sharper min/max container pruning.
ROS container: An immutable unit of on-disk storage holding complete tuples in the projection's sort order, with two files per column: the encoded data, and a position index of per-block start position, minimum and maximum value.
WOS (Write Optimised Store): An entirely in-memory, unencoded and uncompressed buffer that absorbs small inserts, deletes and updates so that writes to disk are large enough to amortise their cost. It is segmented like the projection it belongs to, but its contents are lost on node failure until moveout completes.
Tuple mover: The background service that performs moveout, asynchronously draining the WOS into ROS containers, and mergeout, merging small ROS containers into larger ones within exponentially sized strata while purging rows deleted before the Ancient History Mark.
Epoch, LGE and AHM: An epoch is the logical commit timestamp carried by every tuple and delete marker, so an epoch boundary is a cluster-wide consistent snapshot. The Last Good Epoch is the epoch through which a projection's data has actually reached the ROS, and the Ancient History Mark is the point before which no query can see history, so deleted rows may be purged.
K-safety and buddy projection: K-safety is the guarantee that the cluster stays available with K or fewer nodes down, achieved by placing K+1 copies of each segment on different nodes. A buddy projection is the replica projection with the same columns whose segmentation guarantees that no row is stored on the same node by both.

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