How does BigQuery's Capacitor format store a repeated field such as an ARRAY column?

## The problem nesting creates for a column store A columnar format is easy when every row has exactly one value per column: store the column's values in order, compress, done. Nested and repeated data breaks that. A record like `{order_id: 7, items: [{sku:'A', qty:2}, {sku:'B', qty:1}]}` has two values for `items.sku` in one row and possibly zero in another. Storing the record as a serialised blob would work but destroys the whole point of columnar storage, because reading `order_id` would drag every item along with it. The technique BigQuery uses comes from the original Dremel work and is the same idea later adopted by open columnar formats: **shred the record into leaf columns and store enough per-value bookkeeping to put it back together.** ## Repetition and definition levels Each leaf column stores its values plus two small integers alongside each value: - **Repetition level** — at which level of the nested path a new repeated element started. Level 0 means "this value begins a new top-level record"; a higher level means "this value is another element of a repeated field at that depth." That is what tells the reader where one array ends and the next record's array begins. - **Definition level** — how many of the optional or repeated fields along the path were actually present. It encodes NULLs and empty arrays without storing a placeholder value: if the path ran out before reaching the leaf, the definition level says exactly where it stopped. Both levels are tiny integers with a small range, so they compress extremely well — usually to a fraction of the data's size. ## What that buys you at query time **Reading one leaf reads one column.** `SELECT order_id` from a table with a deeply nested `items` array touches only the `order_id` column. `SELECT item.sku FROM t, UNNEST(items) AS item` touches only the `sku` leaf plus its levels. The other 29 fields of the struct are never read, never decompressed, and never billed under on-demand pricing. **Nesting replaces a join.** Because a repeated record can be stored inline and still read column-wise, the classic pattern of a header table joined to a lines table can be collapsed into one table with a repeated field. The engine reads the parent and child fields from the same file with no shuffle, which is exactly the join cost you were trying to avoid. This is why denormalising into nested structures is idiomatic in BigQuery rather than the anti-pattern it would be in a row store. **Reconstruction is lazy.** The record shape is only rebuilt for the columns the query actually selected, and only when a query needs the structure — a filter on a scalar leaf can be evaluated against that column directly. ## The rest of Capacitor Beyond record shredding, Capacitor applies per-column encoding: dictionary encoding for low-cardinality string columns, run-length style encoding for long runs, and general compression on top. Because encoding is chosen per column, a column of a few distinct country codes and a column of unique UUIDs are stored very differently in the same table. BigQuery also performs storage optimisation in the background — reorganising and re-encoding the physical files after writes — which is why you never issue a rewrite or vacuum command yourself, and why a table's storage footprint can change without you doing anything. ## Costs and limits worth naming - **Filtering deep inside an array is not free.** A predicate on a repeated leaf may still require reading that leaf column across all rows unless partitioning or clustering narrows the files first. Nesting removes joins; it does not remove scans. - **`UNNEST` expands rows for downstream operators.** The read is cheap, but if you unnest a large array and then join or aggregate, the row count feeding those stages is the expanded one, and that costs slot time. - **Very large arrays inside single rows concentrate work.** A row whose array holds millions of elements makes that row's processing an outsized unit of work — the nested-data version of skew. - **Selecting the whole struct defeats the benefit.** `SELECT *` on a table with wide nested records reads every leaf column. The saving comes from asking for specific fields. ## How to answer this crisply Say the shape of the mechanism first: *leaf columns plus repetition and definition levels, so structure survives without giving up columnar reads*. Then give the consequence an interviewer cares about: *you can denormalise a parent-child relationship into a repeated field and read one child field without reading the rest, which trades a join for a column read*. That connects a storage-format detail to a modelling decision, which is what the question is really testing.