作者：康凯森，StarRocks PMC，负责查问方向的研发
本文是对我在 StarRocks 线下 MeetUp 演讲的整顿，次要分为三局部：第一局部简要介绍向量化的基础知识，第二局部解说数据库如何进行向量化，最初是 StarRocks 向量化实际后的一些浅显思考。
#01
向量化为什么能够晋升数据库性能？
—
本文所探讨的数据库都是基于 CPU 架构的，数据库向量化个别指的都是基于 CPU 的向量化，因而数据库性能优化的实质在于：一个基于 CPU 的程序如何进行性能优化。这引出了两个关键问题：
- 如何掂量 CPU 性能
- 哪些因素会影响 CPU 性能
第一个问题的答案能够用以下公式总结：CPU Time = Instruction Number CPI Clock Cycle Time
- Instruction Number 示意指令数。当你写一个 CPU 程序，最终执行时都会变成 CPU 指令，指令条数个别取决于程序复杂度。
- CPI 是（Cycle Per Instruction）的缩写，指执行一个指令须要的周期。
- Clock Cycle Time 指一个 CPU 周期须要的工夫，是和 CPU 硬件个性强关联的。
咱们在软件层面能够扭转的是前两项：Instruction Number 和 CPI。那么问题来了，具体到一个 CPU 程序，到底哪些因素会影响 Instruction Number 和 CPI 呢？
咱们晓得 CPU 的指令执行分为如下 5 步：
- 取指令
- 指令译码
- 执行指令
- 内存拜访
- 后果写回寄存器
其中 CPU 的 Frontend 负责前两局部，Backend 负责前面三局部。基于此，Intel 提出了《Top-down Microarchitecture Analysis Method》的 CPU 微架构性能分析方法，如下图所示：
Top-down Microarchitecture Analysis Method 的具体内容大家能够参考相干的论文，本文不做开展，为了便于大家了解，咱们能够将上图简化为下图（不齐全精确）：
即影响一个 CPU 程序的性能瓶颈次要有 4 大点：Retiring、Bad Speculation、Frontend Bound 和 Backend Bound，4 个瓶颈点导致的次要起因（不齐全精确）顺次是：不足 SIMD 指令优化，分支预测谬误，指令 Cache Miss，数据 Cache Miss。
再对应到之前的 CPU 工夫计算公式，咱们就能够得出如下论断：
而数据库向量化对以上 4 点都会有晋升，后文会有具体解释，至此，本文从原理上解释了为什么向量化能够晋升数据库性能。
#02
向量化基础知识
—
在理解数据库如何向量化之前，咱们先了解一些向量化的基础知识。
留神，在第二个章节外面，向量化一词能够了解为和 SIMD 等价，仅指广义上的 CPU SIMD 向量化，与数据库畛域狭义的向量化含意不同。
1、SIMD 简介
SIMD 是 Single Instruction Multiple Data 的缩写，指单个指令能够操作多个数据流，与之绝对的是传统的 SISD，单指令单数据流。
如上图所示，对于最简略的 A + B = C，如果咱们要计算 4 组加法，传统的 SISD 须要执行 8 次 Load 指令 (A 和 B 别离 4 次)、4 次 Add 指令、4 次 Store 指令。但当咱们应用 128 位宽的 SIMD，咱们只须要 2 次 Load 指令、1 次 Add 指令、1 次 Store 指令，这样实践上就能够取得 4 倍的性能晋升。而目前的向量化寄存器位宽曾经倒退到 512 位，实践上 Int 的加法操作就能够减速 16 倍。
2、如何触发向量化？
如前文所述，SIMD 指令会带来微小的性能晋升，数据库开发人员天然须要了解并把握如何进行 SIMD 编程。
如上图所示，SIMD 触发向量化个别有 6 种形式，这 6 种形式自顶向下，对工程师的要求越来越高，须要手动编写的货色越来越多。
- 第一种是编译器主动向量化，代码不须要做非凡解决和改变，编译主动将默认的标量代码转换成向量化代码。但编译器默认只能解决比较简单的程序，具体反对的 Case 大家能够在网上搜寻，材料很多；
- 第二种是咱们给编译器一些 Hint，给编译器更多的信息和上下文，编译器也能够生成 SIMD 指令；
- 第三种是应用像 OpenMP 或者 Intel Cilk 这种并行编程 API，开发者能够加一些 Pragma 来生成 SIMD 指令；
- 第四种是应用一些 SIMD Intrinsics 的包装类；
- 第五种是间接应用 SIMD Intrinsics 编程；
- 最初一种是间接写汇编代码。
在 StarRocks 我的项目中，咱们向量化的准则是尽可能触发编译器的主动向量化，也就是第一种和第二种，对于不能主动向量化然而性能又很要害的操作，咱们会通过 SIMD Intrinsics 的形式手动向量化。
对于如何触发编译器的自动化，如何给编译器加 Hint 触发向量化以及如何通过 SIMD Intrinsics 的形式手动向量化大家能够参考我集体博客《数据库学习材料》向量化局部的材料，本文不再赘述。
《数据库学习材料》：https://blog.bcmeng.com/post/…
3、如何验证程序生成了向量化代码？
当一个我的项目代码比较复杂时，如何确保代码触发向量化是很常见的问题。咱们能够通过两种形式来查看：
第一种是给编译器加一些编译选项，编译器会输入某些代码是否触发向量化，以及没有向量化的起因。比方 GCC 编译器，咱们能够退出 -fopt-info-vec-all 或者 -fopt-info-vec-optimized，-fopt-info-vec-missed，-fopt-info-vec-note 编译选项。成果如下图所示：
第二种办法，咱们能够间接查看最终执行的汇编代码，比方应用 https://gcc.godbolt.org/ 等网站或者 Perf、Vtune 等工具，如果汇编代码外面的寄存器是 xmm,ymm,zmm 或者指令以 v 结尾，个别就阐明代码触发了向量化。
#03
数据库向量化
—
1、数据库向量化的外围
StarRocks 的向量化引擎从写下第一行代码到成为一款成熟、稳固、世界领先的查问执行器，曾经有 2 年多的工夫，以咱们的教训来看，数据库的向量化并不仅仅是触发 CPU 的 SIMD 向量化，而是一个微小的、系统化的性能优化工程。
2、数据库向量化的挑战
数据库向量化的挑战次要有以下几点：
- 全面的列式布局：在磁盘，内存，网络中全部都是列式布局，这象征存储引擎和计算引擎的齐全重构
- 所有算子、表达式和函数反对向量化：这象征数人年的工作
- 算子和表达式计算尽可能应用 SIMD 指令：这意味着大量 Case By Case 的粗疏优化
- 从新设计内存治理：因为解决的数据从一行变成了数千行
- 从新设计数据结构：比方 Join、Aggregate、Sort 等外围算子的数据结构都须要进行扭转
- 整体性能晋升 5 倍以上：所有的算子和表达式性能都要晋升 5 倍以上，意味着全面地、系统地性能优化，所有重要的算子和表达式性能都不能有短板
3、算子和表达式向量化的关键点
数据库的向量化在工程上次要体现在算子和表达式的向量化，而算子和表达式的向量化的关键点就一句话：Batch Compute By Column, 如下图所示：
对应 Intel 的 Top-down 分析方法，Batch 优化了 分支预测谬误和指令 Cache Miss，By Column 优化了 数据 Cache Miss，并更容易触发 SIMD 指令优化。
Batch 这一点其实比拟好做到，难点是对一些重要算子，比方 Join、Aggregate、Sort、Shuffle 等，如何做到按列解决，更难的是在按列解决的同时，如何尽可能触发 SIMD 指令的优化。每个算子的按列解决和 SIMD 指令优化咱们会在之后的《StarRocks 查问源码解析》系列文章中具体解释。
4、数据库向量化如何进行性能优化
后面提到，数据库向量化是一个微小的、零碎的性能优化工程，两年来，咱们实现了数百个大大小小的优化点。我将 StarRocks 向量化两年多的性能优化经验总结为 7 个方面（留神，因为向量化执行是单线程执行策略，所以上面的性能优化教训不波及并发相干）：
- 高性能第三方库：在一些部分或者细节的中央，曾经存在大量性能杰出的开源库，这时候，咱们可能没必要从头实现一些算法或者数据结构，应用高性能第三方库能够减速咱们整个我的项目的进度。在 StarRcoks 中，咱们应用了 Parallel Hashmap、Fmt、SIMD Json 和 Hyper Scan 等优良的第三方库。
- 数据结构和算法：高效的数据结构和算法能够间接在数量级上缩小 CPU 指令数。在 StarRocks 2.0 中，咱们引入了低基数全局字典，能够通过全局字典将字符串的相干操作转变成整形的相干操作。如下图所示，StarRcoks 将之前基于两个字符串的 Group By 变成了基于一个整形的 Group By，这样 Scan、Hash 计算、Equal、Memcpy 等操作都会有数倍的性能晋升，整个查问最终会有 3 倍的性能晋升。
- 自适应优化：很多时候，如果咱们领有更多的上下文或者更多的信息，咱们就能够做出更多针对性的优化，然而这些上下文或者信息有时只能在查问执行时才能够获取，所以咱们必须在查问执行时依据上下文信息动静调整执行策略，这就是所谓的自适应优化。下图展现了一个依据选择率动静抉择 Join Runtime Filter 的例子，有 3 个关键点：
a. 如果一个 Filter 简直不能过滤数据，咱们就不抉择；
b. 如果一个 Filter 简直能够把数据过滤完，咱们就只保留一个 Filter;
c. 最多只保留 3 个有用的 Filter
- SIMD 优化：如下图所示，StarRcoks 在算子和表达式中大量应用了 SIMD 指令晋升性能。
- C++ Low Level 优化：即便是雷同的数据结构、雷同的算法，C++ 的不同实现，性能也可能相差好几倍，比方 Move 变成了 Copy，Vector 是否 Reserve，是否 Inline，循环相干的各种优化，编译时计算等等。
- 内存治理优化：当 Batch Size 越大、并发越高，内存申请和开释越频繁，内存治理对性能的影响越大。咱们实现了一个 Column Pool，用来复用 Column 的内存，显著优化了整体的查问性能。下图是一个 HLL 聚合函数内存优化的代码示意，通过将 HLL 的内存调配变成按 Block 调配，并实现复用，将 HLL 的聚合性能间接晋升了 5 倍。
- CPU Cache 优化：做性能优化的同学都应该对下图的数据了熟于心，分明 CPU Cache Miss 对性能的影响是非常微小的，尤其是咱们启用了 SIMD 优化之后，程序的瓶颈就从 CPU Bound 变成了 Memory Bound。同时咱们也应该分明，轻易程序的一直优化，程序的性能瓶颈会一直转移。
上面的代码展现了咱们利用 Prefetch 优化 Cache Miss 的示例，咱们须要晓得，Prefetch 应该是最初一项优化 CPU Cache 的尝试伎俩，因为 Prefetch 的机会和间隔比拟难把握，须要充沛测试。
#04
StarRocks 向量化工程的浅显思考
—
其一，很多事物的底层原理是类似的： 当我深刻理解到 CPU 的微架构后，发现 CPU 的微架构和数据库的整体架构也很相似，比方 CPU 和 StarRocks 都分 Frontend 和 Backend，CPU 的 Frontend 负责指令的取码和编解码，Backend 负责指令的执行和数据的交互，StarRocks 的 Frontend 负责 SQL 的 Parse 和 Plan，Backend 负责 SQL 的执行和存储的交互。当你理解的零碎、架构越多，你的这种感触会越粗浅。
其二，打造一个高性能的数据库，须要的不仅是优良正当的架构，还须要极致优良的工程细节。 这一点看似非常显然，其实并不是，如果你认可这一点，当你想打造一个极致性能的数据库时，你就不会像 ClickHouse 一样 Bottom-Up 地从细节和算法层面登程去设计整个零碎，也不会抉择 Java 或者 Go 等语言去实现查问执行层和存储层。
其三，向量化和查问编译的交融。 咱们晓得，向量化和查问编译是查问执行的两大类形式，是正交的，并不抵触，只是目前业界大多数开源的数据库抉择了向量化的做法，其实咱们齐全能够通过查问编译的形式，联合上下文信息，生成更弱小的向量化代码。而且，近几年查问编译的自身诸多毛病业界也始终在改良。
其四，尝试 GPU、FPGA 等新硬件。 咱们晓得，如果一件事件，做到 80 分，须要一个月的工夫，那么从 80 分做到 90 分，可能就须要 1 年的工夫，从 90 分做到 99 分，可能就须要 2 年的工夫。尽管目前基于 CPU 架构下的性能还没到极限，然而获得大的冲破可能须要比拟大的精力，咱们或者能够思考在新的硬件开拓新的赛道和战场。
其五，挑战不可能。 守业两年来，咱们团队从零实现了向量化引擎、CBO 优化器、Pipeline 并行引擎……看着一个又一个冲破和问题，我最大的一个感触就是咱们应该永远深信本人，挑战不可能。最初我向大家举荐一本书 《像火箭科学家一样思考: 将不可能变为可能》，这本书比拟完满地诠释了 StarRocks 团队的价值观：在 Think Big、敢想敢干的同时，如何攻坚克难、疾速迭代，将一个又一个巨大的想法落地。
本期 StarRocks 技术底细到这就完结了，好学的你必定学会了一些新货色，或者又产生了一些新困惑，无妨扫描下方用户群二维码退出 StarRocks 社区一起交换！
对于 StarRocks
StarRocks 创建两年多来，始终专一打造世界顶级的新一代极速全场景 MPP 数据库，帮忙企业建设“极速对立”的数据分析新范式，助力企业全面数字化经营。
以后曾经帮忙腾讯、携程、顺丰、Airbnb、滴滴、京东、众安保险等超过 110 家大型用户构建了全新的数据分析能力，生产环境中稳固运行的 StarRocks 服务器数目达数千台。
2021 年 9 月，StarRocks 源代码凋谢，在 GitHub 上的星数已超过 3100 个。StarRocks 的寰球社区飞速成长，至今已有超百位贡献者，社群用户冲破 5000 人，吸引几十家国内外行业头部企业参加共建。