高级数据看二十一：查询计划编译

系统管理员 2022-06-01 00:07 171阅读 0赞

# Query Compilation #

## 背景 ##

对于in-memory数据库，因为所有的数据都在内存之中，所以很多其他影响速度的因素（如磁盘IO等）都消失了，所以提高吞吐量的唯一方法是减少执行的指令数量。

*  提高十倍速度，DBMS需要减少90%的指令
 *  提高百倍速度，DBMS需要减少99%的指令

我们可以通过code specialization来实现这种指令数量的减少。即，通过生成DBMS中特定任务的代码来减少指令数量。

大多数代码是为了让人们理解而写的，而不是这样写的效率最高。

接下来的分析都是从逻辑查询计划方面进行分析，但是不是说物理查询计划不会对此造成影响。而是在分析的时候，只要照着逻辑方面进行理解即可

## Code Generation / Transpilation ##

举一个例子

![15159896729924.jpg][]

对于如上的数据库，执行如下的操作

SELECT * FROM A, C, ( SELECT B.id, COUNT(*) FROM B WHERE B.val = ? + 1 GROUP BY B.id) AS B WHERE A.val = 123 AND A.id = C.a_id AND B.id = C.b_id

我们根据之前文章上讲到的火山模型，可以得到相应的查询树和查询计划

![15159900179603.jpg][]

我们的查询语句会被根据优化器进行重写，重写成Join的形式。

对于人类而言，这写代码以及这种查询树是非常好理解的。但是这段代码对CPU而言就非常不友好:

1.  过多的结构和分支：无论是for还是if都会产生大量的分支，导致CPU要不断刷新管道和缓存。
2.  大量的函数调用：函数调用导致CPU在内存中不断跳跃。

这些都会带来大量的时间损耗。

![15159903048116.jpg][]

在执行参数输入的时候，`B.val = ? + 1`。

为了使得判断语句加快执行，我们也必须将一些其他的信息传入，如，现在所在元组，现在所在元组的位置信息，查询参数。

对于上面的查询树，我们为了处理一个元组，至少需要执行4次函数调用或者类似操作。

这样的代价也是非常大的。

### CODE SPECIALIZATION ###

那么对于上面的操作而言，都是一些通用的更加general的查询编译过程，它支持大多数的查询。

如果在不同的输入上具有相似的执行模式，则可以本地编译任何数据库的CPU密集型实体。即，针对一些特殊的查询进行特定的编译设计。

关于这一点，我觉得大家可以去查一查为什么Python这种弱类型语言的执行速度比较慢的原因。C++的执行效率比Python块很多，这个原因我觉得可以类比到CODE SPECIALIZATION的问题上。

*  访问方法
 *  存储过程
 *  操作员执行
 *  谓词评估
 *  记录操作

这样做的好处是

1.  属性类型是先验已知的。  
    
    
     *  数据访问函数调用可以转换为内联指针转换。
     *  即，可以直接通过offset访问元组中的某个属性。
2.  谓词是先验已知的。  
    
    
     *  可以使用原始数据直接比较来评估它们。
3.  循环中没有函数调用  
    
    
     *  允许编译器高效地将数据分发到寄存器并增加缓存重用。
     *  因为没有函数调用，所以只需要直接比较内存块的几个offset的某个size的数据的关系即可。

### CODE GENERATION METHOD ###

方法＃1：Transpilation

*  编写将关系查询计划转换为C/C++的代码，然后通过常规编译器运行它以生成机器码。

方法＃2：JIT Compilation

*  生成可快速编译为本地代码的查询的中间表示（IR）。

### [HIQUE - CODE GENERATION][] ###

对于给定的查询计划，创建一个实现该查询执行的C/C++程序。

*  将在所有谓词和类型转换都固定下来。

使用现成的编译器将代码转换为共享对象，将其链接到DBMS进程，然后调用exec函数。

这种方式就类似于一些用C++写的Python库一样，只是这里的方式是动态链接。

![15159914786124.jpg][]

总体结构是这样的，所以这是一个动态的编译过程。对于查询计划中的特定部分，通过算法将这部分进行重新编译，并连接到最终的查询程序中。

生成的查询代码的组件可以调用DBMS中的任何其他函数。这允许它使用与Interpreted Plan使用相同的组件。

*  并发控制
 *  记录/检查点
 *  索引

#### Interpreted Plan VS. Templated Plan ####

![15159913949730.jpg][]

1.  需要明确表中的信息，如，属性值大小等。
2.  计算每个tuple的大小。
3.  返回tuple指针

![15159916346663.jpg][]

做了一大堆事情就是为了判断条件。

![15159917594132.jpg][]

在已知所有的常数时，只要从内存中的某个位置计算一下偏移，并直接通过属性的偏移得到属性值，计算出结果。

然后直接和参数进行比较。

#### 评估 ####

1.  Generic Iterators：通用模型
2.  Optimized Iterators：对属性值有特定代码生成的模型，即，固定属性值，固定属性值大小
3.  Generic Hardcoded：对谓词和泛型迭代器产生特定的代码
4.  Optimized Hardcoded：直接访问元组的评估模型
5.  HIQUE：对特定查询计划产生代码的评估模型

![15159922836569.jpg][]

因为后两者几乎不用到哈数调用，所以占有绩效的Memory stall时间。

![15159923296127.jpg][]

GCC编译所需时间，这个代价也是非常大的。GCC需要查看环境、链接、库等等，所以也是较慢的。因此就产生了一种新的方式JIT Compilation。

## JIT Compilation (LLVM) ##

1.  关系运算符是推断查询的有效方式，但不是执行查询的最有效方法。
2.  GCC编译速度慢
3.  HIQUE不支持完全的管道，如下图，它的管道会因为其他的数据没有处理完，而等待其他数据的处理。这是管道瓶颈。

![15159924860970.jpg][]

所以产生了JIT Compilation这种技术，这种技术是当今世界上最好的查询编译技术，但是真正实现这种方式的数据库不多。

### [HYPER – JIT QUERY COMPILATION][HYPER _ JIT QUERY COMPILATION] ###

使用LLVM编译器去编译上面的查询计划，能够尽可能地将tuple留存在CPU寄存器之中。

它集合了多种编译器的特征，所以能够产生更加复杂的程序和功能。

它的核心部件是一种低级的编程语言IR，和汇编较为相似。

不是所有的DBMS系统都需要用IR去实现，LLVM代码可以被C++代码调用。也就是C++写结构，调用一个更快的语言写的库。

![15159928281810.jpg][]

它会根据管道瓶颈生成代码，但是多个core或者多个thread都不能同时在一个查询中的多个管道上运行，只能一个线程按顺序在多个管道上完成处理。但是可以安排在管道执行的先后顺序。

#### 评估 ####

![15159929430989.jpg][]

总体而言效果非常棒。

![15159929955584.jpg][]

编译时间也减少了非常多。

## Real-world Implementations ##

### [IBM System R][] ###

IBM在20世纪70年代使用了一种原始形式的代码生成和查询编译。通过为每个运算符选择代码模板，将SQL语句编译为汇编代码。

但是这种技术在DB2的时候就被放弃了

1.  外部调用代价高昂
2.  可移植性差，每次修改其他模块必要重构此模块

### Oracle ###

Oracle从始至终都没有用过重构代码的方式对查询进行加速。

它将PL/SQL存储过程转换为Pro\*C代码，然后编译为原始的C/C++代码。

他们还将Oracle特定的操作直接放在SPARC芯片中作为协处理器。他们没有从软件上对代码进行重写，而是从硬件上对代码进行了重写。

*  内存扫描
 *  位模式字典压缩
 *  为DBMS设计的矢量化指令
 *  安全/加密

### [Microsoft Hekaton][] ###

可以编译procesdures和SQL。

*  非Hekaton查询可以通过编译的运算符访问Hekaton表。

从命令式语法树生成C代码，直接跳过Intepretation阶段，将其编译为DLL文件，并在运行时链接。

采取安全措施，防止有人在查询中注入恶意代码。

### Cloudera Impala ###

用于谓词评估和记录解析的LLVM JIT编译。是为数不多的使用LLVM JIT编译的数据库

*  不知道他们是否也在做操作符编译。

优化的记录分析对于Impala非常重要，因为它们需要处理存储在HDFS上的多种数据格式。这个数据库非常强，比HIVE在交互和速度方面都强一些。

### [Actian Vector][] (formerly Vectorwise) ###

预编译数千个对输入数据执行基本操作的“原语”。

DBMS然后通过小test case的查询优化的运行，得出数据的类型从而选择应用何种基本操作。再在运行时调用这些原语。

*  函数调用在多个元组上分摊
 *  通过test case测试是哪种数据类型

![15159939149094.jpg][]

不是对于一个个元组进行处理，而是通过矢量的方式直接处理批量的元组。

### MemSQL ###

执行与HIQUE相同的C/C ++代码生成，然后调用gcc。将所有查询转换为参数化表单并缓存已编译的查询计划，从而减少GCC的调用。

![15159940017018.jpg][]

如果查询语句变化，如`B.id = A.id`和`A.id = B.id`，那么在2016年之前的MemSQL就无法判断是否产生过类似的GCC。虽然可以通过关系代数产生的查询树去判断，但是2016年之前的MemSQL并没有这么做。

2016年之后的MemSQL将查询计划进行了多层次地编译：

1.  MemSQL Programming Language (MPL)类似于C++
2.  DSL
3.  MemSQL Bit Code (MBC)类似于JVM的byte code
4.  LLVM IR
5.  native code

从而使得可移植性大大加强。

### VitesseDB ###

Postgres / Greenplum使用LLVM +查询内并行性的查询加速器。

*  JIT谓词
 *  基于推送的处理模式
 *  间接呼叫变为直接或内联。
 *  利用硬件进行溢出检测。

不支持Postgres的所有类型和功能。 所有的DML操作仍然被解释。

[15159896729924.jpg]: https://lh3.googleusercontent.com/-vtd4umTFAdk/Wlw860wxO2I/AAAAAAAAAi4/JZ5VzRVMhtwT1EPEModGXdI97LTX2xW9gCHMYCw/I/15159896729924.jpg
[15159900179603.jpg]: https://lh3.googleusercontent.com/-_fk7R0VwC9Q/Wlw87fLiErI/AAAAAAAAAi8/SanbeTr0-DIwN2KDXr6E2NQadyG58pq_gCHMYCw/I/15159900179603.jpg
[15159903048116.jpg]: https://lh3.googleusercontent.com/-8lX4SlQc3EM/Wlw87jMCefI/AAAAAAAAAjA/gd2HeLaW3Rormb70_leoqeh7dknCVw4sgCHMYCw/I/15159903048116.jpg
[HIQUE - CODE GENERATION]: http://15721.courses.cs.cmu.edu/spring2017/papers/20-compilation/krikellas-icde2010.pdf
[15159914786124.jpg]: https://lh3.googleusercontent.com/-IwH0sD-ZVIM/Wlw871XO2zI/AAAAAAAAAjE/e0N6Itk5YzwQXXEUZ1qI4ywgbvV8CmLbgCHMYCw/I/15159914786124.jpg
[15159913949730.jpg]: https://lh3.googleusercontent.com/-oDxrSG_cewg/Wlw88I9ZbsI/AAAAAAAAAjI/TH5o6TugO5MH3E15hSfHXk0fwJE7_c0FgCHMYCw/I/15159913949730.jpg
[15159916346663.jpg]: https://lh3.googleusercontent.com/-mHpk5RXj9jE/Wlw88SCfZHI/AAAAAAAAAjM/OtNG5NG31UkFJhE2ltF-tNXHsGg97EZKgCHMYCw/I/15159916346663.jpg
[15159917594132.jpg]: https://lh3.googleusercontent.com/-oAIDNl7JwVM/Wlw88i_x5yI/AAAAAAAAAjQ/iWHJ0HjlfMM8UjUTJsCTUrOCz508x6hEACHMYCw/I/15159917594132.jpg
[15159922836569.jpg]: https://lh3.googleusercontent.com/-6dNoI_iG_Rs/Wlw886czqeI/AAAAAAAAAjU/aVvEvnCf4aYI4HsG8q8gDM2SVn14-Ig0gCHMYCw/I/15159922836569.jpg
[15159923296127.jpg]: https://lh3.googleusercontent.com/-dRqEKVhWEGc/Wlw89IQQ3wI/AAAAAAAAAjY/xS1HUHy_-3AQlrIqjhQiLT_WMdRNpnmDgCHMYCw/I/15159923296127.jpg
[15159924860970.jpg]: https://lh3.googleusercontent.com/-QXTqThMkYe4/Wlw89dePF2I/AAAAAAAAAjc/IRH8Ow8vPHcXCfjrr7W8EVADJjbBaz4gQCHMYCw/I/15159924860970.jpg
[HYPER _ JIT QUERY COMPILATION]: http://15721.courses.cs.cmu.edu/spring2017/papers/20-compilation/p539-neumann.pdf
[15159928281810.jpg]: https://lh3.googleusercontent.com/-f9KoCKqDMrw/Wlw89hPyKPI/AAAAAAAAAjg/RuIR7kS9hKYAXyb6t5NdzRH1JG0sqwo2gCHMYCw/I/15159928281810.jpg
[15159929430989.jpg]: https://lh3.googleusercontent.com/-h9FMz3h8Hi8/Wlw89_zFZTI/AAAAAAAAAjk/X5c7-H2zByoxo-D9z9nwoRKHmOY8ndYUQCHMYCw/I/15159929430989.jpg
[15159929955584.jpg]: https://lh3.googleusercontent.com/-DdJosNZeTlY/Wlw8-Rbow_I/AAAAAAAAAjo/0Ka5R8eaBFgzaNCN80BHKDRGM5ItXw6YQCHMYCw/I/15159929955584.jpg
[IBM System R]: https://dl.acm.org/citation.cfm?id=358784
[Microsoft Hekaton]: http://15721.courses.cs.cmu.edu/spring2017/papers/20-compilation/freedman-ieee2014.pdf
[Actian Vector]: https://dl.acm.org/citation.cfm?id=2465292
[15159939149094.jpg]: https://lh3.googleusercontent.com/-RyuTcRYJvOE/Wlw8-pDtYCI/AAAAAAAAAjs/5gz7_T_enRY2UcbARWcmlGzlQHtypqPTACHMYCw/I/15159939149094.jpg
[15159940017018.jpg]: https://lh3.googleusercontent.com/-U1chY0ScIGg/Wlw8-9o9y8I/AAAAAAAAAjw/gK20GjjlYDYXvYVZD_Cw-_rOTJybFUMjgCHMYCw/I/15159940017018.jpg