vault

Columnar Analytical Databases

15 min read

Columnar Analytical Databases

A columnar (column-oriented) analytical database physically stores each column of a table as its own contiguous run of values on disk, rather than storing whole rows together — and it builds its entire execution engine around that layout. Because analytical queries typically touch a handful of columns but scan billions of rows (SELECT region, SUM(revenue) ... GROUP BY region), reading only the needed columns collapses I/O, and storing a column’s values adjacently makes them extraordinarily compressible and amenable to batch/SIMD processing. The design lineage runs from the academic C-Store prototype (Stonebraker, Abadi, Madden et al., VLDB 2005) — “a read-optimized relational DBMS that contrasts sharply with most current systems, which are write-optimized” — through its commercial descendant Vertica, to today’s open engines ClickHouse and DuckDB and the open file formats Apache Parquet and ORC that underpin the modern data lakehouse. This note is about the systems built on the layout; the layout itself and the row-vs-column trade-off is covered in Row-Oriented versus Column-Oriented Storage.

Columnar ≠ Wide-Column — do not conflate them

“Columnar” (this note: ClickHouse, DuckDB, Parquet, Vertica) is a physical on-disk layout — each column is written as a separate stream of values. “Wide-column” ( HBase) is a data model — a sparse row-key indexed map with column families, whose bytes are stored row-by-row within a partition in LSM SSTables. Cassandra is not a column-store despite the name “column family”: it does not lay each column out contiguously and it is optimized for row/partition point access, not full-column scans. The two ideas share the word “column” and nothing else. This confusion is the single most common error in database writing — see the mirror-image callout in the wide-column note.

Mental Model — Rotate the Table Ninety Degrees

The whole field falls out of one picture: a table is a two-dimensional grid, and you can serialize it to a one-dimensional disk either row-major (all of row 1’s fields, then all of row 2’s) or column-major (all of column A’s values, then all of column B’s). A row-store answers “give me everything about customer 42” in one seek; a column-store answers “give me the average of the revenue column over 100 million rows” by streaming exactly one column and ignoring the rest.

flowchart LR
  subgraph ROW["Row store — good for OLTP point access"]
    R["Page: (1,Ann,US,90) (2,Bob,UK,80) (3,Cy,US,70)<br/>one row's fields are adjacent"]
  end
  subgraph COL["Column store — good for OLAP scan+aggregate"]
    C1["id file: 1,2,3,..."]
    C2["name file: Ann,Bob,Cy,..."]
    C3["country file: US,UK,US,... (RLE/dict)"]
    C4["revenue file: 90,80,70,... (bit-pack/FoR)"]
  end
  Q["SELECT country, SUM(revenue) GROUP BY country"] -->|"reads 2 of 4 columns"| COL
  Q -.->|"must read ALL columns of every row"| ROW

What it shows: the same table serialized two ways. Insight to take: a scan-and-aggregate query in a column-store reads only the country and revenue streams — half the I/O here, and often a tiny fraction on a wide fact table with hundreds of columns — while a row-store drags every unused field through the memory hierarchy. Adjacency also means the country column is a long run of a few repeated strings (compresses to almost nothing) and revenue is a dense array of fixed-width integers (SIMD-friendly). The column layout is simultaneously an I/O win, a compression win, and a CPU win — which is why it dominates analytics.

The C-Store Blueprint — Where the Ideas Come From

C-Store crystallized the modern column-store playbook. Its authors observed that “most major DBMS vendors implement record-oriented storage systems, where the attributes of a record (or tuple) are placed contiguously in storage… we call a DBMS with a row store architecture a write-optimized system,” ideal for OLTP, whereas “systems oriented toward ad-hoc querying of large amounts of data should be read-optimized” (Stonebraker et al. 2005). The key economic insight was that CPU speed was outrunning disk bandwidth, so it pays to “trade CPU cycles, which are abundant, for disk bandwidth, which is not” — spend compute to decompress and pack data tightly so that fewer bytes cross the slow disk boundary. Crucially, C-Store insisted the executor “operate on the compressed representation whenever possible to avoid the cost of decompression, at least until values need to be presented to an application.”

C-Store’s structural ideas, several of which recur in modern engines:

  • Projections, not tables. C-Store does not physically store the logical table; it stores overlapping projections — groups of columns sorted on some attribute(s). “The same column may exist in multiple projections, possibly sorted on a different attribute in each.” Different sort orders let the optimizer pick the projection whose ordering best serves a query. Modern engines echo this with sort keys (ClickHouse ORDER BY) and materialized/ordered projections.
  • A write store and a read store bridged by a tuple mover. Because columnar, sorted, compressed data is expensive to update in place, C-Store split storage into a small Writeable Store (WS) absorbing inserts/updates and a large Read-optimized Store (RS), with a tuple mover batching records from WS to RS “in an efficient manner reminiscent of merge sort” — explicitly “a variant of the LSM-tree concept.” This write-buffer-then-merge pattern is exactly how ClickHouse’s MergeTree and every modern column-store handle ingestion (see below).
  • Updates as insert + delete, reads as snapshots. C-Store implemented updates as an insert plus a delete and ran read-only queries in “historical mode” against a timestamp T, giving snapshot isolation “to avoid 2PC and locking for queries.” Analytical stores overwhelmingly favor multiversion/snapshot reads over lock-based concurrency.
  • Heavy compression and bitmap indexes to complement B-trees, and K-safety (redundant projections in different sort orders) for high availability.

Vertica is the commercial descendant of C-Store (both led by Michael Stonebraker) and carried these ideas — projections, WOS/ROS write-then-merge, aggressive encoding — into production data warehousing.

Uncertain

Verify: the claim that Vertica is the direct commercial descendant of the C-Store prototype and preserved projections/WOS-ROS. Reason: I relied on the C-Store paper (which describes the prototype, not Vertica) plus general knowledge; I did not fetch a primary Vertica source in this pass. To resolve: cite a primary Vertica architecture paper (e.g. Lamb et al., “The Vertica Analytic Database,” VLDB 2012). uncertain

The Four Engine-Level Optimizations

Storing columns separately is necessary but not sufficient; a naïve column-store that immediately stitches columns back into rows and runs row-at-a-time operators throws away most of the benefit. Abadi, Madden & Hachem’s “Column-Stores vs. Row-Stores: How Different Are They Really?” (SIGMOD 2008) isolated the four techniques that actually deliver column-store performance. (The primary PDF was not directly extractable in this pass; the mechanisms below are drawn from an accessible faithful summary of the paper, Emani’s CS632 seminar, and cross-checked against the vendor docs cited elsewhere here.)

1. Late materialization. A “tuple” — a reconstructed row — should be assembled as late as possible, ideally never for columns that get filtered away. For SELECT a FROM t WHERE b = X AND c = Y, a late-materialized plan reads the b column and produces a bitmap/position-list of rows passing b = X, reads c and produces the positions passing c = Y, bitwise-ANDs the two position lists, and only then fetches the surviving positions from column a. Column a is touched only for rows that survive both predicates. Early materialization — stitch rows first, filter later — would drag every column of every row through the operators. Late materialization also keeps data in compressed, cache-friendly form for longer.

2. Block iteration (vectorized processing). Row-at-a-time execution (the classic iterator model) pays one or more function calls per tuple just to fetch the next value — interpretation overhead that dwarfs the actual arithmetic. Column-stores instead pass blocks/vectors of thousands of values through each operator in a single call. Because a column is a run of fixed-width values, the inner loop is a tight array loop the compiler can auto-vectorize into SIMD instructions. This is the MonetDB/X100 (VectorWise) insight and the execution model of DuckDB and ClickHouse: “a large batch of values (a ‘vector’) are processed in one operation” (DuckDB).

3. Compression, and operating on compressed data. Adjacent values in a column are the same type and often highly repetitive, so lightweight schemes shrink them dramatically (details below). The deeper win is that many operators run directly on the compressed form — counting a run-length-encoded run without expanding it, comparing dictionary codes instead of strings — so compression saves CPU as well as I/O.

4. Invisible join. Star-schema queries join a huge fact table to several small dimension tables, filter on dimension attributes, and aggregate. The invisible join rewrites each dimension join as a predicate on the fact table’s foreign-key column, executed in three phases: (1) apply each dimension’s predicate to get its set of satisfying keys and hash them; (2) probe each fact-table foreign-key column against its hash to build a per-dimension bitmap, then AND the bitmaps to find fact rows satisfying all joins; (3) use the surviving foreign keys to look up the needed dimension values. Values are extracted only for rows that survive the whole predicate conjunction, and when dimension keys are contiguous the hash probe degenerates into a fast array index (or a “between” range check). It is “invisible” because the joins never materialize as classic row-pipelined joins.

Compression Encodings — the Column-Store Toolkit

The economics of the whole design rest on encodings that exploit columnar homogeneity. The Apache Parquet spec’s encoding list is a good concrete catalog, because Parquet is the open lingua franca of columnar storage:

  • Dictionary encoding (RLE_DICTIONARY): build a dictionary of the column’s distinct values, replace each value with a small integer code. Ideal for low-cardinality columns (country, status, category). Parquet falls back to plain encoding if the dictionary grows too large. Predicates can run on the codes.
  • Run-length encoding (RLE) + bit-packing hybrid: store a repeated value once with a count; store non-repeating dictionary codes bit-packed at the minimum bit width. Superb for sorted or low-entropy columns. Parquet uses this hybrid for booleans, dictionary indices, and the definition/repetition levels of nested data.
  • Bit-packing: if a column’s values fit in k bits, pack N values into N·k bits instead of N·32. C-Store noted you can code a US-state attribute “into six bits, whereas the two-character abbreviation requires 16 bits.”
  • Delta encoding (DELTA_BINARY_PACKED): store differences between consecutive values in bit-packed miniblocks — excellent for sorted integers, IDs, timestamps.
  • Frame of Reference (FoR): store a per-block base value and small offsets from it; a variant of delta that shrinks clustered numeric ranges. (Combined with delta and bit-packing, this is the workhorse for numeric columns; the closely related timestamp/float schemes for metrics are covered in Time-Series Databases.)
  • Byte-stream split (BYTE_STREAM_SPLIT): scatter each float’s bytes into per-byte-position streams so a general compressor (zstd/Snappy) finds more redundancy.

General block compressors (LZ4, zstd, Snappy, gzip) are then layered on top of the lightweight encodings. The lightweight schemes do the heavy lifting because they preserve queryability; the general compressor mops up residual redundancy.

Zone Maps and Data Skipping

The second pillar of scan performance is not reading blocks that cannot match. Columnar engines store lightweight per-block metadata — the min and max of each column within a block (a zone map, the term popularized by Netezza/Redshift) — so a predicate like WHERE event_date = '2026-06-30' can skip any block whose [min,max] range excludes that date without decompressing it.

  • Parquet records statistics (min/max, null count) at both the column-chunk and the data-page level in its footer/metadata, enabling engines to prune row groups and pages before reading them (Parquet file format). Because metadata is written after the data (“to allow for single pass writing”), a reader first reads the footer, decides which column chunks to fetch, then seeks straight to them.
  • ClickHouse combines a sparse primary index — one index mark per granule (default index_granularity = 8192 rows) recording the sort-key value at the granule boundary — with optional data-skipping indexes (minmax, set, bloom filter) that let it skip granules whose aggregated values cannot satisfy the predicate (MergeTree docs). The primary index is sparse (one entry per 8192 rows, not per row) precisely because a column-store scans granules, not chases individual rows.

Zone maps are why sorting the data on a frequently-filtered column matters enormously: a well-clustered column has tight, non-overlapping zone ranges and prunes aggressively; a randomly-ordered column has zones that all overlap and prunes nothing.

Modern Engines — ClickHouse and DuckDB

ClickHouse is a column-oriented OLAP DBMS whose flagship MergeTree engine stores “each column in a separate file” (Wide format; Compact packs small parts into one file), sorted by the table’s ORDER BY key (ClickHouse intro, MergeTree). Inserts create immutable data parts, each internally sorted by the primary key; a background process continuously merges parts “similar to LSM-tree architecture” — the direct heir of C-Store’s tuple mover. The docs demonstrate scanning “100 million rows in 92 milliseconds… over 1 billion rows per second,” attributing the speed to reading “only the columns required for a query… avoiding unnecessary I/O,” per-column compression, the sparse index, and vectorized execution. The parallel to SSTable engines is real and deliberate: write to memory, flush sorted immutable runs, merge in the background.

DuckDB is the “SQLite for analytics”: an in-process, embedded analytical database with “no external dependencies,” a columnar-vectorized query execution engine, and “custom, bulk-optimized Multi-Version Concurrency Control (MVCC)” tuned for analytical rather than transactional workloads (DuckDB). It reads and writes Parquet natively and can query data lakes “up to petabytes.” Where SQLite is a row-store for embedded OLTP, DuckDB is its column-store counterpart for embedded OLAP — the same in-process deployment model, the opposite storage layout.

When Columnar Wins — and When It Loses

Columnar dominates scan-heavy, aggregation-heavy, append-mostly analytics: data warehouses, dashboards, ad-hoc exploration, star-schema reporting, log analytics. It loses badly at the OLTP tasks a row-store excels at:

  • Single-row point reads/writes. Reconstructing one full row means one seek into every column file and stitching the pieces — the exact cost column layout was designed to avoid for scans, now paid on every point lookup.
  • Row-level updates and deletes. Sorted, compressed, immutable columnar parts cannot be updated in place cheaply. Engines emulate updates with insert+delete + background merge (C-Store’s WS/RS, ClickHouse’s parts, ALTER TABLE ... UPDATE as an async mutation), so high-frequency small updates are an anti-pattern.
  • Highly selective narrow queries that a row-store answers with a single B-tree index probe returning one full row — a column-store’s strength (scanning) is wasted, and it may touch many column files.

The honest framing is the OLTP-vs-OLAP split from Row-Oriented versus Column-Oriented Storage: pick the layout that matches whether you read few-rows-all-columns (row) or all-rows-few-columns (column). Hybrid (HTAP) systems try to serve both from one engine — see NewSQL and Hybrid Transactional Analytical Processing.

Failure Modes and Misunderstandings

  • “Columnar means Cassandra.” No — see the top callout. Cassandra/Bigtable/HBase are wide-column models stored row-wise in LSM SSTables; they are not scan-optimized column-stores.
  • Trickle inserts kill columnar engines. Loading one row at a time creates a flood of tiny parts/row-groups that never compress or prune well and swamp the background merger. Batch loads (thousands–millions of rows) are mandatory; ClickHouse explicitly warns against frequent small inserts.
  • Unsorted data defeats zone maps. If the data isn’t clustered on the columns you filter on, every zone range overlaps and no blocks are skipped — you scan everything. Choosing the sort/ORDER BY key is the highest-leverage tuning decision.
  • Wide SELECT * on a column-store is the worst case. It forces every column file to be read and every row reconstructed — you’ve paid columnar’s costs and taken none of its benefits. Project only the columns you need.
  • Small-dictionary explosion. High-cardinality string columns (UUIDs, free text) defeat dictionary/RLE encoding; the dictionary grows unbounded and the engine falls back to plain encoding, ballooning size. Model such columns carefully or hash them.

Alternatives and When to Choose Them

  • Row-store OLTP engine (PostgreSQL, InnoDB): choose when the workload is point reads/writes and single-row transactions. See B-Tree and B-Plus-Tree Storage Engines.
  • Open columnar file format + query engine (Parquet/ORC on object storage, queried by DuckDB, Spark, Trino, DataFusion): choose for a decoupled lakehouse where storage and compute scale independently and multiple engines share one copy of the data. The IOx rewrite onto Arrow + Parquet + DataFusion is a case of a specialized store adopting exactly this stack.
  • Purpose-built columnar warehouse (ClickHouse, Vertica, Snowflake, BigQuery, Redshift): choose for managed, high-concurrency analytics with tight ingest-to-query latency.
  • Wide-column NoSQL (Cassandra): choose for write-heavy, horizontally-scaled operational workloads keyed by a known partition key — a different problem entirely (see Key-Value and Wide-Column Stores).

Production Notes

The industry’s decisive move is the open columnar lakehouse: Parquet/ORC files on object storage as the durable format, Apache Arrow as the in-memory columnar interchange, and multiple engines (DuckDB, Spark, Trino, DataFusion, ClickHouse) reading the same files. This is why Parquet’s design choices — footer metadata for single-pass writes, per-page min/max statistics for predicate pushdown, a rich encoding menu — matter far beyond any one database. ClickHouse’s public benchmarks (billions of rows/sec on a single node) and DuckDB’s embedded model (analytics inside a Python/R process with zero server) show the two poles the layout now spans: massive shared-nothing clusters and single-process embedded analytics, both built on the same rotate-the-table-ninety-degrees idea.

See Also

Graph View

Backlinks