写点什么

数据库内核杂谈 (十七):code-gen 深入学习

2021 年 4 月 02 日

数据库内核杂谈(十七):code-gen 深入学习

本文是数据库内核系列文章之一。


本文我们将和大家一起深入学习 code-gen,基于 Thomas Neumann 的论文:Efficiently Compiling Efficient Query Plans for Modern Hardware。

Volcano 模式的不足


稍稍复习一下传统的 Volcano(火山模型)执行模式:优化器会生成由物理算子构成的物理执行计划;执行计划呈树状结构,上层的算子通过 pull 模式拉去数据:调用下层算子的 next 方法获取下一个 tuple。Volcalno 模式的优势在于,容易理解,非常通用,并且容易实现。但是,通用性却带来了性能的损失,仅从 next 方法的调用来看,首先,由于通用性,会牵涉到 dynamic binding,其次是方法调用本身会造成开销。并且,每一个算子在处理每一个 tuple 都需要调用 next 方法。试想一个复杂的查询语句由 20 个算子构成,处理大约 10Million 个数据。光调用 next 方法就有约 200Million 次。其次,由于数据是一个 tuple 一个 tuple 处理,数据的 locality 不好,即,要被处理的数据在内存中可能并不是挨得很近,这使得 CPU 寄存器使用效率降低(因为需要不断地将待处理的数据换入和换出寄存器),导致性能降低。

手写代码的洞见


本文引用了 MonetDB/X100 的另一篇文章(MonetDB/X100 - a DBMS in the CPU cache)中的一个观点:给定一个 SQL 语句,如果让一个技术精湛的程序员(比如 Jeff Dean),手写一段代码来实现这个语句,那一定能得到比 Volcano 模型更好的性能。仔细想想,这个观点很容易被证实。首先,因为已经了解了所有的 SQL 查询算子,完全可以把所有的算子放在一个方法中实现。这样,就完全避免了方法调用,因此减少了不计其数的 next 方法调用。其次,因为完全不需要兼顾数据和代码通用性,可以通过直接访问内存来访问和操纵数据。抛开其他的优化方式,仅上述提到的两种优化,就能明显地提高执行语句的性能。MonetDB 文中一个给出了了一个比较数据,参见下图。

 

 

基于上述的洞见,本文提出了一个新的执行模式和优化方法:给定一个 SQL 语句,除了生成优化后的执行计划,更进一步,生成执行计划的机器代码。这个机器代码只服务于执行这一个语句,完全不用考虑各种通用和兼容性。虽然,生成的代码可能不能真正达到 Jeaf Dean 的水准,但是完全可以通过一些优化方式来逼近最佳性能。

 

如何定义最佳性能呢?因为程序最终都是由 CPU 执行,本文定义的优化函数是,尽可能地减少 CPU instructions。如何才能减少 CPU instruction 呢?文章给出的答案是,以数据为中心来执行 SQL 语句,而不是算子。这句话听起来有点玄学,但本质很简单,要尽最大可能,使被处理的数据,保存在 CPU 寄存器中。如此,减少了把数据换入和换出寄存器的无用操作,最终达到减少 CPU instructions 的目的。

新的执行模式

 

本文提出的执行模式是最大化以数据为中心来处理执行逻辑。

 

首先,文章定义了一个新的概念来辅助介绍这种执行模式,pipeline-breaker。Pipeline-breaker 的定义是,在执行语句中的某一个算子,如果它的执行逻辑需要把一个待处理的 tuple 从 CPU 寄存器中去除,那这个算子就被定义成一个 pipeline-breaker。如果一个算子需要等待子算子把所有的 tuple 都送给它,才能处理数据,那这个算子就被定义成 full-pipeline-breaker。(当然,实际情况中,可能某个 tuple 已经大到 CPU 寄存器无法存下,文章这边做了个小假设, 假设有足够的寄存器)。

 

有了这个定义后,下一个问题就是,如何才能一直将数据放在寄存器中呢?上面介绍的传统火山模型显然是做不到这一点:因为火山模型算子之间通过方法调用来传递 tuple,方法调用牵涉到方法栈的更新,数据早就被移出寄存器了。本文提到的方法就是,通过不断地把数据 push 给下一个要处理的算子,直到遇到 pipeline-breaker。但这个解释不直观。我的理解就是,对于某一个 tuple 数据,把要对其进行处理的算子(直到遇到 pipeline-breaker)排成队,依次对数据进行操作,在这个 pipeline 处理过程中,数据始终是存放在 CPU 寄存器中,因此,执行一个 pipeline 是非常高效的。而根据 pipeline-breaker,一个执行计划就会被 pipeline-breaker 算子分解成几个 pipeline,数据在这个维度下,总是从一个 pipeline,被处理完,进入另一个 pipeline。

 

通过一个例子,更直观地来了解一下整个过程。给定下面这个 SQL 语句:

一个 join 查询内部夹带一个子查询语句。


正常生成的执行计划如下图所示:


先对 R2 进行扫描,filter,然后对 R2.z 做 group by count(*)计算,得到一个临时的表;然后和 R3 进行 join,最后再和处理过的 R1 的 tuple 进行 join。

 

而根据 pipeline-breaker 的定义,图中的 GroupBy 算子和 Join 算子就是 pipeline-breaker。因为它们都需要得到子算子的所有 tuple,才可以执行:GroupBy 算子需要得到所有的结果才可以对 Z 进行 count 聚合操作,而 Join 算子,则需要把左侧结果生成 hash 表来做 hashJoin。根据先前的定义,这个执行计划被分解成 4 个 pipeline。如下图所示:

而每个 pipeline 在执行的过程中,是可以最大化将数据保存在 CPU 寄存器中的。根据这个结果,就可以生成出下面的执行语句代码:



可见,每个 pipeline 对应一个最外层的 for 循环,总共有 4 个外层 for 循环,最后一个三层 for 循环嵌套就是对两个 join 的执行。在执行每一层 for 循环的时候,都可以通过代码优化,尽可能地将数据保留在 CPU 寄存器中。

 

文中还介绍了一种新的 algebra 来描述对算子的改造,并且示例讲解,如何根据新定义的 algebra,把一个执行计划拆分成多个 pipeline,然后生成出伪代码。我觉得有点抽象,就不在这深入讲解了,有兴趣的同学可以去参考原文。

code-gen 代码生成


刚才的示例展现了拆分成 4 个 pipeline 后的 4 段 for 循环的伪代码,现在来讨论如何来生成计算机能看懂的机器代码。作者提到,一开始想直接让优化器,优化 SQL 语句后生成出 C++代码(类似上面的 for 循环伪代码),然后编译成机器码,但在实验的过程中发现了弊端,最重要的问题就是生成优化的 C++代码的这个过程非常耗时,时间消耗以秒计算,这个性能是无法接受的。

 

最终通过实验,决定直接使用 LLVM,将语句生成 LLVM 的汇编代码,然后用 LLVM 自带的 JIT 编译器来运行生成机器代码。文中提到 LLVM 的好处如下:1)生成的汇编代码质量很高,会尽可能提高 CPU 寄存器的使用率,并且,LLVM 汇编代码是可 portable 的,可以通过不同平台的 LLVM 的 JIT 编译器最终生成机器码。2)LLVM 的汇编代码是强类型的(我也不太清楚好处在哪,可能强类型在运行时就性能更好)。3)LLVM 已经被广泛使用在工业界,质量有保证,而且,不断在进步。4)编译时间短,是以毫秒计算。

 

但是,文中指出,也并不是把整个 SQL 语句,一股脑地全部编译成 LLVM 代码,最重要的原因就是,实现工程量太大了。文中指出,其实一个 C++执行引擎代码都在那里,并不需要把所有的代码都重新用 LLCVM 汇编,而且 LLVM 汇编代码的好处在于,和 C++代码,双向之间可以无缝调用。一些复杂的逻辑和复杂的算子可以用 C++的现有实现,比如复杂数据结构的 access,包括需要把数据暂存到文件中等等的逻辑。LLVM 相当于把这些 C++代码根据具体的执行语句,动态地把这些预编译的 C++代码结合起来,生成一个完整的执行计划的汇编代码。对于热点代码(某些 code 会被几乎全部的 tuple 都运行的代码),可以完全由 LLVM 生成汇编代码来提高性能。LLVM 和 C++代码的嵌合,文章给出了示意图。


另外,在测试中,由于会遇到复杂的算子,很难完全生成一个完整的方法来执行语句的所有逻辑,因此可以在 LLVM 汇编代码中调用现成的 C++代码来执行。

 

文中还介绍了用 SIMD 来进一步提升性能的高级优化方法。因为在 for 循环中,如果 block 如果过大,对 CPU 寄存器不友好,就会影响性能。可以通过减少数据 block 的大小,让所有的数据还是能存放在寄存器内,然后通过 SIMD instructions 来提升速度。除了 SIMD,还可以利用 multi-core processing,主要就是把要处理的数据分成多分,然后通过多 CPU 并行处理来提高性能。回顾上面介绍的例子中,不同的 pipeline 可以并行处理,比如处理 R1 的 pipeline 和 R2 的 pipeline,可以并行处理。

 

文章在最后对这项技术进行了一些测试,测试结果结果肯定显而易见,


从图上很容易得出:

1)C++代码的编译时间远高于 LLVM 编译。

2)即使算上代码的编译时间,LLVM 编译加执行的性能也是最高的。

3)Vec-exec 的性能也不错。

4)这两种技术都远优于传统的数据库执行引擎。

总结


这篇文章,通过对 Thomas Neumann 的文章 Efficiently Compiling Efficient Query Plans for Modern Hardware 进行解读,深入了解了 code-gen 是如何提高性能的。文章通过定义 pipeline-breaker 的算子,将一个执行计划分成多个 pipeline,不同的 pipeline(如果没有依赖关系)可以并行执行;并且,每个 pipeline 都可以尽可能地优化来将数据始终保存在 CPU 寄存器中来提升性能。文章还验证了使用 LLVM 编译代码的可行性,并且认为比 C++代码生成要更优秀。在商用的数据库系统中,除了上次介绍的 Snowflake,也有使用 code-gen 来提升执行性能的。GreenPlum GPDB 的这篇博客介绍了如何通过 code-gen 来提升性能,贴在这里作为参考,有兴趣的同学可以继续阅读。

 

感谢阅读这一期杂谈!2021 年的愿景之一是做更多对于技术和管理的输出,如果想要和我更多交流,欢迎关注我的知识星球:Dr.ZZZ 聊技术和管理

2021 年 4 月 02 日 12:062588

评论

发布
暂无评论
发现更多内容

智慧仓储管理系统,是否能解决购物狂欢节后新一轮爆仓危机?

一只数据鲸鱼

物联网 数据可视化 智慧物流 智慧仓储

工具词典:精力管理

lidaobing

精力管理 张遇升 28天写作

像用户一样测试:打破知识的诅咒

QualityFocus

测试 软件质量 可用性 用户体验

犯“走私罪”的CTO | 法庭上的CTO(19)

赵新龙

CTO 法庭上的CTO

阿里P8大牛手把手教你!高级Android晋升之View渲染机制,先收藏了

欢喜学安卓

android 程序员 面试 移动开发

创建493个测试账户,被公司索赔527万 | 法庭上的 CTO(14)

赵新龙

CTO 法庭上的CTO

从MongoID的生成讨论分布式唯一ID生成方案

行如风

雪花算法 分布式ID 全局唯一ID 流星算法

“盗窃”公司源代码被开除的CTO | 法庭上的CTO(20)

赵新龙

CTO 法庭上的CTO

生产环境全链路压测建设历程 21:某快递 A 股上市公司的生产压测案例之基于测试流量的混沌工程(故障演练)

数列科技杨德华

全链路压测 七日更

劫持Chrome浏览器“获利”8000万元 | 法庭上的CTO(13)

赵新龙

CTO 法庭上的CTO

混合用工、被拖欠工资的 CTO | 法庭上的 CTO(16)

赵新龙

CTO 法庭上的CTO

未签订劳动合同的CTO | 法庭上的 CTO(17)

赵新龙

CTO 法庭上的CTO

计算机网络简述

lee

计算机网络 网络协议 网络

为什么要TDD(测试驱动开发)

sherlockq

敏捷开发 TDD 极限编程

程序员开发指南!1-3年的Android开发工程师看过来,经典好文

欢喜学安卓

android 程序员 面试 移动开发

ZooX首发双向电动无人车,会成为自动驾驶出行的主流吗?

脑极体

从一个模糊词查询需求的处理方案讨论到一种极速匹配方案的实现

行如风

模糊匹配 双数组trie树 ahocorasick ac自动机 黑名单过滤

股东变员工,所以不发工资?| 法庭上的CTO(18)

赵新龙

CTO 法庭上的CTO

重学JS | 数组遍历的7种方法及兼容性处理(polyfill)

梁龙先森

前端 编程语言

“有点技术之外,基本什么都没有”的CTO | 法庭上的CTO(15)

赵新龙

CTO 法庭上的CTO

Spring 源码学习 11:invokeBeanFactoryPostProcessors

程序员小航

Java spring 源码 源码阅读

深入浅出 ZooKeeper

vivo互联网技术

zookeeper 分布式 ZAB

什么是浮点数?

Kaito

计算机基础 浮点数

(经验分享)作为一名普通本科计算机专业学生,我大学四年到底走了多少弯路

Java鱼仔

Java 程序员 面试 大学生

大作业一

黄立

这个问题值得讨论吗?

Alan

沟通 团队文化 七日更 28天写作

anonymous匿名者场外交易系统APP软件开发

开發I852946OIIO

系统开发

英特尔赵宏:从硬件创新到平台突破,PC的未来非常值得期待

intel001

人工智能不过尔尔,基于Python3深度学习库Keras/TensorFlow打造属于自己的聊天机器人(ChatRobot)

刘悦的技术博客

人工智能 tensorflow chatbot 聊天机器人 keras

为新基建按下加速键:从openEuler看中国操作系统的产业生态未来

脑极体

甲方日常 75

句子

工作 随笔杂谈 日常

4月17日 HarmonyOS 开发者日·上海站

4月17日 HarmonyOS 开发者日·上海站

数据库内核杂谈(十七):code-gen 深入学习-InfoQ