PostgreSQL主要基于以下两点设计:

对于1，在一条query的执行中，表达式通常只会init一次，而表达式的evaluate会在query的执行过程中发生无数次，任何额外的指令重复无数次，其开销都是不可忽略的。

对于2，应该是query caching和parallel query方面的考虑，在不可变的plan上做这些事情会比较简单

相关类的定义

PostgreSQL的表达式模块主要与以下几个类有关:

  1. Expr: 表达式的逻辑表示，表达式会被表达为由Expr作为节点的一颗树
  2. ExprState: 表达式执行中的核心部分，其中有几个关键成员:
    • 表达式的指令序列，可以通过顺序执行这些执行来执行表达式
    • ExprStateEvalFunc evalfunc 表达式执行的入口，通过调用该函数进行表达式的执行
    • <resvalue, resnull> 用来存放表达式的结果。需要注意的是 ExprEvalStep 中也拥有这两个成员，用来存放中间结果

表达式的执行流程

如果粗略的分，表达式的执行可以分为两个阶段: Init(复杂) 和 Eval(简单)，代码里面的流程如下:

  1. 表达式初始化，由函数ExecInitExpr()完成

这个函数主要做了以下几点事情

  • 创建一个ExprState，解析表达式的逻辑表示，生成对应的ExprEvalStep数组(调用ExecInitExprRec())。其中除了表达式对应的ExprEvalStep之前，还会在表达式开始前额外插入一些EEOP_*_FETCHSOME的step，这些step用于将对应field的值存入表达式(例如表达式t1.a > 5中的t1.a)
  • 选择恰当的执行方式，并做一些相对应的前置准备，主要有两种执行方式：
    • 解释执行，这里由分为传统的解释执行(switch case)和computed goto两种，由宏EEO_USE_COMPUTED_GOTO控制，在编译时决定。
    • 编译执行，依靠LLVM将表达式编译为机器码执行。 2. 执行表达式，会依靠之前初始化时确定的执行方式:

  • 解析执行，通过调用函数ExecInterpExprStillValid()

    1.  Datum
    2.  ExecInterpExprStillValid(ExprState *state, ExprContext *econtext, bool *isNull)
    3.  {
    4.    CheckExprStillValid(state, econtext);
    6.    /* skip the check during further executions */
    7.    /* in general, state->evalfunc_private = ExecInterpExpr */
    8.    state->evalfunc = (ExprStateEvalFunc)state->evalfunc_private;
    10.    /* and actually execute */
    11.    return state->evalfunc(state, econtext, isNull);
    12.  }

    函数ExecInterpExpr中包含了一个巨大的switch-case块，其中的执行逻辑根据宏EEO_USE_COMPUTED_GOTO有所不同:

    • 如果EEO_USE_COMPUTED_GOTO未被定义，那么就是传统的解析执行，这时ExprEvalStep::opcode表示一个enum ExprEvalOp，switch将根据opcode跳转到合适的case执行
    • 如果EEO_USE_COMPUTED_GOTO被定义，这时ExprEvalStep::opcode是一个指向某个case块代码的地址，执行时将不会反复通过switch执行，而将进行一连串的GOTO语句执行合适的逻辑

    一个简单的执行(调用一个函数)的例子:

    1.  /* ----------- Utils ----------- */
    2.  #if defined(EEO_USE_COMPUTED_GOTO)
    3.  // ...
    4.  #define EEO_SWITCH()
    5.  #define EEO_CASE(name)    CASE_##name:
    6.  // goto op_func_addr
    7.  #define EEO_DISPATCH()    goto *((void *) op->opcode)
    9.  #else              /* !EEO_USE_COMPUTED_GOTO */
    11.  #define EEO_SWITCH()    starteval: switch ((ExprEvalOp)op->opcode)
    12.  #define EEO_CASE(name)    case name:
    13.  // return to EEO_SWITCH(), interpret opcode of next op
    14.  #define EEO_DISPATCH()    goto starteval
    16.  #endif              /* EEO_USE_COMPUTED_GOTO */
    17.  #define EEO_NEXT() \
    18.    do { \
    19.      op++; \
    20.      EEO_DISPATCH(); \
    21.    } while (0)
    23.  /* ----------- In ExecInterpExpr ----------- */
    24.  #if defined(EEO_USE_COMPUTED_GOTO)
    25.    // goto opcode of 1st ExecStep 
    26.    EEO_DISPATCH();
    27.  EEO_SWITCH()
    28.  {
    29.    // ...
    30.    EEO_CASE(EEOP_FUNCEXPR)
    31.    {
    32.      // fcinfo包含函数入参(由前置ExprEvalStep计算)
    33.      FunctionCallInfo fcinfo = op->d.func.fcinfo_data;
    34.      Datum d;
    36.      fcinfo->isnull = false;
    38.      *op->resvalue = d;
    39.      *op->resnull = fcinfo->isnull;
    40.    // EEO_NEXT() will call EEO_DISPATCH() (goto NEXT_LABEL)
    41.      EEO_NEXT();
    42.    }
    43.  }

  • 编译执行，通过调用函数ExecRunCompiledExpr()

    1.  static Datum
    2.  ExecRunCompiledExpr(ExprState *state, ExprContext *econtext, bool *isNull)
    3.  {
    4.    CompiledExprState *cstate = state->evalfunc_private;
    5.    ExprStateEvalFunc func;
    7.    CheckExprStillValid(state, econtext);
    9.    llvm_enter_fatal_on_oom();
    10.    // get function ptr of expression
    11.    func = (ExprStateEvalFunc) llvm_get_function(cstate->context, cstate->funcname);
    12.    llvm_leave_fatal_on_oom();
    13.    Assert(func);
    15.    /* remove indirection via this function for future calls */
    16.    state->evalfunc = func;
    18.    return func(state, econtext, isNull);
    19.  }

    与PG不同，TiDB的表达式看起来与MySQL比较相似，所有表达式都继承自Expression interface(对应MySQL中的Item)，Expression类拥有一系列eval接口(对应纯虚函数Item::val_)，表达式执行是后续遍历表达式树的过程，举个例子

对比下MySQL对应的实现

  1. longlong Item_func_plus::int_op() {
  2.   longlong val0 = args[0]->val_int();
  3.   longlong val1 = args[1]->val_int();
  4.   longlong res = val0 + val1;
  5.   bool res_unsigned = false;
  7.   if ((null_value = args[0]->null_value || args[1]->null_value)) return 0;
  8.   // ...
  9.   return check_integer_overflow(res, res_unsigned);
  10. }

目前的表达式实现

上文提到了TiDB这种与MySQL相似的表达式才运行时会产生大量函数调用，解决这个问题可以从两个方面考虑:

  • 减少表达式计算时的函数调用：利用JIT技术在运行时将表达式编译成一个函数，减少函数调用

  • 减少函数调用的开销：利用向量化技术，表达式每次运算会同时计算若干行的结果，均摊了函数调用的开销

Postgre提供了前者，而TiDB选择了后者，以TiDB中简单的filter为例，看看TiDB表达式的向量化实现

  1. // SelectionExec represents a filter executor.
  2. type SelectionExec struct {
  3.   baseExecutor
  5.   // batched: whether to use vectorized expressions
  6.   batched     bool
  7.   filters     []expression.Expression
  8.   // selected: result of vectorized expression
  9.   selected    []bool
  10.   inputIter   *chunk.Iterator4Chunk
  11.   inputRow    chunk.Row
  12.   childResult *chunk.Chunk
  14.   memTracker *memory.Tracker
  15. }

filter类的定义并不复杂，接下来看看表达式是怎么执行的，先确定是否能够使用向量化表达式

  1.   // ...
  2.   // Vectorizable?
  4.   if e.batched {
  5.     e.selected = make([]bool, 0, chunk.InitialCapacity)
  6.   }
  7.   e.inputIter = chunk.NewIterator4Chunk(e.childResult)
  8.   e.inputRow = e.inputIter.End()
  9.   return nil
  10. }

然后执行表达式

在函数expression.VectorizedFilter中，如果Expression拥有vecEval*接口，就会调用这些接口进行批量计算，将结果存在selected中作为filter的结果，下面是TiDB向量化加法的实现

  1. // unsigned a + b
  2. func (b *builtinArithmeticPlusIntSig) plusUU(result *chunk.Column, lhi64s, rhi64s, resulti64s []int64) error {
  3.   // vectorized here
  4.   for i := 0; i < len(lhi64s); i++ {
  5.     if result.IsNull(i) {
  6.       continue
  7.     }
  8.     lh, rh := lhi64s[i], rhi64s[i]
  9.     // do overflow check...
  10.     resulti64s[i] = lh + rh
  11.   }
  12.   return nil
  13. }

可以改进的地方

现在TiDB表达式向量化的batch size是固定的32。实际上不同的batch_size对性能会有所影响，主要取决于CPU cache的大小

将来一个可能做的改进是根据表达式与CPU cache大小计算出一个合适的batch size让表达式的中间结果全部放在CPU的L1 cache中，同时最大程度减少函数调用的开销

PolarDB IMCI作为PolarDB的列式索引用于加强其应对复杂查询的能力，作为一个侧重分析性能的组件，其表达式实现也采用了大量的优化技术

IMCI的数据以列式存储，因此向量化成为了很自然的选择，与此同时，我们也采用了PostgreSQL解析执行表达式时的优化:

  • 只读的expression + 可读写的data slot
  • 执行前消除递归，分解为若干ExprStep

另外，云上运行的软件与普通软件不同，由于云上硬件往往统一更新，因此对于云上运行的软件，我们可以利用机器硬件的特性进行优化，以一个简单的IF(x > 0, a, b)表达式为例，一个可能的向量化实现

  1. void IF_func::vec_val_int(Pred *pred, Expr val1, Expr val2, int32_t *dst) {
  2.   size_t batch_size = this->batch_size;
  3.   uint8_t *pred_val = return val1->vec_val_bool();
  4.   // we can push down the mask to val1 and val2
  5.   // but in this example, it's harmless
  6.   int32_t *val1_val = return val1->vec_val_bool();
  7.   int32_t *val2_val = return val1->vec_val_bool();
  8.   for (size_t i = 0; i < batch_size; i++) {
  9.     if (Utils::test_bit(pred_val, i)) {
  10.       dst[i] = val1_val[i];
  11.     } else {
  12.       dst[i] = val2_val[i];
  13.     }
  14.   }
  15. }
  1. void IF_func::vec_val_int(Pred *pred, Expr val1, Expr val2, int32_t *dst) {
  2.   size_t batch_size = this->batch_size;
  3.   uint16_t *pred_val = return val1->vec_val_bool();
  4.   // we can push down the mask to val1 and val2
  5.   // but in this example, it's harmless
  6.   int32_t *val1_val = return val1->vec_val_bool();
  7.   int32_t *val2_val = return val1->vec_val_bool();
  9.   constexpr step = 64 / sizeof(int32_t);
  10.   for (size_t i = 0; i < batch_size; i++) {
  11.     size_t val_idx = (i * step);
  12.     auto val1_512 = _mm512_load_epi32(val1_val + val_idx);
  13.     auto val2_512 = _mm512_load_epi32(val2_val + val_idx);
  14.     _mm512_store_epi32(dst + val_idx, val2_512)
  15.     _mm512_mask_store_epi32(dst + val_idx, pred_val[i], val1_512)
  16.   }
  17. }

借助CPU对带mask指令的原生支持，我们能够消除分支，并且减少了循环的次数，IMCI也利用SIMD指令对表达式进行了优化以最大程度利用硬件为表达式加速

对于列式存储的数据，因为同一列的数据排布在一起，相对于行式数据来说，压缩取得效果会更好一些，另一方面，由于SIMD寄存器宽度是固定的，因此每一个数据越短，一条SIMD指令能够处理的数据就越多，如果能够在压缩的数据上进行表达式计算，就可以加速我们的表达式，例如对于一个bigint列，如果其数据都在int16范围内，对于SIMD指令来说

  • ，一次处理8行数据
  • _mm512_eval_epi16(...)，一次处理32行数据

同样的指令，处理了4倍的数据。

在IMCI中，我们会根据数据压缩的情况在对表达式采取合适的优化以最大化SIMD指令的处理效率

下图展示了SIMD与Type Reduction对表达式的加速效果 性能测试

可以看出SIMD指令对于表达式的加速还是很明显的。

上文已经介绍了目前数据库系统中常见的两种优化: 向量化与JIT编译执行，如果单独拆出来看这两个技术的话，他们的优缺点如下:

  • 向量化：简单，通用，相较于最传统的逐行解析执行来说足够有效
  • JIT编译：可以对表达式做一些额外的优化（依靠编译器），但是需要考虑代价（编译时间）如果Query本身是很简单的Query(IndexScan)，那么这个代价会比较明显，在AP查询中这个代价就不太起眼

数据库的表达式，或者更进一步来说，整条SQL实际上都是一段代码，除了顶层的优化（数据库的优化器）之外，一些微观层面上的优化也许直接交给编译器是更好的选择，实际上现在也已经有将整条Query编译为二进制代码执行的数据库出现(Hyper, NoisePage)。

另一方面实际上这两种优化手段也并不对立，我们也可以编译向量化执行的代码，甚至依靠LLVM平台无关的IR，我们甚至可以实现跨平台使用SIMD指令，所以与其认为向量化和JIT是两种优化，不如说向量化是一种实现方式，JIT则基于已有的实现通过编译进行优化，不过虽然这么说，这两个技术的结合依然会带来一些问题：

  • JIT在数据库中的实现会比较麻烦，实际上相当于用另一种语言(LLVM IR)开发数据库的执行器，会比较别扭，并且调试等操作都会更麻烦。
  • 虽然两个方向是正交的，但是两个优化加在一起可能会造成1+1<2的效果，如果结合编译时间和1，就会出现”值不值“的问题

对于第一个问题，PostgreSQL提供了一个解决方案，先将源码编译为LLVM IR，运行时读取进内存供内核使用，如图所示：

实际上，这是一个在已有的实现上添加JIT功能的示范，这样可以极大程度应用已有的C语言实现，免于大量LLVM IR的手动编写。

对于第二个问题，Hyper提供了一个可能的结合方案：在列式压缩数据上的Scan采用了向量化技术，其上的算子使用tuple-at-a-time的编译执行技术。

  • 对于PostgreSQL的JIT集成方式，对于表达式来说是很合理且方便的，但如果要借鉴并应用到一个已有的系统（不仅是表达式，还有执行框架），合理的代码结构设计依然很重要。