ch04Nested data

What you build: The RLE/bit-packing hybrid for levels, a column read into triples, and records rebuilt from them.

The question#

How can nested, nullable records live in flat columns without losing their shape?

ch03 rebuilt the schema tree and gave every leaf two numbers: a maximum definition level and a maximum repetition level. Every column of tiny.parquet had zero for both, and its pages held values and nothing else. This chapter reads a file whose columns do not.

A column stores a flat sequence of values. A record can hold a null, a list, an empty list, or a list of structs that each hold a list. Store only the values and the shape is gone: nothing says which record a value belongs to, where one list ends and the next begins, or whether a missing value was null, in an empty list, or under a null parent. Parquet keeps the shape in two small integers stored beside every value, a method it takes from Google’s Dremel paper.

The experiment#

Four orders, every way of being missing#

nested.parquet holds four orders. Each has an optional email, an optional list of tags, and an optional list of items, where each item has a sku and its own list of discounts. Between them the orders contain a null string, a null list, an empty list, a list holding a null, and a list inside a list. Appendix B says how pyarrow wrote it.

Each step below is a few lines of code. In Python, run them in the page, change them with Edit, and run them again. In Rust, open them in a Codespace, or run one at a desk with cargo run -p walkthroughs --bin and its name. Each step finds the footer as ch02 did and rebuilds the schema as ch03 did.

The levels as stored. A column chunk is a run of pages, each a header and a body. ch06 reads pages in full; here the reader’s walk_pages finds the one page of items[].discounts[], the discounts of every item of every order. Unpack the start of its body by hand:

# Unpack a page's levels by hand: a length, a run header, then levels, lowest bits first.
import sys
sys.path.insert(0, "python")  # the book's reader, from the repository's python/ directory
from parquet_lab import metadata, pages, schema

data = open("fixtures/nested.parquet", "rb").read()
length = int.from_bytes(data[-8:-4], "little")
base = len(data) - 8 - length
md = metadata.decode_file_metadata(data[base:-8], base)
column = 4  # items[].discounts[]; try 2, which is tags[], or 1, which is email
leaf = schema.leaves(schema.build(md.schema))[column]
chunk = md.row_groups[0].columns[column].byte_range()
page = pages.walk_pages(data[chunk.start:chunk.end], chunk.start)[0]  # its one page
body, slots = data[page.body_span.start:page.body_span.end], page.num_values

at = 0  # repetition levels come first, then definition levels, then values
for name, most in (("rep", leaf.max_repetition_level), ("def", leaf.max_definition_level)):
    if most == 0:
        print(f"{name}: none stored, since the maximum is 0")
        continue
    size = int.from_bytes(body[at:at + 4], "little")  # a version-1 page's length prefix
    header, width = body[at + 4], most.bit_length()  # a ULEB128 header, one byte here
    bits = int.from_bytes(body[at + 5:at + 4 + size], "little")
    kind = f"{name}: {size} bytes, header {header:02x},"
    if header & 1:  # bit-packed: header >> 1 groups of eight levels, width bits each
        groups = header >> 1
        levels = [bits >> (i * width) & (1 << width) - 1 for i in range(slots)]
        padding = f"(+{8 * groups - slots} padding)"
        print(kind, f"bit-packed, {groups} group:", *levels, padding)
    else:  # RLE: header >> 1 copies of the one level that follows
        print(kind, f"RLE, {header >> 1} copies of", bits)
    at += 4 + size

//! Unpack a page's levels by hand: a length, a run header, then levels, lowest bits first.

use parquet_lab::metadata::decode_file_metadata;
use parquet_lab::{pages, schema};

fn main() {
    let data =
        std::fs::read("fixtures/nested.parquet").expect("run this from the repository's root");
    let n = data.len();
    let length = u32::from_le_bytes(data[n - 8..n - 4].try_into().unwrap()) as usize;
    let base = n - 8 - length;
    let md = decode_file_metadata(&data[base..n - 8], base as u64).expect("a footer");
    let column = 4; // items[].discounts[]; try 2, which is tags[], or 1, which is email
    let leaf = &schema::leaves(&schema::build(&md.schema).expect("a schema"))[column];
    let chunk = md.row_groups[0].columns[column].byte_range();
    let (start, end) = (chunk.start as usize, chunk.end as usize);
    let pages = pages::walk_pages(&data[start..end], chunk.start).expect("pages");
    let page = &pages[0]; // its one page
    let body = &data[page.body_span.start as usize..page.body_span.end as usize];
    let slots = page.num_values.expect("a data page") as usize;

    let mut at = 0; // repetition levels come first, then definition levels, then values
    for (name, most) in [
        ("rep", leaf.max_repetition_level),
        ("def", leaf.max_definition_level),
    ] {
        if most == 0 {
            println!("{name}: none stored, since the maximum is 0");
            continue;
        }
        // A version-1 page's length prefix, then a ULEB128 header, one byte here.
        let size = u32::from_le_bytes(body[at..at + 4].try_into().unwrap()) as usize;
        let (header, width) = (body[at + 4], 32 - most.leading_zeros());
        let bits = body[at + 5..at + 4 + size]
            .iter()
            .rev()
            .fold(0u64, |acc, b| acc << 8 | u64::from(*b));
        let kind = format!("{name}: {size} bytes, header {header:02x},");
        if header & 1 == 1 {
            // Bit-packed: header >> 1 groups of eight levels, width bits each.
            let groups = (header >> 1) as usize;
            let level = |i: usize| bits >> (i as u32 * width) & ((1 << width) - 1);
            let levels: Vec<String> = (0..slots).map(|i| level(i).to_string()).collect();
            let padding = format!("(+{} padding)", 8 * groups - slots);
            println!(
                "{kind} bit-packed, {groups} group: {} {padding}",
                levels.join(" ")
            );
        } else {
            // RLE: header >> 1 copies of the one level that follows.
            println!("{kind} RLE, {} copies of {bits}", header >> 1);
        }
        at += 4 + size;
    }
}

The body opens with two streams of small integers, one line each. The first holds the repetition levels, the second the definition levels, and the values come after both. pyarrow wrote a version-1 data page, so each stream starts with its length in four bytes. Then comes a header byte, which says how the levels are packed, and the levels themselves. Each takes as few bits as the column’s maximum needs. The step takes the maximums from the schema, as ch03 counted them: 2 for repetition and 6 for definition, so two bits and three.

Count the levels in each stream: one per slot. There are more slots than orders, and more than discounts. The levels say which slot starts a record, which holds a discount, and which holds nothing.

Change column to 2, which is tags[], and its levels need fewer bits. Change it to 1, which is email: nothing on its path repeats, so the page stores no repetition levels at all.

The levels, read by the reader. The book’s reader decodes the same streams, pairs each slot’s two levels with its value, and rebuilds the records from them. Ask it for tags:

# The book's reader: every slot of a column as its two levels and a value, then the records.
import sys, json
sys.path.insert(0, "python")  # the book's reader, from the repository's python/ directory
from parquet_lab import column, logical, metadata, nested, schema

data = open("fixtures/nested.parquet", "rb").read()
length = int.from_bytes(data[-8:-4], "little")
base = len(data) - 8 - length
md = metadata.decode_file_metadata(data[base:-8], base)
root = schema.build(md.schema)
name = "tags"  # try "email", "order_id", or "items", which has two columns

for leaf in (leaf for leaf in schema.leaves(root) if leaf.path[0] == name):
    fields = nested.path_fields(root, leaf)  # each field on the path, with its levels
    triples = column.read_column(data, md.row_groups[0].columns[leaf.column], leaf).triples
    most = f"definition {leaf.max_definition_level}, repetition {leaf.max_repetition_level}"
    print(f"{fields[-1].label}  max levels: {most}\nr d value")
    for t in triples:
        v = t.value
        v = None if v is None else logical.value_json(leaf.physical_type, leaf.logical_type, v)
        print(t.rep, t.definition, json.dumps(v))
    for record in nested.assemble(fields, leaf, triples):
        print(json.dumps(record))

//! The book's reader: every slot of a column as its two levels and a value, then the records.

use parquet_lab::json::Json;
use parquet_lab::logical::value_json;
use parquet_lab::metadata::decode_file_metadata;
use parquet_lab::{column, nested, schema};

fn main() {
    let data =
        std::fs::read("fixtures/nested.parquet").expect("run this from the repository's root");
    let n = data.len();
    let length = u32::from_le_bytes(data[n - 8..n - 4].try_into().unwrap()) as usize;
    let base = n - 8 - length;
    let md = decode_file_metadata(&data[base..n - 8], base as u64).expect("a footer");
    let root = schema::build(&md.schema).expect("a schema");
    let name = "tags"; // try "email", "order_id", or "items", which has two columns

    for leaf in schema::leaves(&root).iter().filter(|l| l.path[0] == name) {
        let fields = nested::path_fields(&root, leaf); // each field on the path, with its levels
        let chunk = &md.row_groups[0].columns[leaf.column];
        let read = column::read_column(&data, chunk, leaf).expect("a column");
        let triples = read.triples;
        let label = &fields.last().expect("a path").label;
        let (d, r) = (leaf.max_definition_level, leaf.max_repetition_level);
        println!("{label}  max levels: definition {d}, repetition {r}\nr d value");
        let logical = leaf.logical_type.as_ref();
        for t in &triples {
            let v = t.value.as_ref();
            let v = v.map_or(Json::Null, |v| value_json(leaf.physical_type, logical, v));
            println!("{} {} {}", t.rep, t.def, v.to_json());
        }
        for record in nested::assemble(&fields, leaf, &triples) {
            println!("{}", record.to_json());
        }
    }
}

One row per slot: its repetition level r, its definition level d, and its value. The reader calls each row a triple. Only a triple whose d is the column’s maximum has a value.

The first two rows are the first order’s two tags, and the r of 1 on the second says it continues the same list. The next two rows have no value, and each is still a whole record: an empty list and a null list. Without their slots, the reader would not know those records existed. The last row is a null inside a list, one level below the maximum. The records at the end are rebuilt from these rows alone.

Change name to "email", "order_id" or "items", and watch the maximum levels set what a row can say. items has two columns, and each rebuilds its own view of the same records.

What the levels say#

The file’s schema, as ch03 rebuilt it:

message schema {
  required int64 order_id;
  optional binary email (STRING);
  optional group tags (LIST) {
    repeated group list {
      optional binary element (STRING);
    }
  }
  optional group items (LIST) {
    repeated group list {
      optional group element {
        optional binary sku (STRING);
        optional group discounts (LIST) {
          repeated group list {
            optional int32 element;
          }
        }
      }
    }
  }
}

A list is three levels of schema, not one. An optional group annotated LIST can be null. Inside it, a repeated group called list makes the repetition. Inside that, an optional element can be null. That shape is what lets a file tell a null list from an empty list from a list holding a null. The book writes these columns the way a reader of the data would, tags[] rather than tags.list.element:

The definition level d counts how many optional or repeated fields on the path are present for this slot. At the maximum, the value is there. Below it, the first missing field is the one whose definition level is d + 1. For tags[], as the second step printed:

• d = 0: tags itself is absent. The list is null.
• d = 1: tags is present, but its repeated list group has no entries. The list is empty.
• d = 2: an entry exists, but its element is absent. The element is null.
• d = 3: the value is present.

The repetition level r says where the slot sits in the nesting. Zero starts a new record. Any other value names the repeated field that gains a new element: here, r = 1 adds an element to tags.

email is the simplest case. One optional field is on its path, so its maximum definition level is 1: a d of 0 is a null and a d of 1 is a value. No field on the path is repeated, so the page stores no repetition levels, as the first step found, and the reader takes every r as zero.

Two lists deep#

Every item has its own list of discounts, so items[].discounts[] has two repeated fields on its path and a maximum repetition level of 2. Now r has three meanings: 0 is a new record, 1 is a new item, and 2 is another discount in the same item. These are the levels the first step unpacked, with what the reader makes of each:

{"items":[{"discounts":[5,10]},{"discounts":[]}]}
{"items":[]}
{"items":[{"discounts":[7]}]}
{"items":null}

Read the third row. Its r of 1 says a new item has started. Its d of 4 says the item exists and has a discounts list, but that list has no entries. That is item B2, whose discounts are empty, and the reader can tell it from a record with no items at all, which is the next row.

How the levels are stored#

Levels are small integers with a known maximum, so a writer stores them in as few bits as that maximum needs, using the RLE / bit-packing hybrid. The stream is a sequence of runs, and each starts with a ULEB128 header whose lowest bit gives the run’s kind:

• Lowest bit 0: an RLE run. The rest of the header is a count, and one value follows. A column with no nulls has definition levels that are all the maximum, and a whole page of them is one run of a couple of bytes.
• Lowest bit 1: a bit-packed run. The rest of the header is a number of groups of eight values, each packed into the bit width, least significant bit first.

The discount column’s levels are short and varied, so the writer bit-packed both streams. The header 03 that the first step printed is binary 11: bit-packed, one group of eight. The repetition levels need two bits each, so eight of them take two bytes; the definition levels need three bits each and take three. With the header byte, those are the stream lengths the step printed. The page has six slots, so the last two values in each group are padding.

Building it#

The steps called three parts of the book’s reader: the decoder of the level streams, the split of a page’s body into levels and values, and the rebuild of records. This section builds them, in both languages, and the tabs switch every excerpt on the page between them.

Decoding the hybrid#

The decoder reads a header and decides the run’s kind from its low bit. Every run keeps the span of its header and its body, so a caller can say which bytes held which levels. An RLE run is one value, stored in as many whole bytes as the bit width needs:

def decode(data: bytes, base: int, width: int, count: int) -> list[Run]:
    """Decode ``count`` values of ``width`` bits from ``data``, which start at file offset
    ``base``."""
    r = ByteReader(data, base)
    runs = []
    produced = 0
    value_bytes = (width + 7) // 8
    while produced < count:
        header_start = r.offset()
        header = r.read_uleb128()
        header_span = Span(header_start, r.offset())
        wanted = count - produced
        if header & 1 == 0:
            # RLE: one value, repeated.
            raw, body = r.read_bytes(value_bytes)
            value = int.from_bytes(raw, "little")
            run = Run(RLE, header_span, body, [value] * min(header >> 1, wanted))

pub fn decode(
    bytes: &[u8],
    base: u64,
    bit_width: u32,
    count: usize,
) -> Result<Vec<Run>, BytesError> {
    let mut r = ByteReader::new(bytes, base);
    let mut runs = Vec::new();
    let mut produced = 0;
    let value_bytes = bit_width.div_ceil(8) as usize;
    while produced < count {
        let header_start = r.offset();
        let header = r.read_uleb128()?;
        let header_span = Span::new(header_start, r.offset());
        let wanted = count - produced;
        let run = if header & 1 == 0 {
            // RLE: one value, repeated.
            let repeat = (header >> 1) as usize;
            let (raw, body) = r.read_bytes(value_bytes)?;
            let mut value = 0u32;
            for (i, b) in raw.iter().enumerate() {
                value |= u32::from(*b) << (8 * i);
            }
            Run {
                kind: RunKind::Rle,
                header: header_span,
                body,
                values: vec![value; repeat.min(wanted)],
            }

A bit-packed run is the header’s count of groups, each eight values of the bit width. The last group of a stream can run past the count of values, as it did in the first step, and the padding is dropped:

            # Bit-packed: groups of eight values, packed least significant bit first.
            groups = header >> 1
            raw, body = r.read_bytes(groups * width)
            n = min(groups * 8, wanted)
            run = Run(BIT_PACKED, header_span, body, [unpack(raw, i, width) for i in range(n)])
        if not run.values and run.body.length == 0:
            # A run that produces nothing and consumes nothing would loop forever.
            raise UnexpectedEnd(header_start, 1)
        produced += len(run.values)
        runs.append(run)
    return runs

            // Bit-packed: groups of eight values, packed least significant bit first.
            let groups = (header >> 1) as usize;
            let (raw, body) = r.read_bytes(groups * bit_width as usize)?;
            let total = groups * 8;
            let mut values = Vec::with_capacity(total.min(wanted));
            for i in 0..total.min(wanted) {
                values.push(unpack(raw, i, bit_width));
            }
            Run {
                kind: RunKind::BitPacked,
                header: header_span,
                body,
                values,
            }
        };
        if run.values.is_empty() && run.body.is_empty() {
            // A run that produces nothing and consumes nothing would loop forever.
            return Err(BytesError::UnexpectedEnd {
                offset: header_start,
                wanted: 1,
            });
        }
        produced += run.values.len();
        runs.push(run);
    }
    Ok(runs)
}

Bit-packed values are read one bit at a time, least significant first, which makes the packing order explicit:

def unpack(raw: bytes, i: int, width: int) -> int:
    """The ``i``\\ th value of ``width`` bits in a little-endian bit stream."""
    value = 0
    for bit in range(width):
        at = i * width + bit
        if raw[at // 8] >> (at % 8) & 1:
            value |= 1 << bit
    return value

fn unpack(raw: &[u8], i: usize, bit_width: u32) -> u32 {
    let mut value = 0u32;
    for bit in 0..bit_width as usize {
        let at = i * bit_width as usize + bit;
        if raw[at / 8] >> (at % 8) & 1 == 1 {
            value |= 1 << bit;
        }
    }
    value
}

Splitting a page into levels and values#

A data page body holds the repetition levels, then the definition levels, then the values. A level stream is present only when the column’s maximum for it is above zero. In a version-1 data page each stream starts with a four-byte length. The second version of the data page, which ch06 reads, gives both lengths in its header instead, so its streams have no prefix:

        rep_levels = (
            level_stream(r, leaf.max_repetition_level, count, rep_len)
            if leaf.max_repetition_level > 0
            else None
        )
        def_levels = (
            level_stream(r, leaf.max_definition_level, count, def_len)
            if leaf.max_definition_level > 0
            else None
        )
        reps = rle.values(rep_levels[1]) if rep_levels else [0] * count
        defs = rle.values(def_levels[1]) if def_levels else [leaf.max_definition_level] * count

        let rep_levels = if leaf.max_repetition_level > 0 {
            Some(level_stream(
                &mut r,
                leaf.max_repetition_level,
                count,
                rep_len,
            )?)
        } else {
            None
        };
        let def_levels = if leaf.max_definition_level > 0 {
            Some(level_stream(
                &mut r,
                leaf.max_definition_level,
                count,
                def_len,
            )?)
        } else {
            None
        };
        let reps = rep_levels
            .as_ref()
            .map(|(_, runs)| rle::values(runs))
            .unwrap_or(vec![0; count]);
        let defs = def_levels
            .as_ref()
            .map(|(_, runs)| rle::values(runs))
            .unwrap_or(vec![leaf.max_definition_level; count]);

Only slots whose definition level is the maximum have a value, so the reader counts those, and decodes that many PLAIN values after the levels (the plain module).

Rebuilding records#

The reader turns triples back into records by splitting them. Records split where r is 0. Within a record, a repeated field’s triples split into elements wherever r is at most that field’s repetition level, and a field whose first triple has too low a d is null or, for a repeated field, empty:

    def field_value(i: int, ts: list[Triple]) -> object:
        """The value of ``fields[i]``, given the triples of one instance of its parent."""
        f = fields[i]
        if f.repetition == REPEATED:
            if ts[0].definition < f.definition:
                return []
            elements, start = [], 0
            for j in range(1, len(ts) + 1):
                if j == len(ts) or ts[j].rep <= f.rep:
                    elements.append(element_value(i, ts[start:j]))
                    start = j
            return elements
        if ts[0].definition < f.definition:
            return None
        if f.is_list and i + 1 < len(fields):
            # A LIST group is its list: present it as the array, not as a struct holding one.
            return field_value(i + 1, ts)
        return element_value(i, ts)

    fn field_value(&self, i: usize, triples: &[Triple]) -> Json {
        let fields = self.fields;
        let f = &fields[i];
        if f.repetition == Repetition::Repeated {
            if triples[0].def < f.def {
                return Json::Arr(vec![]);
            }
            let mut elements = Vec::new();
            let mut start = 0;
            for j in 1..=triples.len() {
                if j == triples.len() || triples[j].rep <= f.rep {
                    elements.push(self.element_value(i, &triples[start..j]));
                    start = j;
                }
            }
            return Json::Arr(elements);
        }
        if triples[0].def < f.def {
            return Json::Null;
        }
        if f.is_list && i + 1 < fields.len() {
            // A LIST group is its list: present it as the array, not as a struct holding one.
            return self.field_value(i + 1, triples);
        }
        self.element_value(i, triples)
    }

Checking it#

The fixture tests read every column of every fixture from its page bytes, rebuild the records, and compare them with the rows pyarrow reported when it wrote the file, reduced to that one column:

python3 -m pytest python/tests -k records_rebuilt

cargo test -p parquet-lab --test fixtures records_rebuilt

Ask a library#

pyarrow reads the levels and does not show them. It turns them into Arrow’s shape for a list: an array of offsets, where list i runs from offsets[i] to offsets[i + 1] in one array of values, and a validity bitmap saying which lists are null. The parquet crate’s column reader works below Arrow, and hands you the levels as the page stores them:

# The same column from pyarrow, which reads the levels into Arrow's own shape and hides them.
import pyarrow.parquet as pq

tags = pq.read_table("fixtures/nested.parquet", columns=["tags"]).column("tags")
tags = tags.combine_chunks()  # one Arrow ListArray: offsets, a validity bitmap, and values
print("offsets:", tags.offsets.to_pylist())  # list i is values[offsets[i]:offsets[i + 1]]
print("null lists:", tags.is_null().to_pylist())
print("values:", tags.values.to_pylist())
print("records:", tags.to_pylist())

//! The same column from the `parquet` crate, whose column reader hands you the levels as stored.

use parquet::column::reader::get_typed_column_reader;
use parquet::data_type::ByteArrayType;
use parquet::file::reader::{FileReader, SerializedFileReader};

fn main() {
    let file = std::fs::File::open("fixtures/nested.parquet")
        .expect("run this from the repository's root");
    let reader = SerializedFileReader::new(file).expect("a Parquet file");
    let row_group = reader.get_row_group(0).expect("a row group");
    let column = row_group.get_column_reader(2).expect("a column"); // tags[]
    let mut tags = get_typed_column_reader::<ByteArrayType>(column);
    let (mut defs, mut reps, mut values) = (Vec::new(), Vec::new(), Vec::new());
    let (records, _, _) = tags
        .read_records(usize::MAX, Some(&mut defs), Some(&mut reps), &mut values)
        .expect("the column's pages");
    println!("{records} records");
    println!("rep: {reps:?}");
    println!("def: {defs:?}");
    let values: Vec<&str> = values.iter().map(|v| v.as_utf8().unwrap()).collect();
    println!("values: {values:?}");
}

The two describe the same four records of tags. In pyarrow’s offsets, the empty list and the null list both have length zero, and only the validity bitmap tells them apart: the job a definition level of 1 or 0 did in the file. A null element is a null in the values array, where the file stored no value at all. The crate prints the repetition and definition levels the reader decoded in the second step. Its values hold only the present strings, and it counts records where the repetition level is zero.

In Python, the first run loads pyarrow into the page, a much larger download than the other steps. In Rust the step needs the parquet crate, in walkthroughs/libraries, so it runs in a Codespace or at a desk:

cargo run -q --manifest-path walkthroughs/libraries/Cargo.toml --bin levels_with_a_library

What this cannot tell you#

How several columns become one record. The reader rebuilds each column’s view of a record on its own. A query engine that wants whole records runs the same splitting over several columns at once, in step. ch12 describes what an engine does with the columns a query needs.

How pages divide a record. Each fixture column is one page. When a column spans pages, a record can begin in one and continue in the next under data page version 1. A version-2 data page always starts a new record, which ch06 shows.

How other formats keep the shape. Apache Arrow, in memory, stores offsets and validity bitmaps per nesting level instead of levels, as pyarrow showed for one list. Converting between the two is much of a Parquet reader’s work in practice; this reader produces JSON instead.

Legacy list layouts. Older writers produced two-level lists and other shapes. The specification’s backward-compatibility rules say how to read them; this reader follows the standard three-level form only.

Key takeaways#

Problems#

Three, in exercises/python/nested_data.py, or in Rust in exercises/src/nested_data.rs. The first two have tests. The third has none.

The editor below holds the Python stubs and keeps your edits in this browser. Run the tests runs the graders in the page, the same tests that run at a desk.

4.1 The hybrid. Decode an RLE / bit-packing hybrid stream. The test uses every level stream in the fixture and a thousand generated streams.

4.2 A list from its levels. Rebuild a list of optional strings from its levels and values. The test compares with pyarrow on the fixture and with the reader on generated levels.

4.3 Your own nested data. No test: the data is yours. Take a nested column from your own Parquet files and run PYTHONPATH=python python3 -m parquet_lab levels FILE COLUMN or cargo run -p pqlab -- levels FILE COLUMN, where COLUMN is its position among the leaves. Pick three records and write down, before looking, the levels you expect for each value slot. Then compare. A good answer explains every disagreement. If your records never reach the column’s maximum repetition level, say what the schema allows that the data never uses.

For the Rust stubs, or to work at a desk, run the chapter’s graders with these commands. Add -k problem_4_1 in Python, or problem_4_1 before the -- in Rust, to run one problem:

python3 -m pytest exercises/python/tests/test_nested_data.py --problems

cargo test -p exercises --test nested_data -- --ignored

Where to go next#

• The levels come from Melnik and others’ Dremel paper, section 4.
• The standard LIST and MAP layouts, and the backward-compatibility rules for older ones, are in the format repository’s LogicalTypes.md.
• The hybrid encoding is specified in Encodings.md.
• ch05 uses the same hybrid for dictionary indices, and adds the encodings for values.

Built from commit c32f48e.