网站推广工具有哪些,仿站小工具官网,张家港网页设计培训,成都网站建设企业简介#xff1a; 向量化引擎为PolarDB-X的表达式计算带来了显著的性能提升。 介绍 PolarDB-X是阿里巴巴自研的云原生分布式数据库#xff0c;采用了计算-存储分离的架构#xff0c;其中计算节点承担着大量的表达式计算任务。这些表达式计算涉及到SQL执行的各个环节#xff… 简介 向量化引擎为PolarDB-X的表达式计算带来了显著的性能提升。 介绍 PolarDB-X是阿里巴巴自研的云原生分布式数据库采用了计算-存储分离的架构其中计算节点承担着大量的表达式计算任务。这些表达式计算涉及到SQL执行的各个环节对性能有着重要的影响。为此PolarDB-X引入向量化执行引擎为表达式计算带来了几十倍的性能提升。 传统数据库执行器的缺陷 现代数据库系统的执行引擎大多采用一次计算一行数据Tuple-at-a-time的处理方式并且需要在运行时对数据类型进行解析和判断来适应复杂的表达式结构。我们称之为“标量scalar表达式”。这种方式虽然易于实现、结构清晰但是当需要处理的数据量增大时它具有显著的缺陷 为了适应复杂的表达式结构计算一条表达式往往需要引入大量的指令对于行式执行来说处理单条数据需要算子树重新进行指令解释instruction interpretation从而带来了大量的指令解释开销。据论文《MonetDB/X100: Hyper-Pipelining Query Execution》统计在MySQL执行TPC-H测试集的 Query1 时指令解释就耗费了90%的执行时间。 此外在最初的Volcano结构设计中算子内部逻辑并没有避免分支预测branch prediction。错误的分支预测需要CPU终止当前的流水线将ELSE语句中的指令重新载入我们将这一过程称为pipeline flush或pipeline break。频繁的分支预测错误会严重影响数据库的执行性能。 向量化执行系统 数据库向量化执行系统最早由论文《MonetDB/X100: Hyper-Pipelining Query Execution》提出它有以下几个要点
采用vector-at-a-time的执行模式即以向量vector为数据组织单位。使用向量化原语vectorization primitives来作为向量化算子的基本单位从而构建整个向量化执行系统。原语中避免产生分支预测。使用code generation代码生成技术来解决静态类型带来的code explosion代码爆炸问题。向量化引擎为PolarDB-X的表达式计算带来了显著的性能提升。在下图中横轴为向量大小纵轴为吞吐量不同标量表达式和向量化表达式的性能测试对比结果如下 case表达式性能测试对比结果如下 整体流程 PolarDB-X中向量化表达式的执行分为以下几个阶段
用户SQL经解析后在validator中进行校验推导和修正表达式的类型信息这一阶段为向量化运算提供正确的、静态的类型信息在优化器形成执行计划之后需要对表达式树进行表达式绑定实例化对应的向量化原语同时分配好向量下标供运行时内存分配执行阶段依据Volcano式的结构自顶向下的触发执行向量化原语并将向量作为运行时数据结构。运行时结构 数据结构 在PolarDB-X向量化执行系统中采用以下的数据结构来存放数据 向量化表达式执行时所有的数据都会存放在batch这一数据结构中。batch由许多向量vector和一个selection数组而组成。其中向量vector包括一个存储特定类型的数值列表values和一个标识null值位置的null数组组成它们在内存中都是连续存储的。null数组中的bit位以0和1来区分数值列表中的某个位置是否为空值。 我们可以用vector(type, index)来标识batch中一个向量。每个向量有其特定的下标位置(index)来表示向量在batch中的顺序类型信息type来指定向量的类型。在进行向量化表达式求值之前我们需要遍历整个表达式树根据每个表达式的操作数和返回值来分配好下标位置最后根据下标位置统一为向量分配内存。 延迟物化 selection数组的设计体现了延迟物化的思想参考论文《Materialization Strategies in a Column-Oriented DBMS》。所谓延迟物化就是尽可能地将物化matrialization这一过程后推减少内存访问带来的开销。在执行表达式计算时往往会先经过Filter表达式过滤一部分数据再对过滤后的数据执行求值处理每次过滤都会影响到batch中所有的向量。以上图中的batch为例如果我们针对第0个向量设置 vector(int, 0) ! 1这一过滤条件假设vector(int, 0)中有90%的数据满足该过滤条件选择率selectivity 0.9那么我们需要将batch中所有向量90%的数据重新物化到另一块内存中。而如果我们只记录满足该过滤条件的位置存入selection数组我们就可以避免这一物化过程。相应的以后每次向量化求值过程中都需要参考此selection数组。 向量化原语 向量化原语是向量化执行系统中的执行单位它最大程度限制了执行期间的自由度。原语不用关注上下文信息也不用在运行时进行类型解析和函数调用只需要关注传入的向量即可。它是类型特定Type-Specific的即一类原语只能处理特定类型。 向量化原语的主体是Tight-Loop的代码结构。在一个循环体内部只需要进行取值和运算即可没有任何的分支运算和函数调用。一个简单的向量化原语结构如下所示 map_plus_double_col_double_col(int n,
double*__restrict__ res,
double*__restrict__ vector1, double*__restrict__ vector2,
int*__restrict__ selection)
{if (selection) {for(int j0;jn; j) {int i selection[j];res[i] vector1[i] vector2[i];} } else {for(int i0;in; i)res[i] vector1[i] vector2[i];}
}
注*左右滑动阅览 其运算过程利用了selection数组逐步对向量进行取值、运算和存值如下图所示 向量化原语带来了以下优点
Type-Specific以及Tight-Loop的结构大大减少了指令解释的开销避免分支预测失败和虚函数调用对CPU流水线的干扰同时也能有利于 loop pipeline 优化【论文引用】从向量中存取数据有利于触发cache prefetch减少cache miss带来的开销。我们为各种标量化表达式提供相应的原语实现从而完成从标量到向量化的转变。例如将加法运算 plus(Object, Object) 针对不同操作数类型生成原语包括plus(doubledouble)plus(long, long)等。 短路求值 在向量化原语的基础上我们可以进一步对分支运算也称为控制流运算 Control-Flow进行短路求值short-circuit calculation优化提升表达式计算的性能。 例如case 表达式由n个when表达式、n-1个then表达式、1个else表达式构成。对于表达式 select case when a 1 then a * 2when b 1 then b * 2else a * b 具有以下树形结构 由于标量化表达式按照volcano结构编排并提供了统一的next()的接口case表达式必须执行完所有的子表达式a1a*2b1b*2和a*b之后将全部结果汇总到一起最后做case语义处理。这种执行方式不能根据when表达式的处理结果及时终止计算过程而是对全部子表达式无差别执行。 引入向量化执行器以后我们可以设计短路求值来优化此问题每一个子表达式需要被提供合适的selection数组从而正确选择列中合适的位置来进行向量运算。 作者君启
原文链接
本文为阿里云原创内容未经允许不得转载
