本期技能贴主要介绍查询履行引擎的优化。查询履行引擎负责将SQL优化器生成的履行方案进行解说，经过使命调度履行从存储引擎里边把数据读取出来，核算出成果集，然后返回给客户。

在联系型数据库开展的早期，受制于核算机IO才能的约束，核算在查询全体的耗时占比并不明显，这个时候重视要点主要放在关于查询的优化。优化器的好坏，关于履行方案的好坏有着重要的意义，查询履行引擎的作用在数据库优化中对应等级是相对弱化的。但随着核算机硬件的开展，查询履行引擎也逐渐展现出他们的重要地位。

本篇博客结合 KaiwuDB 的部分源码和实例，介绍其如何充分发挥底层硬件的才能，优化查询履行引擎，然后提高数据库系统的功能。查询履行引擎是否高效与其采用的模型有直接联系，1990年，论文 “ Volcano, an Extensible and Parallel Query Evaluation System” 提出了火山模型，这也是 KaiwuDB 查询履行引擎的根底。

一、火山模型/迭代模型

火山模型作为经典的查询履行模型被诸如 Oracle、MySQL 等主流联系数据库采用。该模型将联系代数中每一种算子笼统为一个Operator（迭代器），每个 Operator 都提供一个接口 Next()，调用该接口会返回该算子产生/处理的一行数据（Tuple）。经过在查询树根节点自顶向下地调用 Next()，数据自底向上地被拉取处理，因而火山模型也称为拉取履行模型（Pull Based）。

火山模型

调用 Next() 办法从其子运算符恳求下一行，并检查它是否经过了挑选条件。如果是，则该行将返回到其父运算符；不然，将丢弃该行并重复该进程。

// RunFilter runs a filter  expression and returns whether the filter passes.
func RunFilter(filter tree.TypedExpr, evalCtx *tree.EvalContext)(bool, error){
    if filter == nil{
        return true, nil
    }
    d, err := filter.Eval(evalCtx)    
    if err != nil{
        return false,err    
    }
    return d == tree.DBoolTrue, nil
}

上述即 KaiwuDB 在处理行时进行过滤的函数，参数 Filter 类型为 tree.TypedExpr，意为一个通用表达式。也就是说，关于每一行，都会调用一个完全通用的标量表达式的过滤器。表达式可所以任何东西：乘法、除法、相等检查或内置函数，它甚至可所以由上述表达式组成的树。由于这种通用性，核算机在过滤每一行时都有许多工作要做，它必须在做任何工作之前检查表达式是什么，这与解说型言语的逻辑相同（与编译型言语相比）。

尽管火山模型简略、直观、易用，只需将 Operator 自由地组装，且每个 Operator 只关怀自己的处理逻辑，履行引擎并不感知。但是，在履行进程中，迭代一次只处理一行数据，数据局部性差，很简略使 CPU cache 失效，并且调用 Next() 函数（虚函数）次数太多，开支较大，使得 CPU 履行效率不高。

二、算子交融

将经常出现的 Operator（如 Project 和 Filter）交融在其他 Operator 中能够必定程度上削减虚函数的调用，提高单个 Operator 的处理才能和数据局部性。以 KaiwuDB 的 tablereader 算子为例，在扫表时便能够对数据行进行过滤和投影，其 Next() 函数中完成了相关逻辑。

下图是 tablereader 算子 Next() 函数调用的简化时序图，能够看到，在读取一条数据进行处理时会判别 Filter 和 outputCols 决议是否进行 Filter 和 Projection 操作。

查询的方案示例

三、向量化模型

不同于火山模型按行迭代的方法，如下图所示，向量化模型采用批量迭代，在算子间一次传递一批数据。经过更改数据方向（从行到列），把从列到元组的转化推迟到较晚的时候履行，来更有效地利用现代 CPU。接连的数据有利于 CPU cache 的命中，削减 memory stall 现象；除此之外，经过 SIMD 指令一次处理多个数据，能够充分利用 CPU 的核算才能。

火山模型和向量化模型迭代数据的差异

向量化模型全体架构与火山模型相似，仍然采用了拉取式模型。考虑一个具有 Id，Name 和 Age 三列的表 People, batch 将由 Id 的整型数组、Name 的字符串数组以及 Age 的整型数组组成，面对查询 SELECT Name, (Age – 30) * 50 AS Bonus FROM People WHERE Age > 30; 其向量化模型大致下图所示。

向量化模型

明显向量化模型与列式存储搭配运用能够获得更好的作用，但非列式存储也能够采用折中的方法来完成向量化模型。KaiwuDB 运用的是行存储引擎，在其向量化履行模型中，在底层 Operator 中完成了多行到向量块的转化，上层的 Operator 则以向量块作为输入进行处理，最终再由顶层的 Operator 进行向量块到行数据的转化。

除此之外，为了防止上文说到的火山模型下由于 Filter 所运用标量表达式的通用性带来的额定核算开支，在 KaiwuDB 的向量化履行模型中，每个向量化 Operator 在履行期间不允许任何自由度或运行时挑选。
这意味着，关于数据类型、特点和工作使命的任意组合，都有一个专门的 Operator 负责工作。履行引擎从 Operator 链恳求 batch：每个 Operator 从其子级 Operator 恳求一个 batch，履行其特定工作使命，然后将 batch 返回到其父级 Operator。

因而关于示例查询 SELECT Name, (Age – 30) * 50 AS Bonus FROM People WHERE Age > 30;实践向量化模型比上述的内容更杂乱，详细如下图所示。

详细向量化模型

SelectIntGreaterThanInt Operator 在获取 People 表的 batch 后将挑选所有 Age 大于 30 的值；然后，这个新的 sel_age batch 将传递给 ProjectSubIntInt Operator，该 Operator 履行简略的减法以生成 tmp batch；最终，这个 tmp batch 被传递给 ProjectMultIntInt Operator，该 Operator 核算最终的 Bonus=（Age – 30）* 50。

为了详细完成这些向量化 Operator，KaiwuDB 将流程分解为单个列上的严密 for 循环。以下的代码段（有删减）完成了 SelectIntGreaterThanInt Operator 的部分功用。该函数从其子项 Operator 中检索 batch，并循环访问列的每个元素，同时将大于 30（p.constArg）的值选中标记。然后，将 batch 及其选中向量返回给父级 Operator 进行进一步处理。这段代码尽管简略但却非常有效，for 循环迭代了一个 int64 的切片，将每个切片元素与另一个 int64 常量进行比较，并将成果存储在另一个 int32 切片中，然后完成了一个快速的循环。

func (p *selGTInt64Int64Const0p) Next(ctx context,Context) coldata,Batch {
    // In order to inline the templated code of overloads, we need to have a
   // 'decimalScratch' local variable of type 'decimalOverloadScratch'.
   decimalScratch := p.decimalScratch
   // However, the scratch is not used in all of the selection operators, so
   // we add this to go around "unused" error.
   _ = decimalScratch
   for{
       batch := p.input.Next(ctx)        
       if batch.Length() == 0 {         
          return batch
   }    
   vec := batch.ColVec(p.colIdx)    
   col := vec.Int64()    
   var idx int   
   n := batch.Length() 
   if sel := batch,Selection(); sel != nil {      
   sel = sel[:n]      
   for _, i := range sel {        
       var cmp bool        
       arg := col[i]        
       {          
         var cmpResult int          
         {            
           a, b := int64(arg), int64(p.constArg)            
           if a < b {              
              cmpResult = -1            
           } else if a > b {              
              cmpResult = 1             
           } else {              
              cmpResult = 0            
           }          
         }          
         cmp = cmpResult > 0       
       }        
       isNull := false        
       if cmp && !isNull{          
         sel[idx] = i          
         idx          
       }      
     }   
    }    
    if idx > 0 {      
      batch.SetLength(idx)      
      return batch    
    }  
 }

KaiwuDB 运用 kv 存储引擎 rocksdb 作为底层存储。经过从存储读取行后将行转换为列式数据的 batch，然后将这些 batch 送到向量化履行引擎中处理，关于处理大量数据时有可观的功能提高，但在数据量小时向量化是没有优势的，由于向量化的进程会带来额定的开支。

因而，面向行的履行模型能够为联机事务处理（OLTP）查询提供杰出的功能，而向量化履行模式往往更适用于涉及海量数据的联机分析处理（OLAP）查询。KaiwuDB 在履行方案时会依据估量的 tablereader 输出的最大行数，与 SessionData 中的 VectorizeRowCountThreshold 字段比较来判别是否需求向量化履行。

KaiwuDB 默认开启向量化履行引擎，用户也能够挑选关闭。关闭和开启向量化履行引擎能够经过 SET 进行设置，如下图所示。除此之外，运用 EXPLAIN(VEC)语句可用于查看查询的向量化履行方案。

经过 SET 设置关闭向量化履行引擎