Columnar storage

Deep dive

How it works

Parts:

• row group — about 10⁵-10⁶ rows written together
• column chunk — one column's values for a row group, split into pages
• page encoding — dictionary, RLE, delta, frame-of-reference, bit-packing, then optional LZ4 or zstd
• statistics — min/max/null counts per chunk (zone maps)
• footer — schema, chunk offsets and statistics, read first
• delete vector or file — marks removed rows without rewriting chunks

row group 0 (1M rows)                     footer
 ├─ col a: [page][page]... min=3 max=97    schema, chunk offsets,
 ├─ col b: [page][page]... min=0 max=12    min/max/null counts per chunk
 └─ col c: ...
row group 1 ...

1. Partition rows into groups (about 10⁵-10⁶ rows). Within a group, write each column as a chunk of pages.
2. Encode each page: dictionary if the number of distinct values is small, otherwise plain, delta or frame-of-reference with bit-packing. Store nulls as a bitmap (Arrow) or definition levels (Parquet).
3. Footer: schema, chunk offsets and statistics, read first (one small I/O).
4. Scan: prune row groups by statistics and partition keys, read only the referenced column chunks, decode in batches of about 1-2k values (vectorized execution), evaluate predicates into a selection vector, then fetch the other columns only for the selected rows (late materialization).
5. Updates: write new files plus delete vectors or bitmaps, then merge in the background (C-Store's write store and read store; Delta Lake and Iceberg delete files).

Code

Frame-of-reference + bit-packing per chunk, zone-map pruning and late materialization:

pub struct Chunk { pub min: i64, pub max: i64, bits: u32, pub n: usize, packed: Vec<u64> }

impl Chunk {
    pub fn encode(vals: &[i64]) -> Chunk { // vals non-empty
        let (min, max) = (*vals.iter().min().unwrap(), *vals.iter().max().unwrap());
        let range = (max as i128 - min as i128) as u64;
        let bits = 64 - range.leading_zeros(); // 0 bits when all values are equal
        let mut packed = vec![0u64; (vals.len() * bits as usize + 63) / 64];
        if bits > 0 {
            for (i, &v) in vals.iter().enumerate() {
                let d = v.wrapping_sub(min) as u64; // offset from the frame of reference
                let (w, o) = ((i * bits as usize) / 64, (i * bits as usize) % 64);
                packed[w] |= d << o;
                if o + bits as usize > 64 { packed[w + 1] |= d >> (64 - o); } // straddles two words
            }
        }
        Chunk { min, max, bits, n: vals.len(), packed }
    }

    #[inline]
    pub fn get(&self, i: usize) -> i64 {
        if self.bits == 0 { return self.min; }
        let b = self.bits as usize;
        let (w, o) = ((i * b) / 64, (i * b) % 64);
        let mask = if b == 64 { u64::MAX } else { (1u64 << b) - 1 };
        let mut d = self.packed[w] >> o;
        if o + b > 64 { d |= self.packed[w + 1] << (64 - o); }
        self.min.wrapping_add((d & mask) as i64)
    }
}

/// Two columns cut into chunks over the same row ranges.
pub struct Table { pub a: Vec<Chunk>, pub b: Vec<Chunk> }

/// SELECT sum(b) FROM t WHERE a BETWEEN lo AND hi
pub fn sum_b_where_a_between(t: &Table, lo: i64, hi: i64) -> i64 {
    let mut sel: Vec<u32> = Vec::new();
    let mut sum = 0i64;
    for (ca, cb) in t.a.iter().zip(&t.b) {
        if ca.max < lo || ca.min > hi { continue; } // zone map: chunk skipped, nothing decoded
        sel.clear();
        for i in 0..ca.n {
            let v = ca.get(i);
            sel.push(i as u32);
            sel.truncate(sel.len() - (!(v >= lo && v <= hi)) as usize); // branch-free keep/drop
        }
        for &i in &sel { sum = sum.wrapping_add(cb.get(i as usize)); } // b decoded only where a matched
    }
    sum
}

Predicates can also run on the encoded values: compare the packed offsets with lo − min and hi − min without adding min back. On dictionary columns, compare dictionary codes after translating the constant once.

Complexity and constants

• I/O reduction = (bytes of referenced columns) / (bytes of all columns), multiplied by the compression ratio. 3 of 50 similar columns at 5× compression means about 1 % of the row-store bytes.
• In-memory scans run near memory bandwidth: order of 1-10 GB/s per core for simple filters on bit-packed integers. SIMD unpacking decodes billions of values per second.
• A selective filter with zone maps on a sorted column reads O(matching chunks), not O(table).
• Point lookup of a full row = one random read per column chunk plus a decode of the page around it.

Efficiency

• Cost: a scan reads (bytes of referenced columns) / (bytes of all columns) times the compression ratio: 3 of 50 similar columns at 5× compression is about 1 % of the row-store bytes (computed). In memory, scans run order of 1-10 GB/s per core on bit-packed integers. Bound: I/O bandwidth when cold, memory bandwidth and SIMD when cached.
• Levers:
  • column pruning — read only referenced columns (computed above) — any query touching few columns
  • dictionary, RLE, delta, bit-packing — smaller columns, filter without full decompression (Abadi et al., 2006) — low-cardinality or sorted columns
  • sort by the common filter column — zone maps and Bloom filters exclude whole chunks — repeated filters on one column
  • vectorized loops, LZ4 or plain for hot data — high-level zstd can bottleneck fast NVMe (order of) — cached data
  • large row groups, compact tiny files — sequential reads — data lakes
• Naive → standard → state of the art:
  • row store scan · all columns through I/O and cache
  • columnar chunks with light encodings and zone maps · about 1 % of the bytes in the example
  • sorted layout, late materialization, vectorized decode · scans near memory bandwidth

Implementation notes

• Sort key: sorting by a common filter column makes zone maps effective and runs long (RLE). ClickHouse ORDER BY, Snowflake clustering, Parquet files written sorted.
• Dictionary fallback: Parquet writers fall back from dictionary to plain encoding when the dictionary grows too big (1 MiB page by default). High-cardinality strings then lose their compression.
• Row group size trades I/O efficiency (large sequential reads, good compression) against memory for writers and parallelism granularity.
• Strings: offsets array + contiguous bytes (Arrow layout), or dictionary codes. Avoid one heap allocation per value.
• Nested data: Dremel repetition and definition levels (Parquet), or Arrow's list offsets.
• Bloom filters per chunk help equality predicates on unsorted high-cardinality columns where min/max are useless.

Pitfalls

• The small-files problem: thousands of tiny Parquet files mean metadata and open costs dominate, and compression is poor. Compact them.
• Row-at-a-time inserts into a column store: each one touches N files or segments. Batch inserts (ClickHouse recommends ≥ 1000s of rows per insert).
• Wide SELECT * over many columns erases the advantage.
• Unsorted data makes every zone map span the full range, so nothing is skipped.
• Decompressing heavy codecs (zstd at high levels) can become the bottleneck on fast NVMe. Use LZ4 or plain encodings for hot data.

Variants and alternatives

In production

• Analytics databases: ClickHouse MergeTree, DuckDB, Vertica (C-Store), Snowflake, BigQuery (Capacitor), Redshift, Druid, Pinot.
• Data lakes and pipelines: Apache Parquet and ORC files; Apache Arrow as the in-memory form.
• Time-series and observability: InfluxDB 3 stores data as Parquet; ClickHouse is widely used for event and log analytics.
• Machine learning: Hugging Face Datasets stores data in Arrow and reads Parquet.

Implementations

Sources

• M. Stonebraker et al., C-Store: A Column-oriented DBMS, VLDB, 2005. paper
• D. Abadi, S. Madden, M. Ferreira, Integrating Compression and Execution in Column-Oriented Database Systems, SIGMOD, 2006. paper
• D. Abadi et al., The Design and Implementation of Modern Column-Oriented Database Systems, Foundations and Trends in Databases, 2013. paper
• S. Melnik et al., Dremel: Interactive Analysis of Web-Scale Datasets, VLDB, 2010. paper
• A. Ailamaki, D. DeWitt, M. Hill, M. Skounakis, Weaving Relations for Cache Performance (PAX), VLDB, 2001. paper
• Apache Parquet, File format documentation. docs