Column stores: from C-Store to modern analytical databases

The question

A data warehouse spends most of its time scanning large tables to answer questions like revenue by region over a year. Those queries touch many rows but only a few columns. A layout built for updating one record at a time keeps each record's fields together, so a broad scan pulls every field of every row through memory whether the query needs it or not.

Storing each column on its own fixes that in principle. The question the talk followed is why a new storage layout was not enough on its own, and why the rest of the engine had to change with it.

One table, two layouts

I used one small table for the whole talk, so that every later execution step could be checked against the same answer.

A row store lays this out as East, 40, A, then West, 70, B, and so on. A column store keeps three sequences: all the regions, all the amounts, all the notes. For the query

SELECT SUM(amount)
FROM Sales
WHERE region = 'East';

the column layout reads the region and amount sequences and never touches the notes. East is at positions 1 and 3, the amounts there are 40 and 20, and the answer is 60.

The same arithmetic on a wider table is where the intuition comes from. With 100 columns of equal width and a query that uses 3, a column scan can leave 97 unread and touch 3% of the values. That is an opportunity, not a 33-times speedup. The query still has to filter, join, aggregate and decompress, and a row store can avoid a full scan with a covering index or a materialized view. Whether the opportunity turns into speed is what the three papers test.

C-Store: a design built for reading

C-Store keeps SQL over logical tables and changes everything below that interface. Instead of base tables plus indexes, it stores projections: groups of columns from a table, each group sorted on its own key, with a column allowed to appear in several projections. Sorting a sales projection by region puts the East rows together and turns the region column into long runs of one value, which compress well. A second projection sorted by date can serve a different workload.

The redundant orderings have a cost. Inside one projection the columns share a row order, so position 1 of the region column and position 1 of the amount column are the same sale. Across two projections sorted differently that stops being true, and C-Store needs join indexes to map one order onto the other. The choice of projections therefore changes the cost of every later step in a plan.

Updates go to a small writeable store, and a tuple mover merges them in batches into the large read-optimized store. One point is easy to get wrong: in the 2005 design the writeable store is also column-oriented. It differs from the read store in representation (uncompressed values, B-trees that keep logical order), not in orientation. Read-only transactions see a consistent snapshot through epochs and a high-water mark, and K-safety places redundant projections so the data survives K node failures.

What the first experiment shows

The evaluation is narrower than the design. It runs seven simplified TPC-H-style queries on one machine, read-only, against the implemented read-store executor. The writeable store and the tuple mover were early implementations outside the measured configuration, and so was the distributed design.

Giving the row store comparable materialized views closes most of the gap. On Q4 it falls from 722.90 to 21.76 seconds against C-Store's 2.09, while using more storage. The remaining gap is real, but two engines with different tuning, access structures and executors cannot tell you how much of it the column layout causes. That attribution problem is what the 2008 paper takes on.

How different are row stores and column stores?

Abadi, Madden and Hachem ran two complementary experiments on the Star Schema Benchmark: 13 queries at scale factor 10, with a 60-million-row fact table. The first holds a commercial row store, System X, fixed and changes its physical design to imitate a column store. The second holds C-Store fixed and switches its execution features off.

Imitating columns inside a row store

• Vertical partitioning: one narrow table per column with a position attribute. The engine still carries a tuple header per value and has to join the partitions back together.
• An index on every column, so plans can avoid the base table. They still scan and combine lists of record identifiers.
• Materialized views for each query flight. These perform best of the three, and they assume the workload is known in advance.

Averaged over the 13 queries, the conventional row-store configuration takes 25.7 seconds, the row store with materialized views 10.2, and C-Store 4.0. These are still differently built systems, so the bars establish that a gap exists without saying what causes it.

Switching features off inside C-Store

The second experiment is the more informative one. It names four execution features and removes them in combination:

• Block processing: an operator hands its parent a block of values per call rather than one tuple, which spreads the call overhead. This is not the same thing as SIMD, and a row store can batch work too.
• Invisible joins for a star schema: filter each dimension down to a set of keys, probe the fact table's foreign-key columns with them, intersect the qualifying positions, and only then fetch the values needed for grouping and output.
• Compression, with operators working on the encoded data where they can.
• Late materialization: evaluate predicates column by column while carrying positions, and build tuples only for the rows that survive. In the running example, only positions 1 and 3 ever need an amount.

With every feature on, C-Store averages 4.0 seconds. Removing the invisible join takes it to 7.5, removing compression as well to 14.7, and switching off all four to 41.0. That last figure is slower than System X's conventional configuration at 25.7. The comparison crosses engines and carries the caveat from before, but the direction is clear: the column layout without the engine built around it does not produce the result.

In the talk I showed four of these bars, and the jump from ticL to Ticl changes two features at once. The full set separates them. Switching to tuple-at-a-time moves 14.7 to 16.0, and then removing late materialization alone moves 16.0 to 41.0. Across the paper's experiments compression and late materialization matter most.

These ratios are conditional effects. The gain from block processing depends on whether compression is still on and whether the system is limited by CPU or by I/O at that point. Multiplying the factors together as though the features were independent overstates what any one of them does.

Compression as part of execution

Compression is usually presented as a storage trade: fewer bytes, paid for with CPU time to decode them. The 2006 paper asks whether an operator can use the encoded form directly and skip work it would otherwise do. On the five values East, East, East, West, West the three families look like this:

Run-length encoding shows the idea most clearly. A run of the value 7 repeated 1,000 times sums to 7 × 1,000 = 7,000 without expanding the run, and its count is the run length. If a predicate selects only the last 200 positions, the operator has to use the overlap, 200, and the usual SQL details (nulls, numeric types, overflow, group boundaries) still apply.

To avoid writing one version of every operator for every encoding, the paper gives compressed blocks a common interface. An operator asks a block about properties it can exploit: whether it holds a single value, whether its values are sorted, whether its positions are contiguous. When it cannot exploit them, it decodes through getNext() or asArray().

The best encoding depends on the data's order

Run-length encoding is the worst choice on data without runs and the best once repeated values sit together, so locality matters separately from the number of distinct values. The paper ends with a decision tree over run length, domain size, locality and how the query accesses positions. Its thresholds come from one machine and one aggregation workload, so I presented the tree as a summary of the experiments rather than a rule.

Two traps came up in preparing the questions. Dictionary codes support equality once the constant is translated into the same dictionary, but not less-than unless the dictionary preserves order. And two columns with separate dictionaries cannot be joined on their raw codes; the join needs a shared dictionary, recoding or decoding, and the paper charges that cost in its join experiment.

Where the ideas went

Vertica is the direct commercial line. Its 2012 paper describes a new implementation that kept projections, sort orders and compression, dropped join indexes, and required a superprojection holding every column of a table, because reconstructing tuples across projections proved too expensive. The other systems in the talk use related mechanisms; I made no claim that they share code or lineage.

• Snowflake keeps per-column metadata, including value ranges, for each micro-partition (roughly 50 to 500 MB before compression) and skips the partitions a filter cannot match.
• DuckDB queries Parquet files in place, reading only the columns a query needs and using row-group statistics to skip parts of a file.
• ClickHouse added lazy materialization in 2025: for a top-N query it reads large text columns only for the rows that survive. In the developers' test on about 151 million reviews with a cold cache, a top-3 query went from 61.148 seconds and 16.28 GB read to 0.181 seconds and 807.55 MB. That is a developer-reported result on a workload that favours the technique, and I did not reproduce it.
• GaussDB (Zeyl et al., PVLDB 2026) keeps a row store for transactions and an in-memory column view for analytics. On TPC-H at 7.5 TB, lightweight compression cut the memory needed from about 10 TB to 4 TB with a negligible change in query latency. Its 30 TB performance comparison combines many changes and was unaudited at publication, so it cannot isolate what compression contributes.

Where I would push back

The 2005 numbers describe a read-store executor

The paper describes a distributed, updatable, K-safe system and measures a single-site, read-only executor. The results show that the read-side techniques work under the tested conditions. They do not measure the cost of keeping redundant projections current or of making recent writes visible to queries, which is where a design built for reading pays.

Comparisons across systems cannot assign causes

The headline bars of both the 2005 and 2008 papers compare engines that differ in implementation, configuration and access paths. The 2008 paper earns its reputation by adding the experiment inside C-Store, and that experiment, rather than the ratio between systems, is the evidence about mechanisms.

The effects do not multiply

Each feature's benefit depends on which others are still active and which bottleneck dominates. A factor measured with compression on does not carry over to a configuration with compression off.

The magnitudes belong to older hardware

Cache sizes, memory bandwidth and the balance between CPU and I/O have all moved since 2006, and the decision tree's thresholds come from one machine. The mechanisms carry forward. The numbers need fresh measurements before anyone quotes them about a current system.

The case is about a workload

All three papers evaluate read-heavy analytical queries. Point lookups and frequent updates can favour other designs, and a row store with covering indexes is fast at selective retrieval. Related work such as PAX, which reorganizes data inside each page, and MonetDB/X100, which focuses on CPU-efficient execution, helps separate the storage choice from the execution choice.

Questions I put to the room

• When can early materialization be cheaper than late materialization?
• Which physical properties belong in a planner's search state?
• What would you measure before trusting a reported speedup?

Slides

The deck has 40 slides with full speaker notes: per-slide timings, backup numbers for every chart, and answers to the questions I expected.

Download slides (PPTX, 0.7 MB)

References

1. Mike Stonebraker, Daniel J. Abadi, Adam Batkin, et al. C-Store: A Column-oriented DBMS. In Proceedings of VLDB, pages 553-564, 2005. PDF at vldb.org
2. Daniel J. Abadi, Samuel R. Madden, and Nabil Hachem. Column-Stores vs. Row-Stores: How Different Are They Really? In Proceedings of SIGMOD, pages 967-980, 2008. doi:10.1145/1376616.1376712
3. Daniel J. Abadi, Samuel R. Madden, and Miguel C. Ferreira. Integrating Compression and Execution in Column-Oriented Database Systems. In Proceedings of SIGMOD, pages 671-682, 2006. doi:10.1145/1142473.1142548
4. Andrew Lamb, Matt Fuller, Ramakrishna Varadarajan, Nga Tran, Ben Vandiver, Lyric Doshi, and Chuck Bear. The Vertica Analytic Database: C-Store 7 Years Later. PVLDB 5(12), pages 1790-1801, 2012. doi:10.14778/2367502.2367518
5. Tim Zeyl, Jason Lam, Shu Lin, et al. No Silver Bullet: Boosting GaussDB Performance on the 30TB TPC-H Workload. PVLDB 19(12), pages 4036-4048, 2026. doi:10.14778/3827998.3828014
6. Tom Schreiber. ClickHouse gets lazier (and faster): Introducing lazy materialization. ClickHouse blog, 22 April 2025. clickhouse.com
7. Snowflake documentation, Micro-partitions and data clustering. docs.snowflake.comChecked 20 September 2026.
8. DuckDB documentation, Reading and writing Parquet files. duckdb.orgChecked 20 September 2026.

The chart on this page is drawn from the values reported in Figure 7(b) of Abadi, Madden and Hachem (2008) rather than reproduced from the paper, and the tables quote numbers from the papers as cited. The sales table is a teaching example, not benchmark data. The slides include three figures from the cited papers, credited on the slides.