我们如何用矢量化执行实现10倍快的表达式求值

简体中文 English

Vectorized execution

查询执行引擎对数据库系统的性能起着重要的作用。TiDB是一个开源的，兼容MySQL的混合事务/分析处理(HTAP)数据库，实现了广泛使用的Volcano model若要计算查询，请执行以下操作。不幸的是，当查询大型数据集时，火山模型导致了高解释开销和低CPU缓存命中率。

受论文启发MonetDB/X100: Hyper-Pipelining Query Execution为了提高查询性能，我们开始在TiDB中使用矢量化执行。（除了这篇文章，我们还建议您参加Andy Pavlo的课程Query Execution，其中详细介绍了执行模型和表达式求值的原理。）

2017年底，我们对TiDB SQL执行引擎进行了三项优化:

  • 实现了一个面向列的内存布局，以便在执行引擎中存储数据元组。这种方法类似于Apache Arrow使用的内存布局。参见pull request (PR) #4856。
  • 将每元组一次迭代（Volcano模型）更改为每批一次迭代（1024个元组）。参见PR #5178。
  • 基于向量化查询执行的原理优化了各种查询操作符。参见PR #5184。

得益于这些优化，与TIDB1.0相比，TIDB2.0显著提高了分析查询性能。有关我们使用的TPC-H基准测试的信息，请参见TiDB TPC-H 50G Performance Test Report。

后来我们发布了TiDB 2.1和TiDB 3.0，我们的矢量化执行引擎变得更加稳定。我们现在正在开发TiDB 4.0，它包括向量化表达式，以进一步提高TiDB的性能。

在这篇文章中，我将深入探讨为什么我们需要矢量化执行，我们是如何实现它的，我们是如何与社区贡献者一起将360多个函数矢量化的，以及我们对未来的想法。

您可能还对以下内容感兴趣:How to Use Vectorized Reader in Hive

为什么我们需要矢量化执行？

此前，TiDB实现了火山风格的执行引擎。这个迭代器模型使用标准的数据访问接口。它在代数运算符之间有open（）-next（）-close（），逐行处理数据。火山模型简单，可扩展。

但是在评估大型查询时，火山模型会导致很高的解释开销。此外，它不能充分利用现代CPU硬件特性，如CPU缓存，分支预测和指令流水线。

向量化执行使用单个指令在内存中执行类似数据项的顺序集合。与火山模型相比，矢量化模型大大减少了解释开销。因此，我们选择矢量化执行。

在本节中，我将使用TiDB表达式colA * 0.8 + colB以显示基于行的执行和向量化执行之间的开销差距。

根据算术运算符及其运算符优先级，TiDB将此表达式解析为表达式求值树。

在该树中，每个非叶节点代表一个算术运算符，叶节点代表数据源。每个非叶节点要么是一个常量（如0.8）或字段（如colA）。节点之间的父子关系表示计算依赖关系:子节点的计算结果是父节点的输入数据。

每个节点的计算逻辑可以抽象为如下评估接口:

type Node interface {
    evalReal(row Row) (val float64, isNull bool)
}


取*,0.8，和col节点作为示例，所有三个节点都实现了上面的接口。它们的伪代码如下:

func (node *multiplyRealNode) evalReal(row Row) (float64, bool) {
    v1, null1 := node.leftChild.evalReal(row)
    v2, null2 := node.rightChild.evalReal(row)
    return v1 * v2, null1 || null2
}

func (node *constantNode) evalReal(row Row) (float64, bool) {
    return node.someConstantValue, node.isNull  // 0.8 in this case
}

func (node *columnNode) evalReal(row Row) (float64, bool) {
    return row.GetReal(node.colIdx)
}


基于行的执行的解释开销

与火山模型类似，上面讨论的表达式实现是在行上迭代。

逐行迭代的解释开销是多少？我们来看看一个函数在TiDB中的实现。

这builtinArithmeticMultiplyRealSig函数将两个浮点数相乘。下面的代码块描述了这个函数的实现。右边的数字表示对应行的汇编指令数，这些指令是代码汇编后得到的。请注意，此块仅包括在正常条件下迭代的行，并忽略用于错误处理的逻辑。

func (s *builtinArithmeticMultiplyRealSig) evalReal(row chunk.Row) (float64, bool, error) {                                                                              9
  a, isNull, err := s.args[0].EvalReal(s.ctx, row)                                    27
  if isNull || err != nil {                                                           3
     return 0, isNull, err
  }
  b, isNull, err := s.args[1].EvalReal(s.ctx, row)                                    25
  if isNull || err != nil {                                                           3
     return 0, isNull, err
  }
  result := a * b                                                                     2
  if math.IsInf(result, 0) {                                                          6
     return 0, true, types.ErrOverflow.GenWithStackByArgs(...)
  }
  return result, false, nil                                                           7
}


下表列出了每个builtinArithmeticMultiplyRealSig函数任务和执行该任务的汇编指令数。（如果一个任务需要多行代码，则每行的指令数显示在括号中。）

任务 指令数
检查堆栈并调用process函数 9
获取第一个子节点的数据 30(27+3)
获取第二个子节点的数据 28(25+3)
执行乘法并检查错误 8(2+6)
处理函数返回的结果 7

如表所示，每次该函数执行乘法时，82条(9+30+28+8+7=82)指令中只有8条在执行“实”乘法。这只占全部指令的10%左右。其他90%被认为是口译开销。一旦我们对这个函数进行矢量化，它的性能提高了近九倍。参见PR #12543。

批处理减少解释开销

像SQL运算符的向量化优化一样，我们可以一次处理和返回一批数据。这减少了表达式求值过程中的解释开销。

假设一批数据中有1024行。优化后，每次调用函数，处理1024行数据，然后返回。函数调用的解释开销变成1/1024原来的那个。

因此，我们可以添加以下接口，以批处理的方式对一个表达式进行求值:

type Node interface {
  batchEvalReal(rows []Row) (vals []float64, isNull []bool)
}


我们的向量处理接口是什么样子的？为什么？

真实的源代码与上面显示的模型并不完全相同。它看起来是这样的:

type VecNode interface {
  vecEvalReal(input *Chunk, result *Column)
}


你可能想知道为什么。

为了解释原因，让我简单介绍一下tidb的Chunk结构，它是查询执行阶段内存中的数据表示形式。

2017年底，我们在做向量优化，引入了a的概念Chunk。AChunk由多列组成。

有两种类型的列:

  • 固定长度列，其中的数据具有无法更改的指定长度。
  • 可变长度列，其中的数据长度可以更改。

无论数据长度是固定的还是可变的，列中的数据都连续存储在Column.data字段（它是一个数组）。如果数据长度不同，Column.offset记录数据偏移量。如果数据具有固定长度，则不记录偏移。

下图说明了我们最近为其引入的新的矢量访问接口ChunkS:

  • 对于固定长度的数据，如int64号，Golangunsafe包直接转换Column.data到[]int64在Int64s() []int64，并返回结果。要读取或修改的用户Column.data可以直接操作数组。这是访问固定长度数据的最有效方式。
  • 对于长度可变的数据（如字符串），我们只能使用GetString(rowIdx int) string以获取相应行中的数据，并且只追加数据来更新它。随机修改可变长度数据列中的元素涉及移动所有后续数据。这会产生很大的开销。若要提高整体性能，此操作不在中实现Column。

现在您已经了解了TiDB的基础知识Chunks，让我们回到界面设计上来。

基于Chunk实现和Golang的特点，我们在这几个方面对表达式求值界面进行了优化:

  • 我们直接通过了*Chunk而不是[]Row以避免创建大量Row物体。这减轻了Golang垃圾收集(GC)的压力，提高了性能。
  • 我们访问了数据（存储在Column.data）通过Column而不是Row以减少函数调用的次数。这有助于减少解释开销并加快访问数据的速度。
  • 我们将用于存储数据的列放在参数中，并传递参数，而不是直接返回[]float64和[]bool数组。这提高了内存重用率，减少了Golang GC开销。

基于这些优化，我们的表达式矢量化求值界面就变成了今天的样子。

我们如何实现矢量化执行？

本节介绍如何实现函数的矢量化执行。

取multiplyRealNode例如:

func (node *multiplyRealNode) vecEvalReal(input *Chunk, result *Column) {
  buf := pool.AllocColumnBuffer(TypeReal, input.NumRows())
  defer pool.ReleaseColumnBuffer(buf)
  node.leftChild.vecEvalReal(input, result)
  node.rightChild.vecEvalReal(input, buf)

  f64s1 := result.Float64s()
  f64s2 := buf.Float64s()
  result.MergeNulls(buf)
  for i := range i64s1 {
     if result.IsNull(i) {
        continue
     }
     i64s1[i] *= i64s2[i]
  }
}


对于此功能:

  1. 前两行申请ColumnBuffer以缓存正确的子级（第二个参数）的数据。左子参数（第一个参数）的数据存储在指向result指针。
  2. Columns.MergeNulls(cols…)合并NULL多列的标志。这个方法就像result.nulls[i] = result.nulls[i] || buf.nulls[i]。Column在内部使用位图来维护NULL旗帜。调用此函数时，列执行按位操作以合并NULLS。
  3. 一个循环直接将左右子节点的数据相乘。
  4. 在乘法过程中，这个函数调用左和右子接口来获取它们的数据。

这种实现方法减少了批处理的解释开销，对现代CPU更有利:

  • 按顺序访问数据向量。这减少了CPU缓存未命中。
  • 大部分的计算工作都在一个简单的循环内。这便于CPU分支预测和指令流水线。

矢量化执行与基于行执行的基准测试比较

在本节中，我将使用TiDB源代码进行基准测试，并比较代码矢量化前后的性能。

我们使用相同的数据（由两列浮点数组成的1024行）分别计算col0 * 0.8 + col1有两种方式:基于行的执行和向量化的执行。结果如下:

BenchmarkVec-12           152166              7056 ns/op               0 B/op          0 allocs/op
BenchmarkRow-12            28944             38461 ns/op               0 B/op          0 allocs/op


上面的结果表明，向量化执行比基于行的执行快四倍。

下图对比了各种小于（LT）函数。横轴表示LT函数进行测试，纵轴表示完成一个操作的执行持续时间（以纳秒为单位）。

下图对比了算术函数在矢量化前后的性能:

我们测试了300多个矢量化函数后发现，这些函数中超过50%的函数性能提高了一倍以上，18.7%的函数达到了10倍的性能。

我们如何向量化360+内置功能？

在我们迈向TiDB 4.0的征途上，表达式向量化是一个庞大的工程，因为表达式涉及到500多个内置函数。由于我们在TiDB的代码中有如此多的内置函数--而且人员相当少--逐一手工制作这些内置函数几乎是不可能完成的任务。

为了更有效地开发代码，我们使用Golang向量化了尽可能多的内置函数text/template。此模板生成向量化函数的源代码。为了让更多的人参与这个项目，我们创建了Vectorized Expression Working Group在开发人员社区中。在这种方法中，社区贡献者承担了矢量化过程中的绝大多数工作。

在我们的共同努力下，我们重构了超过三分之二的内置功能，其中大部分功能获得了令人印象深刻的性能提升。有的甚至实现了一两个数量级的业绩收益。

使用模板的矢量化

当我们向量化内置函数时，我们发现很多函数都有相似之处。例如，大多数LT（<），>（>），和LE（<=）函数具有相似的逻辑，只是它们使用的运算符不同，因此，可以使用模板来生成这些函数的代码。

目前，Golang不支持泛型类型和宏定义，因此我们使用text/template包生成代码。

基于Golang模板的语法，我们将要生成的函数抽象成一个模板。例如，下面是比较函数的模板，如下所示LT和GT：

var builtinCompareVecTpl = template.Must(template.New("").Parse(`
func (b *builtin{{ .compare.CompareName }}{{ .type.TypeName }}Sig) vecEvalInt(input *chunk.Chunk, result *chunk.Column) error {
    n := input.NumRows()
    buf0, err := b.bufAllocator.get(types.ET{{ .type.ETName }}, n)
    if err != nil {
        return err
    }
    if err := b.args[0].VecEval{{ .type.TypeName }}(b.ctx, input, buf0); err != nil {
        return err
    }
    ...
    for i := 0; i < n; i++ {
{{ if eq .type.ETName "Json" }}
        val := json.CompareBinary(buf0.GetJSON(i), buf1.GetJSON(i))
{{ else if eq .type.ETName "Real" }}
        val := types.CompareFloat64(arg0[i], arg1[i])
{{ else if eq .type.ETName "String" }}
        val := types.CompareString(buf0.GetString(i), buf1.GetString(i))
        ...

        if val {{ .compare.Operator }} 0 {
            i64s[i] = 1
        } else {
            i64s[i] = 0
        }
    }
    return nil
}


对于不同类型的数据和运算符，模板生成相应的代码。有关完整代码，请参见PR #12875。

此模板位于expression/generator包裹。我们可以运行main()函数生成相应的内置函数代码（xx_vec_generated.go）在表情包中。

在社区的帮助下实现矢量化

除了使用模板向量化内置函数之外，我们还启动了我们的vectorization campaign让更多的人参与到矢量化中来。在运动开始时，我们发现当我们合并PRs时，经常会发生冲突。因此，我们编写了一个脚本，为所有内置函数生成向量化接口，并在代码中保留了这些接口:

func (b *builtinCastStringAsIntSig) vecEvalInt(input *chunk.Chunk, result *chunk.Column) error {
  return errors.Errorf("not implemented")
}

func (b *builtinCastStringAsDurationSig) vectorized() bool {
  return false
}


从那时起，我们一直要求贡献者填充或重构他们感兴趣的函数。

保留函数接口可以避免合并代码时不同的拉请求同时修改同一文档而引起的冲突。

我们还编写了一个测试框架。在贡献者将函数向量化之后，他们可以使用框架来测试内置函数的正确性和性能，只需编写几行简单的配置。

如下面的代码所示，贡献者只需要将相关参数添加到vecBuiltinArithemeticCases。

var vecBuiltinArithmeticCases = map[string][]vecExprBenchCase{
  ast.Div: {
     {retEvalType: types.ETReal, childrenTypes: []types.EvalType{types.ETReal, types.ETReal}},
  },
}

func (s *testEvaluatorSuite) TestVectorizedBuiltinArithmeticFunc(c *C) {
  testVectorizedBuiltinFunc(c, vecBuiltinArithmeticCases)
}

func BenchmarkVectorizedBuiltinArithmeticFunc(b *testing.B) {
  benchmarkVectorizedBuiltinFunc(b, vecBuiltinArithmeticCases)
}


接下来，它们可以运行我们编写的以下两个函数。然后，他们可以执行正确性和性能测试。

> GO111MODULE=on go test -check.f TestVectorizedBuiltinArithmeticFunc                                              
PASS: builtin_arithmetic_vec_test.go:30: testEvaluatorSuite.TestVectorizedBuiltinArithmeticFunc 0.002s
OK: 1 passed
PASS
ok      github.com/pingcap/tidb/expression      0.636s

> go test -v -benchmem -run=BenchmarkVectorizedBuiltinArithmeticFunc -bench=BenchmarkVectorizedBuiltinArithmeticFunc
BenchmarkVectorizedBuiltinArithmeticFunc/builtinArithmeticDivideRealSig-VecBuiltinFunc-12                 424515              2808 ns/op               0 B/op          0 allocs/op
BenchmarkVectorizedBuiltinArithmeticFunc/builtinArithmeticDivideRealSig-NonVecBuiltinFunc-12               47856             25272 ns/op               0 B/op          0 allocs/op
PASS
ok      github.com/pingcap/tidb/expression      4.116s


正确性和性能测试都直接生成随机数据，比较矢量化执行和基于行的执行的性能。

上面的两个操作帮助贡献者轻松地向量化我们的内置函数。

在社区的帮助下，我们在两个月内实现了360多个功能的矢量化。在此期间，我们的社区捐助者提交了256份公共关系报告。

这一运动还产生了9名积极撰稿人（他们在一年内至少合并了8份减贫战略文件）和2名审稿人（他们在一年内至少合并了30份减贫战略文件）。

接下来是什么

通过引入矢量化执行，我们极大地提高了表达式执行的性能。目前，默认情况下，向量化执行在我们的主分支上启用。一旦表达式的所有内置函数都支持向量化执行，这个表达式就会使用向量化执行。在将来，我们还将使用矢量化执行来改进TIDB的HTAP功能。

注意，上面所有的性能测试数据都在内存中。如果数据存储在磁盘上，读取它可能会导致高开销。在这种情况下，向量化执行的好处可能就不那么明显了。但总体而言，向量化执行明显提高了TiDB表达式求值的性能。

另外，当我们对表达式进行向量化时，我们发现向量化执行可以应用到很多其他的情况下，从而提高性能。例如:

  • 在哈希联接中，我们向量计算内部数据的哈希键（请参阅PR #12076）和外部数据（请参见PR #12669）。在某些情况下，性能分别提高了7%和18%。我们要感谢一位名为sduzh他独自完成了这些改进工作。
  • 在散列聚合中，我们对数据进行矢量编码。在当地的一次测试中，性能比之前快了20%到60%。有关详细信息，请参见PR #12729。
  • 在StreamAggregation运算符，我们将数据向量分成组。在一次局部测试中，性能提升了约60%。有关详细信息，请参见PR #12903。

我们欢迎您加入我们的vectorization campaign for built-in functions。

在以后的文章中，我们将介绍如何使用向量化思想来优化SQL执行引擎的其他部分。继续关注。

进一步阅读

Vectorized Algorithms in Java

Measuring Query Execution Time: What Is Most Accurate