Repetition and Definition Levels in Nested Columns

Storing a nested record in a columnar file raises a question that has no analogue in a flat table: the leaf values of one column do not correspond one-to-one with rows. A record may contain a list of three items, another a list of one, another an empty list, and another no list at all. If the writer stores only the leaf values, the reader cannot reconstruct how they group into records, and if the writer stores a structure per row, the columnar property is lost.

The Dremel encoding answers with two integers attached to every leaf value: a repetition level and a definition level. The pair is small, it is computed from the schema path rather than from the data, and it is enough to reconstruct the nesting exactly. Understanding it requires reading the schema as a path with two counters attached.

Reading a schema path as two counters

Take a path from a record to a leaf field. Along that path some fields are required, some are optional, and some are repeated. Two quantities attach to the path.

The maximum definition level is the number of fields on the path that may be absent, counting both optional fields and repeated fields (a repeated field may be absent in the sense that the list is empty). The actual definition level of a value is the number of those fields that are present for this particular value. When the actual level is less than the maximum, the missing prefix of the path tells the reader exactly which ancestor was absent.

The maximum repetition level is the number of repeated fields on the path. The actual repetition level of a value records the depth at which this value starts a new occurrence: zero means a new record, one means a new element of the outermost repeated field, two means a new element of a nested repeated field inside that element, and so on.

A leaf under a path with one optional field and one repeated field therefore has a maximum definition level of 2 and a maximum repetition level of 1. Both counters are bounded by the schema, so both fit in a couple of bits, which is why formats bit-pack them alongside the values rather than storing them as bytes.

A worked encoding

Consider a schema of orders, each with a list of items, where each item has an optional SKU:

message Sale {
  required int64 order_id;
  repeated group Item {          // list, max def 1, max rep 1
    optional string sku;         // max def 2, max rep 1
  }
}

The sku column for three records:

• order 10: two items, SKUs A and B
• order 11: one item, SKU absent
• order 12: no items at all

The encoded column is four entries:

value	def	rep
A	2	0
B	2	1
null	1	0
null	0	0

Three items across the records would suggest three entries; the encoding needs four, because the empty list still occupies one. The empty list produces exactly one entry and no value. The fourth row of the table is the empty list: definition level 0 means the Item list itself is absent, so no SKU can exist, and the entry carries no value at all. The third is the list present with one element whose SKU is null: definition level 1 means the list exists but the optional field below it does not.

The distinction between the last two is the reason a plain validity bitmap cannot represent nested data. Both are “null SKU” from the perspective of a two-state marker, and they mean different things: one record has an item with no SKU, the other has no items. Downstream, count(items) and count(distinct sku) differ, and flattening the data would produce one row in the first case and zero in the second.

Repetition levels encode the grouping without any explicit delimiters. Scanning the column, every entry with repetition level 0 begins a new record; within a record, an entry with level 1 begins a new element of the outermost repeated field. A decoder maintains a stack of counters, one per repeated level, and increments the counter at the level named by the repetition level while resetting all deeper counters. That stack is the entire reconstruction state, and its depth is bounded by the schema, not by the data.

def group_records(entries, max_def):
    """entries: (value, def_level, rep_level) for one leaf column.
    Yields (defined_values, path_exists) once per record."""
    vals, exists, started = [], False, False
    for value, d, r in entries:
        if r == 0:                 # a repetition level of 0 always begins a record
            if started:
                yield vals, exists
            vals, exists, started = [], False, True
        if d > 0:
            exists = True          # some prefix of the path is present
        if d == max_def:
            vals.append(value)     # the leaf itself is present
    if started:
        yield vals, exists

The function above reconstructs one leaf per record for a path with a single repeated level; deeper paths need one counter per level, because a repetition level of two means a new element of the inner list inside the same element of the outer one. The essential point is that the decoder’s state is bounded by the schema depth, so reconstruction is a linear pass with no recursion and no lookahead.

Why the levels are stored with the values, not with the records

An alternative design stores, per record, the shape of its nesting: a count of items, then a count of nested fields, and so on. That makes each record self-describing and reconstruction trivial, and it destroys the columnar property, because the shape data is interleaved with the values and differs per record. It also breaks compression: shape counts are a separate sequence with their own distribution, and mixing them into the value stream prevents the value encoder from seeing a homogeneous run.

Storing levels per value instead has three consequences that matter at scale. The levels are small integers with a narrow domain, so they bit-pack into one or two bits per value and compress well under run-length encoding when the structure is regular. They are computed at write time from the schema path and the record, so the writer needs no global view of the file. And they are independent of the record’s content, so a reader can decode a column chunk without having read any other column, which is what makes independent column reads possible at all.

That last property is what makes projection work on nested data. A query that needs only item.sku reads the sku column chunk, including its level streams, and never touches item.qty or any sibling. The record structure is recoverable from the levels alone, so no other column has to be read to interpret this one. This is the nested analogue of the flat projection argument in Columnar Layout and the Cost of Reading One Field.

Where the encoding becomes expensive

The costs appear when the schema is deep and sparse. Each level of optionality adds a definition level, and the level’s bit width grows as $\lceil \log_2(\text{max def} + 1) \rceil$, so a path with fifteen optional ancestors needs four bits per value for the definition level alone, doubled for a repeated path. Parquet stores definition and repetition levels in a bit-packed run-length hybrid, which recovers most of that when values share levels, and none of it when they alternate.

Sparse nesting is worse. A struct field that is usually absent costs one definition-level entry per record in every leaf column beneath it, even though the leaf values are rare. A schema with thirty optional leaves under a rarely-present struct pays thirty level streams for one present record. This is a property of the physical layout, not of the logical model, and it is the reason deeply nested schemas are frequently flattened before storage: the flattening removes levels and replaces them with columns that are mostly null, which at least compress well.

Reconstruction also has a cost that flat data does not: the record assembly step must materialize the nesting, and the number of objects created is proportional to the number of list elements, not to the number of records. A reader that assembles records for a query that only needs a scalar aggregate has wasted that work, which is why engines push aggregation down to the leaf columns and assemble records only at the end, if at all.

There is one more asymmetry worth noting. The encoding is lossless with respect to the logical schema, but it is not self-describing with respect to the schema itself: the levels are meaningless without the path that defines their maximum values. A file that records levels but not the schema tree cannot be decoded, and a schema change that adds an optional field to a path changes the maximum definition level, which changes the meaning of every stored level value in that column. This is why schema evolution on nested columns is more constrained than on flat ones, a point that connects to Schema Evolution Without Rewriting Files.