One Size Fits None

The Column-Store Argument

Michael Stonebraker’s 2005 ICDE paper “One Size Fits All: An Idea Whose Time Has Come and Gone” is a polemic, and we should read it as one — not for its specific predictions (some aged badly) but for its method. The argument runs: commercial RDBMSs of the era were all descendants of System R, tuned for the workload of 1985 — OLTP, write-heavy, short transactions, terminals operated by humans. By 2005 the actual workload population had diversified: stream processing, scientific arrays, text, warehousing. Stonebraker’s move was to take one workload class, design an engine for it alone, and measure the gap against the general-purpose incumbent. For warehousing, that purpose-built engine was C-Store, and the gap wasn’t 20% — it was one to two orders of magnitude. When a specialized design beats the generalist by 50×, the generalist isn’t a compromise; it’s a category error. That method — pick the workload, derive the architecture, measure the gap — is the method of this entire course, because agents are exactly the kind of new workload class that the method demands we take seriously.

Rows are an OLTP decision, not a law of nature

A row store lays a tuple’s attributes contiguously: (id, name, state, price, qty, …), then the next tuple. This is optimal when your unit of work is the tuple — insert an order, read a customer record, update a balance. One seek, one page, done. But an analytical query like SELECT AVG(price) FROM lineitem WHERE shipdate > '2025-01-01' touches 2 of, say, 16 attributes. In a row store with 200-byte tuples, you drag all 200 bytes through the memory hierarchy to use 12 of them — a 94% waste of every cache line and every byte of disk bandwidth. A column store flips the layout: all values of price contiguous, all values of shipdate contiguous. The scan now reads only the columns the query names. For a 16-column table and a 2-column query, that’s an immediate 8× I/O reduction before we’ve even mentioned compression.

Compression: where columns earn their second order of magnitude

The I/O reduction above is the boring half. The exciting half: a column is a run of same-typed, often-sorted, low-entropy values, which compresses dramatically better than interleaved rows. Three encodings carry most of the weight. Work the numbers with me on a 1-billion-row lineitem table.

Run-length encoding (RLE). Take shipdate, and suppose the table is sorted on it. A billion rows spanning ~2,500 distinct days means each date repeats ~400,000 times consecutively. Store (value, run_length) pairs: 2,500 pairs × 8 bytes ≈ 20 KB, versus 4 GB raw (4-byte dates × 10⁹). That’s a 200,000× ratio — absurd, and real, but only on the sort column. RLE on an unsorted column degenerates to runs of length 1 and a 2× expansion. Lesson: compression choice is a function of sort order, which is why C-Store makes sort order a first-class physical-design decision.

Dictionary encoding. Take ship_state: 50 distinct values, stored as variable-length strings averaging 9 bytes. Build a dictionary mapping each string to an integer code; ⌈log₂ 50⌉ = 6 bits per value. Raw: 9 GB. Encoded: 10⁹ × 6 bits = 750 MB, plus a 450-byte dictionary. Ratio: 12×. Better still, predicates rewrite into code space — state = 'CA' becomes code = 4, an integer comparison against packed data, no string handling in the inner loop.

Bit-packing. Take quantity, stored as a 4-byte int but actually ranging 1–50. You need ⌈log₂ 50⌉ = 6 bits, not 32. Packed: 750 MB vs 4 GB — 5.3×, from nothing but refusing to store leading zeros. Combine with frame-of-reference (store deltas from a per-block minimum) and ascending keys like order IDs pack into a few bits each. These three encodings stack: dictionary first, then bit-pack the codes, then RLE the packed runs. Real Parquet files on real warehouse data routinely land at 5–10× overall — which means a 10 TB logical scan is a 1–2 TB physical one.

Late materialization and projections

If you decompress and glue columns back into tuples at the bottom of the plan, you’ve rebuilt a row store with extra steps. C-Store’s answer is late materialization: operate on columns (ideally still compressed) as long as possible, carrying only position lists between operators. Evaluate shipdate > X directly on RLE runs — a predicate on a run of 400,000 identical values is one comparison, not 400,000 — producing a bitmap of qualifying positions. AND that bitmap with the result of state = 4. Only then fetch price values at the surviving positions and aggregate. Tuples get stitched together only at the top, for the handful of rows that survive, instead of at the bottom for all billion.

C-Store’s other heresy: it doesn’t store “the table” at all. It stores projections — overlapping subsets of columns, each sorted on a different key, each compressed per its own sort order. A query picks whichever projection covers its columns with the friendliest sort order. Redundant storage buying read speed — this is the RUM triangle from Week 2 wearing different clothes. The write problem (sorted, compressed, replicated data is miserable to update) is handled by a small row-oriented Writeable Store in front, merged into the Read-optimized Store in batches. Squint and you’ll see the LSM shape again: optimize reads in the big immutable structure, absorb writes in a small mutable one, pay with background merges.

Why the hardware votes for columns

Two mechanical facts seal the argument. Cache lines: memory arrives in 64-byte lines. Scanning a column of 4-byte ints, every line delivers 16 useful values; scanning the same predicate over 200-byte rows, every line delivers at most a fraction of one. On a machine with ~25 GB/s per-core effective bandwidth, that utilization difference is the speedup, because scans are bandwidth-bound. SIMD: AVX-512 compares 16 packed 32-bit values per instruction — but only if the values are contiguous and same-typed. Columnar layout is precisely the precondition for SIMD; row layout makes it impossible without a gather, which forfeits the win. The column store isn’t clever; it’s shaped like the machine.

Vectorized Execution: From Tuple-at-a-Time to Batches

Tuesday was about layout; today is about execution, and the villain is one of the most beloved designs in database history. The Volcano iterator model (Graefe, 1990) gives every operator the same interface — open(), next(), close() — and composes plans like Unix pipes: each next() call pulls one tuple from the operator below. It is beautiful, modular, and memory-frugal: only one tuple is in flight at a time, which mattered enormously when RAM was measured in megabytes. It is also, on modern CPUs, catastrophically slow for analytics — and the MonetDB/X100 paper (CIDR 2005) measured exactly how slow: commercial DBMSs executing TPC-H Query 1 ran at roughly a third of the instructions-per-cycle of hand-written C — and paid an order of magnitude more cycles per tuple — spending under 10% of their cycles on actual query work.

The price of one tuple at a time

Count the overhead per tuple in a Volcano plan. Each next() is a virtual function call — an indirect branch the CPU can’t reliably predict, ~20–40 cycles with the pipeline flush. A three-operator plan (scan → filter → aggregate) costs three of those per tuple, plus attribute extraction from the tuple slot, plus type-dispatch (“is this an int4 or a numeric?”) decided per value inside the expression interpreter. Total: hundreds of cycles of interpretation wrapping ~5 cycles of actual work — a compare, an add. At 10⁹ tuples, a query whose useful work is ~5 billion cycles spends 100+ billion on ceremony. The function-call tax doesn’t show up in OLTP, where a query touches 10 rows; it devours OLAP, where a query touches 10⁹. Same model, different workload, opposite verdict — Stonebraker’s thesis again, now at the level of the inner loop.

X100: vectors of ~1000, primitives, cache residency

MonetDB/X100’s fix keeps Volcano’s composable pull-based plan but changes the unit of exchange: next() returns a vector of ~1000 values per column, not one tuple. The virtual call, the branch misprediction, the operator-dispatch logic — all still there, but amortized over 1000 values: 30 cycles ÷ 1000 = 0.03 cycles per value of overhead instead of 30. Inside operators, work is done by primitives: pre-compiled, type-specialized tight loops like select_lt_int32 or map_mul_double. No interpretation inside the loop — the type dispatch happened once per vector, not once per value — so the compiler unrolls, the hardware prefetcher streams, and SIMD applies. X100 reported TPC-H Q1 going from ~minutes-per-gigabyte interpretation regimes to being limited by memory bandwidth, roughly 3× the IPC and one to two orders of magnitude more raw execution power than the tuple-at-a-time commercial engines it benchmarked.

Why 1000 and not 1,000,000? Because the other failure mode is full-column-at-a-time execution (original MonetDB BAT algebra): materializing every intermediate result as a complete column array spills intermediates to RAM — or disk — between every operator. The vector size is chosen so that all the vectors live in a plan’s working set fit in L1/L2 cache. A 1000-value vector of 4-byte ints is 4 KB; a dozen of them in flight is ~50 KB — comfortably inside a 1 MB L2. Each vector is produced, consumed by the next primitive, and overwritten while still cache-hot. The X100 paper’s own sensitivity graph is U-shaped: performance climbs steeply from vector size 1 (interpretation-dominated), plateaus around 10²–10³, then degrades past ~10⁴ as vectors fall out of cache. The sweet spot is “big enough to amortize interpretation, small enough to stay resident.” Memorize that sentence; it generalizes to half of systems design.

/* An X100-style primitive: selection on one column vector.
 * One virtual call delivered 'n' ≈ 1024 values; everything
 * below is a branch-free, type-specialized, cache-resident loop
 * the compiler auto-vectorizes (AVX2: 8 lanes per instruction).
 */
size_t sel_lt_int32(const int32_t *col, int32_t bound,
                    uint32_t *sel_out, size_t n)
{
    size_t k = 0;
    for (size_t i = 0; i < n; i++) {
        sel_out[k] = (uint32_t)i;     /* write position…        */
        k += (col[i] < bound);        /* …keep it only on match */
    }
    return k;   /* selection vector: positions, not copies —
                   late materialization at execution scale */
}

Note what the primitive returns: a selection vector of qualifying positions, not a copied-out vector of survivors. Downstream primitives take (data, sel, n) and iterate only the selected positions. This is Tuesday’s late materialization recurring at micro-scale — pass positions, defer copying — and the branch-free k += (cond) idiom sidesteps the branch predictor entirely, which matters because a 50%-selective predicate is the predictor’s worst nightmare.

Vectorize or compile? The HyPer counterpoint

Vectorization is not the only escape from Volcano. The other is JIT compilation: HyPer (Neumann, 2011) compiles each query into LLVM machine code that fuses a whole pipeline — scan, filter, aggregate — into one loop, keeping the current tuple in registers with zero materialization between operators. Both approaches kill interpretation overhead; they differ in what they pay. The 2018 “Everything You Always Wanted to Know…” study (Kersten et al.) built both models in one codebase and found neither dominates: compilation wins on computation-heavy queries with long pipelines (no vector materialization at all), vectorization wins on memory-bound scans (SIMD-friendly, better cache behavior on hash joins) — usually within 2× of each other, both ~100× over Volcano.

The agent angle: scan-dominant, speculative, and impatient

Now run this week through the course thesis. A human analyst issues perhaps a dozen carefully-considered queries per hour. An agent doing exploratory analysis issues hundreds: profile every column, test five hypotheses, compute a correlation matrix, abandon four branches, drill into the fifth. Three properties of this workload follow. It is scan-dominant — profiling and hypothesis-testing queries are aggregations over wide ranges, the exact shape columns plus vectorization serve best, and the exact shape B-tree point indexes serve worst. It is speculative — most queries are dead ends, so the economics demand cheap queries over fast-but-expensive ones; you can’t justify building an index, or even a long JIT compile, for a query that will run once and be discarded. And it is impatient in aggregate — per-query overhead (connection setup, planning, compilation) multiplies by the query count, which is why vectorized engines with precompiled primitives and near-zero startup (DuckDB embedded in the agent’s process is the limit case) fit agents better than engines that amortize heavy per-query investment over long-running reports.

This is also why the open descendants of this week’s papers matter more than the papers’ own systems. Parquet is C-Store’s storage chapter standardized: columnar layout, dictionary + RLE + bit-packing per column chunk, min/max zone maps per row group for predicate skipping — readable by every engine, sitting in object storage. Arrow is the X100 vector standardized: a common in-memory columnar format so that the engine, the dataframe library, and the agent’s tool-call boundary pass vectors by pointer instead of serializing tuples. An agent that calls DuckDB over Arrow against Parquet in S3 is running the 2005 research stack, verbatim, as commodity open infrastructure. One size fit none; so the sizes became formats, and the formats won.

Read Before Thursday

This Week’s Problems