水简介

首页 » 常识 » 诊断 » OLAP中SQL表达式执行加速技术浅析
TUhjnbcbe - 2022/2/24 14:25:00
表达式执行作为在SQL查询处理中被大量调用的模块,其实现的好坏会直接影响数据库的查询性能,如PostgreSQL中不同的表达式计算方式将会给TPC-HQ1带来5倍的性能差距,因此一个追求性能的数据库系统都会对自己的表达式模块的性能做一些优化。本文会基于目前已有的一些优化技术看看几个数据库系统的实现(一)常见表达式优化技术表达式为什么慢在提到怎么优化之前,要先搞清楚一个问题,就是数据库的表达式为什么慢,因为以MySQL的表达式处理为例子,当我们计算一个简单的a+b时,MySQL大概是这么处理的:先构造出一棵表示a+b的表达式树调用根节点表达式的val_int()接口所有节点的val_int()接口被递归调用返回结果从这个执行流程上来看,这里的问题是大量的虚函数调用,虽然对于一次计算来说可能浪费的时间不值一提,但是在火山模型中表达式往往会被调用成千上万次,这时候这样的开销就变的不能忽视了。虚函数调用的来源,实际上是我们在做"parse"导致的,试想一下,如果在写代码时就知道要计算的表达式是a+b,大多数人不会采取上文提到的流程执行,他们不会构造一棵树,会直接写出一个函数解决一切问题。再退一步再说,即使仍然是这样的流程,编译器都能够帮助你消除这其中所有的虚函数调用,而这一切的源头,都是我们要对用户的输入做解析,才能决定如何去执行。目前比较有名的表达式优化技术实际上都是在解决这一个问题:解决因为解析用户输入导致的开销,外在的表现就是大量的函数调用。方法1:向量化执行一个经常被提到的技术就是利用向量化执行加速表达式的执行,向量化实际上是一个“batch的火山模型”,与传统的一次处理一行的火山模型不同,batch模型通过一次处理一批数据来加速表达式的执行,例如对于一个普通的火山模型,表达式的计算可能是这样的:

intadd(Expr*lhs,Expr*rhs){returnlhs-val_int()+rhs-val_int();}对于向量化模型下的表达式,这个接口可能会变成这样:

int*add(Expr*lhs,Expr*rhs){int*dst=newint[BATCH_SIZE];int*lhs_val=lhs-val_int();int*rhs_val=lhs-val_int();for(inti=0;iBATCH_SIZE;i++)dst=lhs_val+rhs__val;returndst;}两者的不同就是后者能够在一次函数调用中处理一批数据,这样处理相同数据的话就让函数调用的次数大大减少了,从均摊到处理每一行数据来说,函数调用的开销就可以变的很小以至于忽略不计。方法2:SIMD指令向量化与SIMD在很多数据库表达式相关的文章中都会提到,并且往往一同出现,这让许多人会分不清两者的区别,这两者实际上完全不是一个东西,只是两者恰好常常出现在一起而已:

向量化:

利用batch模型在一次函数调用中处理多行数据,通过均摊消除表达式计算中的函数调用开销

SIMD:

通过CPU支持的指令集对向量化表达式的一种优化,还是以上文的加法举个例子,我们可以用SIMD指令对这个加法表达式进行优化:

可以看到接口是没有变的,只是里面通过SIMD指令进行了加速,现在执行一条指令的时间可以直接处理16条结果的加法运算,而之前只能处理一条,因此可以说这两个优化是分别作用在接口和实现上的优化,并没有什么特别的联系.

//SIMD优化int*add(Expr*lhs,Expr*rhs){int*dst=newint[BATCH_SIZE];int*lhs_val=lhs-val_int();int*rhs_val=lhs-val_int();intoffset=0;for(offset=0;offsetBATCH_SIZE;offset+=16){__mival1_=_mm_load_epi32(lhs_val+offset);__mival2_=_mm_load_epi32(rhs_val+offset);__mires_=_mm_add_epi32(val1_,val2_);_mm_store_epi32(dst+offset,res_);}//省略尾部处理...returndst;}方法3:编译执行上面的向量化执行可以把函数调用的开销降低到原来的千分之一,万分之一...但是之前我们也提到,如果我们能够知道表达式是什么然后手写代码的话,那我们就可以完全消除这些开销,那么自然就会想到另一个办法:“解析用户输入之后手写一份代码来执行这个表达式不就好了么?”这就是编译执行的来由。编译执行相当于依靠编译器做了所有优化,消除函数调用利用了编译器的inline,中间变量可以依靠编译器的寄存器分配,没用的分支可以被消除...实际上你没有改动任何实现,只是将用户的输入提供给了编译器并要求编译器重新生成代码,编译器拿到了额外的信息,自然就可以帮你进行更多更好的优化。(二)各家数据库的优化技术1.PostgreSQLPostgreSQL主要利用编译执行的方式来进行表达式的加速(需要开关),不过在编译执行之外,也有一些比较有趣的优化ComputedgotoPG的表达式计算在传统的解析执行(switchcase)以外还提供了一种

1