MatrixOne Intelligence 开服在即，点击数据库内核之Binder
作者：欧远宁 MO研发工程师
目录
Part 1.
数据库内部处理流程及Binder的位置
Part 2.
Binder模块的主要职责
Part 3.
从伪代码看Binder的输出
Part 4.
Binder的执行顺序和输出
Part 5.
绑定过程中的一些问题及处理方案
本文字数：3800+字 阅读时间：10分钟
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 从取数到输出结果集整个过程的伪代码： 从伪代码中，我们可以看到一条查询操作，从读取数据到返回结果集之间，其实是由一个个完成特定计算需求的子模块所组成的。 这些计算子模块在执行期间被称为算子，在Bind阶段我们称为一个计算节点。 对于Binder来说，其输出的结果就是这些计算节点的组合。我们可以参考伪代码的执行流程，把这些计算节点按树状结构或数组等形式输出。这样的输出就可以在逻辑上表达清楚执行期的执行逻辑，并被数据库内核的后续阶段所使用。//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})}
Part 4 Binder的执行顺序和输出 Binder在对AST进行绑定操作的时候，也是有执行顺序的。这个顺序的参考依据就是伪代码中的执行顺序，因为只有按照这个顺序，我们才能根据当前节点的上下文信息验证语义的正确性。 参考伪代码中的执行顺序，大部分情况下，各个子句的绑定顺序和对应的计算节点如下： << 左右滑动查看全图 >> 当然还有一些比较复杂的子句和计算节点/算子（比如union、窗口函数类），这里不做一一介绍了。大家可以参考MO中的plan.proto，里面的NodeType有比较全面的定义。比如这样的一个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列。所以应该要报错，不然执行期间也会找不到这一列。
Part 5 绑定过程中的一些问题及处理方案 >>> 5.1 不同子句中对于表达式（Expr）的支持不一样的问题 因为不同子句所处的上下文不同，对于所支持的表达式类型会有不同。 这时候需要我们在Bind Expr的时候，能根据当前子句的类型来做处理。这时可以建立一个基类来处理通用的 Bind Expr，通过不同子句的子类来处理特定的情况。 目前MO是通过实现一个Binder接口，然后各个子句实现自己的Binder来做处理。对应的Binder接口如下： >>> 5.2 如何精确定位某个列 非Source类的计算节点，其输入都会包含上一个计算节点处理后的数据集。当我们要定位数据集中某列数据的时候，可以通过名称来查找，也可以相对位置（第几列），或者绝对位置（列的全局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部分的实现，应该会更加清晰。比如：select a, b from t1 order by 2这里的2这个常量表达式，其含义是以当前投影（Projection）的第二列来排序。而其他的子句，那就是一个普通的数字常量2.一般来说，不同的子句在Bind Expr的时候一般要注意：- 是否支持列表达式。比如 limit 子句 是不支持列表达式的- 是否支持聚合函数，比如where子句是不支持聚合函数的，应该放在having子句中- 是否支持窗口函数，大部分子句都不支持窗口函数，应该放在select子句中处理- 是否支持子查询，比如 limit子句是不支持子查询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}假设存在表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去上游数据集里查找到对应列。