向量化
数据库性能优化的本质在于：一个基于 CPU 的程序如何进行性能优化。最直接的体现即基于 CPU 的向量化。
如何衡量 CPU 性能
公式总结：CPU Time = Instruction Number * CPI * Clock Cycle Time
Instruction Number 表示指令数。当你写一个 CPU 程序，最终执行时都会变成 CPU 指令，指令条数一般取决于程序复杂度。
CPI 是 （Cycle Per Instruction）的缩写，指执行一个指令需要的周期。
Clock Cycle Time 指一个 CPU 周期需要的时间，是和 CPU 硬件特性强关联的。
哪些因素会影响 CPU 性能
我们知道 CPU 的指令执行分为如下 5 步：
1. 取指令
2. 指令译码
3. 执行指令
4. 内存访问
5. 结果写回寄存器
其中 CPU 的 Frontend 负责前两部分，Backend 负责后面三部分。
影响一个 CPU 程序的性能瓶颈主要有4大点：Retiring、Bad Speculation、Frontend Bound 和 Backend Bound，4个瓶颈点导致的主要原因（不完全准确）依次是：缺乏 SIMD 指令优化，分支预测错误，指令 Cache Miss， 数据 Cache Miss。
3.SMID
SIMD 是 Single Instruction Multiple Data 的缩写，指单个指令可以操作多个数据流，与之相对的是传统的 SISD，单指令单数据流。
在操作SIMD指令时，一次性把多条数据从内存加载到宽寄存器中，通过一条并行指令同时完成多条数据的计算。例如一个操作32字节(256位)的指令，可以同时操作8个int类型，获得8倍的加速。同时利用SIMD减少循环次数，大大减少了循环跳转指令，也能获得加速。SIMD指令可以有0个参数、1个数组参数、2个数组参数。如果有一个数组参数，指令计算完数组中的每个元素后，分别把结果写入对应位置；如果是有两个参数，则两个参数对应的位置分别完成指定操作，写入到对应位置。
如上图所示：SIMD指令同时操作A和B中4对数字，产生4个结果存放到C中
4.如何生成SIMD指令呢？
第一种是编译器自动向量化，代码不需要做特殊处理和改动，编译自动将默认的标量代码转换成向量化代码。但编译器默认只能处理比较简单的程序，具体支持的 Case 大家可以在网上搜索，资料很多；
第二种是我们给编译器一些 Hint，给编译器更多的信息和上下文，编译器也可以生成 SIMD 指令；
第三种是使用像 OpenMP 或者 Intel Cilk 这种并行编程 API，开发者可以加一些 Pragma 来生成 SIMD 指令；
第四种是使用一些 SIMD Intrinsics 的包装类；
第五种是直接使用 SIMD Intrinsics 编程；
最后一种是直接写汇编代码。
5.向量化的代码要求
循环次数可计算
简单计算，不包含函数调用、switch/if/return 等
在循环在内层
访问连续的内存空间（才可以通过simd指令从内存加载数据到寄存器）
数据无依赖
使用数组而不是指针
6.如何验证程序生成了向量化代码？
我们可以通过两种方式来检查：
第一种是给编译器加一些编译选项，编译器会输出某些代码是否触发向量化，以及没有向量化的原因。比如 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 开头，一般就说明代码触发了向量化。
7.数据库向量化的挑战
数据库向量化的挑战主要有以下几点：
1. 全面的列式布局：在磁盘，内存，网络中全部都是列式布局，这意味存储引擎和计算引擎的完全重构
2. 所有算子、表达式和函数支持向量化：这意味数人年的工作
3. 算子和表达式计算尽可能使用 SIMD 指令：这意味着大量 Case By Case 的细致优化
4. 重新设计内存管理：因为处理的数据从一行变成了数千行
5. 重新设计数据结构：比如 Join、Aggregate、Sort 等核心算子的数据结构都需要进行改变
6. 整体性能提升 5 倍以上：所有的算子和表达式性能都要提升 5 倍以上，意味着全面地、系统地性能优化，所有重要的算子和表达式性能都不能有短板
8.算子和表达式向量化的关键点
算子和表达式的向量化的关键点就一句话：Batch Compute By Column。
对应 Intel 的 Top-down 分析方法，Batch 优化了 分支预测错误和指令 Cache Miss，By Column 优化了 数据 Cache Miss，并更容易触发 SIMD 指令优化。
Batch 这一点其实比较好做到，难点是对一些重要算子，比如 Join、Aggregate、Sort、Shuffle 等，如何做到按列处理，更难的是在按列处理的同时，如何尽可能触发 SIMD 指令的优化。
9.数据库向量化如何进行性能优化
1. 高性能第三方库：在一些局部或者细节的地方，已经存在大量性能出色的开源库，这时候，我们可能没必要从头实现一些算法或者数据结构，使用高性能第三方库可以加速我们整个项目的进度。在 StarRcoks 中，我们使用了 Parallel Hashmap、Fmt、SIMD Json 和 Hyper Scan 等优秀的第三方库。
2. 数据结构和算法：高效的数据结构和算法可以直接在数量级上减少 CPU 指令数。在 StarRocks 2.0 中，我们引入了低基数全局字典，可以通过全局字典将字符串的相关操作转变成整形的相关操作。如下图所示，StarRcoks 将之前基于两个字符串的 Group By 变成了基于一个整形的 Group By，这样 Scan、Hash 计算、Equal、Memcpy 等操作都会有数倍的性能提升，整个查询最终会有 3 倍的性能提升。
3. 自适应优化：很多时候，如果我们拥有更多的上下文或者更多的信息，我们就可以做出更多针对性的优化，但是这些上下文或者信息有时只能在查询执行时才可以获取，所以我们必须在查询执行时根据上下文信息动态调整执行策略，这就是所谓的自适应优化。下图展示了一个根据选择率动态选择 Join Runtime Filter 的例子，有 3 个关键点：
a. 如果一个 Filter 几乎不能过滤数据，我们就不选择；
b. 如果一个 Filter 几乎可以把数据过滤完，我们就只保留一个 Filter;
c. 最多只保留 3 个有用的 Filter
4. SIMD 优化：如下图所示，StarRcoks 在算子和表达式中大量使用了 SIMD 指令提升性能。
5. C++ Low Level 优化：即使是相同的数据结构、相同的算法，C++ 的不同实现，性能也可能相差好几倍，比如 Move 变成了 Copy，Vector 是否 Reserve，是否 Inline， 循环相关的各种优化，编译时计算等等。
6. 内存管理优化：当 Batch Size 越大、并发越高，内存申请和释放越频繁，内存管理对性能的影响越大。我们实现了一个 Column Pool，用来复用 Column 的内存，显著优化了整体的查询性能。下图是一个 HLL 聚合函数内存优化的代码示意，通过将 HLL 的内存分配变成按 Block 分配，并实现复用，将 HLL 的聚合性能直接提升了 5 倍。
7. CPU Cache 优化：做性能优化的同学都应该对下图的数据了熟于心，清楚 CPU Cache Miss 对性能的影响是十分巨大的，尤其是我们启用了 SIMD 优化之后，程序的瓶颈就从 CPU Bound 变成了 Memory Bound。同时我们也应该清楚，随便程序的不断优化，程序的性能瓶颈会不断转移。
8.下面的代码展示了我们利用 Prefetch 优化 Cache Miss 的示例，我们需要知道，Prefetch 应该是最后一项优化 CPU Cache 的尝试手段，因为 Prefetch 的时机和距离比较难把握，需要充分测试。
pipeline
Pipeline 调度与 MPP 调度之间存在着明显的差异，前者是单机多核调度，后者是分布式集群的多机调度。总结下来，Pipeline 调度的目的包括三点：
1. 降低计算节点的任务调度代价；
2. 提升 CPU 利用率；
3. 充分利用多核计算能力，提升查询性能、自动设置并行度、消除人为设置并行度的不准确性。
Pipeline 是一组算子构成的链，开始算子为 SourceOperator，末尾算子为 SinkOperator。Pipeline 中间的算子只有一个输入端和输出端。
SourceOperator 获取数据的途经有：
1. 读本地文件或者外部数据源，比如 ScanOperator；
2. 获得上游 Fragment Instance 的输出数据，比如 ExchangeSourceOperator；
3. 获得上游 Pipeline 的 SinkOperator 的计算结果，比如 LocalExchangeSourceOperator。
SinkOperator 作为 Pipeline 的末尾算子，吸收 Pipeline 的计算结果， 并输出数据，输出途经有：
1. 把计算结果输出到磁盘或者外部数据源，"比如OlapTableSinkOperator, ResultSinkOperator"；
2. 把结果发给下游 Fragment Instance，比如 ExchangeSinkOperator；
3. 把结果发给下游 Pipeline 的 SourceOperator，比如 LocalExchangeSinkOperator；
Pipeline 实例 (PipelineDriver)
PipelineDriver 是 Pipeline 实例，一条 Pipeline 可以产生多个 PipelineDriver。在代码实现中，Pipeline 由一组 OperatorFactory 构成， Pipeline 可以调用 OperatorFactory 的 create 方法，生成一组 Operator，这组 Operator 即构成 PipelineDriver。
PipelineDriver 也是 Pipeline 执行引擎的基本调度单位，其本质上是一个协程，具有三种状态：Ready、Running 和 Blocked。
Running：PipelineDriver 在当前执行线程中执行，执行线程反复调用相邻算子的 pull_chunk/push_chunk 函数移动 chunk。
Blocked：PipelineDriver 处于阻塞状态，等待就绪事件，此时 PipelineDriver 不占用执行线程，被放置在阻塞队列中，由专门的 Poller 线程持续检查 PipelineDriver 的状态，当 PipelineDriver 等待的事件就绪后，状态设置为 Ready，放回就绪队列。
Ready：PipelineDriver 执行时间超过时间片，会被放回就绪队列；阻塞解除的 PipelineDriver 也会放回就绪队列。执行线程从就绪队列中获得 PipelineDriver 并执行。执行线程的数量为计算节点 BE 的物理核数，而同时 BE 需要调度的 PipelineDriver 可能成千上万，因此执行线程是全局资源，跨所有查询，被所有的 PipelineDriver 所复用(multiplexing)。
Pipeline 引擎中协程调度模型和传统的线程调度模型的主要区别是，前者实现了用户态的 yield 语义，而后者依赖 OS 的线程调度，在高并发场景下的频繁的上下文切换增加了调度成本，降低了 CPU 的有效利用率。如下图所示:
pipeline阻塞操作异步化
实现 Pipeline 执行引擎的协程调度，最为关键处理是阻塞操作异步化，如果没有实现异步化，PipelineDriver 的阻塞操作会导致执行线程陷入内核挂起，退化为 OS 线程调度。为了避免执行线程的上下文切换，需要控制执行线程的数量不超过物理核数，并且执行线程为跨查询的全局资源，这种阻塞挂起会显著影响 CPU 利用率和其他 PipelineDriver 的调度。因此，涉及阻塞的操作，需要异步化处理，例如：
1. ScanOperator 读 Tablet 数据，访问磁盘。
2. ExchangeSinkOperator 发送数据，ExchangeSourceOperator 接收数据。
3. HashJoinProbeOperator 所在 PipelineDriver 等待 HashJoinBuildOperator 完成 HashTable 的构建和 RuntimeFilter 的生成。
4. 需要全量物化的物理算子拆分成一对 SinkOperator 和 SourceOperator，其中 SinkOperator 位于上游的 Pipeline，而 SourceOperator 位于下游的 Pipeline，SourceOperator 需要等待 SinkOperator 算子完成。比如物理算子 AggregateBlockingNode 转换为 Pipeline 引擎的 AggregateBlockingSinkOperator 和 AggregateBlockingSourceOperator，后者需要等待前者完成。
BE 负责 Pipeline 调度
BE 执行 PipelineDriver 使用两种类型的线程和两种队列，分别为 Pipeline 执行引擎的工作线程 PipelineDriverExecutor、阻塞态 PipelineDriver 的轮询线程 PipelineDriverPoller。队列分别为就绪 Driver 队列(Ready Driver queue)和阻塞 Driver 队列(Blocked Driver queue)
执行线程 PipelineDriverExecutor：不断地从就绪 Driver 队列中获得就绪态的 PipelineDriver 并执行，把主动让出 CPU 的PipelineDriver 再次放回就绪 Driver 队列，把处于阻塞态 PipelineDriver 放入阻塞 Driver 队列。
轮询线程 PipelineDriverPoller：不断地遍历阻塞 Driver 队列，跳过仍然处于阻塞态的 PipelineDriver，将解除阻塞态的 PipelineDriver，设置为 Ready 状态，放回就绪 Driver 队列。
