本文作者：吕政、长别、知数等
目的
随着数字经济时代的到来，越来越多的应用依赖数据分析来挖掘数据的价值。作为大数据存储、在线分析的重要基础系统，分析型数据库（OLAP）为数据价值的在线化提供重要的技术平台。
阿里巴巴OLAP团队经过调研发现，现有的OLAP数据库执行引擎往往是在已有的OLTP执行引擎的基础之上，进行二次开发而来，存在性能损耗大、历史包袱重、未充分利用最新优化技术、未充分发挥新硬件优势等问题。
随着数据量的快速增长和数据分析需求的日趋强劲，OLAP系统所需要承担的计算量也呈指数级增长，现有系统的性能难以满足未来的在线数据分析的需求。经过分析，阿里巴巴OLAP团队认为，真正面向全面上云时代、面向数字经济时代的OLAP执行引擎，应当具备如下技术特点：
• 支持多种硬件平台。满足企业上云需求，支持多种硬件平台。除了支持传统X86平台，也应当兼容ARM平台，同时支持利用GPU、FPGA等新兴硬件进行加速。
• 极致性价比。充分利用硬件性能，精选最佳算法和算子实现，提升硬件执行效率。对于密集、复杂的计算，使用特殊算法特殊硬件来提升效率。
• SQL 兼容性高。高度兼容现有的SQL标准、优化器标准、存储标准，减少用户的迁移难度和学习难度。用户无需改写SQL，无需重新学习优化技术，无需迁移数据，仅需要进行小版本软件升级，即可享受到最新的性能优化技术。
为了解决如上需求，阿里巴巴OLAP AnalyticDB Postgres(简称ADB PG版)研发团队历时1年多，研发了新型的计算引擎Odyssey。Odyssey计算引擎具备如下主要技术特点:
• 支持多种软硬件平台。除传统X86平台外，也支持ARM芯片服务器；支持采用GPU、FPGA加速部分核心算法。
• 性能强劲。抛弃传统数据库执行引擎的实现方式，充分利用硬件执行效率。通过算法设计，消除了火山模型、碎片化内存分配、冗余逻辑等带来的性能问题，将宝贵的CPU资源用于核心计算；采用LLVM进行动态代码生成（CodeGen），提升表达式计算性能、精简计算逻辑，实现逻辑计算完美“瘦身”；采用“超算”优化技术、对算子性能进行建模，全面分析代码热点，严格考察每一行代码的实现性能；充分利用新硬件特性，利用CPU的SIMD技术、GPU的超高带宽技术、FPGA的深度流水线，进一步提升性能。
• 兼容性强。Odyssey计算引擎内生于ADB PG版，与PostgreSQL的SQL标准、优化器、存储层多个层面实现完美兼容，用户无需任何操作，即可从原生引擎迁移到Odyssey计算引擎。
本文的如下部分，我们将从架构设计、核心技术点、性能评测三个维度，介绍新型计算引擎Odyssey的特点。
Odyssey计算引擎介绍
基本框架
下图是ADB PG版的系统框架，以及Odyssey计算引擎与ADB PG版的关系。
ADB PG是一个MPP架构、高可用、可伸缩的分布式分析型数据库系统。一个ADB PG集群由Master节点和Segment节点组成，通过网络进行互联。Master节点负责接收用户请求、对SQL进行解析/优化、下发计算任务。Segment节点负责存储数据、执行计算任务，Segment节点之间可能会有多次数据交换(shuffle)操作。网络互联速度、存储性能、Segment节点的执行性能，均对ADB PG的性能有重要影响。本次发布的Odyssey计算引擎，主要提升了Segment的执行性能。
Odyssey计算引擎的研发目标，是为ADB PG新增一个更高效的计算引擎，而保持原有各模块不变。ADB PG的Master节点在接收到用户的SQL请求之后，对SQL进行解析、优化，生成执行计划然后下发到Segment，Odyssey计算引擎对这一环节没有影响，因此用户无需修改SQL、无需重新优化SQL。
Segment接受到Master节点下发的执行计划后，若Odyssey打开，将不再调用原生执行引擎，而是调用Odyssey计算引擎。在存储层面，Odyssey计算引擎与ADB PG原生的Heap表、AOCS表、AORO表均完全兼容，复用原生存储结构和存储访问接口，Odyssey专注于执行层。理论上说，Odyssey原生引擎与ADB PG的优化器优化、存储优化等不同层次的优化是正交的，可以无缝衔接。
Odyssey计算引擎执行流程如上图所示。Odyssey通过hook接入ADB PG，成为对用户透明的新引擎。ADB PG在SQL执行开始时，通过选择不同的Hook函数，来选择不同的执行引擎。对于用户来说，既可以选择原生执行引擎，也可以通过设置GUC参数选择Odyssey执行引擎。下一个版本将通过代价模型和规则来自动的选择计算引擎，更能发挥各自的优势。
为了保证系统的稳定性和功能的完整性，Odyssey计算引擎支持执行引擎的回退，当功能不支持或者执行失败，可以自动回退到原生的执行引擎。由于执行引擎本身是无状态的，用户可以根据需求，以任意粒度（库级别、session级别、SQL级别）进行执行引擎切换。
设计思想
基于上述架构，Odyssey计算引擎充分利用ADB PG自身的优势，复用其存储、优化器和事务控制，Odyssey专注于计算性能的提升，与原生ADB PG强大、丰富的功能形成互补。为了提升计算性能，通过对原生执行引擎进行分析、横向对比多种执行引擎，我们设计了新的计算引擎。Odyssey计算引擎重新设计了plan node、codegen和executor，三者之间一一对应，如下图所示，每个plan的node对应一个codegen单元和一个Executor，codegen单元根据plan node生成code(IR)，Executor根据硬件平台选择不同的后端，将IR生成对应的执行文件，并申请资源执行，最终的结果通过master返回给客户端。
执行模型优化。Odyssey计算引擎放弃了传统的火山模型，改用批量化(batch)的火山模型，批量化执行减少函数调用的开销，也方便使用向量化计算提升数据处理效率，同时也使得开发更为灵活、优化空间更大。
即时编译技术。Odyssey计算引擎采用了Just-in-Time(JIT)技术，采用LLVM动态生成代码。在一些核心操作上采用JIT技术，解决了高级语言抽象程度过高带来的性能开销，可以对表达式计算、复杂逻辑操作进行汇编级优化，最大化压缩指令的规模。
内存管理优化。ADB GP原生执行引擎存在碎片化内存分配、碎片化内存拷贝等性能问题。Odyssey计算引擎在算法层进行了重新设计，采用模块化内存分配、最大化重复利用已分配内存，大大减少了内存分配的次数。
超算软件优化。Odyssey计算引擎的开发，大量采用了“超级计算机”软件开发中的优化技术。在超算软件优化中，建立理论性能模型、进行详细性能剖析（Profiling）、严格审核代码性能，能够有效帮助软件性能的提升。Odyssey计算引擎全面采用了相关技术，做到每个算子、每段代码，都进行了深度优化。
多平台兼容。除传统X86平台，Odyssey计算引擎兼容其他X86平台和ARM平台，同时支持不同版本的Linux操作系统，为用户提供了更多的选择和优化空间。
硬件加速优化。Odyssey计算引擎能够利用GPU的超大吞吐能力和FPGA的高密度计算能力。对于部分计算量大、吞吐要求高的算子，采用GPU进行加速；对于部分计算逻辑相对固定、逻辑复杂的算子，采用FPGA进行加速。
核心技术点
执行模型优化
上图展示了TPCH-Q3的执行计划。在ADB PG中，一条SQL会被转化成一个树形执行计划。数据库传统的传统火山模型，是父节点驱动子节点执行，子节点按行返回数据给父节点，然后父节点再继续执行。火山模型有三个核心性能问题：
(1) 函数调用过多，每行数据的传递需要至少一次函数调用，CPU开销大；
(2) 优化困难，一些逻辑运算横跨多个函数，无法进行优化；
(3) CPU利用率低，CPU完成某个算子的一个操作后，马上返回到上层节点去做另一个操作，逻辑跳转多，不利于提升CPU执行效率。
Odyssey计算引擎对火山模型进行了完全重写，在复用原有的树形架构基础上，采用批量化(batch)执行提升执行性能。
火山模型中，节点之间传递数据的单位为一行，每个节点生成一行数据之后会被上层节点层层拉取，然后进行下一阶段的计算。 而Odyssey计算引擎以batch为单位进行数据传递。一个Batch包含多行数据（通常是数千行数据），采用列优先格式进行数据存储。一个节点在生成多行数据、填满一个batch之后，才会将数据返回给上层节点，消除了火山模型的性能问题。一方面，该方案将火山模型的函数调用的次数降低了三个数量级，消除了过多函数调用带来的性能影响；另一方面，减少了跨函数的操作，有利于在算法层进行优化、为各个算子选取最佳算法；最后，减少了逻辑跳转操作，能够有效利用现代CPU的执行资源。
内存管理
Odyssey计算引擎继续沿用了ADB PG的内存管理模块。ADBPG原生的内存管理模块除了性能上有所提升，而且能够自动追踪内存的分配，从而实现自动的内存释放，提升性能的同时避免了内存泄露的问题。该模块已经经过大规模云上实践的检验，因此在工程上。Odyssey计算引擎沿用了这一模块，但是在内存的使用上进行了优化，减少了不必要的内存分配和碎片化的内存分配。
一方面，Odyssey会尽力复用已分配的内存，避免不必要的多次内存分配。在火山模型中，部分节点生成一行数据后会为这行数据分配新的内存空间，因此每行数据都可能需要一次内存分配。Odyssey抛弃了火山模型、使用batch进行数据中转。每个batch的数据被上层节点消费完一行，Odyssey会复用此batch的内存空间，无须重新进行分配。
// 原生引擎：碎片化分配，按行分配内存
for (...) {
void* hash_entry = palloc(32);
... // copy data
}
// Odyssey引擎：整块内存分配。
void* hash_table = palloc(32*1000,000);
for () {
... // copy data
}另一方面，在一些大快内存分配时，Odyssey选取了效率更高的分配方式(如上述伪代码所示)。例如在Hash Join建哈希表时，一次插入一行数据，ADB PG的原生执行引擎，会在每行数据的插入之前为这一行分配内存。因此，每一行数据都需要重新进行一次内存分配，这种方案会带来大量的碎片化内存分配。例如Hash表有1M行，每行32字节，会导致1M个32字节的碎片化内存分配。对于现代化的系统来说，碎片化的内存分配对于性能的影响是非常大的，不仅分配过程非常耗时，后续的管理、追踪、释放过程也会非常耗时。
Odyssey对ADB PG原生执行引擎的碎片化内存分配问题进行了诊断和原因分析，排查出几个导致碎片化内存分配的关键算法问题。通过算法设计，Odyssey避免了碎片化内存分配问题，从而在不降低内存使用效率的同时，提高了内存管理的性能。
Codegen
Odyssey计算引擎采用基于LLVM的Codegen(代码生成)技术，减少了虚函数的调用，提升了复杂逻辑表达式和逻辑判断的性能。有别于PostgreSQL 11中表达式的codegen，Odyssey计算引擎是对整个算子进行codegen。目前Codegen主要用于三个层面的优化，算子优化、逻辑表达式优化和Code Specialization(代码专业化)。
算子优化。采用codegen，可以将整个算子生成一个函数，减少虚函数调用和冗余代码，也可以将多个算子生成一个函数，不光有上述优势，还能减少内存的使用和内存的拷贝。例如join + group by的场景，可以融合成一个函数，将join和AGG在一个函数里实现。特别是如果hash key和group key相同时，只需要建一个hash表。
逻辑表达式优化。如下代码实例解释了是如何实现这一优化的。对于a > 10 and b < 5这样一个过滤条件, ADBPG是通过三个函数调用来实现的，第一个函数调用Int32GT(a, 10)实现 a > 10, 第二个函数调用Int32LT(b, 5)实现b < 5, 第三个函数实现And操作。该方案需要三次函数调用，对性能有明显的影响。而Odyssey计算引擎采用的方案，使用LLVM生成LLVM IR，在编译成底层的机器码，只需要三条指令即可完成这一操作。通过该方案，Odyssey计算引擎避免了大量的冗余操作，能够针对不同的表达式、不同的逻辑判断，生成最小化的底层代码。
// 实例SQL
select count(*) from table where a > 10 and b < 5;
// ADBPG表达式方案：多次函数调用
result = Int8AndOp(Int32GT(a, 10), Int32LT(b, 5));
// Odyssey方案：生成最小化底层代码
%res1 = icmp ugt i32 %a, 10;
%res2 = icmp ult i32 %b, 5;
%res = and i8 %res1, %res2;Code Specialization。 对于一些在执行全已知的逻辑判断，可以通过LLVM进行code specialization, 从而消除逻辑判断。例如，某些数据结构的类型SQL解析完成后、在执行引擎开始执行前是确定的，比如每个节点的输出数据类型、数据长度。如果是使用高级语言（比如C语言）进行执行，由于写代码是开发者并不知道数据的类型，需要对每个元素的类型、长度进行判断。但是LLVM是在代码生成时就确定了数据的类型，因此生成的最终代码无需进行判断、直接进行操作即可。由于执行引擎经常需要进行数据类型、长度判断，尽管每次节省的时间非常少，但是累计下来性能的提升非常明显。
向量化执行
将按行拉取数据的火山模型改为按batch拉取数据的火山模型后，结合按列存放的优势，可以更进一步挖掘处理器的性能。例如，批量化处理的模型可以利用CPU的向量指令，或者GPU的众核优势，进一步提升性能。
// 伪代码样例：利用SIMD指令加速聚合
for (int i = 0; i < round_row; i += 8) {
__m256 m_tmp = _mm256_load_ps(&(aligned_input_data[i]));
__m256 ymm2 = _mm256_permute2f128_ps(m_tmp , m_tmp , 1);
m_tmp = _mm256_add_ps(m_tmp, ymm2);
m_tmp = _mm256_hadd_ps(m_tmp, m_tmp);
m_tmp = _mm256_hadd_ps(m_tmp, m_tmp);
result += m_tmp[0];
}例如OLAP 中常用的Aggregation操作，采用SIMD指令，计算性能能提升4倍左右，伪代码如上所示。一些更为复杂的算法可以利用GPU众核计算能力，例如并行过滤、聚合、规约等算法，计算性能最高可以提升一个数量级。
跨平台支持
云计算时代，云平台支持多种不同的硬件资源，除传统x86平台外，国产x86平台、国产ARM平台、GPU、FPGA资源均可支持，用户只需要购买相应的资源规格即可，满足了用户不同的场景需求。Odyssey计算引擎在ADB PG的基础之上，进一步扩展了支持的范围，目前Odyssey计算引擎已经完美运行在x86平台和ARM平台上。
除此之外，Odyssey计算引擎支持使用GPU和FPGA对关键算子进行加速。GPU作为一种众核架构，计算资源和带宽资源充足，适合数据密集型、高吞吐的场景。FPGA作为一种可定制化处理器，非常适合一些逻辑复杂的操作，有效提升硬件的资源利用率。目前Odyssey计算引擎支持使用GPU加速部分高密度算子，可实现超过5倍的性能提升。支持使用FPGA加速存储层的压缩和解压缩，最高性能提升超过10倍。
性能结果
测试采用的是标准的TPCH测试集，使用TPCH官方的工具生成数据和22条SQL，数据量为1TB，scale factor = 1000，集群规模都为32个segment。22条SQL从Q1到Q22单并发顺序、连续执行，每一条SQL发送出去记为开始时间，返回结果为结束时间，执行时间为两者的差值。
X86平台测试结果
x86平台测试在阿里云上进行，实例的具体规格如下：
单节点核数：4
单节点内存：32G
单节点磁盘：320G SSD
实例节点数：32
测试结果如下：
从图中可以看出，Odyssey计算引擎比原生引擎有比较明显的优势，Q1、Q4、Q9、Q11、Q17、Q20、Q21、Q22这些SQL有1倍以上的提升，其中Q17有2倍以上的性能提升。提升的比例与SQL类型有关，对于计算密集型的SQL优势更加明显。对于IO密集型的SQL，我们在IO接口上做了适配和优化，计算性能提升的同事，IO性能也有提升。
ARM平台测试结果
ARM平台的测试采用三台服务器，一台作为master，另外两台作为计算节点。计算节点上各部署16个segment，共32个segment。每台服务器的配置如下：
CPU：128 cores
内存：378G
磁盘：3.84Tx4 AliFlash
从图中可以看出，在ARM平台，Odyssey计算引擎也有比较大的优势，而且相对x86平台，Odyssey在ARM平台上优势更明显。
总结
以上是ADB PG新的计算引擎Odyssey的一些技术细节，总的来说，Odyssey使用了新的技术：JIT，新的模型：批量（batch）化的火山模型，新的硬件特性：CPU的AVX指令、GPU的众核计算、FPGA的专用计算。在公有云上1TB的TPCH实测，22条语句的总时间是原引擎的50%，单条SQL性能最高提升2倍多；ARM服务器上搭载Odyssey计算引擎的ADB PG也有一倍的性能提升，并且相对X86平台，Odyssey引擎提升更明显。
接下来的Odyssey计算引擎还会在存储层适配优化，更极致的性能优化上下功夫，敬请各位关注!
