【连载】openGauss 执行器技术

执行器在数据库的整个体系结构中起承上(优化器)启下(存储)的作用。本文首先介绍执行器的基本框架，然后引申介绍执行引擎中的一些关键技术。通过本文的阅读，读者能对执行器有个基本的认识。

一、 openGauss 执行器概述

从客户端发出一条 SQL 语句到结果返回给客户端的整体执行流程如图1所示，从中可以看到执行器所处的位置。

图1 客户端发出 SQL 语句的执行流程示意图

如果把数据库看成一个组织，优化器位于组织的最上层，是这个组织的首脑，是发号施令下达指令的机构，执行器位于组织的中间，听从优化器的指挥，严格执行优化器给予的计划，将从存储空间中读取的数据进行加工处理最终返回给客户端。

关系是元组(表中的每行，即数据库中每条记录)的集合，而关系代数是集合上的一系列操作。

执行器接收到的指令就是由优化器应对 SQL 查询而翻译出来的关系代数运算符所组成的执行树。一棵形象的执行树如图2所示。

图2 执行树示意图

图中的每一个方块代表一个具体的关系代数运算符，称其为算子，而两种箭头代表流（蓝色箭头为①，红色箭头为②）。其中，标注为①的流代表数据流，可以看到数据从叶节点流到根节点;标注为②的流代表控制流，从根节点向下驱动(指上层节点调用下层节点函数的数据传送函数，从下层节点请求数据)。

执行器的整体目标就是在每一个由优化器构建出来的执行树上，通过控制流驱动数据流在执行树上高效流动，其流动的速度决定了执行器的处理效率。

二、openGauss 执行引擎

下面具体介绍 openGauss 的执行引擎。

（一）执行流程

执行器的整体执行流程如图3所示。

图3 执行器整体执行流程图

上文 openGauss 执行器概述中描述了执行器在整个数据库架构中所处的位置，执行引擎的执行流程非常清晰，分成3个阶段。

(1)初始化阶段。在这个阶段执行器会完成一些初始化工作，通常的做法是遍历整个执行树，根据每个算子的不同特征进行初始化执行。比如 HashJoin 这个算子，在这个阶段会进行 Hash 表的初始化，主要是内存的分配。

(2)执行阶段。这个阶段是执行器最重要的部分。在这个阶段，执行器完成对于执行树的迭代(Pipeline)遍历，通过从磁盘读取数据，根据执行树的具体逻辑完成查询语义。

(3)清理阶段。因为执行器在初始化阶段向系统申请了资源，所以在这个阶段要完成对资源的清理。比如在 HashJoin 初始化时对 Hash 表内存申请的释放。

（二） 执行算子

openGauss 执行器概述中提到表达一个SQL语句需要很多不同的代数运算符进行组合。openGauss 为了完成这些代数运算符的功能，引入了算子(Operator)。算子是执行树的最基本的运算单元。按照不同的功能，算子划分为如下几种。

1.控制算子 

控制算子并不映射代数运算符，而是为使执行器完成一些特殊的流程所引入的，其主要类型及描述见表1。

表1 控制算子

算子类型	描述
Result	处理仅需要一次计算的条件表达式或insert中的value子句
Append	处理大于或者等于2的子树流程
BitmapAnd	需要对两个或以上位图进行并操作的流程
BitmapOr	需要对两个或以上位图进行或操作的流程
RecursiveUnion	用于处理with recursive递归查询
Limit	用于处理下层数据的limit操作
VecToRow	用于普通执行器和向量化执行器之间数据传输的转换

2.扫描算子

扫描算子负责从底层数据来源抽取数据，数据来源可能来自文件系统，也可能来自网络(分布式查询)。扫描节点(算子在执行树上称为节点)都位于执行树的叶子节点，作为执行树的数据输入来源。扫描算子的类型及描述见表2。

表2 扫描算子

算子类型	描述
Seqscan	顺序扫描行存
CstoreScan	顺序扫描列存
DfsScan	顺序扫描HDFS类文件系统
Stream	顺序扫描来自网络的数据流，数据流一般来自其他子树执行分发到网络中的数据
BitmapHeapScan	通过bitmap结构获取元组
BitmapIndexScan	利用索引获取满足条件的bitmap结构
TidScan	通过事先得到的Tid来扫描heap上的数据
SubQueryScan	从子查询的输出来扫描数据
ValueScan	扫描Values子句产生的数据源
CteScan	扫描cte表达式
WorkTableScan	扫描RecursiveUnion产生的迭代数据
FunctionScan	扫描Function产生的批量数据
IndexScan	扫描索引得到Tid，然后从heap上扫描数据
IndexOnlyScan	在某些情况下，可以只用扫描索引就能得到查询想要的数据，因此不需要扫描heap
ForgeinScan	从用户定义的外表数据源扫描数据

3.物化算子

物化算子指算子的处理无法全部在内存中完成，需要进行下盘(即写入磁盘)操作。因为物化算子算法要求，在做物化算子逻辑处理的时候，要求把下层的数据进行缓存处理。因为对于下层算子返回的数据量不可提前预知，所以需要在物化算子算法上考虑数据无法全部放置到内存的情况。物化算子的类型及描述见表3。

表3 物化算子

算子类型	描述
Sort	对下层数据进行排序，例如快速排序
Group	对下层已经排序的数据进行分组
Agg	对下层数据进行分组（无序）
Unique	对下层数据进行去重操作
Hash	对下层数据进行缓存，存储到一个hash表里
SetOp	对下层数据进行缓存，用于处理intersect等集合操作

 4.连接算子

连接算子是为了应对数据库中最常见的连接操作，根据处理算法和数据输入源的不同，连接算子分成以下几种类型，如表4所示。

表4 连接算子

算子类型	描述
Nestloop	对下层两股数据流实现循环嵌套连接操作
MergeJoin	对下层两股排序数据流实现归并连接操作
HashJoin	对下层两股数据流实现哈希连接操作

同时为了应对不同的连接操作，openGauss定义了如下的连接算子的连接类型。定义两股数据流，一股为S1(左)，一股为S2(右)，连接算子的连接类型如表5所示。

表5 连接算子的连接类型

Join算子连接类型	描述
Inner Join	内连接，对于S1和S2上满足条件的数据进行连接操作。
Left Join	左连接，对于S1没有匹配S2的数据，进行补空输出。
Right Join	右连接，对于S2没有匹配S1的数据，进行补空输出。
Full Join	全连接，除了Inner Join的输出部分，对于S1，S2没有匹配的部分，进行各自补空输出
Semi Join	半连接，当S1能够在S2中找到一个匹配的，单独输出S1
Anti Join	反连接，当S1能够在S2中找不到一个匹配的，单独输出S1

 表4中的3个连接算子都已经支持表5中6种不同的连接类型。

NestLoop算子:对于左表中的每一行，扫描一次右表。算法简单，但非常耗时(计算笛卡儿乘积)，如果可以用索引扫描右表，则可能是一个不错的策略。可以将左表的当前行中的值用作右索引扫描的键。

MergeJoin:在连接开始前，先对每个表按照连接属性(Join Attributes)进行排序，然后并行扫描两个表，组合匹配的行形成连接行。MergeJoin只需扫描一次表。排序可以通过排序算法或使用连接键上的索引来实现。

HashJoin:先扫描内表，并根据其连接属性计算哈希值作为哈希键(Hash Key，也称散列键)存 入 哈 希 表 中。然后扫描 表，计算哈希键，在哈希表中找到匹配的行。

对于连接的表无序的情况，MergeJoin操作需要将两个表扫描并进行排序，复杂度会达到O(nlogn)，而 NestLoop操作是一种嵌套循环的查询方式，复杂度达到O(n2)。而 HashJoin操作借助哈希表来加速查询，复杂度基本在O(n)。

不过，HashJoin操作只适用于等值连接，对于>、<、<=、>=这样的连接还需要 NestLoop这种通用的连接方式来处理。如果连接键是索引列本来就有序，或者 SQL 本身需要排序，那么用 MergeJoin操作的代价会比 HashJoin操作更小。

下面简单介绍 HashJoin操作的执行流程。

HashJoin，顾名思义，就是利用哈希表进行连接查询，哈希表的数据结构组织形式如图4所示。

图4 哈希表

可以看到，哈希表根据哈希值分成多个桶，相同的哈希键值的元组用链表的方式串联在一起，因为哈希算法的高效和哈希表的唯一指向性，HashJoin操作的匹配效率非常高，但是 HashJoin操作只能支持等值查询。

HashJoin节点有两棵子树:一棵称为外表; 另一棵称为内表。内表输出的数据用于生成哈希表，而外表生成的数据则在哈希表上进行探查并 返回连接结果。

在内、外表的选择上，优化器一般根据这两棵子树的代价进行分析选择。因为哈希表需要申请内存进行存放，因此优化器倾向于输出行数少的子树作为内表，这样数据能够被内存存放的概率比较大，如果存放不下，则需要进行下盘操作。

HashJoin操作的主要执行流程如下:

(1)扫描内表元组，根据连接键计算哈希值，并插入到哈希表中根据哈希值计算出来的槽位上。在这个步骤中，系统会反复读取内表元组直到把内表读取完，并将哈希表构建出来。

(2)扫描外表元组，根据连接键计算哈希值，直接查找哈希表进行连接操作，并将 结果输出，在这个步骤中，系统会反复读取外表直到外表读取完毕，这个时候连接的结 果也将全部输出。

上面提到，如果当前的内表元组无法全部放在内存里，会进行下盘(写入磁盘)操作，HashJoin对于下盘支持的设计思想非常精妙，采用了典型的分而治之的算法。

(3)根据内表和外表的键值的哈希值，对内表和外表进行分区，经过分区之后，内表和外表被划分成很多小的内、外表，这里的划分原则是以相同的哈希值分区之后数据要划分到相同下标的内、外表中，同时内表的数据要能够存放在内存里。

(4)取相同下标的内、外表，重复步骤(1)和(2)中的算法进行元组输出。

(5)重复步骤(4)的操作，直到处理完所有的经过分区后的内、外表。

（三）表达式计算

除了算子，为了代数运算符的完备性，还需要有表达式的计算。根据SQL语句的不同，表达式的计算可能产生在每个算子上，用于进一步处理算子上的数据流。表达式的计算主要有以下两个功能。

(1)过滤:根据表达式的逻辑，过滤掉不符合规则的数据。

(2)投影:根据表达式的逻辑，对数据流进行表达式变换，产生新的数据。表达式计算的核心是对表达式树的遍历和计算，前面说到算子也是用树来表达执行计划。树这个基础的数据结构在执行器的流程中扮演了非常重要的角色。

看下面这个SQL语句:

SQL2：select w_id from warehouse where 2*w_tax + 0.9 > 1 and w_city != ‘Beijing’;

SQL语句中 where条件后面的就是SQL表达式，如果以树的形式展现，如图5所示。

图5 SQL语句表达式树

表达式计算对算子上的数据流进行计算，通过遍历表达式计算树完成整体的表达式计算(为了便于说明，我们对上述表达式树中每个节点进行了编号，见节点前的数字)，可以看到上面的图中有些节点中标注的是 Const，这代表这个节点是一个定值节点，存储了一个定值，有些节点中标注的是 ExpOp，这代表这个节点是一个计算节点，根据表达式的不同有不同的计算方法，有些节点标注的是 Col，代表从表中的某个列中读取的数据。上述的表达式计算的详细的流程如下:

(1)根节点11 代表一个 AND 运算符，AND 逻辑是只要有一个子树的结果为false，则提前终止运算，否则进行下一个子树运算。下面有两个子表达式，先处理节点9，首先递归遍历到其子节点3。

(2)节点3代表了一个乘法，有两个子节点1、2，从节点1列中取得w_tax的值，从节点2中取得定值2，然后进行乘法运算，计算数据存储到节点3引擎的暂存空间中。

(3)节点5代表一个加法运算，有两个子节点3、4，因此从节点4上取定值0.9，表达式3的结果刚才在第(2)步中已经计算了，只需要读取出来，运算结果存储到节点5的暂存空间里。

(4)节点9代表一个比较运算，其有两个子节点5、6，因此将节点5存储的数据和节点6上的定值数据1进行大于比较，如果结果为false，则提前终止当前的表达式运算， 跳入下一行，重新从步骤(1)开始计算，如果为true，则进行下一个子表达式的计算。

(5)节点9已经处理完毕，接着处理节点10。

(6)节点10代表字符串不等于比较运算，有两个子节点7、8，从节点7中取得 w_city值，同时从节点8中取得定值字符串“Beijing”，然后进行不等于字符串比较运算，如果为true，输出元组(Tuple)，否则重新从步骤(1)开始计算。

由此可见，通过遍历整个表达式树，根据表达式树的不同节点的类型做出相应的动作，有些是对数据的读取，有些是进行函数计算。表达式树中叶子节点都来自数据流中的数据或者栈上的定值，而非叶子节点都是计算函数。

三、openGauss 执行器的高级特性介绍

本文将介绍openGauss执行器的几个高级特性，在介绍高级特性之前，先简单介绍当前 CPU 体系架构中影响性能的几个关键因素。这些关键因素和其对应的技术构成了执行器中的两个高级特性:编译执行和向量化引擎。影响性能的关键因素如下:

(1)函数调用:函数调用过程中需要维护参数和返回地址在栈帧的管理，处理完成之后还要返回到之前的栈帧，因此在用户的函数调用过程中，CPU 要消耗额外的指令进行函数调用上下文的维护。

(2)分支预测:指令在现代 CPU 中以流水线运行，当处理器遇到分支条件跳转指令时，通常不能确定执行哪个分支，因此处理器采用分支预测来预测每条跳转指令是否会执行。如果猜测准确，那么流水线中就会充满指令;如果对跳转猜测错误，那么就要求处理器丢掉它这个跳转指令后的所有已做的操作，然后再开始用从正确位置起始的指令去填充流水线。可以看到，这种预测错误会导致很严重的性能惩罚，即会导致20~40个时钟周期的浪费，从而导致 CPU 性能严重下降。提速方式有两种:一种是更准确的智能预测，但是无论多么准确，总会存在误判;另一种就是从根本上消除分支。

(3)CPU 存取数据:CPU 对于数据的存取存在鲜明的层次关系，CPU 在寄存器、CPU 高速缓存(CACHE)、内存中的存取速度依次越来越慢，所承载的容量却越来越大。同时，CPU 在访问数据的时候也会遵循从快到慢的原则，比如缓存中找不到的数据才会从内存中找，而这两者的访问速度差距在两个数量级。如果 CPU 的访问模式是线性的(比如访问数组)，CPU 会主动将后续的内存地址预加载到缓存，这就是 CPU的数据预取。因此，如果程序能够充分利用这个特征，将大大提高程序的性能。

(4)SIMD(单指令多数据流):对于计算密集型程序来说，可能经常需要对大量不同的数据进行同样的运算。SIMD引入之前，执行流程为同样的指令重复执行，每次取一条数据进行运算。而SIMD可以一条指令执行多个位宽数据的计算。比如当前最新的体系结构已经支持512位宽的SIMD指令，那么对于16位整型的加法，可以并行执行32个整型对的加法。

（一）编译执行

上文介绍了基于遍历树的表达式计算框架。这种框架的好处是清晰明了，但在性能上却不是最优的，主要有以下几个原因:

(1)表达式计算框架的通用性决定了其执行模式要适配各种不同的运算符和数据类型，因此在运行时要根据表达式遍历的具体结果来确定执行的函数和类型，对这些类型的判断要引入非常多的分支判断。

(2)表达式计算在整体的执行过程中要进行多次的函数调用，其调用的深度取决于表达式树的深度，这也有着非常大的开销。

除了上述两个主要原因，分支判断和函数调用在执行算子中也是影响性能的关键因素。为了提升表达式计算的执行速度，openGauss引入了业界著名的开源编译框架———LLVM(LowLevelVirtualMachine)。

LLVM 是一个通用的编译框架，能够支持不同的计算平台。LLVM 提升整体表达式计算执行速度的核心要点如下。

(1)openGauss内置的 LLVM 编译框架通过为每一个计算单元(表达式或者执行算子里面的热点函数)生成一段独特的执行代码，由于在编译的时候提前知道了表达式涉及的操作和数据类型，可将表达式生成的执行代码中所有的逻辑内联，完全去除函数调用。

比如对于上文提到的表达式计算过程，openGauss内置的 LLVM 编译为这个表达式生成了下面这样一段特殊代码，其中已经没有任何函数调用，所有的函数都已经被内联在一起，同时去掉了关于数据类型的分支判断。

Bool qual()
{
bool qual1res = 2 * w_tax + 0.9 > 1;
bool qual2res = w_city !=’Beijing’;
Return qual1res && qual2res;
}

(2)LLVM 编译框架利用编译技术最大限度地让生成的代码将中间结果的数据存储在 CPU 寄存器里，以加快数据读取的速度。

（二） 向量化引擎

上文提到了执行器的数据流动模式:控制流向下、数据流向上。传统的执行引擎数据流遵循一次一元组的传输模式，而向量化引擎将这个模型改成一次一批元组的模式，这种看似简单的修改却带来巨大的性能提升。单个元组与向量化元组的对比如图6所示。

图6 单个元组与向量化元组对比

其中的主要原因如下，这也与前面介绍的 CPU 架构中影响性能的几个关键因素对应。

(1)一次一元组的函数模型在控制流的调动下，每次都需要进行函数调用，调用次数随着数据的增长而增长，而一次一批元组的模式则大大降低了执行节点的函数调用开销，如果设定一次一批元组的数量为1000，则函数调用相对于一次一元组能减少3个数量级。

(2)一次一批元组的模式在内部实现上是通过数组来表达的，CPU 对数组的存取非常友好，能够让数组在后续的数据处理过程中，大概率能够在缓存中被命中。比如下面这个简单计算两个整型数据加法的函数(其代码仅为了展示，不代表真实实现)，展示了一次一元组和一次一批元组的两种编写代码方法。

一次一元组的整型数据加法:

int int4addint4(int4 a, int b)
{
     Return a+b;

一次一批元组的整型数据加法:

void int4addint4(int4 a[], int b[], int res[])
{   for(int i = 0; i < N; i++)
       res[i] = a[i] + b[i];
}

一次一批元组的这个计算函数，因为 CPU 高速缓存的局部性原理，数据和指令的缓存命中率会非常好，可极大提升处理性能。

(3) 一次一批元组的数据数组化的组织方式为利用SIMD特性带来了非常好的机会，使SIMD能够大大提升在元组上的计算性能。还是以上述整型数据加法的例子讲解，可以重写上述的函数如下。

void int4addint4SIMD(int4 a[], int b[], int res[])
{  
for(int i = 0; i < N/SIMDLEN; i++)
   res[i..i+SIMDLEN] = SIMDADD(a[i..i+SIMDLEN], b[i..i+ SIMDLEN];
}

可以看到，由于SIMD可以一次处理一批数据，使循环的次数衰减，因此性能可得到进一步提升。

四、小结

本文描述了 openGauss 执行引擎的基本构成和一些技术特点，执行器作为数据库查询的最 终 执 行 单 元，其 架 构 和 技 术 决 定 了 数 据 库 执 行 查 询 的 整 体 运 行 效 率，openGauss 执行引擎采用了诸如向量化、编译执行等多种现代软件技术，并充分结合硬件技术的特征进行高效执行。

---

全文完，希望可以帮到正在阅读的你，如果觉得此文对你有帮助，可以分享给你身边的朋友，同事，你关心谁就分享给谁，一起学习共同进步~~~

❤️ 欢迎关注我的公众号【JiekeXu DBA之路】，一起学习新知识！

————————————————————————————
公众号：JiekeXu DBA之路
CSDN ：https://blog.csdn.net/JiekeXu
墨天轮：https://www.modb.pro/u/4347
腾讯云：https://cloud.tencent.com/developer/user/5645107
————————————————————————————