Typed Type Exercise in Rust

Build database expression type checker and vectorized runtime executor in type-safe Rust.

This project is highly inspired by @skyzh's type-exercise-in-rust. While adopting his idea in Databend, I also implemented a few features that I think are useful:

1. Type checking. The type checker can catch all type errors in the SQL compilation phase with a set of carefully defined typing rules. The type checker outputs a totally untyped expression that is ready for runtime execution. So this makes the runtime free of any type information.

2. Type-safe downcast. Function authors no longer have to worry about downcasting runtime inputs. Thanks to Rust's type system, so long as your function compiles, the downcast is always successful.

3. Enum-dispatched columns. Use enum to exhaustive all column types and scalar types. They should further minimize runtime overhead and mental effort, compared to dyn-dispatched strategy.

4. Generic types. Use generic in the function signature to reduce the number of hand-written overloads. For example, you can express get(arr: Array<T0>, idx: i64) -> T0 in the type system.

Snippet of code

Define a fast, type-safe, auto-downcating and vectorized binary function in several lines of code:

registry.register_2_arg::<BooleanType, BooleanType, BooleanType, _>(
    "and",
    FunctionProperty::default(),
    |lhs, rhs| lhs && rhs,
);

Define a generic function get which returns an item of an array by the index:

registry.register_with_writer_2_arg::<ArrayType<GenericType<0>>, Int16Type, GenericType<0>, _>(
    "get",
    FunctionProperty::default(),
    |array, idx, output| output.push(array.index(idx as usize)),
);

Run

cargo run

Things to do

• Automatcially generate the nullable function.
• Automatcially generate the Null function.
• Automatcially dispatch arithmetic types.
• Implement arrays.
• Implement column builder.
• Implement unlimited-length tuples.
• Implment generic functions.
• Implment functions properties.
• Implment variadic functions.
• Implment sparse columns (some of the rows in a column are hidden).
• Check ambiguity between function overloads.
• Read material for the project.

Reading material

• Databend/RFC: Formal Type System
• type-exercise-in-rust
• 数据库表达式执行的黑魔法：用 Rust 做类型体操
• Book: Types and Progaming Language
• Paper: Type inference with simple subtypes