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(left.wrapping_add(right)),
        _ => None,
    });
}

The design problem appears when the engine must also borrow strings without copying, read constants and dictionaries, 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.

This course builds the connections that move those decisions out of the row loop. You will first write the small cases by hand. Only after their duplication is visible will you introduce the catalogs and generic adapters that remove it.

The map has three reading 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, dictionary, and typed-null encodings before one selected typed expression enters its row loop.

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, and return-position impl Trait in the concrete places that need them.

Every chapter names prerequisites, exact starter targets, required work, extensions, and a copied test. Passing the test is necessary; you should also be able to explain why the new boundary exists and which failure it prevents.

Continue to Environment Setup.

Your feedback is greatly appreciated. Join our Discord Community. Found an issue? Create an issue or pull request.

© 2022-2026 Alex Chi Z. Licensed under CC BY-NC-SA 4.0.

Environment Setup

Install rustup, update stable Rust, and install mdBook:

rustup update stable
rustc --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 --lib --locked
cargo test -p type-exercise-starter --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/src/.
• Do not edit src/tests.rs or copied files under src/tests/.
• 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.

Preview the course

mdbook serve course --open

Continue to Chapter 1: Connect One Type Family by Hand.

Your feedback is greatly appreciated. Join our Discord Community. Found an issue? Create an issue or pull request.

© 2022-2026 Alex Chi Z. Licensed under CC BY-NC-SA 4.0.

Chapter 1: Connect One Type Family by Hand

An i32 can be copied out of an array. A String should be read as an &str that borrows the array. This chapter connects both cases without forcing one into the other’s ownership model.

Prerequisites: enums, traits, references, associated types, and Option.

By the end of this chapter, you will:

• connect owned values, borrowed values, arrays, and builders for i32 and String;
• use a generic associated type for the borrowed member of each family; and
• upcast typed values with From and downcast erased enums with checked TryFrom conversions.

See the missing connections

Copy the cumulative contract and run it once:

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

The untouched starter compiles because it declares the Day 1 target shapes, but the focused test should fail at the Day 1 todo! boundary. It should not fail on an unresolved target. Do not edit the copied test.

The family you are building has reciprocal arrows:

Scalar ──RefType<'a>──> ScalarRef<'a>
  │                         │
ArrayType                ArrayType
  ▼                         ▼
Array ─────Builder─────> ArrayBuilder

For i32, the borrowed scalar is another i32. For String, it is &'a str. Array::get therefore returns Option<i32> for I32Array and Option<&str> for StringArray without an allocation on the string read.

Checkpoint 1: describe the two physical families

• Target: type-exercise-starter/src/physical_type.rs::{PhysicalType, TypeMismatch} and type-exercise-starter/src/scalar.rs::{Scalar, ScalarRef, ScalarImpl, ScalarRefImpl}.
• Change: add only the Int32 and String physical rows and their reciprocal associated types.
• Preserve: the original two ScalarImpl variants and safe Rust.
• Run: the Chapter 1 focused test.
• Passing means: owned and borrowed values point to the correct array family.

for<'a> on a bound means the relationship holds for every caller-chosen borrow lifetime. The integer implementation may ignore that lifetime; the string implementation cannot.

Checkpoint 2: store nullable rows

• Target: type-exercise-starter/src/array.rs::{Array, ArrayBuilder, ArrayImpl}, type-exercise-starter/src/array/primitive_array.rs::{PrimitiveArray, PrimitiveArrayBuilder}, and type-exercise-starter/src/array/string_array.rs::{StringArray, StringArrayBuilder}.
• Change: implement get, len, iter, from_slice, builder push, and finish for the two families. Expose read-only values/validity accessors on PrimitiveArray and data/offsets/validity accessors on StringArray so the buffer contract is visible.
• Preserve: row count and null positions; returned strings must borrow array storage; offsets count UTF-8 bytes rather than characters.
• Run: the same focused test.
• Passing means: normal, null, and empty arrays read through one generic contract.

Use the Arrow-like layout required by the supplied test. A fixed-width array stores one flat Vec<T> with exactly one slot per row. A string array stores all UTF-8 bytes in one flat Vec<u8> and uses rows + 1 monotone offsets: the first is zero, the last is the byte-buffer length, and a null or empty row repeats an offset. Both arrays store row validity in the packed bitvec::vec::BitVec already declared in the starter. A null row returns None, but it is never an Option<T> payload slot; strings are not stored as one owned String per row.

Checkpoint 3: erase and recover values

• Target: From/TryFrom implementations in type-exercise-starter/src/scalar.rs and type-exercise-starter/src/array.rs, plus exports in type-exercise-starter/src/lib.rs.
• Change: upcast typed values into erased enums and recover the requested type.
• Preserve: wrong variants return TypeMismatch { expected, actual }; they do not panic.
• Run: the focused and cumulative starter tests.
• Passing means: correct variants round-trip and wrong variants fail at the boundary.

Required and extension work

Required work is exactly the explicit i32 and String rows. Additional physical types, macros, columns, and expressions belong to later chapters. As an extension, sketch a third family on paper and mark every enum arm and conversion it would require; do not implement it yet.

cargo test -p type-exercise-starter chapter_1 --locked
cargo test -p type-exercise-starter --lib --locked

Before continuing, explain why StringArray::get needs a lifetime-indexed associated type and why an erased downcast is fallible even when the compile-time family is consistent.

Next: Chapter 2 scales the family without copying every connection.

Your feedback is greatly appreciated. Join our Discord Community. Found an issue? Create an issue or pull request.

© 2022-2026 Alex Chi Z. Licensed under CC BY-NC-SA 4.0.

Chapter 2: Scale the Physical Type Family

Adding f64 beside the two Chapter 1 rows repeats physical variants, scalar variants, array aliases, builders, and conversions. Repeating that work for every primitive makes drift more likely than the type itself warrants.

Prerequisites: Chapter 1 and basic declarative macros.

By the end of this chapter, you will:

• add complete i16, i64, bool, f32, and f64 static families plus a metadata-aware Decimal family;
• map planner-visible DataType values to physical storage; and
• keep the non-List physical rows in one catalog that drives exhaustive code.

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

The first run should fail at the declared Day 2 todo! boundaries for the new families and catalog, not on a missing file or symbol.

Add Double explicitly before generalizing

Connect DataType::Double, PhysicalType::Float64, f64, F64Array, and its builder by hand. Use the same checkpoints as Chapter 1. The copied test includes NaN, infinity, and signed zero so the family cannot accidentally require total equality.

This explicit row is evidence: the repeated edits are real. Now a single family catalog can own the remaining non-List rows:

Char { width } retains logical metadata without changing String storage. Decimal is different: its precision and scale define the physical value’s meaning, including for empty and all-null arrays. Use DecimalType::try_new(precision, scale) and enforce 1 <= precision <= 38 plus scale <= precision. This course keeps scale nonnegative.

Checkpoint 1: make primitive storage generic

• Target: type-exercise-starter/src/array/primitive_array.rs::{PrimitiveArray, PrimitiveArrayBuilder}.
• Change: implement the Array family once for supported primitive scalars and expose aliases.
• Preserve: nullable, empty, and special-float behavior from Chapter 1.
• Run: the Chapter 2 focused test.
• Passing means: every primitive family satisfies the same reciprocal type equations.

Checkpoint 2: add the family catalog

• Target: type-exercise-starter/src/variant_catalog.rs::for_each_physical_family, plus generated arms in type-exercise-starter/src/physical_type.rs, type-exercise-starter/src/scalar.rs, and type-exercise-starter/src/array.rs.
• Change: make one row define the physical variant, array, builder, owned scalar, and borrowed scalar.
• Preserve: String remains the one borrowed row and every downcast remains checked.
• Run: the focused test and inspect PHYSICAL_FAMILY_CATALOG failures.
• Passing means: omitting or duplicating a family becomes a compile or test failure.

Checkpoint 3: map logical meaning to storage

• Target: type-exercise-starter/src/data_type.rs::{DataType, DataType::physical_type}.
• Change: add all scalar logical types in the table.
• Preserve: DataType is planner metadata; do not add Nullable or List yet.
• Run: the focused and cumulative tests.
• Passing means: every logical scalar type has one documented physical family.

Checkpoint 4: give Decimal one shared descriptor

• Target: type-exercise-starter/src/decimal.rs::{DecimalType, Decimal, DecimalError} and type-exercise-starter/src/array/decimal_array.rs::{DecimalArray, DecimalArrayBuilder}.
• Change: store one flat i128 unscaled coefficient per row, packed validity, and one checked DecimalType shared by the whole array. Require the descriptor before the first builder push.
• Preserve: null rows use validity rather than Option<Decimal> storage; empty and all-null arrays remain typed; a failed coefficient or metadata check must not append a partial row.
• Run: the focused and cumulative tests.
• Passing means: scalar, array, and erased Decimal values preserve exact precision and scale.

The represented value is unscaled × 10^-scale. A valid coefficient has fewer than or exactly precision decimal digits, so 10^precision itself is out of range. Validate with an overflow-safe absolute value: i128::MIN is an ordinary error case, not a reason to panic. Do not use rust_decimal; repeating scale inside every stored row would create a second source of truth.

Decimal is a dedicated catalog row rather than a PrimitiveArray<Decimal> alias. Static numeric families can use metadata-free ArrayBuilder::with_capacity; Decimal uses DecimalArrayBuilder::try_with_type. Decimal arithmetic, comparisons, casts, rounding, and implicit coercion remain outside this chapter.

Required and extension work

All table rows and Decimal storage checks are required. Decimal arithmetic and casts are not. Extending the catalog with another physical family is useful practice, but it must bring the complete scalar, array, erasure, and mismatch surface rather than one enum variant.

The starter’s type-exercise-starter/API_ROADMAP.md names every later target through Day 13. Only Days 1–2 are Rust modules in this snapshot; future declarations stay documentation-only until their cumulative checkpoint lands. Day 5 includes numeric comparisons, Day 7 introduces three-valued Boolean logic, and the former Days 7–12 shift to Days 8–13.

cargo test -p type-exercise-starter chapter_2 --locked
cargo test -p type-exercise-starter --lib --locked

Your feedback is greatly appreciated. Join our Discord Community. Found an issue? Create an issue or pull request.

© 2022-2026 Alex Chi Z. Licensed under CC BY-NC-SA 4.0.