在“国产数据库硬核技术沙龙 -TDSQL- A 技术揭秘”系列分享中，5 位腾讯云技术大咖别离从整体技术架构、列式存储及相干执行优化、集群数据交互总线、Fragment 执行框架 / 查问分片策略 / 子查问框架以及向量化执行引擎等多方面对 TDSQL- A 进行了深刻解读。没有观看直播的小伙伴，可要认真做笔记啦！明天带来本系列分享中最初一篇腾讯云数据库高级工程师胡翔老师主题为 “TDSQL- A 向量化执行引擎技术揭秘” 的分享的文字版。

作为当先的剖析型数据库，TDSQL- A 是腾讯首款分布式剖析型数据库，采纳全并行无共享架构，具备自研列式存储引擎，反对行列混合存储，适应于海量 OLAP 关联剖析查问场景。它可能反对 2000 台物理服务器以上的集群规模，存储容量能达到单数据库实例百 P 级。

一、TDSQL- A 向量化执行引擎

1.1 背景

要优化数据库的查问执行效率，就要充沛地利用 CPU、缓存等资源。但在事实中，硬件倒退带来的能力晋升并没有在理论利用中失去体现。右图统计了不同的数据库操作的 CPU 利用率，能够看到像 seq scan、index scan 这些根本的数据库操作，实际上并没有无效地利用好 CPU，利用率还是很低。根本原因在于没有依照最高效应用 CPU 的形式来设计和实现理论的利用零碎。所以咱们必须理解当代 CPU 的次要特色。

以后 CPU 次要具备以下 五个特色：

●流水线。能够容许一个指令周期内执行多个命令，具备多个外围的 CPU 还反对超标量流水线，容许并发执行多个流水线，进一步提高 CPU 的计算能力。

●乱序执行。能够容许不具备依赖关系的指令并发执行，防止因为期待某个指令而阻塞运行。

●分支预测。CPU 会对分支进行预测并依据预测选取下一步执行的门路，提前加载指令和数据，但如果分支预测失败，也会导致流水线中断。

●分层存储。CPU 四周设置了寄存器、L1/L2/L3 缓存、内存和磁盘等多级存储，数据越凑近 CPU，计算速度越快，反之，如果频繁地从内存或者磁盘读取数据，会导致 CPU 把较多的工夫节约到 IO 上，计算效率减低。

●SIMD 等新硬件能力。SIMD 即单指令多数据流，一次操作实现多组操作数的计算，能够进一步提高计算效率。像 SIMD 等新硬件提供了更强的执行能力。

咱们针对 CPU 的这些特色，提出了几个数据库查问性能的优化方向：

首先，能够通过向量化批量计算进步 CPU 流水线和乱序执行的执行效率；其次，编写 CPU 计算敌对的程序，比方通过缩小高低依赖、缩小分支、预取数据到缓存等形式，让 CPU 集中于计算工作；最初，还能够通过 SIMD 来对计算密集型的简略程序进行革新，减速计算效率。

1.2 向量化计算

顾名思义，向量化计算就是依照向量的形式计算，也就是一次计算多对操作数。

依照实现形式的不同，向量化次要分为以下 三种类型：

●主动向量化。编译器能够辨认出循环内哪些操作能够写成向量化执行的形式，但要求必须是简略的循环，不能蕴含条件、跳转等语句，不能蕴含前后依赖关系，硬件也必须要反对 SIMD 指令。

●增加编译器提醒。通过应用一些关键字或者预编译指令，强制进行向量化。

●显式向量化。通过 CPU 提供的 SIMD 指令集来手工编写向量化执行的代码。

三种形式中，第一种是最为简略也是利用最宽泛的形式，只须要遵循肯定的代码编写规定即可，不会影响原来代码的逻辑性和可读性，性能减速成果也不错。而另外两种形式对编程人员的要求很高，须要联合编译器和硬件能力来做深度优化。

1.3 列存储

这里再次介绍一下列存储，因为列存储跟向量化密切相关，向量化计算就是基于列存储来构建。

咱们先来理解下数据库存储。数据库存储次要分为两类：行存储和列存储。

行存储中，每一行的元组的每一列实际上是间断存储的，这样的长处是易于增加或者批改一个元组，但在读取数据时可能会额定读到不须要的列，比拟适宜于蕴含大量高并发增删改查事务的 OLTP 场景。

列存储中，每一列是独自存储的，这样就能够只读取须要的列，但毛病是元组的写入须要操作多个文件，比拟适宜于蕴含大数据量读取和简单计算的 OLAP 场景。

采纳列存储的益处有很多。除了下面提到的数据裁剪能力之外，列存储还能够通过压缩算法带来更高的压缩比，也能够通过字典里列排序或者稠密索引减速数据的查找效率。另外，这种列式的存储组织模式还为下层计算的性能优化提供了很大的便当，特地是在向量化查问和提早物化等方面。

1.4 向量化查问执行引擎

这部分次要介绍的是，如何联合后面提到的向量化和列存储技术，来对查问执行引擎进行向量化减速计算。

传统查问执行引擎采纳火山模型，依照一次解决一个元组的形式，逻辑非常简单，便于开发实现，然而效率比拟低，次要起因有以下三点：

首先，CPU 把大部分工夫都花在遍历查问操作树上，而不是在真正解决数据。一次解决一个 Tuple 的处理速度可能十分快，然而解决完之后就须要调用上层算子获取下一个 tuple，这就导致函数调用的次数比拟多，这样就进而会节约掉 CPU 的很多工夫。其次，数据和指令的缓存命中率低。频繁的函数调用导致寄存器须要保留更多的信息，而且实现时可能会为了通用性的思考，对接口进行封装，这就会导致复杂度的晋升，执行越简单就会导致缓存利用率越低。最初，这种传统的形式无奈利用新硬件提供的 SIMD 能力进行进一步优化。

与之相比，向量化查问执行引擎依然采纳火山模型，然而依照一次解决一组元组的形式，实现批量读取和批量解决，大大减少了函数调用开销，CPU 能够把更多的工夫集中到理论的计算上，效率会更高。

依照向量化计算的形式，对一组数据做简略的循环计算，同时数据依照列组织模式示意成列向量，每个列向量对应的一整块间断数据，进而能够批量读入缓存以及进行批量解决，这就能够大大提高指令、数据的缓存命中率，进而进步 CPU 的执行效率。

以上图中的例子为例。这是一个带 where 子句的聚合运算语句，右边是行存储非向量化查问执行过程，左边是列存储向量化查问执行过程。基于列存储，咱们只须要获取 id 和 agg 列的数据。基于向量化查问执行引擎，每层算子获取的都是示意成列向量的一组元组，并对每个列向量进行批量计算。

1.5 向量化执行实例

上面通过一个聚合计算的例子来进一步介绍向量化执行的具体步骤。

这个例子应用两个列进行分组，并对每个组内进行 count(*)计算。整个流程蕴含两个步骤：一是构建 hash table 并在每个 hash entry 上计算聚合后果；二是遍历 hash table，计算最终的聚合后果。

向量化革新之后，一些具体步骤能够通过简略的循环来进行批量解决。

首先，依据输出的向量在分组列上批量计算 Hash 值；其次，依据上一步计算的 Hash 值批量获取 Hash bucket 值；而后，批量解决输出向量内的每个元组，在 Hash table 内查找匹配的 Hash entry 或者创立新的 Hash entry，如果产生哈希抵触，依照 Open addressing 的解决形式，持续对下一个地位进行匹配解决；接着依据上一步获取的对应每个输出向量的 Hash entry，批量计算 Agg 后果并更新到对应的 Hash entry 上（count++）；最初，扫描 Hash table 的每一个 Hash entry，计算最终的 Agg 后果（count 计算不须要此步骤），将后果组织成向量模式返回给下层算子。

1.6 向量化执行成果

接下来看一下向量化执行的成果。上面给出了一些测试用例，次要蕴含多种不同类型的 Agg 和 Join 场景，涵盖了定长和变长列。

蓝色是行存，橙色是原列存，灰色是列存向量化。测试了 1G/10G/100G 的后果，能够看出列存向量化的执行工夫最短。数据量越大，原列存和列存向量化成果越显著。最好的状况下，列存向量化运行工夫是原列存的 1 /2，列存向量化运行工夫是行存的 1 /8。

1.7 下一步打算

最初介绍对于向量化的下一步打算，次要有以下 四方面：

●Just-in-Time 编译优化。对函数调用进行开展，缩小函数调用，比拟适宜于简单的表达式或者算子计算。

●SIMD 指令减速。适宜于简略的线性计算，能够利用古代 CPU 的 SSE、AVX 指令让一条指令实现 512bit 数据计算。

●Hash Agg/Hash Join 等算法进一步向量化优化。

●列存扫描等存储相干局部进一步优化。