8.5.2 Storage Formats

Basic Prerequisites: 01 · From Zero and Memory & Cache.

---

1. Intuition & Practical Objective

The physical layout of a tick store is decided by three nested choices, and each one can be made independently:

1. Within a record - are fields interleaved (Array-of-Structures) or split into parallel arrays (Structure-of-Arrays)?
2. Within a file - are columns chunked into row groups with per-group zone maps (min/max statistics)?
3. Across files - is the table partitioned by date, by symbol, or both?

The objective of this page is to make the file format itself legible: Parquet and Arrow are not magic - they are the SoA choice plus row groups plus statistics, and knowing the mechanics is what lets you predict whether a query will scan 2.4 GB or 10 MB.

The essence. “A columnar file is a transposed table with a table of contents: columns are stored contiguously, chunked into row groups, and each group carries min/max statistics so the engine can skip whole chunks without reading them.”

---

2. Mathematical Ground Truth & Derivations

AoS vs SoA (the in-memory half). For $N$ records of width $s={\sum }_j{s}_j$, scanning one field of width $s_c$ touches

$$W_{\text{AoS}}=Ns,W_{\text{SoA}}=N{s}_c,L_{\text{AoS}}=\lceil \frac{Ns}{64}\rceil ,L_{\text{SoA}}=\lceil \frac{N{s}_c}{64}\rceil .$$

The ratio $s/s_c$ (here $6$) is structural: no predicate, index, or SIMD instruction recovers bytes never laid out contiguously.

Partition pruning. With the table split into $D$ equal day-partitions - each self-contained with its own header and statistics - a single-day predicate reads

$$B_{\text{pruned}}=\frac{B_{\text{table}}}{D}⟹\text{I/O reduction}=D.$$

Zone maps (min/max pushdown). A row group of $R$ rows keeps, per column, a $(min,max)$ pair (16 B). For an equality/range predicate known to select a fraction $f$ of the value domain, an engine that reads only the groups whose $[min,max]$ overlaps the predicate reads approximately

$$G_{\text{read}}\approx \lceil fG\rceil \text{groups instead of }G=\lceil \frac{R_{\text{day}}}{R}\rceil ,$$

with a metadata overhead of only

$$\text{overhead}=\frac{16|\text{cols}|}{Rs}\text{fraction of the day’s bytes}$$

(equivalently $\frac{16|\text{cols}|G}{R_{\text{day}}s}$, with $G=R_{\text{day}}/R$ groups).

This is why a sorted table is cheap to filter: sorting co-locates values, so each group’s $[min,max]$ band is narrow and few groups are needed.

---

3. Computational Implementation - pruning and projection in numbers

A one-year, 100M-row Parquet-style table partitioned by date, with 16,384-row row groups. The model computes the bytes a query is forced to read under full scan, partition pruning, projection, and zone-map filtering.

Three independent multipliers compound: 252× from date partitioning, 6× from column projection, and up to 12× from zone-map skipping within a day - all purchased by writing the data columnar, sorted, and date-chunked.

---

4. Failure Modes & First-Principles Breakdowns

1. Row groups too large. With one 1M-row group per day, zone maps cannot skip anything inside the day - pruning collapses to all-or-nothing. Smaller groups improve skipping but raise metadata overhead; 16k–128k rows is the usual band.
2. Unsorted writes. If ticks land in arrival order rather than sorted by time, each row group’s [min,max] spans the whole day and zone maps become useless. The sort is what buys the pruning.
3. Schema drift breaks readers. Parquet is self-describing, but a service that assumes fixed offsets (or an Arrow schema pinned at process start) will mis-decode the moment a feed adds a field (see 05 · Failure Modes).
4. Tiny files. Partitioning too finely (per-symbol-per-day across 3,000 symbols) creates metadata swamps and kills sequential throughput. Partition on the dominant predicate - date - and use sortedness for the rest.
5. Confusing Arrow (in-memory) with Parquet (on-disk). Arrow is the zero-copy columnar memory layout; Parquet is the compressed file format. A pipeline reads Parquet → Arrow to query, and the conversion cost is real.

---

5. References

• DuckDB - AsOf Join, Parquet & Arrow documentation (duckdb.org)
• Needham & Simons - DuckDB in Action (Manning), ch. 4 (window functions, Parquet, as-of joins)
• ClickHouse Documentation (clickhouse.com)
• Arrow & Parquet specifications (arrow.apache.org, parquet.apache.org)
• Bryant & O’Hallaron - CS:APP, ch. 6 (locality)

---

6. Connected Graph Bridges

• Back: 01 · From Zero · Index Hub
• Forward: 03 · Compression (how those columns shrink) → 04 · Time-Series Databases (which engine reads them)
• Systems base: Memory & Cache
• Engines in practice: 04 · Time-Series Databases