数据库内核之 Binder

作者：欧远宁  MO 研发工程师

Part 1 数据库内部处理流程及 Binder 的位置

数据库是“按照数据结构来组织、存储和管理数据的仓库”，是一个长期存储在计算机内的、有组织的、可共享的、统一管理的大量数据的集合。

而数据库对外服务的过程一般是：解析输入的结构化查询语言（SQL），并根据解析结果执行内部数据操作，最后返回响应信息（一般是错误信息或者所查询数据集）。

一个通过网络对外提供服务的数据库，其内部的执行过程可以简单理解为这样：

图中的 Listener、Codec、Protocol 几个模块是一般网络服务器的通用模块。数据库系统一般会根据自定义协议，完成网络数据包的拆包、封包以及传输，这里不做特别讨论。

图中其他的部分就是数据库内核的主要模块了。这些模块的简要说明如下：

这里的元信息是比较笼统的概念，它可能包含了操作系统元信息、数据库系统元信息、当前 Session 元信息、本次请求上下文元信息等。事务执行器这里指能基于事务隔离级别和当前事务状态，获取可见数据、增删改可见数据的特定数据结构（Struct）、类（Class）等。

Part 2 Binder 模块的主要职责

从数据库内核的执行顺序，可以看到 Binder 是数据库内核中非常关键的模块。它是从用户想要做什么到数据库内核要怎么做的连接模块。

• 用户想要做什么的表达方式是输入的 SQL，并在 Binder 前被转成抽象语法树（AST）。

• 数据库内核要怎么处理的表达方式就是最后执行的物理计划（PhysicalPlan）。

所以对于 Binder 的主要工作我们可以理解为：根据输入的符合 SQL 语法的抽象语法树结构，通过当前数据库系统的各类元信息来验证语义的合法性（比如：通过 Schema 信息确定表是否存在；通过函数注册信息，确定函数是否存在；通过节点上下文确定列的含义等），然后根据数据库内核的实际执行流程，构造出对应的逻辑执行节点。以便后续的优化、编译和执行。

由于 Binder 最后输出的结果最终是服务于执行的，所以首先需要了解数据库内核在执行期（Executor 执行阶段）的执行逻辑，从而确定我们大概要输出些什么？确定了输出之后我们再看从 AST 到这个输出的步骤和面临的问题。

Part 3 从伪代码看 Binder 的输出

由于各数据库内核使用的执行模型不同，其逻辑计划的组织方式会有些差异。比如火山模型，其执行期的输入更多时候倾向于一棵执行节点的树；Push 模型的话，更倾向于在执行前编译成一条条并行的执行管道（Pipeline）数组。

但是无论使用哪种模型，数据库系统都是要根据用户描述的需求（SQL），从存储的数据单元中取出数据，然后进行过滤、分组、排序、抽取等操作从而得到最终结果集的过程（insert/update/delete 可以理解为得到结果集后再进行一次数据操作）。也就是其实我们可以不用特别关心内核使用哪种执行模型，我们可以从这个数据操作的过程（可用伪代码模拟）来推导一下，Binder 的输出大概应该是怎么样的。

我们以一条相对复杂的单表查询语句为例，通过手写代码，看看完成这条 SQL 语句所需执行的步骤有哪些。

我们假设有表结构如下：

create table t1(a int, b int, c int, d int);

所需执行的 SQL：

select a, sum(d) as sum_d from t1 where abs(b) > 5 group by a, c having sum_d > 10 order by sum_d limit 3 offset 2

从取数到输出结果集整个过程的伪代码：

//0 从事务执行器中，获取当前事务的可见数据rows = txn_operator.get_rows_you_can_see() //1对数据进行筛选，结果列包含：a,b,c,dvar after_filter_rowsfor row in rows {    if abs(row.b) > 5 {after_filter_row.push(row);}} //2.1 对数据进行分组求和，hash_sum = hashmap<(int, int), int64>for row in after_filter_rows {    hash_sum[(a, c)] += row.d}//2.2返回分组求和后的结果集，结果列包含：a,c,sum_dvar after_agg_rows;for (a,c), sum_d in hash_sum {    after_agg_rows.push({a, c, sum_d})} //3 继续对数据进行筛选,  未更改输出列var after_agg_filter_rowsfor row in agg_rows {    if row.sum_d > 10 {after_agg_filter_rows.push(row)}} //4 排序, 不改变输出列after_sort_rows = sort_by_fileds(after_agg_filter_rows, [“sum_d”]) //5 跳过2行，不改变输出列after_offset_rows = skip_some_rows(after_sort_rows, 2) //6 取其中3行，不改变输出列after_limit_rows = fetch_some_rows(after_offset_rows, 3) //7 提取所需的列作为返回结果，结果列包含 a, sum_dresult_rows = []rowfor row in after_limit_rows {      result_rows.push({row.a, row.sum_d})}

从伪代码中，我们可以看到一条查询操作，从读取数据到返回结果集之间，其实是由一个个完成特定计算需求的子模块所组成的。

这些计算子模块在执行期间被称为算子，在 Bind 阶段我们称为一个计算节点。

对于 Binder 来说，其输出的结果就是这些计算节点的组合。我们可以参考伪代码的执行流程，把这些计算节点按树状结构或数组等形式输出。这样的输出就可以在逻辑上表达清楚执行期的执行逻辑，并被数据库内核的后续阶段所使用。

Part 4 Binder 的执行顺序和输出

Binder 在对 AST 进行绑定操作的时候，也是有执行顺序的。这个顺序的参考依据就是伪代码中的执行顺序，因为只有按照这个顺序，我们才能根据当前节点的上下文信息验证语义的正确性。

比如这样的一个SQL： create table t1(a int, b int);  select a, b, sum(c) from t1 group by a; //这里为什么会报错，说b不在group by子句或聚合函数中？  其实从上面伪代码的执行过程，我们可以了解到：1、要先执行group by 子句的binding，再执行select子句的binding。2、group by子句在binding后，其输出的列被改变为只剩下分组列和聚合函数结果列了（类似这里，就只剩下a, sum(c) 这2个列）。3、那么后面执行select子句binding的时候，它只能看到上面计算节点输出的a 列和sum(c)列，并没有b列。所以应该要报错，不然执行期间也会找不到这一列。

参考伪代码中的执行顺序，大部分情况下，各个子句的绑定顺序和对应的计算节点如下：

当然还有一些比较复杂的子句和计算节点/算子（比如 union、窗口函数类），这里不做一一介绍了。大家可以参考 MO 中的 plan.proto，里面的 NodeType 有比较全面的定义。

Part 5 绑定过程中的一些问题及处理方案

>>> 5.1 不同子句中对于表达式（Expr）的支持不一样的问题

因为不同子句所处的上下文不同，对于所支持的表达式类型会有不同。

比如：select a, b from t1 order by 2这里的2这个常量表达式，其含义是以当前投影（Projection）的第二列来排序。而其他的子句，那就是一个普通的数字常量2. 一般来说，不同的子句在Bind Expr的时候一般要注意：- 是否支持列表达式。比如 limit 子句 是不支持列表达式的- 是否支持聚合函数，比如where子句是不支持聚合函数的，应该放在having子句中- 是否支持窗口函数，大部分子句都不支持窗口函数，应该放在select子句中处理- 是否支持子查询，比如 limit子句是不支持子查询

这时候需要我们在 Bind Expr 的时候，能根据当前子句的类型来做处理。这时可以建立一个基类来处理通用的 Bind Expr，通过不同子句的子类来处理特定的情况。

目前 MO 是通过实现一个 Binder 接口，然后各个子句实现自己的 Binder 来做处理。对应的 Binder 接口如下：

type Binder interface {BindExpr(tree.Expr, int32, bool) (*plan.Expr, error)BindColRef(*tree.UnresolvedName, int32, bool) (*plan.Expr, error)BindAggFunc(string, *tree.FuncExpr, int32, bool) (*plan.Expr, error)BindWinFunc(string, *tree.FuncExpr, int32, bool) (*plan.Expr, error)BindSubquery(*tree.Subquery, bool) (*plan.Expr, error)GetContext() context.Context}

>>> 5.2 如何精确定位某个列

非 Source 类的计算节点，其输入都会包含上一个计算节点处理后的数据集。当我们要定位数据集中某列数据的时候，可以通过名称来查找，也可以相对位置（第几列），或者绝对位置（列的全局 id）来定位。

假设存在表t1create table t1(a int, b int, c int); 执行SQL： select a from t1 where b > 0; 对于TableScan节点，在没有做列裁剪的情况下，它会返回（a,b,c）三个列的数据集给后面的节点。 对于Filter节点来说， 要表达 b>0 中的b列。可以：- 在TableScan返回的数据集中包含列名；那么Filter节点则可根据列名“b”找到对应的列- 在Bind Filter的时候，告诉Filter节点请使用上游数据集中第2列的数据。- 在Bind TableScan的时候，给每个列一个全局列id。在Bind Filter的告诉Filter节点用b那列的全局列id去上游数据集里查找到对应列。

使用列名的方式会需要处理列名重叠的问题，一般比较少使用。

使用全局列 id 在优化器阶段会更便利，相对位置在执行阶段效率会更高一些。

也可以 Binder 和 Optimizer 阶段使用全局 id，Optimizer 最后把全局 id 转化为相对位置以便执行期更方便使用。这也是目前 MO 所使用的方案。

>>> 5.3 函数绑定的处理

一般来说具体的函数实现跟函数输入参数的类型是相关的。

比如对于 abs 函数的实现，输入参数是 int8 类型，它会有一个具体的实现，输入参数是 int64 类型，会有另外一个具体的实现。（我们把这些具体的实现函数叫做函数的重载）。

那么在 Bind 阶段，我们是应该确定到具体的重载，还是只检查函数名称是否有注册即可？

如果 Bind 阶段确定到重载，那么执行期效率会高些。但是那么对于类似：select * from t1 where a > ? and b < @var 这类 SQL 中的?和 @var 这些执行期才确定类型的表达式，需要特别处理。比如执行期将？和 @var 的表达式替换为对应类型的常量值表达式，然后重新再做一次函数绑定，才能确定其具体使用的函数重载。

如果 Bind 阶段只确定到名称，执行期再最后确定函数执行的重载，那么只需要绑定函数一次。不过在多数时候会牺牲一点执行效率。

>>> 5.4 其他

当然还有很多其他议题可以继续展开讨论，比如逻辑计划应该是树状结构还是 DAG 结构？Binder 和 Optimizer 的界限在哪里，是否 Bind 的过程就一定不要执行任何优化规则？Parser 应该提前给 Binder 预留点什么信息以简化 Bind 的过程及提升性能？Binder 又应该提前预留点什么信息给 Optmizer 等。

以上就是数据库内核中 Binder 的一个简单介绍。各个数据库系统也会根据自己的设计和需求特点对 Binder 的实现进行调整和优化。大家可以结合自己熟悉的数据库项目的源代码，参考其执行模型再去看 Binder 部分的实现，应该会更加清晰。