关于存储:怎样避免每次都解释大量指令

简介：向量化引擎为 PolarDB- X 的表达式计算带来了显著的性能晋升。

作者：君启

介绍

PolarDB- X 是阿里巴巴自研的云原生分布式数据库，采纳了计算 - 存储拆散的架构，其中计算节点承当着大量的表达式计算工作。这些表达式计算波及到 SQL 执行的各个环节，对性能有着重要的影响。为此 PolarDB- X 引入向量化执行引擎，为表达式计算带来了几十倍的性能晋升。

传统数据库执行器的缺点

古代数据库系统的执行引擎，大多采纳一次计算一行数据（Tuple-at-a-time）的解决形式，并且须要在运行时对数据类型进行解析和判断，来适应简单的表达式构造。咱们称之为“标量（scalar）表达式”。这种形式尽管易于实现、构造清晰，然而当须要解决的数据量增大时，它具备显著的缺点：

为了适应简单的表达式构造，计算一条表达式往往须要引入大量的指令；对于行式执行来说，解决单条数据须要算子树从新进行指令解释（instruction interpretation），从而带来了大量的指令解释开销。据论文《MonetDB/X100: Hyper-Pipelining Query Execution》统计，在 MySQL 执行 TPC- H 测试集的 Query1 时，指令解释就消耗了 90% 的执行工夫。

此外，在最后的 Volcano 结构设计中，算子外部逻辑并没有防止分支预测（branch prediction）。谬误的分支预测须要 CPU 终止以后的流水线，将 ELSE 语句中的指令从新载入，咱们将这一过程称为 pipeline flush 或 pipeline break。频繁的分支预测谬误会重大影响数据库的执行性能。

向量化执行零碎

数据库向量化执行零碎最早由论文《MonetDB/X100: Hyper-Pipelining Query Execution》提出，它有以下几个要点：

1. 采纳 vector-at-a-time 的执行模式，即以向量（vector）为数据组织单位。
2. 应用向量化原语（vectorization primitives）来作为向量化算子的根本单位，从而构建整个向量化执行零碎。原语中防止产生分支预测。
3. 应用 code generation（代码生成）技术来解决动态类型带来的 code explosion（代码爆炸）问题。

向量化引擎为 PolarDB- X 的表达式计算带来了显著的性能晋升。在下图中，横轴为向量大小，纵轴为吞吐量，不同标量表达式和向量化表达式的性能测试比照后果如下：

case 表达式性能测试比照后果如下：

整体流程

PolarDB- X 中，向量化表达式的执行分为以下几个阶段：

1. 用户 SQL 经解析后，在 validator 中进行校验，推导和修改表达式的类型信息；这一阶段为向量化运算提供正确的、动态的类型信息；
2. 在优化器造成执行打算之后，须要对表达式树进行表达式绑定，实例化对应的向量化原语，同时调配好向量下标，供运行时内存调配；
3. 执行阶段，根据 Volcano 式的构造，自顶向下的触发执行向量化原语，并将向量作为运行时数据结构。

运行时构造

数据结构

在 PolarDB- X 向量化执行零碎中，采纳以下的数据结构来存放数据：

向量化表达式执行时，所有的数据都会寄存在 batch 这一数据结构中。batch 由许多向量（vector）和一个 selection 数组而组成。其中，向量 vector 包含一个存储特定类型的数值列表（values）和一个标识 null 值地位的 null 数组组成，它们在内存中都是间断存储的。null 数组中的 bit 位以 0 和 1 来辨别数值列表中的某个地位是否为空值。

咱们能够用 vector(type, index)来标识 batch 中一个向量。每个向量有其特定的下标地位(index)，来示意向量在 batch 中的程序；类型信息（type）来指定向量的类型。在进行向量化表达式求值之前，咱们须要遍历整个表达式树，依据每个表达式的操作数和返回值来调配好下标地位，最初依据下标地位对立为向量分配内存。

提早物化

selection 数组的设计体现了提早物化的思维，参考论文《Materialization Strategies in a Column-Oriented DBMS》。所谓提早物化，就是尽可能地将物化（matrialization）这一过程后推，缩小内存拜访带来的开销。在执行表达式计算时，往往会先通过 Filter 表达式过滤一部分数据，再对过滤后的数据执行求值解决；每次过滤都会影响到 batch 中所有的向量。以上图中的 batch 为例，如果咱们针对第 0 个向量设置 vector(int, 0) != 1 这一过滤条件，假如 vector(int, 0)中有 90% 的数据满足该过滤条件（选择率 selectivity = 0.9），那么咱们须要将 batch 中所有向量 90% 的数据从新物化到另一块内存中。而如果咱们只记录满足该过滤条件的地位，存入 selection 数组，咱们就能够防止这一物化过程。相应的，当前每次向量化求值过程中，都须要参考此 selection 数组。

向量化原语

向量化原语是向量化执行零碎中的执行单位，它最大水平限度了执行期间的自由度。原语不必关注上下文信息，也不必在运行时进行类型解析和函数调用，只须要关注传入的向量即可。它是类型特定（Type-Specific）的，即一类原语只能解决特定类型。

向量化原语的主体是 Tight-Loop 的代码构造。在一个循环体外部，只须要进行取值和运算即可，没有任何的分支运算和函数调用。一个简略的向量化原语构造如下所示：

map_plus_double_col_double_col(int n,
double*__restrict__ res,
double*__restrict__ vector1, double*__restrict__ vector2,
int*__restrict__ selection)
{if (selection) {for(int j=0;j<n; j++) {int i = selection[j];
            res[i] = vector1[i] + vector2[i];
        } 
  } else {for(int i=0;i<n; i++)
          res[i] = vector1[i] + vector2[i];
  }   
}

注：* 左右滑动阅览

其运算过程利用了 selection 数组，逐渐对向量进行取值、运算和存值，如下图所示：

向量化原语带来了以下长处：

1. Type-Specific 以及 Tight-Loop 的构造，大大减少了指令解释的开销；
2. 防止分支预测失败和虚函数调用对 CPU 流水线的烦扰，同时也能有利于 loop pipeline 优化【论文援用】
3. 从向量中存取数据，有利于触发 cache prefetch，缩小 cache miss 带来的开销。

咱们为各种标量化表达式提供相应的原语实现，从而实现从标量到向量化的转变。例如将加法运算 plus(Object, Object) 针对不同操作数类型生成原语，包含 plus(double，double)，plus(long, long)等。

短路求值

在向量化原语的根底上，咱们能够进一步对分支运算（也称为控制流运算 Control-Flow）进行短路求值（short-circuit calculation）优化，晋升表达式计算的性能。

例如，case 表达式由 n 个 when 表达式、n- 1 个 then 表达式、1 个 else 表达式形成。对于表达式

select case when a > 1 then a * 2
             when b > 1 then b * 2
            else a * b

其逻辑语义是：

• 对于满足 a > 1 的向量地位，计算 a * 2；
• 对于满足 a <= 1 and b > 1 的向量地位，计算 b * 2；
• 对于满足 a <= 1 and b <= 1 的向量地位，计算 a * b；
• 把所有地位的数值组合在一起造成新的向量，输入。

具备以下树形构造：

因为标量化表达式依照 volcano 构造编排，并提供了对立的 next()的接口，case 表达式必须执行完所有的子表达式 a >1，a*2，b>1，b* 2 和 a * b 之后，将全副后果汇总到一起，最初做 case 语义解决。这种执行形式不能依据 when 表达式的处理结果及时终止计算过程，而是对全副子表达式无差别执行。

引入向量化执行器当前，咱们能够设计短路求值来优化此问题，每一个子表达式须要被提供适合的 selection 数组，从而正确抉择列中适合的地位来进行向量运算。设第 i 个 when 条件表达式承受的 selection 元素汇合为 ，其输入的 selection 元素汇合为，也就是第 i 个 then 条件表达式承受的 selection 元素汇合。那么满足 ，其中 是原始的 selection 数组中的下标汇合。咱们把求取 selection 元素汇合的步骤称为 substract selection，case 运算的整个过程如下图所示：

总结

PolarDB- X 向量化引擎利用原语（primitive）来构建表达式，以向量作为运行时数据结构。每种原语仅为特定类型进行服务，从而缩小了指令总数；原语中的 tight-loop 构造不仅对 CPU 流水线非常敌对，也容许 CPU 进行数据预取，并且防止分支预测。此外，一些优化如提早物化、短路求值，进一步晋升了表达式求值性能。

然而，从用户 SQL 到向量化执行之间，存在着一道微小的鸿沟。咱们须要解决以下几个重要问题：

1. 如何确定表达式的输入输出类型，并为 SQL 中的表达式调配适合的原语？2. 每个原语须要应用不同的向量来进行输出和输入，如何为正确地为原语调配向量？3. 每种原语仅为特定类型进行服务，那么咱们必然须要为一个表达式装备大量不同的原语，来适应不同的数据类型。如何应答原语数量爆炸这一问题？

在下一篇文章中，咱们将为上述问题的解决方案进行具体介绍。

【相干浏览】

PolarDB-X 面向 HTAP 的混合执行器

PolarDB-X 面向 HTAP 的 CBO 优化器

如宝马 3 系和 5 系：PolarDB-X 与 DRDS 并驾齐驱

PolarDB-X 存储架构之“基于 Paxos 的最佳生产实践”

PolarDB-X 公有协定：晋升集群的性能和稳定性

技术解读 | PolarDB-X 分布式事务的实现

技术解读 | PolarDB-X 强统一分布式事务

PolarDB-X 一致性共识协定 (X-Paxos)

版权申明：本文内容由阿里云实名注册用户自发奉献，版权归原作者所有，阿里云开发者社区不领有其著作权，亦不承当相应法律责任。具体规定请查看《阿里云开发者社区用户服务协定》和《阿里云开发者社区知识产权爱护指引》。如果您发现本社区中有涉嫌剽窃的内容，填写侵权投诉表单进行举报，一经查实，本社区将立即删除涉嫌侵权内容。