Guadazi
0%

向量化执行引擎与火山模型

Posted on Edited on In

向量化执行引擎

向量化执行引擎

解决的问题

  1. 传统的一次一个tuple的pipeline模式，CPU的大部分处理时在遍历操作数，而不是在处理数据，CPU利用率低，还导致缓存性能低和频繁跳转。
  2. 寻址性能是存储的瓶颈，顺序读写性能比随机读取效率更高，但大部分查询都是随机读取，此外磁盘读写速度远远落后于CPU数据执行速度。列存储可以最大化利用磁盘读写能力

列存储的优势:

  • 压缩能力提升: 列类型统一，存放一起，易于压缩
  • 减少IO读写总量：仅仅需要读取需要的列
  • 减少查询过程中的节点函数的调用次数：计算过程中，列存以数据块的形式返回上层节点，减少函数调用次数
  • 向量化执行：计算的过程中，相同的列执行相同的操作，可以使用SIMD提升计算效率；不支持SIMD，也可以通过循环提升效率
  • 延迟物化：减少查询计划树之间传递数据总量

向量化引擎的适用条件

  • 列存储
  • OLAP

OLAP适合列存储
OLTP点查询适合行存储

实现方法

  • 火山模型: 修改成一次返回一组列
  • 层次型执行模式: 将优化好的执行计划数转换为编译执行：一次调用下来后，每一层都完成后才向上返回数据，减少各层次节点间的调用次数

在数据量比较大的情况下，内存可能放不下这些数据，需要写盘，这样会造成额外的开销。

优势

  • 向量化执行引擎可以减少节点间的调度，提高CPU的利用率。
  • 因为列存数据，同一列的数据放在一起，导致向量化执行引擎在执行的时候拥有了更多的机会能够利用的当前硬件与编译的新优化特征。
  • 因为列存数据存储将同类型的类似数据放在一起使得压缩比能够达到更高，这样可以拉近一些磁盘IO能力与计算能力的差距。

注意的问题

  • 通信库的效率: MPP架构上是share nothing架构的，所以它的集群各执行节点是有通信需要的，通信效率的高低也是决定了查询执行效率。另外就是大集群情况下，如果使用tcp方式连接，连接数会受限。
  • 数据读写争抢问题 这个问题本身不是向量化执行引擎的，而是列存带来的，因为列存储表每一列单独存储为一个文件，这样在写盘的时候有优化与没有优化的差距还是非常明显的。
  • 列存数据过滤效率问题 列存数据中的一个处理单元是由连续的N个值放在一起组成的一个Col（数组），然后再由多个Col的数组组成了一个处理单元。在进行过率的时候如何能够更加紧凑的放置数据是需要我们考虑列存在过滤掉效率和存放之间如何优化的问题。
  • 表达式计算问题（LLVM） LLVM优化可以将表达式计算由遍历树多层调用模式变为，只调用一个函数的扁平式执行方式。这样可以极大的提高表达式的执行性能。值得一提的是LLVM技术的优势也可以应用在执行计划编译执行模型的构建上面。

火山模型

例如 SQL：

1
2
3
SELECT Id, Name, Age, (Age - 30) * 50 AS Bonus
FROM People
WHERE Age > 30

对应火山模型如下：

其中——

User：客户端；

Project：垂直分割（投影），选择字段；

Select（或 Filter）：水平分割（选择)，用于过滤行，也称为谓词；

Scan：扫描数据。

这里包含了 3 个 Operator，首先 User 调用最上方的 Operator（Project）希望得到 next tuple，Project 调用子节点（Select），而 Select 又调用子节点（Scan），Scan 获得表中的 tuple 返回给 Select，Select 会检查是否满足过滤条件，如果满足则返回给 Project，如果不满足则请求 Scan 获取 next tuple。Project 会对每一个 tuple 选择需要的字段或者计算新字段并返回新的 tuple 给 User。当 Scan 发现没有数据可以获取时，则返回一个结束标记告诉上游已结束。

为了更好地理解一个 Operator 中发生了什么，下面通过伪代码来理解 Select Operator：

1
2
3
4
5
6
7
8
9
Tuple Select::next() {
    while (true) {
        Tuple candidate = child->next(); // 从子节点中获取 next tuple
        if (candidate == EndOfStream) // 是否得到结束标记
            return EndOfStream;
        if (condition->check(candidate)) // 是否满足过滤条件
            return candidate; // 返回 tuple
    }
}

火山模型的优缺点

可以看出火山模型的优点在于：简单，每个 Operator 可以单独抽象实现、不需要关心其他 Operator 的逻辑。

那么缺点呢？也够明显吧？每次都是计算一个 tuple（Tuple-at-a-time），这样会造成多次调用 next ，也就是造成大量的虚函数调用，这样会造成 CPU 的利用率不高。

知识点补习——虚函数
C++ 中用 virtual 标记的函数，而在 Java 中没有 final 修饰的普通方法（没有标记为 static、native）都是虚函数。
虚函数的重要特性是支持在子类中进行 override（重写），从而实现面向对象的重要特性之一：多态。

但是为什么之前的数据库设计者没有去优化这方面呢？是他们没想到吗？怎么可能？这个时候我们可能要考虑到 30 年前的硬件水平了，当时的 IO 速度是远远小于 CPU 的计算速度的，那么 SQL 查询引擎的优化则会被 IO 开销所遮蔽（毕竟花费很多精力只带来 1% 场景下的速度提升意义并不大）。

可是随着近些年来存储越来越快，这个时候我们再思考如何让计算更快可能就有点意思了。

虚函数造成cpu利用率不高

  • 空间开销
    首先，由于需要为每一个包含虚函数的类生成一个虚函数表，所以程序的二进制文件大小会相应的增大；其次，对于包含虚函数的类的实例来说，每个实例都包含一个虚函数表指针用于指向对应的虚函数表，所以每个实例的空间占用都增加一个指针大小（32位系统4字节，64位系统8字节）。这些空间开销可能会造成缓存的不友好，在一定程度上影响程序性能。
  • 时间开销
    虚函数的时间开销主要是增加了一次内存寻址，通过虚函数表指针找到虚函数表，虽对程序性能有一些影响，但是影响并不大。

影响到虚函数调用性能的背后原因是流水线和分支预测，由于虚函数调用需要间接跳转，所以会导致虚函数调用比普通函数调用多了分支预测的过程，产生性能差距的原因主要是分支预测失败导致的流水线冲刷性能开销。

优化方向

代码生成

向量化

按照行加载到CPU Cache，如果只访问个别列就丢弃了，CPU Cache利用率不高。
按列存储，因为输入是同列的一组数据，面对的是相同的操作，并且如果每次只取一列的部分数据，返回一个可以放到 CPU Cache 的向量，那么又可以利用到 CPU Cache。

知识点补习：向量化
向量化计算就是将一个循环处理一个数组的时候每次处理 1 个数据共处理 N 次，转化为向量化——每次同时处理 8 个数据共处理 N/8 次，其中依赖的技术就是 SIMD（Single Instruction Multiple Data，单指令流多数据流），SIMD 可以在一条 CPU 指令上处理 2、4、8 或者更多份的数据。

代码生成是否因为SQL复杂过慢

循环优化

share nothing架构

表达式计算问题（LLVM）

列式存储

SIMD

火山模型

延迟物化

谓词

Greenplum