Build a Typed Database Expression Engine in Rust

A hand-written loop for i32 + i32 is easy:

for row in 0..left.len() {
    output.push(match (left.get(row), right.get(row)) {
        (Some(left), Some(right)) => Some(
            std::ops::Add::add(std::num::Wrapping(left), std::num::Wrapping(right)).0,
        ),
        _ => None,
    });
}

The design problem appears when the engine must also borrow strings without copying, read constants and Indexed views, promote mixed numeric types, reject bad arity and lengths, and choose a function from runtime names. Repeating those decisions in every loop makes each new function a new place for type drift, null bugs, and inconsistent errors.

You will build the connections that move those decisions out of the row loop. The workspace starts with two crates: type-exercise-starter-core owns storage, views, and reusable evaluators; type-exercise-starter-expr depends on it and owns concrete operations and binding. You will first write the small cases by hand. Once their duplication is visible, generic unary, binary, and ternary auto-vectorizers let a new expression author supply only one scalar operation.

Read the map in four directions:

1. DataType tells the planner what a value means; PhysicalType selects storage.
2. Scalar, ScalarRef, Array, and ArrayBuilder form one compile-time family, while erased enums cross runtime boundaries through checked conversions.
3. ColumnViewImpl normalizes array, constant, Indexed, and typed-null representations before one selected typed expression enters its row loop.
4. The facade depends on core, but core never depends on a concrete arithmetic, Boolean, or string operation. That one-way edge keeps the reusable loop independent of the function catalog.

The numeric chapters keep scalar hooks statically typed, auto-vectorize them through monomorphized generic helpers, and erase only whole-batch adapters. For signed addition, subtraction, and multiplication, std::num::Wrapping<T> makes the chosen cross-profile overflow behavior explicit while still using the standard operator traits.

Nullability is value state—Option or validity—not a DataType::Nullable variant. A one-level List adds offsets and independent outer/child validity; it does not add an aggregate engine.

What you need to know

You should be comfortable with Rust enums, traits, references, Option, and ordinary Cargo use. The course introduces generic associated types, checked runtime erasure, typestate, and return-position impl Trait in the concrete places that need them.

Each checkpoint begins from the preceding completed snapshot, names the learner-owned change, and gives an exact command for useful feedback. Passing the supplied test is necessary; you should also be able to explain why the new boundary exists and which failure it prevents.

The ten cumulative checkpoints form five modules:

1. Type families and nullable views (Checkpoints 1–2) connect owned and borrowed values, then normalize Array, Constant, Indexed, and typed-null inputs.
2. Shared evaluation and transactional strings (Checkpoints 3–4) lift scalar operations over batches and publish variable-width rows without partial writes.
3. Shape specialization and binary semantics (Checkpoints 5–6) specialize common column shapes while preserving fallback behavior, then separate total, fallible, and nullable-aware binary policies.
4. Runtime erasure and the physical catalog (Checkpoints 7–8) erase whole typed expressions behind one checked batch boundary and make concrete operations discoverable.
5. Logical binding, one-level Lists, and batch async (Checkpoints 9–10) resolve runtime calls, add checked nullable List storage, and defer one already-bound batch in a borrowing future.

Treat each checkpoint as roughly half a day. An experienced Rust learner can finish the course in about five working days; newer learners should expect to take longer. Checkpoint 10 is the terminal unit; cargo x copy-test --chapter 10 copies the complete cumulative supplied contract.

Continue to Environment Setup.

Environment Setup

Install rustup, update stable Rust, and install mdBook plus cargo-expand:

rustup update stable
rustc --version
cargo install cargo-expand --locked
cargo expand --version

The repository selects rolling stable and Rust Edition 2024. It does not claim an older minimum supported Rust version.

Check out the starting state

Clone the repository, then create a working branch from main:

git fetch origin
git switch --create course-work --track origin/main

Choose another branch name if course-work already exists. Verify the untouched starter:

cargo check -p type-exercise-starter-core --locked
cargo test -p type-exercise-starter-expr --lib --locked

Both commands should pass. Chapter tests do not exist in the starter until you copy them.

Follow the learner boundary

• Work only in implementation files under type-exercise-starter/expr/src/ and type-exercise-starter/core/src/.
• Do not edit supplied-tests/src/lib.rs or copied files under supplied-tests/src/.
• Do not read, search, diff, or copy type-exercise/, archived/, Git history, or an online solution while implementing a chapter.
• Use the chapter, copied destination test, compiler diagnostics, and official Rust documentation.
• Add only the types, modules, dependencies, and public APIs owned by the current chapter.

The only permitted reference-to-starter operation is:

cargo x copy-test --chapter <N>

Run it without opening the source test. The command copies the cumulative tests through chapter N, removes later managed tests, and regenerates the module list. Afterward, you may read the copied destination. Its first focused run should be red until you implement the chapter.

Focused chapter commands target type-exercise-starter-supplied-tests. For an implementation-only check, target either the facade package, type-exercise-starter-expr, or the reusable framework package, type-exercise-starter-core. Their sources live separately under expr/src/ and core/src/. Dependencies point from supplied tests to the facade to core, with a direct supplied-tests-to-core edge for framework witnesses.

Preview the course

mdbook serve course --open

Continue to Checkpoint 1: Build Physical Types and Arrays.

Checkpoint 1: Build Physical Types and Arrays

Every later expression needs values it can read and arrays it can write. In this checkpoint, you will connect eight physical families and give nullable fixed-width, string, and Decimal values their dense array storage.

Start by copying the public checkpoint test into your starter and running it:

cargo x copy-test --chapter 1
cargo test -p type-exercise-starter-supplied-tests chapter_1 --locked

The copied test should not compile yet. Let its missing names and trait implementations become your work list, and make the changes under type-exercise-starter/core/src rather than in the test.

Connect the physical families

An execution engine needs both compile-time Rust types and runtime tags. Define these eight rows in physical_type.rs and variant_catalog.rs, keeping this order:

PhysicalType carries runtime information. Most variants are simple tags; Decimal(DecimalType) also carries precision and scale. The descriptor-free PhysicalFamily lets PHYSICAL_FAMILY_CATALOG list the same eight supported rows without inventing Decimal metadata.

In scalar.rs, complete the reciprocal relationships among Scalar, ScalarRef, and Array. The generic relationship should be strong enough that code with only S: Scalar can discover S::RefType<'a> and S::ArrayType, and an array can point back to the same scalar family.

The generic associated type matters for strings: an integer read is copied, but an &'a str must stay tied to the array that owns its bytes.

fn first_value<S: Scalar>(array: &S::ArrayType) -> Option<S> {
    array.get(0).map(ScalarRef::to_owned_scalar)
}

Use the catalog callback to generate the repeated scalar and array connections, then implement the erased ScalarImpl, ScalarRefImpl, and ArrayImpl boundaries. Upcasts through From cannot fail. Downcasts through TryFrom must report the actual and expected physical types instead of panicking or reinterpreting bytes.

Map logical types to storage

Define DecimalType and Decimal in decimal.rs. Check precision and scale when the descriptor is created, and reject an unscaled coefficient that cannot fit its precision. One descriptor belongs to the whole Decimal array, so precision and scale are not repeated beside each i128.

Define the planner-facing DataType in data_type.rs. Map SQL names such as SmallInt, Integer, Varchar, and Decimal to the physical families above. Add the string and numeric classifiers used by the public test.

Store fixed-width values densely

Replace the marker types in array/primitive_array.rs with two buffers:

• Vec<T> contains one value slot per row.
• BitVec contains one validity bit per row; true means non-null.

A null row still has a value slot. Store T::default() there and treat it as ignored—the validity bit is the only source of nullness. Implement the six fixed-width aliases with one generic PrimitiveArray<T> and one generic builder. Expose read-only values() and validity() accessors so callers can inspect the layout without mutating it.

Store strings without one allocation per row

In array/string_array.rs, use three buffers:

• Vec<u8> stores all UTF-8 bytes.
• Vec<usize> stores row_count + 1 nondecreasing offsets.
• BitVec stores row validity.

Row i occupies offsets[i]..offsets[i + 1]. Null and empty strings may repeat an offset; the validity bit distinguishes them. get should return an &str borrowed directly from the byte buffer.

This checkpoint stops at storage and borrowed reads. Transactional string writing, slicing, and column views arrive when the evaluator needs them.

Keep Decimal metadata stable

In array/decimal_array.rs, wrap dense i128 storage with one DecimalType. Validate raw-part lengths and every non-null coefficient. If a new row carries different Decimal metadata, reject it before changing the builder’s length or buffers.

Run the checkpoint

Run the same learner command until all five public behaviors pass:

cargo x copy-test --chapter 1
cargo test -p type-exercise-starter-supplied-tests chapter_1 --locked

You can compare against the completed checkpoint without changing the starter:

cargo test -p type-exercise-checkpoint-01-supplied-tests --locked
cargo check -p type-exercise-checkpoint-01-core --locked

You are done when the catalog has all eight rows, dense arrays preserve values and null positions, string reads borrow from the shared bytes, Decimal builders reject incompatible metadata without mutation, and erased downcasts fail safely for the wrong family.

The next checkpoint will add nullable Array, Constant, and Indexed column views. It will use these arrays rather than replacing them.

Checkpoint 2: Add Nullable Column Views

Checkpoint 1 gave you owned arrays. Now let an expression borrow those arrays in three useful shapes without copying their values:

• an Array view reads rows in their original order;
• a Constant repeats one value or typed null for a requested length; and
• an Indexed view remaps rows through a borrowed index slice.

Begin from your completed Checkpoint 1 workspace. Copy the cumulative tests, then run only the new Chapter 2 cases once:

cargo x copy-test --chapter 2
cargo test -p type-exercise-starter-supplied-tests chapter_2 --locked

That focused test should fail because ColumnViewImpl and ColumnView do not exist yet, while the Chapter 1 implementation should still compile. Keep the copied tests unchanged.

Enable the learner-owned module

Open type-exercise-starter/core/src/lib.rs and enable the existing column module and export. Then implement type-exercise-starter/core/src/column.rs.

The erased view must accept every Checkpoint 1 physical family. Its representation stays private; callers create each shape through checked constructors:

let values: ArrayImpl = I32Array::from_slice(&[Some(10), None, Some(30)]).into();
let array = ColumnViewImpl::array(&values);

let constant = ColumnViewImpl::constant(ScalarRefImpl::Int32(7), 3);
let nulls = ColumnViewImpl::null(PhysicalType::Int32, 3);

let indices = [2, 1, 2, 0];
let indexed = ColumnViewImpl::indexed(&indices, &values)?;

All three forms answer the same questions: len, is_empty, physical_type, and get. They borrow their inputs for lifetime 'a, so construction does not allocate another array.

Preserve nulls and physical types

An array view delegates its length, physical type, and row read to the borrowed ArrayImpl. A constant stores one Option<ScalarRefImpl<'a>> and a length:

• constant(value, len) records value.physical_type() and returns that same value for every row;
• null(physical_type, len) records the supplied type and returns None for every row.

The explicit type on a null constant is essential: None carries no scalar variant, but later code must still distinguish a null Int64 column from a null String column.

Treat row < len as the public precondition for get, matching array access in this course. Assert that bound before reading the private representation. Inside a valid range, None means a SQL null rather than an out-of-bounds sentinel.

Validate indexed views once

An indexed view borrows &[u32] and an &ArrayImpl. Its output length is the number of indices, and its physical type is the values array’s type. Output row r reads values.get(indices[r] as usize).

Validate every index in ColumnViewImpl::indexed. If an index falls outside the values array, return an error that identifies the bad index and its output row. Once construction succeeds, every output row is safe to read without repeating index validation or materializing a gathered array.

For example, values ["zero", NULL, "two"] with indices [2, 1, 2, 0] read as ["two", NULL, "two", "zero"]. The two appearances of "two" borrow the same underlying string bytes.

Check the scalar family once

ColumnViewImpl is appropriate when a planner knows the physical type only at runtime. Generic code often wants a concrete scalar family. Add ColumnView<'a, S: Scalar> with the same three private forms and implement:

TryFrom<ColumnViewImpl<'a>> for ColumnView<'a, S>

Compare the erased view’s physical_type() with S::PHYSICAL_TYPE before converting its private state. Then downcast the borrowed array, constant scalar, or indexed values array through the checked conversions from Checkpoint 1. A mismatched family returns TypeMismatch before any row is read.

After that one conversion, ColumnView<'a, S>::get returns Option<S::RefType<'a>> directly. For ColumnView<'_, String>, the returned &str still borrows the original StringArray bytes. Decimal remains available through ColumnViewImpl; its precision and scale are runtime metadata, so it does not use the static Scalar relationship.

Run both checkpoints

Run the focused Chapter 2 cases, then the full cumulative package:

cargo test -p type-exercise-starter-supplied-tests chapter_2 --locked
cargo test -p type-exercise-starter-supplied-tests --locked

The cumulative run should pass nine tests: five from Checkpoint 1 and four from Checkpoint 2. You can run the completed snapshot independently:

cargo test -p type-exercise-checkpoint-02-supplied-tests --locked
cargo check -p type-exercise-checkpoint-02-core --locked

You are done when array views preserve null positions, constants repeat values and typed nulls, indexed views validate and remap rows, and typed views reject the wrong family before returning borrowed scalar references.

The next checkpoint will put these views underneath a shared expression loop.

Checkpoint 3: Build Shared Typed Evaluation

You now have owned nullable arrays and borrowed Array, Constant, Null, and Indexed views. This checkpoint turns them into one complete evaluation path: validate a batch once, read typed rows through ColumnView::get, call one scalar function when its inputs are present, and append a newly owned output array. Later optimizations will still fall back to this path.

Begin from your completed Checkpoint 2 workspace. Copy the cumulative tests, then run only the new Chapter 3 cases:

cargo x copy-test --chapter 3
cargo test -p type-exercise-starter-supplied-tests chapter_3 --locked

The focused test should fail because the shared evaluators and the three numeric facade functions do not exist yet. The inherited Chapter 1 and 2 APIs should still compile; keep the copied tests unchanged.

Validate before traversing rows

Enable the existing expression module and export it from type-exercise-starter/core/src/lib.rs. In core/src/expression.rs, implement:

pub fn validate_expression_inputs(
    inputs: &[ColumnViewImpl<'_>],
    expected_types: &[PhysicalType],
) -> anyhow::Result<usize>

Reject an arity mismatch first. Then compare each input’s physical type with its expected type and check that every input has the same length as the first. Return that common length; an empty input list has length zero.

After validation, the row loop can rely on two facts: each typed view has the requested family, and every input can be read at each output row.

Lift scalar functions through typed views

Implement three public evaluators in the same core module:

evaluate_unary::<I, O, _>(input, scalar_function)
evaluate_binary::<L, R, O, _>(left, right, scalar_function)
evaluate_ternary::<A, B, C, O, _>(first, second, third, scalar_function)

Each evaluator follows one sequence:

1. call validate_expression_inputs with the scalar families’ PHYSICAL_TYPE values;
2. convert every erased input to ColumnView<S> once;
3. allocate <O as Scalar>::ArrayType::Builder for the validated row count;
4. read each row with typed get and call the scalar function only when every input is non-null;
5. append the resulting value or null, finish the builder, and erase the owned array.

Use Option::map for unary input and Option::zip for binary and ternary inputs. That makes strict null propagation part of the shared traversal: a null input produces a null output without calling the scalar function.

Let ColumnView::get hide the Array, Constant, and Indexed variants. It is the representation-generic path that remains correct when later checkpoints place faster loops in front of it, and Indexed inputs can continue to use it unchanged.

Choose numeric meaning in the facade

Enable numeric in type-exercise-starter/expr/src/lib.rs. Core owns validation, traversal, null propagation, and output construction. The expr facade chooses concrete types and one scalar operation.

Expose these exact functions from expr/src/numeric.rs:

pub fn add_i16_i32(
    left: ColumnViewImpl<'_>,
    right: ColumnViewImpl<'_>,
) -> anyhow::Result<ArrayImpl>

pub fn negate_i32(input: ColumnViewImpl<'_>) -> anyhow::Result<ArrayImpl>

pub fn clamp_i32(
    value: ColumnViewImpl<'_>,
    lower: ColumnViewImpl<'_>,
    upper: ColumnViewImpl<'_>,
) -> anyhow::Result<ArrayImpl>

add_i16_i32 instantiates i16 + i32 -> i32, converting the left scalar with i32::from. negate_i32 uses wrapping negation. clamp_i32 instantiates the ternary evaluator with i32::clamp. Each function delegates the complete batch to one core evaluator. The facade chooses the numeric meaning without owning a row loop or knowing how the columns are represented.

Run the cumulative contract

Run the focused Chapter 3 cases, then every copied test:

cargo test -p type-exercise-starter-supplied-tests chapter_3 --locked
cargo test -p type-exercise-starter-supplied-tests --locked

The cumulative run should pass twelve tests: five from Checkpoint 1, four from Checkpoint 2, and three from Checkpoint 3. The new cases cover the public numeric facade, mixed numeric types, Array/Constant/Indexed inputs, strict null propagation, owned output, and arity/type/length validation.

You can also run the completed snapshot independently:

cargo test -p type-exercise-checkpoint-03-supplied-tests --locked
cargo test -p type-exercise-checkpoint-03-expr --lib --locked
cargo check -p type-exercise-checkpoint-03-core --locked

You are done when all three scalar arities share one typed-get path and the facade contains only the concrete numeric choices. The next checkpoint tackles the different publication rule needed by variable-width output.

Checkpoint 4: Build Variable-Width Rows Transactionally

Checkpoint 3 can lift a scalar function when one owned value represents an output row. A string row is different: its UTF-8 bytes, terminal offset, and validity bit must become visible together. This checkpoint makes that publication boundary explicit.

Start from your completed Checkpoint 3 workspace, copy the cumulative tests, and run the focused test once before editing:

cargo x copy-test --chapter 4
cargo test -p type-exercise-starter-supplied-tests chapter_4 --locked

The first run should fail on the missing writer surface. Shape specialization and runtime expression types are not needed for this change.

Consume the only unpublished handle

In core/src/array/string_array.rs, add Writer<'a> and WriterUsed<'a> around a borrowed StringArrayBuilder. The transition has this shape:

impl<'a> Writer<'a> {
    pub fn write(
        self,
        write: impl FnOnce(&mut StringValueWriter<'_>),
    ) -> WriterUsed<'a>;
}

The closure may append several borrowed fragments. A successful call then commits one terminal offset and one true validity bit. A null row appends no bytes, repeats the terminal offset, and commits one false bit. If a fallible builder callback stops before publication, truncate the bytes back to their starting length and leave offsets and validity unchanged.

Consuming Writer prevents a scalar callback from skipping publication or publishing twice. The core evaluator recovers the builder from WriterUsed only after that row is complete, then begins the next row.

Lift one borrowed string operation

Add evaluate_writer_binary to core/src/expression.rs. It validates two String inputs and their lengths before reading a row, converts both inputs to typed borrowed views once, and owns the only batch loop. For a non-null pair it passes &str, &str, and a fresh Writer to the callback. For a null pair it publishes one null directly.

Keep this boundary in core. The supplied test passes its borrowed concatenation callback directly, so the concrete String facade is not needed yet.

The callback can concatenate two borrowed strings without allocating a temporary String:

|left, right, writer| writer.write(|value| {
    value.push_str(left);
    value.push_str(right);
})

Run the focused and cumulative contracts:

cargo test -p type-exercise-starter-supplied-tests chapter_4 --locked
cargo test -p type-exercise-starter-supplied-tests --lib --locked

The two Checkpoint 4 tests distinguish empty from null strings, pin bytes and offsets, and prove failed writes do not leak partial bytes. Together with Checkpoints 1–3, the cumulative suite has 14 tests. With publication now transactional, the next checkpoint can change the loop shape without changing its visible results.

Checkpoint 5: Specialize Common Column Shapes

The Checkpoint 3 fallback calls ColumnView::get(row), so Array, Constant, and Indexed inputs all behave correctly. Its flexibility has a cost: every input selects its representation again on every row. In this checkpoint, you will choose the common shapes once per batch and keep the typed fallback for everything else.

Start from your completed Checkpoint 4 workspace, copy the cumulative tests, and run the focused test before editing:

cargo x copy-test --chapter 5
cargo test -p type-exercise-starter-supplied-tests chapter_5 --locked

The first run should fail only because the three auto-vectorization adapters do not exist yet.

Give one loop a concrete input shape

In core/src/column.rs, let the core expression module inspect the private typed representation enum. Keep that enum crate-private: callers still construct checked ColumnViewImpl values and cannot bypass validation.

Add private Array and Constant accessors in core/src/expression.rs. Each accessor exposes the same typed len and nullable get operations, but its concrete type is selected before the loop begins. The loop remains generic over the accessor and no longer matches a representation at every row.

Build these public adapters around those loops:

• auto_vectorize_unary specializes Array and Constant; Indexed uses the existing typed fallback.
• auto_vectorize_binary specializes Array/Array, Array/Constant, Constant/Array, and Constant/Constant; any Indexed input uses the fallback.
• auto_vectorize_ternary specializes Array/Array/Array; every other combination uses the fallback.

Use the same generic scalar relationships as evaluate_unary, evaluate_binary, and evaluate_ternary. The input families may differ, and the output family belongs to the generic output scalar. Validate physical types and equal lengths before selecting a shape.

Preserve one behavior across every path

A concrete loop must keep the fallback’s semantics:

1. read borrowed typed values from each input;
2. call the scalar function only when every required input is non-null;
3. append null otherwise; and
4. return a new owned output array.

Keep the fallback because Indexed inputs still need indirect lookup. Specialize Array and Constant inputs for unary and binary expressions, along with the common ternary case where all three inputs are Arrays. Covering all 27 Array/Constant/Indexed ternary combinations would add a lot of code without introducing new behavior.

Run the focused and cumulative contracts:

cargo test -p type-exercise-starter-supplied-tests chapter_5 --locked
cargo test -p type-exercise-starter-supplied-tests --lib --locked

The three Checkpoint 5 tests compare nullable owned results across Array and Constant combinations, mixed scalar families, Indexed and non-dense ternary fallback, and invalid types and lengths. Together with Checkpoints 1–4, the cumulative suite has 17 tests. Because callers see results and errors rather than an internal route, both specialized and fallback paths must keep the same contract.

The next checkpoint keeps that contract while separating operations that are total, fallible, or nullable-aware.

Checkpoint 6: Separate Binary Semantics

Checkpoint 5 can lift a strict, infallible scalar function over nullable columns. That contract is not enough for every binary operation. Checked division can fail on a non-null row, while SQL Boolean AND and OR sometimes produce a known answer even when one input is null.

You will give each case its own core boundary. Begin from completed Checkpoint 5, then copy the cumulative tests:

cargo x copy-test --chapter 6
cargo test -p type-exercise-starter-supplied-tests chapter_6 --locked

The focused run should fail only because these three public functions are missing from core/src/expression.rs:

• auto_vectorize_primitive_i32;
• try_evaluate_binary; and
• evaluate_nullable_binary.

Implement them in that file. Keep any raw column helper private.

A raw path for total Int32 operations

Some (i32, i32) -> i32 operations are strict, total, and infallible. Wrapping addition is one example: every pair of non-null inputs has exactly one output, and null in either input produces null. auto_vectorize_primitive_i32 may combine the value buffers and validity bitmaps directly for the Array/Constant cross-product:

pub fn auto_vectorize_primitive_i32<F>(
    left: ColumnViewImpl<'_>,
    right: ColumnViewImpl<'_>,
    function: F,
) -> anyhow::Result<ArrayImpl>
where
    F: Fn(i32, i32) -> i32;

Validate both Int32 inputs and their lengths before evaluating. If either view is Indexed, use the existing typed auto-vectorizer instead. That preserves one well-tested path for indirection. The result must have the same visible values and nulls either way; callers do not observe which path ran.

The raw path works only for total operations with strict null propagation. A callback that can fail or assigns meaning to null still needs a row-aware evaluator.

Checked division: strict but fallible

try_evaluate_binary lifts a fallible scalar function:

pub fn try_evaluate_binary<L, R, O, F, E>(
    left: ColumnViewImpl<'_>,
    right: ColumnViewImpl<'_>,
    function_name: &str,
    function: F,
) -> anyhow::Result<ArrayImpl>
where
    F: Fn(L, R) -> Result<O, E>,
    E: std::fmt::Display;

Validate type and length before calling function. For each row:

1. if either input is null, append null without calling the scalar function;
2. otherwise call the function once;
3. append its value on success; or
4. stop at the first failure and add the function name and row to the returned error.

A checked division callback is now an ordinary scalar function:

let output = try_evaluate_binary::<i32, i32, i32, _, _>(
    left,
    right,
    "checked_divide",
    |left, right| {
        if right == 0 { Err("division by zero") } else { Ok(left / right) }
    },
)?;

A null numerator with a zero denominator remains null because strict lifting does not call the callback for that row. A later non-null division by zero is the first reported error.

Three-valued Boolean logic: null is an input

Strict lifting cannot express SQL Boolean logic. false AND null is known to be false, and true OR null is known to be true. The nullable-aware evaluator therefore passes both optional values to the callback on every row:

pub fn evaluate_nullable_binary<L, R, O, F>(
    left: ColumnViewImpl<'_>,
    right: ColumnViewImpl<'_>,
    function: F,
) -> anyhow::Result<ArrayImpl>
where
    F: FnMut(Option<L>, Option<R>) -> anyhow::Result<Option<O>>;

For AND, return Some(false) when either input is Some(false), Some(true) when both are true, and None otherwise. For OR, return Some(true) when either input is true, Some(false) when both are false, and None otherwise. Validation still happens once before the first callback.

Run the focused and cumulative checks:

cargo test -p type-exercise-starter-supplied-tests chapter_6 --locked
cargo test -p type-exercise-starter-supplied-tests --locked

When the tests pass, the three policies share validation and owned output construction while keeping their different callback and null contracts.

Checkpoint 7 wraps these evaluators in a checked whole-batch expression.

Checkpoint 7: Erase Whole-Batch Expressions

Checkpoint 6 can evaluate complete batches, but callers still choose each evaluator directly. In this checkpoint, you will package a batch function with its physical contract and expose it through one runtime-erased interface.

Begin from completed Checkpoint 6 and copy the cumulative tests:

cargo x copy-test --chapter 7
cargo test -p type-exercise-starter-supplied-tests chapter_7 --locked

The focused run should fail only because BatchKernel, BatchExpression, and Expression are missing from core/src/expression.rs.

Give a complete batch one function type

Start with a function pointer that accepts any lifetime used by the borrowed input views:

pub type BatchKernel =
    for<'a> fn(&[ColumnViewImpl<'a>]) -> anyhow::Result<ArrayImpl>;

The higher-ranked lifetime means the function works with the batch borrowed by each call. A plain function pointer also keeps this checkpoint focused on evaluation: it cannot capture a catalog, binder, or per-row state.

For example, an already-earned evaluator becomes a kernel without rebuilding its loop:

fn i32_add(inputs: &[ColumnViewImpl<'_>]) -> anyhow::Result<ArrayImpl> {
    auto_vectorize_binary::<i32, i32, i32, _>(
        inputs[0].clone(),
        inputs[1].clone(),
        i32::wrapping_add,
    )
}

The expression shell will validate the inputs before this function can index them.

Preserve fixed arity while it is known

Add BatchExpression<const N: usize>. It owns:

• a &'static str name;
• exactly [PhysicalType; N] input types;
• one output PhysicalType; and
• one BatchKernel.

Provide new, name, input_types, output_type, and evaluate. Its direct API keeps the input arity in the type and makes the physical contract inspectable:

let add = BatchExpression::new(
    "i32_add",
    [PhysicalType::Int32, PhysicalType::Int32],
    PhysicalType::Int32,
    i32_add,
);

assert_eq!(add.input_types().len(), 2);
let output = add.evaluate(&[left, right])?;

evaluate has two validation boundaries. First call validate_expression_inputs with the stored input types. Only after arity, physical types, and row counts pass may the kernel run. Then reject a returned array whose physical type differs from output_type or whose length differs from the validated input length. A successful call returns the owned array unchanged.

Erase the shell, not each row

Different fixed arities cannot share one collection directly. Define a dyn-compatible Expression trait with name, input_types, arity, output_type, and evaluate. arity can default to the length of input_types.

Implement the trait for every BatchExpression<N>. The erased path delegates to the same checked whole-batch evaluation:

let expression: Box<dyn Expression> = Box::new(add);
assert_eq!(expression.arity(), 2);
let output = expression.evaluate(&[left, right])?;

The dynamic choice happens once for the complete batch. Rows still run inside the existing typed evaluators, so this boundary does not introduce a virtual call or erased scalar value per row.

Run the focused and cumulative checks:

cargo test -p type-exercise-starter-supplied-tests chapter_7 --locked
cargo test -p type-exercise-starter-supplied-tests --locked

You are done when metadata and direct evaluation survive erasure, invalid inputs never reach the kernel, and invalid kernel outputs are rejected. The next checkpoint will use this whole-batch boundary to build a catalog of concrete expressions.

Checkpoint 8: Build the Physical Expression Catalog

Checkpoint 7 erased one already-constructed whole-batch expression. A caller still needs to know which concrete builder to call. This checkpoint adds a catalog that turns a physical function identifier plus exact physical input types into Box<dyn Expression>.

Begin from completed Checkpoint 7 and copy the cumulative tests:

cargo x copy-test --chapter 8
cargo test -p type-exercise-starter-supplied-tests chapter_8 --locked

The focused run should fail only because try_auto_vectorize_ternary and the Checkpoint 8 catalog/factory surface are missing.

Complete the fallible ternary bridge

Checked division already established the strict fallible rule for two inputs. Add its ternary counterpart in core/src/expression.rs:

pub fn try_auto_vectorize_ternary<A, B, C, O, F, E>(
    first: ColumnViewImpl<'_>,
    second: ColumnViewImpl<'_>,
    third: ColumnViewImpl<'_>,
    function_name: &str,
    function: F,
) -> anyhow::Result<ArrayImpl>
where
    F: Fn(A, B, C) -> Result<O, E>,
    E: std::fmt::Display;

Validate all three physical types and lengths before the first callback. Skip the callback when any input is null. Stop at the first non-null scalar failure and return an error with useful function and row context. Specialize Array/Array/Array and send every other shape through the typed fallback, just as the infallible ternary adapter does. Both routes build a fresh owned output.

This small core-owned bridge lets physical clamp report invalid bounds without panicking or moving a row loop into the facade.

Give each scalar family concrete builders

Enable the numeric, Boolean, and String facade modules. Each module owns scalar meaning and selects an existing core evaluator once for a complete batch:

• numeric builders cover losslessly widened +, -, *, /, negation, fallible clamp, and six comparisons;
• Boolean builders cover three-valued AND and OR, strict NOT, equality, and inequality; and
• String builders cover writer-backed concatenation, containment, and six comparisons.

Choose the physical signature before entering any kernel. Integer overflow uses the course’s wrapping arithmetic rule. Division and clamp use fallible core lifts. String concatenation writes directly through the consumed Writer, so a partially written failing row cannot be published.

Lossless numeric widening is the same for arithmetic, comparisons, and each step of clamp:

• Int16 widens to any numeric family;
• Int32 combines with Int64 or Float64;
• Int32 plus Float32 produces Float64;
• Float32 combines with Float64; and
• Int64 with either floating family is rejected.

List is not a numeric family here.

Build one discoverable physical catalog

In expr/src/catalog.rs, implement this public surface:

pub enum PhysicalFunction { /* numeric, Boolean, and String functions */ }

pub struct PhysicalFunctionEntry {
    pub function: PhysicalFunction,
    pub name: &'static str,
    pub arity: usize,
}

pub const PHYSICAL_FUNCTION_CATALOG: &[PhysicalFunctionEntry];

pub fn find_physical_function(name: &str) -> Option<PhysicalFunction>;

pub fn build_physical_expression(
    function: PhysicalFunction,
    inputs: &[PhysicalType],
) -> anyhow::Result<Box<dyn Expression>>;

The catalog metadata is for discovery. Construction is the checked boundary: reject unsupported arity or physical input types before returning an expression. Numeric construction computes one lossless common physical type, then instantiates the matching typed builder. Boolean and String construction accept only their exact physical signatures.

At this boundary, the caller already has physical columns and deliberately chooses a physical function. Logical names, casts, and overload resolution belong one level earlier and will enter in Checkpoint 9.

Use the complete physical loop

Suppose execution already holds an Int16 column and an Int32 column. The caller can inspect those physical types, choose the catalog’s numeric-add identifier, and ask for one erased expression:

let function = find_physical_function("numeric_add").expect("catalog entry");
let expression = build_physical_expression(
    function,
    &[PhysicalType::Int16, PhysicalType::Int32],
)?;

assert_eq!(expression.output_type(), PhysicalType::Int32);
let output = expression.evaluate(&[left, right])?;

The dynamic choice happens once. The returned expression validates the actual batch and delegates rows to its already-selected typed kernel.

Run the focused and cumulative checks:

cargo test -p type-exercise-starter-supplied-tests chapter_8 --locked
cargo test -p type-exercise-starter-supplied-tests --locked

The tests cover every supported and rejected physical signature plus representative mixed numeric, fallible clamp, nullable Boolean, and transactional String evaluation through dyn Expression. With physical selection complete, Checkpoint 9 can decide which function a SQL name and logical schema should mean.

Checkpoint 9: Bind Logical Calls to Physical Expressions

Checkpoint 8 accepts a physical function and exact physical input types. A query planner begins one level earlier, with a logical function name and logical input types such as SmallInt, Integer, Char, or Varchar. In this checkpoint, you will connect those two worlds with one binding layer.

Begin from completed Checkpoint 8 and copy the cumulative tests:

cargo x copy-test --chapter 9
cargo test -p type-exercise-starter-supplied-tests chapter_9 --locked

The focused run should fail only because the Checkpoint 9 logical-call, bound-expression, and binder names are missing.

Describe one logical call

In expr/src/binder.rs, implement this public surface:

pub struct LogicalCall { /* logical name and input DataTypes */ }

impl LogicalCall {
    pub fn new(
        name: impl Into<String>,
        input_types: impl IntoIterator<Item = DataType>,
    ) -> Self;
    pub fn name(&self) -> &str;
    pub fn input_types(&self) -> &[DataType];
}

pub enum BindError { /* unknown, wrong arity, unsupported, metadata mismatch */ }

pub struct BoundExpression { /* logical contract plus Box<dyn Expression> */ }

pub fn bind_logical_call(call: LogicalCall) -> Result<BoundExpression, BindError>;

BoundExpression should expose the logical call and output type, a borrowed view of the selected physical expression, a way to take its Box<dyn Expression>, and an evaluate method that delegates the entire batch. Its constructor must reject logical metadata whose physical input or output types disagree with the expression it wraps.

Enable the binder module from expr/src/lib.rs. Logical binding belongs in the facade. Core continues to own arrays, logical and physical representations, validation, generic traversal, writers, and the erased batch boundary.

Resolve only the maintained overloads

Map these logical names to the physical catalog identifiers already earned in Checkpoint 8:

Use the same lossless numeric policy as the physical catalog. SmallInt widens to every maintained numeric family. Integer combines with BigInt or Double; Integer plus Real produces Double. Real combines with Double. Reject BigInt with either floating family, Decimal overloads not represented by the physical catalog, and every other unsupported combination.

Char and Varchar are distinct logical types but both map to physical String. That mapping is why a mixed Char/Varchar concat call selects the existing StringConcat expression without a new row loop or a runtime cast.

Check arity before overload resolution. Reject unknown names and unsupported argument types rather than guessing. Each accepted call must select exactly one PhysicalFunction; then call build_physical_expression with the inputs’ physical types and verify the returned metadata before publishing the bound result.

Run the complete logical-to-physical loop

The caller now starts with a logical schema, binds once, inspects the public contract, and evaluates the returned erased expression:

let call = LogicalCall::new(
    "+",
    [DataType::SmallInt, DataType::Integer],
);
let bound = bind_logical_call(call)?;

assert_eq!(bound.output_type(), &DataType::Integer);
assert_eq!(
    bound.physical_expression().input_types(),
    &[PhysicalType::Int16, PhysicalType::Int32],
);

let expression: Box<dyn Expression> = bound.into_physical_expression();
let output = expression.evaluate(&[left, right])?;

Binding performs logical overload and coercion selection once. Execution remains physical: the same whole-batch expression validates the actual columns and delegates to its specialized kernel. Planner trees and casts are outside this course boundary; List storage and async evaluation arrive in the final checkpoint.

Run the focused and cumulative checks:

cargo test -p type-exercise-starter-supplied-tests chapter_9 --locked
cargo test -p type-exercise-starter-supplied-tests --locked

The tests cover exact and widened numeric calls, mixed logical strings, Boolean and ternary binding, representative rejection paths, checked bound metadata, and evaluation through the returned erased expression. The result is a complete synchronous path from a logical call to an owned array.

Checkpoint 10: Add One-Level Lists and Batch Async

The final checkpoint adds two boundaries without changing the scalar functions you already built:

1. a checked, nullable, one-level List value family; and
2. a future that defers one complete, already-bound batch expression.

Start from your completed Checkpoint 9 workspace. Copy the cumulative public contract without opening its source first:

cargo x copy-test --chapter 10
cargo test -p type-exercise-starter-supplied-tests chapter_10 --locked

That focused test should initially fail only because the new List and async names do not exist. Every earlier checkpoint should remain green as you work.

Stage 1: represent nullable one-level Lists

Add PhysicalType::List(Box<PhysicalType>), then extend the erased array, scalar-reference, and column-view families with checked List variants. Implement the public ListScalar, ListScalarRef, ListArray, and ListColumnView surfaces described by the Checkpoint 10 comments in the starter.

A List has two independent layers of nullability. The outer validity says whether the row itself is null. For a present row, the child array may still contain null elements. Empty and all-null Lists therefore cannot infer their child type: callers always provide an explicit non-List child PhysicalType, including the complete Decimal descriptor when the child is Decimal.

For a raw List array, validate all of these invariants before publishing the value:

• nested List and Map children are rejected;
• the child array has exactly the declared physical type;
• there is one more offset than outer rows, the first offset is zero, offsets never decrease, and the final offset equals the child length;
• a null row repeats its preceding offset; and
• row and slice ranges are checked.

A failed constructor, append, or slice must not expose partial state. Array, Constant, and Indexed column views must yield equivalent safe borrowed List rows through the usual checked access path. These are observable invariants, not a required public field layout. Choose private fields that make the checks and rollback behavior clear.

Exercise the boundary directly before moving on:

let child = StringArray::from_slice(&[Some("left"), None, Some("right")]);
let row = ListScalar::try_new(ArrayImpl::String(child))?;
let lists = ListArray::try_from_rows(
    PhysicalType::String,
    [Some(row.as_list_ref()), None],
)?;

assert_eq!(lists.get(0)?.unwrap().len(), 3);
assert!(lists.get(0)?.unwrap().get(1)?.is_none()); // null child element
assert!(lists.get(1)?.is_none());                  // null List row
assert_eq!(lists.slice(0, 1)?.len(), 1);
Ok::<(), ListError>(())

Stage 2: defer one already-bound batch

Keep the Checkpoint 9 binder and all synchronous expression behavior unchanged. Add these four public boundaries in the expression core:

First strengthen the existing trait declaration to pub trait Expression: Send + Sync. The borrowing future is Send, so both the compiler-known expression reference and the expression erased inside Box<dyn Expression> must be safe to share across threads. The starter leaves this bound for you to add here.

• BatchFuture<'a>: a Send future borrowing the expression and input views;
• evaluate_static: a compiler-known async entry point;
• dyn-compatible AsyncExpression; and
• AsyncExpressionAdapter over the existing Box<dyn Expression>.

Creating the future must not evaluate anything. When driven, it evaluates the child exactly once for the complete batch and preserves the same owned array or error as synchronous evaluation. The future may borrow the expression and views and makes no Unpin promise.

Bind the logical call you built in Checkpoint 9, then run the same complete batch through all three paths:

let left: ArrayImpl = I16Array::from_slice(&[Some(2), None, Some(-4)]).into();
let inputs = [
    ColumnViewImpl::array(&left),
    ColumnViewImpl::constant(ScalarRefImpl::Int32(5), 3),
];

let bound = bind_logical_call(LogicalCall::new(
    "+",
    [DataType::SmallInt, DataType::Integer],
))?;

let sync = bound.evaluate(&inputs)?;
let static_async = evaluate_static(bound.physical_expression(), &inputs).await?;
let erased = AsyncExpressionAdapter::new(bound.into_physical_expression());
let erased_async = erased.evaluate_async(&inputs).await?;

assert_eq!(sync, static_async);
assert_eq!(sync, erased_async);
Ok::<(), anyhow::Error>(())

The async layer ends at one deferred whole-batch computation. It does not need an executor, runtime, I/O, retries, locks, per-row futures, or new scalar semantics. Likewise, the List work remains one level deep rather than growing into recursive Lists or Maps.

Finish by running the cumulative contract:

cargo test -p type-exercise-starter-supplied-tests --locked

The final suite checks the one-level List invariants and confirms that synchronous, static async, and erased async evaluation return the same result or error. You now have the complete path from logical binding through typed batch execution, including nullable nested storage and a borrowing future around the finished batch.