mpp数据库查询逻辑（Codegen技术在MPP数据库的应用）

1.背景

Codegen技术是一种runtime态的动态编译技术，在现代OLAP引擎当中，该技术有一个更加贴切的专有名词：查询编译（Query Compilation），我们讲查询编译，就不得不提查询解释，那什么是查询的解释执行呢？我们先来看下数据库当中经典的火山模型执行引擎，如下是的一个SQL的执行计划分解：

在火山模型中，不论多复杂的查询，都会转成由关系代数表示的一个Query Execution Plan。而Plan由一个个小的Operator组成，例如HashJoin、Scan、IndexScan、Aggregation等等。为了连接不同的算子，它们遵循统一的接口，即迭代器模式：open/next/close，每个Operator从子节点的next接口获得一条数据，执行算子内部的计算逻辑，再返回给父节点，这个就类似解释型的语言一样，一条数据解释执行一次。

火山模型有几个特征：

Extensible：Operator之间依赖于接口而非具体实现，很容易实现新的Operator替换现有的；

Parallel：每个Operator可以在不同的线程运行，next不再是函数调用而是进程间通信，即可实现Operator之间的流水线化并行；

Pipeline：每次调用next接口只需要返回一条数据，不需要把所有数据计算完成再返回，避免过多的数据物化的开销；

iterator pull：虽然称之为火山，但数据并不是从Plan Tree的底部网上喷发的，而是从顶部把数据通过迭代器pull上去的。

在机械磁盘的时代，火山模型非常经济实惠，几乎所有主流的商业数据库都采用的这个模型。但在如今硬件快速发展的背景下（NVME的磁盘每秒钟的ioPS高达80万次/s,相比机械盘的IOPS提升了100倍；CPU的流水线技术带来10倍以上的性能提升），这一模型开始暴露出一些局限性：

iterator overhead：实现iterator一般使用virtual function，每读出一行数据需要多次函数调用，带来一些额外开销；

cache inefficiency：使用pull模型，数据加载到内存之后并不能保持在cache、register中，需要多次内存访问；

CPU inefficiency：iterator模型中存在的大量分支语句、内存访问对CPU并不友好。

基于这些问题，从七十年代的System R便开始探索查询编译这条路，但一路坎坷，直到近些年才开始得到更多的实际应用，Impala、SparkSQL、PostgreSQL等工业产品也开始采用编译执行的方案。

本文将结合OLAP场景下常见的SQL语句执行流程说明Codegen在火山引擎下可能存在性能缺陷的地方能够发挥比较好的优势。

2.场景分析

在OLAP场景下，即便是MPP的架构，单个线程也通常会处理上千万的数据，所以我们将按照单线程处理1000万这个数据量级进行相关场景的性能分析，我们在下面将会选择OLAP最多的两个核心逻辑进行对比。

2.1 数据的扫描读取

我们从磁盘上读出数据的时候，由于磁盘中存储的数据都是二进制形式的，所以在上层处理的时候需要将数据转化成schema中所定义的对应的类型，我们假设从数据库当中读取8列不同的数据，原始表的数据有10列，SQL为select c1,c2,c4,c5,c6,c7,c9,c10 from table1，假设table1的数据行数为1000万行，这个在OLAP引擎当中扫描千万行的数据是非常正常的一件事情。这个SQL的核心执行逻辑就是从磁盘读取1000万行数据，然后转换成对应的类型，再返回给客户端。1000万行8列基本类型的数据（都按照4字节计算）在开启压缩之后存储容量大致在100MB左右，我们假设SSD的顺序读取速度在1.5GB/s，忽略掉文件cache，这个读取的时延大概在65ms左右，返回给客户端的数据包大小我们按照原始的数据大小算，为320MB，同一机房内的机器的网卡带宽都在10Gbps左右，所以网络的发送时延约为250ms，剩下的主要是对这8000万个磁盘字节码数据进行解压缩和类型转换，当前业界主流的压缩算法（zstd，lz4，snappy）解压缩速度都在2GB/s左右，按照解压后的数据大小计算，解压时延为160ms，以上三部分的总时延约为475ms。现在还剩下数据转换的时延，我们分别通过查询编译和查询解释的不同实现去对比模拟这段逻辑执行的时延。

A、类似Codegen的核心实现逻辑代码如下：

B、类似查询解释基于if-else的通用实现代码：

C、类似查询解释基于switch-case的代码实现:

以上代码均采用GCC version 10.3.0 (GCC)进行编译并执行。

实际执行时间：

可以看到查询解释的执行时延最大，超过了io和解压缩的总时延，同时查询时延也是查询编译方式的8-9倍左右。由于循环的次数比较大，单次循环差个100ns，1000万行的数据累计起来就会有1s左右的时间，实际上使用Codegen技术动态编译，编译的时间在100ms级别，所以对于这种大数据量分析的OLAP场景还是有很大收益。

我们来看下如上代码的核心汇编指令,分析看下具体的问题所在。

A、类似Codegen代码的核心汇编指令：

实际上核心就是如下的三条指令：

B、类似查询解释if-else实现的核心汇编代码：

以上代码的核心提炼就是如下的指令：

外加平均4次(总共8个if-else的比较)的如下指令：

所以核心指令数从3个增加到了28个，由于没有涉及复合指令和系统内核函数的调用，所以这些指令的消耗的CPU周期差不多，28/3≈2174122/238522。

C、类似解释查询switch-case的核心汇编指令：

以上汇编代码的提炼就是如下的核心逻辑：

外加平均3.5次的如下指令（编译器其实还是做了优化的，按照case条件将值最大的放在最前面，最后的78和89为了减少一次cmp，将78排到了89的前面）

总指令数从3个增加到了11 3.5*4=25，由于没有涉及复合指令和系统内核的函数调用，所以这些指令的消耗的CPU周期差不多，25/3≈1935309/238522。

2.2 大量数据的函数运算

在查询解释执行的情况下，表达式的求值过程中通常需要调用虚函数，我们来看下如下的一个SQL，select sum(col3 5) from tbl2 where col6 > 5.1，假设这张表的数据量为1000万条，根据col6 > 5.1筛选完还剩500万条，我们通过模拟Codegen和查询解释的代码来对比下两种不同实现方式的核心逻辑的时延。

A、类似Codegen方式的核心代码如下：

B、类似解释执行的核心代码如下：

以上两段代码的通过g (GCC) 10.3.0编译，执行时延分别为：

以上两段代码涉及的AnyVal、IntVal、FloatVal、BooleanVal结构体实现如下：

有此可见虚函数调用带来的开销是多么庞大，大家有兴趣也可以使用g -S -o xxx.s xxx.cc进行汇编代码的分析，找出为什么虚函数的执行会有如此大的性能损失。

2.3 场景总结

从上面的场景来看，随着现代硬件的发展，大数据分析场景下的大部分SQL的执行瓶颈都是落在CPU上，所以探索如何利用Codegen减少SQL执行过程当中的CPU的指令运算是非常有必要的而且意义重大的。笔者认为至少有在如下的几个方向可以进行Codegen的探索：

谓词表达式：也就是SQL中的WHERE子句，例如上面的A.val = 123 AND A.id = C.a_id AND B.id = C.a_id；如果进行解释执行，那么就需要遍历这个AST，对每个运算符进行递归求值，虽然容易实现，但性能不容乐观。

数据解析：在反序列数据时，往往需要根据Schema进行解析，但提前知道Schema的情况下，可以对代码进行特化。

表达式：表达式还存在于Projection、GroupBy、Aggregation、Join等子句中，且计算结果不再是简单的Bool。

Operator：这里的Operator指的是Volcano中的单个Operator，在具备Schema信息的情况下，很多执行分支可以去掉。

3.技术方案

3.1 代码生成工具

我们从上了解到了SQL执行路径当中的不少代码可以使用runtime进行编译，那我们可以使用哪些技术实现如上的类似第二章以及上一节的功能呢？

早在上世纪七十年代的System R中，便有了查询编译的技术。（要知道，C语言是1972年才出现的）

The approach of compiling SQL statements into machine code was one of the most successful parts of the System R project. We were able to generate a machine-language routine to execute any SQL statement of arbitrary complexity by selecting code fragments from a library of approximately 100 fragments. The result was a beneficial effect on transaction programs, ad hoc query, and system simplicity.

当时的SystemR可以根据代码模板，直接将SQL编译成汇编，这在现在看来仍是相当硬核，毕竟能够手写汇编的人已经不多了（不可否认，极端性能还是需要撸汇编）。但在八十年代早期，IBM便放弃了这个计划，考虑到较高的外部函数调用开销，汇编的较差的移植性，以及整个方案的可维护性。

由此可见，查询编译最大的一个阻碍，可能是工程上带来的复杂度，并使得项目的可维护性降低，导致其在很长一段时间内没有被广泛采用。

当前阶段，LLVM IR几乎已经成为Codegen的事实标准，被工业界和学术界广泛采用，在讲LLVM IR之前我们先来介绍一下LLVM，LLVM是一个编译器及相关工具的库(toolchain)，它不同于独立应用式(stand-alone)的传统编译器，LLVM是模块化且可重用的，尽管LLVM因一些特殊的能力以及著名的工具，如比GCC更优的CLang编译器，但真正使LLVM区别于其他编译器的是它的内部架构。

经典静态编译器(像多数C编译器)中，最流行的设计是前端、优化器、后端组成的三阶段设计。如下图所示：

◇ Frontend:前端词法分析、语法分析、语义分析、生成中间代码

◇ Optimizer:优化器中间代码优化

◇ Backend:后端生成机器码

◇ LLVM架构：

不同的前端后端使用统一的中间代码LLVM Intermediate Representation (LLVM IR)

◇ 如果需要支持一种新的编程语言，那么只需要实现一个新的前端

◇ 如果需要支持一种新的硬件设备，那么只需要实现一个新的后端

◇ 优化阶段是一个通用的阶段，它针对的是统一的LLVM IR，不论是支持新的编程语言，还是支持新的硬件设备，都不需要对优化阶段做修改。

◇ 相比之下，GCC的前端和后端没分得太开，前端后端耦合在了一起，所以GCC为了支持一门新的语言，或者为了支持一个新的目标平台，就变得特别困难。

LLVM主要使用IR(intermediate representation)来生成代码，例如LLVM的前端Clang C 编译器生成IR，LLVM优化IR并将其编译成机器码。IR类似于汇编语言，由一些简单的、能够直接映射成机器码的指令组成。也可以使用LLVM的IRBuilder API来编程式地生成IR指令。

从上我们可以知道，我们只需要基于IRbuilder进行相应的编码，然后就可以生成对应的机器码进行执行了。

如下是一个简单的使用IRBuilder生成IR 代码的c 代码：

3.2 Codegen在MPP数据库中的应用

我们以Impala的执行流程为例，当Impala接受到查询计划(query plan，由Impala的Java前端负责生成)时，LLVM会被用来在查询执行开始前，生成并编译对性能至关重要的函数的查询特定版本（在代码生成时，由于已经知道了数据的类型，数据的layout。所以生成的代码中，会对循环等进行很多的优化）。在Impala中有两种技术来生成IR函数：同时使用LLVM的IRBuilder API来编程式地生成IR指令以及使用CLang将C 函数交叉编译成IR。

我们来对比一下Impala当中的从hdfs当中读取avro格式数据的两种不同方式的代码。

普通的读取代码如下：

每一行当中的每一列数据都需要switch-case判断类型，然后进行相关的赋值。

使用LLVM IRBuilder生成代码技术的代码如下：

以上代码的意义是将普通DecodeAvroData函数当中的InitTuple、MaterializeTuple、EvalConjuncts、CopyStrings函数替换成特定的生成代码，其中CodegenMaterializeTuple代码如下：

这段代码会根据读取列的类型生成特定的执行代码（这段代码用于生成没有switch-case的MaterializeTuple函数），这个生成代码的代码只会被执行一次，但是被生成没有switch-case的代码会被执行很多次（max_tuple次，也就是扫描的行数），如果max_tuple足够大，就非常有意义。

3.3 优化后结果对比

我们展示了当我们增加查询的复杂性时，运行时代码生成的有效性。这些查询在10个节点的集群上运行，覆盖600M行的Avro[4]数据集。在第一个查询中，我们对表中的行进行简单计数。这不需要实际解析任何Avro数据，因此代码生成的唯一好处是提高计数聚合的效率，这已经非常简单了。因此，代码生成产生的加速比非常小。在第二个查询中，我们对单个列进行计数，这需要解析Avro数据以检测空值。与更简单的查询相比，代码生成的优势增加了60%。最后，这涉及到多个聚合、表达式和GROUP BY子句，从而导致更大的加速比。

我们查看运行时代码生成如何减少运行TPCH-Q1时执行的指令数量。这些计数是使用 Linux Perf工具从硬件计数器收集的。

最后，在上图中，展示了在有和没有代码生成的情况下运行几个稍作修改的TPC-DS查询的结果。这些查询在一个10节点集群上运行，规模因子为1TB的Parquet[6，2]数据集。由于查询执行的某些部分未实现代码生成，因此这些查询无法实现上述TPCH-Q1结果中的5倍加速。特别是，几乎所有的TPCDS查询都包含ORDER BY子句，该子句当前不能从代码生成中受益。然而，在每个查询上仍然获得了显著的加速，并且我们期望一旦更多的执行可以由代码生成， 这将变得更大。

4.总结

LLVM允许我们实现一个通用的SQL引擎，其中各个查询的执行就像我们专门为该查询编写了一个专用的应用程序一样。目前这些技术在MPP数据库当中的应用只局限在某些操作符和函数编写代码生成函数，如果能够生成的查询越多，我们就越能利用函数内联和后续的函数间优化，最终期待将整个查询执行树折叠成一个函数，以便消除几乎所有的内存访问并将状态保存在寄存器中，这个也是MPP数据库性能提升的非常重要的研究方向。

,