红帽白皮书新鲜出炉!点击获取,让你的云战略更胜一筹! 了解详情
写点什么

数据库内核杂谈 (十五): 执行器之 code generation vs vectorized execution

  • 2021-01-27
  • 本文字数:3668 字

    阅读完需:约 12 分钟

数据库内核杂谈(十五): 执行器之code generation vs vectorized execution

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


从本文开始,我们一起来学习一下数据库引擎执行器中非常出名的两种优化方式,code generation(代码生成;以下简称 code-gen)和 vectorized execution(向量计算;以下简称 vec-exec)。为什么说学习呢,因为自己确实也没做过。所有的学习资料也是阅读一些技术博客和技术论文,我会仔细阅读,争取可以用深入浅出的语言写出来。

 

说到 code-gen 和 vec-exec,这两个概念出自两篇非常有名的文章。code-gen 出自 Thomas Neumann 的文章:Efficiently Compiling Efficient Query Plans for Modern Hardware;vec-exec 出自 MonetDB/X00: Hyper-Pipelining Query Execution。MonetDB 的作者之一是 Marcin Zukowski。他的博士毕业论文就是详细阐述了 vec-exec(目前暂定计划是,仔细阅读一下他的博士毕业论文,然后输出一到两期)。他也是目前超级火热的 Snowflake 数据库公司的创始人之一,Snowflake 的执行器就是基于 vec-exec 的。讲到这,我得说一个没吃到葡萄,觉得葡萄特别酸的故事:早先在数据库会议上见过 Marcin 几次,是个非常 nice 的人。当时 Snowflake 也刚开始做没多久吧。Marcin 说,他想招做 optimizer 的。我说,我就是啊。Marcin 说,我想招个女性。。。我说,为啥。。。因为 diversity?他说,不是,因为现在 optimizer 组全是女性,他希望能保持 optimizer 组全女性阵容(强迫症晚期患者)。然后我还去问了 Lyublena,但是 Lyublena 当时也刚加入 Datometry,没有去。我,因为性别,错过了一次财务自由的机会。

 

后来,Andy Pavlo(CMU 数据库教授)把 Thomas 和 Peter(MonetDB 另一位作者)组在一起,写了一篇 survey paper: everything you always wanted to know about compiled and vectorized queries but were afraid to ask(不得不说,Andy 的所有论文,名字起的都特别网红)。今天的内容,咱们从读懂这篇 survey paper 开始。

 

绝大部分的现代数据库的执行器引擎都是基于 code-gen 或者 vec-exec 的。  有意思的是,它们都为了提升性能而生,但是却走了不同的两条路。目前,两种技术都被成熟应用到数据库系统中。但是,至今为止,也没能很客观地去比较这两种技术的好坏。因为,对于一个数据库系统而言,一般只会选择点选一个技能树,然后,就沿着这条技能树发展,所有的发展都是围绕这个技术的。如果比较不同的数据库,由于不可控的因素太多了,很难可观地比较这两种技术。这也是 Andy 他们写这篇文章的初衷:为了可以公正地比较这两种技术,专门在自己开源的数据库上实现了两种技术,而且,尽量做到客观,公正,使用相同的算法和类型模型。

 

杂谈第四章,介绍执行模式的时候,我们介绍过传统的执行器执行模式,Volcano-style 模型(火山模型)。Volcano-style 的优点在于,非常的 general,容易扩展和理解,实现也相对容易。并且,当还处于读写磁盘是主要性能瓶颈的年代,并没有察觉,这个模型会对性能造成太多损失。但现在不同了,所有硬件的性能都提升了不止几个数量级。数据库也在为了追求极致性能不断优化。 普通硬盘慢,那就用 SSD,再不行,就纯 in-memory 数据库。行存(row-store)对于读海量数据的 OLAP 语句来说没有优势,那就改为列存(column-store)。在执行器这方面,就衍生出了两种技术,code-gen 和 vec-exec。主流的数据库几乎都使用了其中一种来作为执行器。用 vec-exec 的有,DB2-BLU,Columnar SQL Server, 以及 QuickStep 等等. 而 code-gen 则有 Apache Spark 以及 Peloton 等等,包括 Pivotal 的 GPDB 也有 code-gen 模式。

 

下面,先简单介绍下这两项技术。

Vec-exec


Vec-exec,类似于 Volcano-style,也是基于拉模式的方式来处理。区别在于,next 方法不再只返回一个 tuple,而是一个 batch 的 tuples。因此在处理的时候,可以批量一起处理一波 tuples。读者可能会有疑问,诚然,每一次拉取了一波 tuples 一起处理,确实是节省了总共调用 next 的次数。但是说到底,总共要处理的 tuple 是没有变化的。为什么 vec-exec 能带来可观的性能提升呢?其实是基于硬件的提升:SIMD: single instruction multi-data。即,单个指令直接作用到多个数据,比如,可以同时计算多个 vector 里数据的 hash 值。因此,vec-exec 更适合配合 column-store。

 

Code-gen


而 code-gen,虽然也是利用硬件带来的性能提升。相比 vec-exec,使用了完全不同的模式。虽然还是有 operator,但 operator 不再是相互独立地处理数据,而是把所有的 operator 当成一个整体,然后生成出一段代码来实现整个逻辑:为每个 query 都会单独去生成一段代码来实现。可能读者会有相同的疑问,性能提升是从何说起。举个例子,大家都听说过 Google 大神 Jeff Dean 的故事。传言 compiler 从来不给他优化提示,因为他手写的代码比 compiler 更优化。你大致可以想象,code-gen 呢就是,对于每个语句,都找一个 Jeff Dean 一样的高手,根据数据的类型,数据的大小,然后结合硬件 CPU,寄存器,内存等的信息,手写一段代码来实现这个语句。不需要兼顾 general 属性,因此可以更高效。而传统的 volcano-style,因为兼顾 general,因此代码本身是并不优化的。而且,code-gen 生成的代码可以进一步通过编译优化生成性能更高的机器代码(比如,通过 LLVM)。

 

稍微展开一点,怎么才可以生成出性能更高的机器代码呢?一个衡量的标准就是运行这个语句,总共的 CPU 指令更少。如何才能生成 CPU 指令更少的机器代码呢。我也不是专家,阅读文章后,这是我自己的理解。CPU 运行的时候,需要通过和寄存器交互来处理数据,而把数据从内存换到寄存器中是需要消耗 CPU 指令的。那一个简单的思想就是,如果生成的代码,可以尽可能地提高寄存器的利用率,即,使得连续的 CPU 指令都能 hit 寄存器中的数据,而不是消耗在不停地交换内存数据中,这样的代码就更高效。

 

什么传统的 volcano-style 对 CPU 或者寄存器不是很友好。原因之一就在于设计模式非常 general(好处在于比较容易实现)但劣势在于,为了追求通用性,会增加额外方法调用的开销,并且大大增加了寄存器 miss 的可能性。为什么这么说呢。来看一个示例。假设处理下列的语句

 

SELECT  COL1 + 10 as NEW_COL1, COL2, COL3, COL4, ...., COL20 FROM  TABLE1WHERE   COL1 > 10;
复制代码

 

因为 tuple 是一条一条处理的,因此,第一个 filter operator 会不停地从 TableScan 读取数据,然后判断是否 COL1>10。判断完了后,上层的 projection operator 会得到这个 tuple,然后处理 COL1+10。但是,这边多了一次方法调用,是有开销的。并且,假设 tuple 过长,极有可能数据就被从寄存器换出,执行加法操作还要再多一条指令将 COL1 读进寄存器。


那 code-gen 可以怎么做呢?对于每一个 COL1,可以把 COL1+10 的这个操作合并到 filter operator 一起,这样,就可以保证寄存器 hit,而且,生成的 code 可以直接是一个大 for 循环,完全去掉不必要的方法调用。

 

论文种给出的 HashJoin 示例比较


文中给出 HashJoin 的 code-gen 和 vec-exec 的代码比较。


可以看到,code-gen 的做法就是先读取用来构建 hash 表一侧的所有数据,构建 hash 表。然后读取右侧 table 来判断 hash 条件是否某满足。从这个实现上看,也没有特别神奇的地方。但总结来说,去掉了一个一个 tuple 处理的模式,对 cache hit 更有利;并且,去掉了 next 方法调用的额外开销。而且,对于这类 for 循环,通常编译器还能更好地做优化来生成机器代码。



上图种 vec-exec 所用的代码,在构建 hash 表时,代码类似,因此省略了。在 hash probe 时,和单个 tuple 比,每次读取一个 batch 的 tuples,来处理,也没有特别多神奇的地方。

比较结果总结


文中用了大段来陈述比较结果,并且从多个维度进行了比较。例如,分别考虑了单线程模型,多线程模型的实现;不同的硬件场景;是否使用 SIMD。比较的维度也有 CPU cycles,指令数,L1 Cache miss, LLC (Last-level cache) miss, branch miss 等等。我在这就不一一复述了,相信大家也不是特别感兴趣。


翻译一下最后的总结:


1)code-gen 对于计算复杂性更高的语句来说,更有优势,因为可以通过代码优化来提高寄存器利用率,从而需要更少的指令来执行整个计划。

2)对于并行处理数据 SIMD 来说, vec-exec 更适合。

3)对于多 CPU 环境,两项技术都可以 scale。

4)对于不同硬件环境,两项技术也是伯仲之间。

 

用一句话而言,两项技术都可以提升性能,侧重点不同,语句的不同,带来的性能提升也不同。

 

说一下我自己肤浅的理解。首先,code-Gen 的实现更复杂。特别是要实现高质量的代码,毕竟,你不会真有一个 Jeff Dean 在后台给你写代码,相当于实现了一个 compiler。另外要提的是,Code-gen 的本身从 query 到 generated code 是需要花时间的。这个时间,通常和 Query Optimization 的时间合并在一起了,但肯定是比普通的优化时间更长的。 此外,还要把这个生成的 code 再翻译成机器代码。文中提到了用 LLVM:LLVM 会进一步对代码优化,生成机器码,时间复杂度基本和代码量成线性。

 

我个人觉得,code-gen 应该会比 vectorized execution 性能更高一些,如果实现的好的话。其实大家可以想一下,code-gen 完全可以生成类似 vec-exec 的代码,如果在某些场景下,后者性能更高的话。


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

2021-01-27 23:027011

评论 5 条评论

发布
用户头像
pull跟push是不能兼容的,但是code-gen跟vectorization肯定是可以兼容的吧。c++写的olap数仓做compiler auto-vectorization不就是code-gen+vectorization么?
2022-07-25 10:21
回复
用户头像
作者留言:2022年1月1日,祝大家新年快乐。不知不觉,数据库内核杂谈又陪伴大家一年(虽然。。还是不可避免地拖更了)。今年的new year resolution,希望创建一个群,和大家一起交流。加我微信 81211430(请备注数据库内核杂谈,谢谢),我会建群。期待和大家交流。
2022-01-01 12:31
回复
用户头像
目前 SparkSQL 貌似就在同时做 codegen 以及向量化,老师有了解过怎么结合起来的吗?
2021-09-02 08:35
回复
用户头像
OTAP场景下向量模型能起到优化作用吗
2021-04-08 00:28
回复
当然,看看cockroach跟tidb做的vectorization的工作即可
2022-07-25 10:11
回复
没有更多了
发现更多内容

Binary Ninja for Mac(功能强大且操作简便的逆向编译工具)v3.5.4526 激活版

影影绰绰一往直前

文心一言 VS 讯飞星火 VS chatgpt (165)-- 算法导论13.1 5题

福大大架构师每日一题

福大大架构师每日一题

AI数字人的制作需要哪些软件?

青否数字人

数字人

软通咨询彭智勇(下):融合“咨询+实施”能力,重塑供应链金融

软通咨询

数据智能 供应链金融 数字化咨询

登上CCTV-1!用友行业化解决方案获最具商业价值奖!

用友BIP

测试开发 | 人工智能无监督学习(Unsupervised Learning)

测吧(北京)科技有限公司

测试

测试开发 | 人工智能强化学习(Reinforcement Learning)

测吧(北京)科技有限公司

测试

软件测试/测试开发丨Web端测试基础知识 学习笔记

测试人

软件测试 测试开发

云服务器比传统服务器更安全的原因与实现机制

天翼云开发者社区

云计算 服务器

好消息!华为云时习知荣获IXDC AWARD国际体验奖

华为云PaaS服务小智

云计算 华为云

使用 GPT4V+AI Agent 做自动 UI 测试的探索 | 京东云技术团队

京东科技开发者

Web 自动化测试 UI测试 GPT

数智驱动,优化资产配置,助力经营效益最大化

用友BIP

资产管理

如何通过云函数操作云数据库?

天翼云开发者社区

数据库 云计算

收不到异步通知的原因

盐焗代码虾

支付宝 异步通知 排查思路

大模型应用由你创造!WAVE SUMMIT+ Workshop等你来参加

飞桨PaddlePaddle

人工智能 深度学习 开发者 WAVE SUMMIT

Tipard DVD Cloner for mac(DVD克隆软件) v6.2.50激活版

影影绰绰一往直前

System Dashboard Pro for Mac(专业系统监视器)v1.10.4激活版

影影绰绰一往直前

三一集团产品负责人谢庚曦:AI重塑HR数智化的实现路径

用友BIP

智能招聘

测试开发 | 拓展学习范式:人工智能半监督学习的探索与应用

测吧(北京)科技有限公司

测试

详解MRS HBase全局二级索引

华为云开发者联盟

大数据 后端 华为云 华为云开发者联盟

System Dashboard for Mac v4.9.1激活版:提升生产力与系统性能的神器

影影绰绰一往直前

Apeaksoft Video Editor for Mac(多功能视频编辑器)v1.0.52免激活版

影影绰绰一往直前

火热报名中·2024北京国际人工智能展览会(世亚智博会)

AIOTE智博会

智博会 人工智能展览会 人工智能展会 人工智能展 世亚智博会

云行| 国云入江南 数智耀太湖,天翼云谱写江苏数智发展新篇!

天翼云开发者社区

云计算 数字化

数字先锋| 审理办案“云上见”,便民利企更高效!

天翼云开发者社区

云计算 数字化

软件测试/测试开发丨黑盒测试方法-边界值 学习笔记

测试人

Photomator for mac(强大的修图工具)v3.2.2激活版

影影绰绰一往直前

AnyMP4 Mac Blu-ray Player Mac(高品质蓝光播放器)v6.3.68激活版

影影绰绰一往直前

测试开发 | 深度学习:人工智能的前沿驱动力

测吧(北京)科技有限公司

测试

LED电子显示屏技术参数的选购指南

Dylan

LED显示屏 全彩LED显示屏 户外LED显示屏 led显示屏厂家

浅谈AIGC对我们的深远影响及细节影响|社区征文

䑣舟

AI AIGC

数据库内核杂谈(十五): 执行器之code generation vs vectorized execution_数据库_顾仲贤_InfoQ精选文章