Columnar Layout and the Cost of Reading One Field

A table with a hundred fields, scanned for one of them. In a file that stores records one after another, every field of a record sits beside every other field, so a scan of the fourth column still drags the other ninety-nine past the memory bus. In a file that stores each field in its own run, the same scan moves only the bytes it asked for. No smarter algorithm is involved. The set of addresses touched is different.

Where the bytes sit

Row-major layout places record $t$ at byte offset $t \cdot W$, where $W$ is the record width, and field $j$ of that record at $t \cdot W$ plus the widths of the fields that precede $j$. Reading field $j$ across every record visits one address per record, each spaced $W$ bytes from the last. Columnar layout gives field $j$ a contiguous run of its own: with a fixed width $w$, value $i$ lives at $\text{base}_j + i \cdot w$, and the stride is $w$.

The two layouts answer different questions well. Row-major answers “return record $t$ in full” with a single contiguous read of $W$ bytes, which is why it dominates transactional storage and every format that must be written one record at a time. Columnar answers “return field $j$ for a range of records” with a single contiguous read of $n \cdot w$ bytes and nothing else.

A concrete pair of structures makes the stride visible:

#include <stdint.h>
#include <stddef.h>

#define ROWS 1000000

struct record {          /* array of structs: 96 bytes per record */
    int32_t id;          /* offset 0  */
    int32_t qty;         /* offset 4  */
    double  price;       /* offset 8  */
    char    note[80];    /* offset 16 */
};

struct columns {         /* struct of arrays: one buffer per field */
    int32_t id[ROWS];
    int32_t qty[ROWS];
    double  price[ROWS];
    char    note[ROWS][80];
};

long sum_qty_rows(const struct record *r) {
    long s = 0;
    for (size_t i = 0; i < ROWS; i++)
        s += r[i].qty;             /* stride sizeof(struct record) */
    return s;
}

long sum_qty_cols(const struct columns *c) {
    long s = 0;
    for (size_t i = 0; i < ROWS; i++)
        s += c->qty[i];            /* stride 4 bytes, no gaps */
    return s;
}

Both loops execute the same number of additions. The first touches 96 bytes of memory per addition, the second touches 4.

The arithmetic of a single-column scan

Take a 96-byte record and a 4-byte integer field. Scanning $10^8$ records reads 9.6 GB in row-major form and 0.4 GB in columnar form. The ratio is exactly $W/w = 24$.

The number that governs the hardware cost is the cache line, 64 bytes on x86-64 and on the common ARM cores. A 96-byte record straddles two lines, so a scan that wants 4 bytes from each record pulls 96 bytes per record and uses one byte in twenty-four. Hardware prefetchers recognize constant strides and keep the pipeline fed, so the waste appears as bandwidth consumption and cache occupancy rather than as a stall per record. At 9.6 GB the scan also touches roughly 2.3 million distinct 4 KiB pages, which is where TLB pressure starts to matter; the columnar version touches a twenty-fourth as many.

Vector width repeats the same argument one level down. A 256-bit register holds eight int32 values when they are contiguous and one value plus seven empty lanes when they sit 96 bytes apart; the compiler must emit a gather, and gathers on mainstream x86 cores retire elements far more slowly than a plain load. The columnar inner loop is a load, a compare, and an accumulate over adjacent addresses.

The layout only pays when the query projects. A scan that reads every field of every record fetches the same bytes either way, and row-major may win, because it makes one linear pass over one region instead of $k$ passes over $k$ regions. Columnar storage is a bet that most scans touch a minority of fields. Analytical queries do; a full export does not.

Variable-width fields and the offset array

Fixed widths make the address arithmetic trivial. Strings and byte arrays do not have one, so a columnar string column is stored as two buffers: a data buffer holding values back to back, and an offsets buffer of $n+1$ integers where value $i$ occupies data[offsets[i] .. offsets[i+1]). The extra integer per value is pure overhead, and for short strings it dominates: six-byte values with 4-byte offsets carry 67 percent overhead before any compression, which is why encoders attack short strings specifically, and why dictionary encoding earns so much on them.

Offsets also decide random access. Reaching value $i$ is two loads, one into the offsets buffer and one into the data buffer, so a columnar column supports random access within itself. What it does not support is random access across columns without paying one cache miss per column, a cost examined below.

Why homogeneity compresses

A column holds values of one type, frequently drawn from a narrow domain, and the encoders exploit exactly that. Dictionary encoding replaces repeated strings with small integers; run-length encoding collapses runs in a sorted column; delta encoding turns a monotone timestamp column into small increments; bit packing stores a 3-bit domain in 3 bits per value. None of these transformations apply across a record, where adjacent values have unrelated types and unrelated distributions, so a record-oriented file presents a general-purpose compressor with a window full of interleaved structure it must rediscover byte by byte. Columnar files hand the compressor a homogeneous window and, in most formats, compress each column chunk or page separately, which keeps the window from mixing fields. The encodings are treated in Dictionary Encoding and the Cardinality Cliff and the block structure in Compression Blocks and the Loss of Splittability.

The second-order effect is that compression changes the scan arithmetic. If a column compresses to a quarter of its width, the bytes fetched fall by four, and the amplification factor computed from raw widths overstates the cost. It can also understate it: a column that must be decompressed before a filter can be applied spends CPU on values that the filter then discards, which is why formats put cheap statistics ahead of the decoder.

What the layout costs on reads, writes, and ingest

Fetching one full record requires one value from each of $k$ columns, so a point lookup touches $k$ distinct regions instead of one. With a warm cache that is $k$ cache misses; against cold storage it is $k$ random reads, and the penalty grows with the column count rather than with the record size. Late materialization reduces the damage: evaluate the predicate against the single column it references, keep the surviving row positions, then gather the remaining columns for those positions only. The row positions are themselves a column, usually the implicit ordinal within a row group, so the second phase is a gather over a small set of offsets instead of a scan.

Updates are worse. A columnar file is normally immutable at the page level: changing one value in a compressed page means decoding the page, substituting the value, and re-encoding it, and appending one record means touching every column. Systems that need both patterns keep a row-major delta store, a small mutable buffer of recent inserts and updates, plus a delete bitmap marking superseded rows, and merge the delta into the columnar base during compaction. The merge is a rewrite of the affected row groups, not an in-place edit.

Ingest carries a matching constraint. A writer receiving records one at a time cannot finalize the chunk for a column until the last record of the group has arrived, so it must buffer an entire group before writing. Flushing often produces many small groups, and metadata multiplies: a 500-column schema spread over 10,000 groups has five million column descriptors in the file metadata before a single value. This is the reason streaming systems buffer by time or size and write groups of tens of megabytes rather than groups of a few thousand rows.

The middle ground

Most columnar formats are not pure. Parquet partitions records into a row group and stores columns contiguously inside the group, which is the PAX layout: pages partition the rows, and within a page the fields are separated. A reader reconstructing a full record reads one page per column, getting page-level locality for the record and column-level locality inside the page for scans. The row group size chooses the position on that spectrum, and Inside a Parquet File works through the consequences.

Row-major remains correct for transactional access, for formats whose schema is unknown at write time such as line-delimited JSON, and for small tables where per-column metadata exceeds the data. The layout is a physical decision about which access pattern to make cheap, and it is made once, at write time, for every future reader.