Expression Execution in Velox Part 3: SpecialForm

放假期间沉迷于看厕纸，本来想过一遍一些 Operator，后来计划大失败。所以最后写一篇短的来灌水。

在前几篇文章里面，我们大概知道了 Expr 的结构。Expr 并不是一个很 Pure 的继承树，默认的 Expr作为基类，可以执行 Vector Function，Vector Function 里面包含了 Simple Function 等执行逻辑。在 Expr::eval 中，如果监测到自身是 SpecialForm，会把逻辑分发给 evalSpecialForm, 具体代码大概如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/// ...
  if (isSpecialForm()) {
    // If, And, Or 之类的洞都是 special case.
    evalSpecialFormWithStats(rows, context, result);
    return;
  }
 /// ...

void Expr::evalSpecialFormWithStats(
    const SelectivityVector& rows,
    EvalCtx& context,
    VectorPtr& result) {
  stats_.numProcessedVectors += 1;
  stats_.numProcessedRows += rows.countSelected();
  auto timer = cpuWallTimer();

  // Q: 为什么 evalSpecialForm 是个特殊函数呢?
  // A: 因为这套东西继承写的一把shit, 拆分出了 eval(base class, non virtual),
  //    和 evalSpecial.
  evalSpecialForm(rows, context, result);
}

我们在之前的章节介绍过两种可以作为表达式输入的 SpecialForm: Constant 和 FieldReference（ https://blog.mwish.me/2024/02/09/Expression-Execution-in-Velox-Part-2-Expr-eval/#%E8%BE%93%E5%85%A5-Constant-FieldReference ）. 这两个表达式和 SpecialForm 本身的逻辑是很好理解的。今天我们会介绍 Lambda 之外的一些 SpecialForm 表达式，来介绍一下基本这块的执行. 我们这边会介绍的大概有：

  1. ConjunctExpr: 多个表达式的 AND 或者多个表达式的 OR
  2. TryExpr: TRY(...) 会把内部的错误转成 NULL
  3. SwitchExpr: 处理 case-when 和 if-else 这样的分支逻辑
  4. CastExpr: 类型转换，Cast TypeA -> TypeB
  5. CoalesceExpr 返回第一个 NonNull 的表达式或者全是 Null 就返回 NULL

我们开始吧。

ConjunctExpr

ConjunctExpr 执行的内容是 AND(expr1, expr2, expr3 ...) 或者 OR(expr1, expr2, ...) 这样的形式。我们可以拿到一个 invariant: 每个 expr 输入都是一样的，输出则是我们简单概述一下其中的内容：

不考虑 Reorder Expr:

  • 从头到尾执行，对于 AND 而言，如果是 False 那么后续就可以熔断；同样对于 OR 而言，是 True 的话后续可以熔断
  • 那么，从头到尾，维护一个新的 RowSelector，然后，每次执行一个表达式带着 rows 去执行。每次 deselector 去 de-select 熔断了的结果。

接下来我们考虑一下 NULL。首先参考 SQL 的 NULL 语义：

然后：

img

  1. NULL AND FALSE -> FALSE
  2. NULL AND TRUE -> NULL
  3. NULL OR TRUE -> TRUT
  4. NULL AND TRUE -> NULL

可以简单当成这是个三值逻辑。那么，原先的执行流程没有变，只是多一个 AND: False > NULL > True 这样类似的逻辑。每轮执行的时候，需要拿 values - nulls 来更新 True / False / Null。具体而言，每次先更新优先级最高的，再更新 Nulls。

然后我们再考虑 Errors 和 reorder 执行，这里首先看官方文档: https://facebookincubator.github.io/velox/develop/expression-evaluation.html#error-handling-in-and-or-try

最重要的一句：

The error suppression logic in the AND and OR expressions is designed to deliver consistent results regardless of the order of the conjuncts.

我们考虑一下用户的表达式：a is not NULL and (a 为 Null 可能错的表达式)，这个 reorder 之后可能就飞了。Velox 这里是希望 Errors 能够在一定条件下被抑制。简单来说，这里可以当成一个四值逻辑：

  • And: False > Error > Null > True

对于 Reorder，这里会额外收集每个表达式的 filter ratio (收集输入和输出的时候的 selectivity）和时间。然后执行。

我们重新再整理一遍这个执行流程：

  1. 准备 SelectionVector，然后设置出现 error 不 throw
  2. 执行表达式，拿到 errors, nulls 和 values。执行的时候需要计时
  3. 更新 value -> errors -> nulls，然后更新 SelectionVector。回到 (2) 准备执行下一轮
  4. 执行完成，处理异常之类的，根据执行结果，在 rethrow 最终异常什么的。

TryExpr

Try 的逻辑相对比较简单，因为下层 error 处理的机制已经比较完备了。直接扯就行

  1. 执行模式上取消 throw on error，然后把原有的 Errors 暂存（比如说 and try(...)，这里原本有一些 Error，执行逻辑不应该影响它们）
  2. 按照 rows 执行表达式
  3. 对错误的表达式清除错误，反选成 NULL
  4. 把原有的 Errors 覆盖回来。

SwitchExpr

Switch 主要处理 if/else 和 switch 逻辑，逻辑如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/// CASE expression:
///
/// case
///  when condition then result
///  [when ...]
///  [else result]
/// end
///
/// Evaluates each boolean condition from left to right until one is true and
/// returns the matching result. If no conditions are true, the result from the
/// ELSE clause is returned if it exists, otherwise null is returned.
///
/// IF expression can be represented as a CASE expression with a single
/// condition.

在 Arrow 之类的系统中，因为不能 Out-of-order write，所以这块可能有一点麻烦。但是 Velox 的任何类型都能支持 Out-of-order write + Selector，这让这块的实现变得很轻松：

  1. 设置 finalSelection 为 false，准备一个 remaingRows 作为 Selector，准备一个 out-of-order 写的 result
  2. 对 remaingRows（除了 Else）执行表达式 case
  3. 拿到本轮的一个需要执行的 Selector （thenRows），在分支结果执行 when 表达式，结果写入 result
  4. 给 remainingRows 去 de-select thenRows，再回到 (2)

CoalesceExpr

Coalesce 的逻辑和之前见到的也差不多。这里逻辑和之前都似曾相似：

  1. 设置 finalSelection 为 false，准备 Remaining 的 SelectionVector
  2. 执行表达式，给 Remaining de-select 掉 non-null 的，再次执行，直到执行最后一个表达式

CastExpr

类型可以自己定义类型，也可以自己定义类型的 Operator，所以 Cast 会需要绑定：

  1. Hooks (Spark / Presto 引擎可能 Cast, Truncate 之类的行为不是完全对等的）
  2. Error Handling: 是否 throw Exception. 这里 SQL 可能会有两种表达式，一种是 tryCast，等价于 try(cast(.. As )，这里设置了对应的逻辑
  3. 自定义类型和自己定义类型的 Operator 的处理。Velox 除了一些基本类型可以自己定义类型和 Operator，以适应不同的计算逻辑。

这里感觉 Velox 的 Cast 相对 Arrow 的 Cast 写的比较 Hack，大概逻辑如下：

1
2
3
cast
- trying to Peel
- applyCast

这里 Cast 中间也会包装一层 Peeling 的逻辑，来避免开销。