五分钟了解 Databend 全新 SQL 类型系统

2年前 (2022) 程序员胖胖胖虎阿

200 0 0

引言

类型系统是数据库的一个重要组成部分，它提供了一种一致的方式来确定 SQL 中的数据类型。类型系统的设计很大程度影响数据库的易用性和健壮性，一个设计合理且一致的类型系统容易让使用者判断 SQL 的行为。反之，一个没有经过正式设计的类型系统会带来各种暗坑和不一致行为在暗中背刺用户。我们用编程语言举个例子，JavaScript 被诟病的类型系统总是成为茶余饭后的谈资：

因此我们希望在 Databend 中实现一个易于理解而又功能强大的类型推导系统，为此我们借鉴了不少优秀编程语言的编译器内部设计，然后从中精简出适用于 SQL 使用的子集。下文将会详细展开介绍这个系统的设计原理。

接口设计

"低耦合高内聚" 是我们经常说的口头禅，讲的是要把做相同事情的代码归拢到一起，然后定义简单的接口供外部使用。类型推导作为一个相对复杂的系统，在设计之初需要先定义好对外暴露的接口，也即能做什么以及外部怎么使用。

简单来说，我们设计的类型推导系统可以做三件事：

输入 SQL 文本（RawExpr），检查 SQL 是否符合类型规则，为函数调用选择合适重载，返回可执行的表达式 (Expr)。
输入可执行的表达式和数据，执行然后返回结果。
输入可执行的表达式和数据取值范围（存储在元数据中），返回结果的取值范围。

为此调用者只需：

定义所有可用函数的类型签名、函数定义域到值域的映射、函数执行体。
在执行 SQL 或 constant folding 时调用执行器。

用布尔 and 函数举个例子，函数定义大致如下：

registry.register_2_arg::<BooleanType, BooleanType, BooleanType, _, _>(
    "and",
    FunctionProperty::default(),
    |lhs, rhs| {
        Some(BooleanDomain {
            has_false: lhs.has_false || rhs.has_false,
            has_true: lhs.has_true && rhs.has_true,
        })
    },
    |lhs, rhs| lhs && rhs,
);

一个完整执行的例子：

// 将 SQL 表达式文本转为结构化 AST
let raw_expr = parse_raw_expr("and(true, false)");

// 获取内置函数，比如之前的 `and` 函数
let fn_registry = builtin_functions();

// 检查类型合法性
let expr = type_check::check(&raw_expr, &fn_registry).unwrap();

// 执行
let evaluator = Evaluator {
    input_columns: Chunk::new(vec![]),
    context: FunctionContext::default(),
};
let result: Value<AnyType> = evaluator.run(&raw_expr).unwrap();

assert_eq!(result, Value::Scalar(Scalar::Boolean(false)));

类型推导原理

新的类型系统支持以下数据类型：

Null
Boolean
String
UInt8
UInt16
UInt32
UInt64
Int8
Int16
Int32
Int64
Float32
Float64
Date
Interval
Timestamp
Array<T>
Nullalbe<T>
Variant

我们以一个例子看看类型推导系统是如何工作的，假设外部输入了一个表达式：

1 + 'foo'

类型推导器首先会将表达式转换为函数调用：

plus(1, 'foo')

然后类型检查器可以简单地推断出常量的类型：

1 :: Int8
'foo' :: String

经过查询 FunctionRegistry，类型检查器得知函数 plus 有这些重载：

plus(Null, Null) :: Null
plus(Int8, Int8) :: Int8
plus(Int16, Int16) :: Int16
plus(Int32, Int32) :: Int32
plus(Float32, Float32) :: Float32
plus(Timestamp, Timestamp) :: Timestamp

我们可以发现，函数 plus 参数类型 Int8 和 String 不能匹配其中任何一个重载，因此类型检查器会返回一个错误报告：

1 + 'foo'
  ^ function `plus` has no overload for parameters `(Int8, String)`

  available overloads:
    plus(Int8, Int8) :: Int8
    plus(Int16, Int16) :: Int16
    plus(Int32, Int32) :: Int32
    plus(Float32, Float32) :: Float32
    plus(Timestamp, Timestamp) :: Timestamp

但在类型检查中我们允许一种例外，我们允许子类型转换为父类型（CAST），这样就可以让函数接受子类型的参数。我们看这样一个例子：

plus(1, 2.0)

类型推导器根据规则推导出常量的类型：

 1 :: Int8
 2.0 :: Float32

经过查询 FunctionRegistry，我们发现函数 plus 有两个重载看似可以使用但又不完全匹配：

(Int8, Int8) :: Int8
plus(Float32, Float32) :: Float32

这时类型检查器会尝试启用 CAST 规则尽最大可能选择一个重载。根据 CAST 规则，Int8 可以无损转化成 Float32，因此类型检查器会改写表达式结构然后重新检查类型：

plus(CAST(1 AS Float32), 2.0)

这样就能顺利通过类型检查了。

泛型

新的类型检查器支持在函数签名定义中包含泛型，用来减少需要手动定义的重载函数的数量。比如我们可以定义一个函数 array_get<T0>(Array<T0>, UInt64) :: T0，它接受一个数组和一个下标，并返回数组中下标对应的元素。

相比上一节中讲到的类型检查，检查含有泛型签名的函数多了一个步骤：选择一个合适的具体类型替换泛型，替换后的类型需要可以通过类型检查，如果不存在这样的具体类型则返回说明原因（比如有冲突的约束）。这个步骤一般称为 Unification，我们也用一个例子加以说明：

假设有两个表达式，它们的类型分别是：

ty1 :: (X, Boolean)
ty2 :: (Int32, Y)

如果我们需要 ty1 和 ty2 拥有相同类型（比如 ty1 是入参表达式类型，ty2 类型是入参签名），unify 会尝试将 X 和 Y 替换为具体类型：

let subst: Subsitution = unify(ty1, ty2).unwrap();

assert_eq!(subst['X'], DataType::Int32]);
assert_eq!(subst['Y'], DataType::Boolean]);

对 unify 有兴趣的读者可以阅读 type_check.rs 源码。在此推荐一本好书《Types and Programing Languages》，其中阐述了编程语言的类型推导发展历史，深入讨论分析各种推导理论的原理和取舍，各个重要概念都有配套的 toy implementation 作为例子，非常值得失眠时阅读。