This article introduces the mini-arrow project, a minimal Apache Arrow implementation written in Rust. With just 1600 lines of Rust code, it demonstrates the design and solutions to several of Arrow’s most core problems. The project is inspired by Type Exercise in Rust.

Before diving into the details, let’s first understand the Arrow project:

What Problems Does Arrow Solve #

Arrow is a columnar in-memory format project that addresses the following core problems:

Row-Oriented vs Column-Oriented #

Traditional databases (such as MySQL) store data in rows: all fields of a record are stored contiguously.

Row-oriented storage:
  [id=1, name="Alice", age=30] [id=2, name="Bob", age=25] [id=3, ...]

Columnar storage (such as Arrow, ClickHouse) stores data in columns: all values of the same column are stored contiguously.

Columnar storage:
  id:    [1, 2, 3, ...]
  name:  ["Alice", "Bob", ...]
  age:   [30, 25, ...]

Why is columnar better? Analytical queries (such as SELECT AVG(age) FROM users) only care about the age column. Columnar storage can:

1. Read only the needed columns, skipping irrelevant data and reducing I/O;
2. Better cache locality — values of the same column are contiguous in memory, so scans have higher hit rates;
3. Support vectorization — SIMD batch operations on contiguous memory are orders of magnitude faster than row-by-row interpretation.

The Difficulties of Columnar Storage #

Storing data by column immediately raises several tricky problems:

Difficulty 1: Fixed-length vs variable-length. i32 can go into a Vec<i32>, but String has variable length and cannot be placed directly into a fixed-length array. An additional layout is needed to manage variable-length data.

Difficulty 2: Null values (NULL). Vec<T> requires contiguous, fixed-length storage and cannot “skip” a position. How is NULL represented? If we wrap every value in an Option, it breaks the contiguous layout, wastes memory, and prevents vectorization.

Difficulty 3: Owned values vs zero-copy references. When reading a StringArray, we want to get a &str directly without copying; but when building an array, we need to hold ownership of the String. How can the two forms coexist?

Difficulty 4: The type is only known at runtime. Rust generics are expanded at compile time, but a database engine only knows a column’s type at runtime (parsed from SQL). How can arrays of arbitrary types be uniformly passed, dispatched, and evaluated?

Difficulty 5: Repeated decisions in expression evaluation. Every binary operation (+, <=, contains) must handle argument count, type checking, length checking, NULL propagation, and output construction. If this logic is hardcoded into every loop, each new function adds another place for duplication and bugs.

Difficulty 6: Scaling the type family. Every time a type is added (such as f64), the physical variants, scalar variants, array aliases, builders, and conversions must all be repeated… The more repetition, the more likely drift.

The four modules of mini-arrow — scalar, array, builder, expr — are designed to tackle these difficulties one by one. Below, starting from “a seemingly simple problem”, we break down the design rationale of each module.

The Starting Point: A Seemingly Simple Problem #

Writing a loop for i32 + i32 by hand 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,
    });
}

This code works fine for i32. But once you ask for more, it starts to “leak”:

1. What about strings? If StringArray::get returns a String, it copies every time; we want it to return &str.
2. What about NULL? We can’t return Vec<Option<T>>, that would break the columnar layout.
3. What about mixed types? Should i32 <= i64 be promoted to i64 first, then compared?
4. What about types only known at runtime? The function name parsed from SQL is a string, and it can only be mapped to a concrete implementation at runtime.
5. What about rewriting the arity / length / NULL checks every time a function is added?

mini-arrow’s solution is to split these problems apart, with each module solving only one problem: move those decisions out of the row loop, distilling them into the four modules scalar, array, builder, expr. Each module corresponds to one of the difficulties listed at the start. Let’s break them down one by one:

Module Breakdown: What Problem Each Module Solves #

1. types: Defining the Boundary of “Primitive Types” #

pub trait PrimitiveType: Default + Copy + Debug + 'static {}
impl PrimitiveType for i32 {}
impl PrimitiveType for i64 {}
impl PrimitiveType for bool {}

Problem to solve: Which types can be stored using a “fixed-length array”?

PrimitiveType is a marker trait. Types that satisfy it can be placed into PrimitiveArray<T> — because they are Default + Copy + Debug + 'static. String is not Copy, so it is excluded and must use the StringArray variable-length layout.

graph LR
    subgraph PrimitiveType boundary
        PT[PrimitiveType trait] --> |i32, i64, bool| PA[PrimitiveArray<T>]
        PT -.->|String does not satisfy Copy| SA[StringArray variable-length layout]
    end

2. scalar: Owned Values and Zero-Copy References #

Problem to solve #

A “value” in a database has two forms:

• Owned value: such as String, which can be freely held and moved.
• Zero-copy reference: such as &str, which merely borrows the bytes in an array without any allocation.

If we force everything into one form, problems arise:

• If we use owned everywhere, then StringArray::get would have to to_string() and copy every time — a performance disaster.
• If we use references everywhere, then we can’t hold data when building an array.

Why design it this way #

Use two traits to express these two forms, and connect them with generic associated types (GAT):

pub trait Scalar: 'static + Clone + Debug + TryFrom<ScalarImpl> + Into<ScalarImpl> {
  type ArrayType: Array<Item = Self>;
  type RefType<'a>: ScalarRef<'a, ScalarType = Self, ArrayType = Self::ArrayType>;
  fn as_scalar_ref(&self) -> Self::RefType<'_>;
}

pub trait ScalarRef<'a>:
  'a + Clone + Copy + Debug + TryFrom<ScalarRefImpl<'a>> + Into<ScalarRefImpl<'a>>
{
  type ArrayType: Array<RefItem<'a> = Self>;
  type ScalarType: Scalar<RefType<'a> = Self>;
  fn as_scalar(&self) -> Self::ScalarType;
}

These two traits form a set of reciprocal arrows:

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

Key insight: primitive types are both Scalar and ScalarRef.

• i32 is Copy, so copying it has no cost; hence RefType<'a> = i32 and as_scalar_ref is just *self.
• String is different: Scalar is String, ScalarRef is &'a str, and as_scalar_ref returns self.as_str().

graph LR
    subgraph Integer i32
        S1[i32 as Scalar] -->|RefType = i32| SR1[i32 as ScalarRef]
        SR1 -->|ScalarType = i32| S1
    end

    subgraph String
        S2[String as Scalar] -->|RefType = &str| SR2[&str as ScalarRef]
        SR2 -->|ScalarType = String| S2
    end

Why do we need a lifetime-indexed associated type? Because the &str returned by StringArray::get must be bound to the lifetime of the array’s borrow. An ordinary associated type cannot express “the return value borrows self”; we must use a GAT like RefItem<'a>. The for<'a> HRTB bound means “the relationship holds for any borrow lifetime chosen by the caller” — the integer implementation can ignore it, but the string implementation cannot.

3. array: Columnar Storage and Null Values #

Problem to solve #

The core of columnar storage is storing the values of the same column contiguously, to gain cache locality and vectorization. But there are two difficulties:

1. Fixed-length vs variable-length: i32 can go into a Vec<i32>, but String has variable length and cannot be placed directly.
2. Null values (NULL): Vec<T> requires contiguous, fixed-length storage and cannot “skip” a position.

Why design it this way #

Using the Arrow standard layout, mini-arrow fully implements both forms:

Fixed-length type PrimitiveArray<T> — data + bitmap:

pub struct PrimitiveArray<T: PrimitiveType> {
  data: Vec<T>,      // contiguous data
  bitmap: BitVec,    // null bitmap
}

• NULL positions are filled with T::default() as a placeholder, and bit i of the bitmap marks whether the value is valid.
• Reading: if bitmap[i] { Some(data[i]) } else { None }.

graph LR
    subgraph PrimitiveArray_i32
        data["data: 1, 2, 3, 0, 5"]
        bitmap["bitmap: 1, 1, 1, 0, 1"]
    end
    data -->|row i corresponds to bit i of bitmap| bitmap
    data -->|bit 3 of bitmap is 0| null["row 3 is NULL, the 0 in data is just a placeholder"]

Variable-length type StringArray — data + offsets + bitmap:

pub struct StringArray {
  data: Vec<u8>,       // all string bytes concatenated
  offsets: Vec<usize>, // starting offset of each string
  bitmap: BitVec,      // null bitmap
}

• The range of the i-th string is offsets[i]..offsets[i+1], and its length is the difference.
• Reading: &data[offsets[i]..offsets[i+1]], zero-copy returns &str.
• The offsets count UTF-8 bytes, not characters; empty rows and NULL rows both repeat the previous offset.

graph LR
    subgraph StringArray
        data["data bytes: h e l l o w o r l d"]
        offsets["offsets: 0, 5, 10"]
        bitmap["bitmap: 1, 1"]
    end
    data -->|all bytes stored contiguously| offsets
    offsets -->|row 0 range 0 to 5| str0["hello"]
    offsets -->|row 1 range 5 to 10| str1["world"]
    bitmap -->|both rows valid| offsets

Why use a bitmap for NULL instead of Option<T>? Nullability is value state, not a type variant. We express it with Option or a validity bitmap, rather than wrapping every value in an Option. Because Vec<Option<T>> breaks the contiguous layout, wastes memory, and cannot be vectorized.

The unified abstraction Array trait:

pub trait Array: Sized + 'static + TryFrom<ArrayImpl> + Into<ArrayImpl> {
  type Builder: ArrayBuilder<Array = Self>;
  type Item: Scalar<ArrayType = Self>;
  type RefItem<'a>: ScalarRef<'a, ScalarType = Self::Item, ArrayType = Self>;
  fn get(&self, idx: usize) -> Option<Self::RefItem<'_>>;
  fn len(&self) -> usize;
  fn iter(&self) -> ArrayIterator<Self>;
  fn from_slice(data: &[Option<Self::RefItem<'_>>]) -> Self; // default impl: goes through builder
}

This way, one generic contract can read ordinary, empty, and all-NULL arrays alike, and string reads incur no allocation.

4. builder: Incremental Construction of Immutable Arrays #

Problem to solve #

Once built, an array is immutable (as is typical for columnar storage). But the construction process needs incremental push, producing the final result in one go.

Why design it this way #

Abstract construction into the ArrayBuilder trait, mutually linked to Array through associated types:

pub trait ArrayBuilder {
  type Array: Array<Builder = Self>;
  fn with_capacity(capacity: usize) -> Self;
  fn push(&mut self, value: Option<<Self::Array as Array>::RefItem<'_>>);
  fn finish(self) -> Self::Array;
}

PrimitiveArrayBuilder<T>: Some(v) pushes data into data and sets the bitmap bit to true; None pushes T::default() as a placeholder and sets the bitmap bit to false.

StringArrayBuilder: Some(s) appends the bytes to data and records the new offset; None leaves the offset unchanged (reusing the previous one) and sets the bitmap bit to false.

graph LR
    subgraph Builder flow
        WC[with_capacity] --> P1[push Some]
        P1 --> P2[push None]
        P2 --> P3[push Some]
        P3 --> F[finish]
        F --> A[Array immutable]
    end

Why are builder and array “reciprocal”? Array::Builder points to the builder that can construct it, and ArrayBuilder::Array points to the array it produces. These two associated types, Array::Builder and ArrayBuilder::Array, point in opposite directions, forming a “reciprocal” relationship. This is how from_slice’s default implementation can be written generically:

let mut builder = Self::Builder::with_capacity(data.len());
// ... push
builder.finish()

5. Type Erasure: Crossing the Runtime Boundary #

Problem to solve #

Rust generics are expanded at compile time, but a database engine only knows a column’s type at runtime (e.g., parsed from SQL). We need a unified type so that arrays of any type can be uniformly passed, dispatched, and evaluated.

Why design it this way #

Use three erased enums for type erasure:

pub enum ArrayImpl {
  Int32(I32Array), Int64(I64Array), Bool(BoolArray), String(StringArray),
}
pub enum ScalarImpl { Int32(i32), Int64(i64), Bool(bool), String(String) }
pub enum ScalarRefImpl<'a> { Int32(i32), Int64(i64), Bool(bool), String(&'a str) }

Upcasting uses From, downcasting uses TryFrom:

impl From<I32Array> for ArrayImpl {          // upcast: concrete → enum
  fn from(array: I32Array) -> Self { ArrayImpl::Int32(array) }
}

impl TryFrom<ArrayImpl> for I32Array {       // downcast: enum → concrete, errors on type mismatch
  type Error = TypeMismatch;
  fn try_from(array: ArrayImpl) -> Result<Self, Self::Error> {
    match array {
      ArrayImpl::Int32(array) => Ok(array),
      other => Err(TypeMismatch(stringify!(Int32), other.identifier())),
    }
  }
}

graph LR
    subgraph Type erasure
        A1[I32Array] -->|From| E1[ArrayImpl::Int32]
        S1[i32] -->|From| E2[ScalarImpl::Int32]
        R1[&str] -->|From| E3[ScalarRefImpl::String]
    end
    E1 -->|TryFrom| A1
    E1 -.->|type mismatch| Err[Err<TypeMismatch>]

Why is downcasting “fallible”? Because ArrayImpl is a runtime value; it might hold a StringArray while the caller requests an I32Array. The compiler cannot guarantee this, so we must use TryFrom to perform a checked conversion at the boundary. This is exactly the purpose of the TypeMismatch error — it turns “type mismatch” into a handleable error rather than a crash. A wrong variant returns Err, not a panic.

6. expr: Moving Decisions Out of the Row Loop #

Problem to solve #

Every binary/unary loop must honor these five repeated decisions:

1. Check the argument count (arity);
2. Check the physical types;
3. Check the length of each input;
4. Skip the scalar function when any strict input is NULL;
5. Build the associated output array, or return the first row error without producing partial output.

If these decisions are hardcoded into every loop, each new function adds another place for duplication and bugs.

Why design it this way #

Use a generic adapter to separate the “row loop” from the “concrete scalar function”:

pub trait BinaryExprFunc<I1: Array, I2: Array, O: Array> {
  fn eval<'a>(&self, i1: I1::RefItem<'a>, i2: I2::RefItem<'a>) -> O::Item;
}

BinaryExpression<I1, I2, O, F> is a generic binary expression, and eval_batch writes the row loop only once:

pub fn eval_batch(&self, i1: &ArrayImpl, i2: &ArrayImpl) -> Result<ArrayImpl> {
  let i1a: &I1 = i1.try_into()?;   // type erasure → concrete type
  let i2a: &I2 = i2.try_into()?;
  assert_eq!(i1.len(), i2.len(), "array length mismatch");
  let mut builder: O::Builder = O::Builder::with_capacity(i1.len());
  for (i1, i2) in i1a.iter().zip(i2a.iter()) {
    match (i1, i2) {
      (Some(i1), Some(i2)) => builder.push(Some(self.expr.eval(i1, i2).as_scalar_ref())),
      _ => builder.push(None),   // NULL propagation
    }
  }
  Ok(builder.finish().into())
}

graph LR
    subgraph Expression evaluation flow
        A1[ArrayImpl] -->|try_into| I1[&I1]
        A2[ArrayImpl] -->|try_into| I2[&I2]
        I1 --> ZIP[iter zip]
        I2 --> ZIP
        ZIP -->|Some, Some| EVAL[F::eval]
        ZIP -->|contains None| NULL[push None]
        EVAL --> PUSH[builder.push]
        NULL --> PUSH
        PUSH --> FINISH[finish]
        FINISH --> OUT[ArrayImpl]
    end

NULL propagation is the core of SQL three-valued logic: if any input is NULL, the output is NULL, and the scalar function is not called.

Concrete functions are implemented via BinaryExprFunc. For example, comparison operations support type promotion:

pub struct ExprCmpLe<I1: Array, I2: Array, C: Array>(pub PhantomData<(I1, I2, C)>);

impl<I1: Array, I2: Array, C: Array> BinaryExprFunc<I1, I2, BoolArray> for ExprCmpLe<I2, I2, C>
where
  for<'a> I1::RefItem<'a>: Into<C::RefItem<'a>>,
  for<'a> I2::RefItem<'a>: Into<C::RefItem<'a>>,
  for<'a> C::RefItem<'a>: PartialOrd,
{
  fn eval<'a>(&self, i1: I1::RefItem<'a>, i2: I2::RefItem<'a>) -> bool {
    i1.into().partial_cmp(&i2.into()).unwrap() == Ordering::Less
  }
}

The third type parameter C is the common promotion type — ExprCmpLe::<_, _, I64Array> means promoting two i32 values to i64 before comparing.

Why use PhantomData? ExprCmpLe itself stores no data; I1/I2/C are only used at the type level. PhantomData<(I1, I2, C)> tells the compiler that this type “owns” these three type parameters, so it can correctly infer trait implementations and lifetimes, without occupying any runtime memory.

Finally, build_binary_expression is a runtime factory that maps the ExpressionFunc enum to a concrete Box<dyn Expression>:

pub fn build_binary_expression(f: ExpressionFunc) -> Box<dyn Expression> {
  match f {
    CmpLe => Box::new(BinaryExpression::<I32Array, I32Array, BoolArray, _>::new(
      ExprCmpLe::<_, _, I32Array>(PhantomData),
    )),
    StrContains => Box::new(BinaryExpression::<StringArray, StringArray, BoolArray, _>::new(ExprStrContains)),
  }
}

This solves the problem of selecting a concrete typed expression from a runtime name — the SQL parser gets a string function name, which must be mapped to a concrete typed implementation.

7. The Macro System: Making the Type Family Extensible #

Problem to solve #

Every time a type is added (such as f64), the physical variants, scalar variants, array aliases, builders, and conversions must all be repeated… The more repetition, the more likely drift — you might add an array but forget the conversion, or write the wrong type name in a conversion.

Why design it this way #

Use a type-family catalog so that “one line defines one type family”. mini-arrow implements this with the for_all_variants! macro:

macro_rules! for_all_variants {
  ($macro:ident $(, $x:ident)*) => {
    $macro! {
      [$($x),*],
      { Int32, int32, I32Array, I32ArrayBuilder, i32, i32 },
      { String, string, StringArray, StringArrayBuilder, String, &'a str }
    }
  };
}

Each tuple is { enum variant name, function suffix, array type, builder type, owned type, reference type }. Then impls.rs uses this catalog to batch-generate all the boilerplate:

• impl_array_dispatch: ArrayImpl’s get / len / is_empty / identifier
• impl_array_conversion: all From / TryFrom conversions
• impl_scalar / impl_scalar_conversion: Scalar / ScalarRef implementations and conversions

Why use macros instead of writing by hand? The macro makes the catalog the single source of truth — adding a type only requires adding one line to the catalog, and the rest of the code is generated automatically, without the drift of “adding an array but forgetting the conversion”. Omitting or duplicating a type family becomes a compile or test failure.

Note: mini-arrow’s macros.rs and impls.rs are currently commented out (//mod macros;, //mod impls;); the hand-written array_impl.rs, builder_impl.rs, etc. are what actually take effect. This shows the project is in a transitional phase from hand-written code to macro generation — the macro version is written but not yet enabled.

Summary #

Design principles that run throughout:

1. Move decisions out of the row loop: arity, type, length, NULL, and output construction are all handled uniformly by the adapter.
2. Nullability is value state: use Option / validity bitmap, not a DataType::Nullable variant.
3. Checked runtime erasure: downcasting is fallible; wrong variants return Err.
4. Catalog-driven extension: one line defines a type family; omitting or duplicating becomes a compile or test failure.

Back to the start: how each difficulty is conquered #