数据库执行引擎性能黑科技

原创闫宗帅 2025-01-01

394

数据库执行引擎性能黑科技

现在业界OLAP数据库中，包括商业数据库和开源数据库，都在执行引擎这块做了很多黑科技，使得执行性能大大提高。比如向量化执行引擎、push-based pipeline执行引擎、JIT和向量化结合等等，本文我们不关注整体的实现以及NVM、GPU、FPGA等新硬件方面的提速，而关注具体性能黑科技的细节。

1、clickhouse中向量化执行引擎中使用的手段

1）大量使用instrinsic函数对关键路径代码进行优化，实际上就是调用SIMD封装的inline函数。参见https://github.com/ClickHouse/ClickHouse/issues/37005

2）统计过滤后有多少个值满足条件？通过popcount函数计算

使用一个字节表示该行是否被选中，通过toBits64函数将64字节压缩成64位：

https://github.com/guevara/read-it-later/issues/9793
3）使用了大量模板，对类型和长度进行分派，可以消除分支跳转语句；并大量使用内联函数消除函数调用
4）使用__restrict关键字，向编译器表明，在该指针的生命周期内，只有该指针本身或者直接由它产生的指针才能够访问该指针指向的对象。限制指针别名，从而帮助编译器进行优化。在ClickHouse中，有很多地方都使用到了该关键字，在 PR9304 中，通过该关键字，使查询的整体性能提升从 5% 到 200% 不等
https://github.com/ClickHouse/ClickHouse/pull/9304
2、oceanbase中向量化执行引擎中使用的手段
1）oceanbase向量化引擎2.0，维护了执行过程中batch数据的特征信息，包括是否不存在NULL，是否batch行均不需要被过滤等信息，利用这些信息可以大大加速表达式计算。比如NULL如果不存在则表达式计算过程中不需要考虑对NULL的特殊处理，如果数据行都没有被过滤，则不需要计算时每行去判断是否被过滤，并且数据时连续的，没有被过滤对使用SIMD计算也更友好
2）oceanbase的算法与数据结构优化：Sort 算子实现了 sort key 与非 sort key 分离物化，结合对 sort key 保序编码(将多列数据编码为 1 列，可直接使用 memcpy 进行比较)，Sort 在比较过程中访问数据 Cache Miss 更低，比较计算本身更快，整体排序效率更高；HashGroupBy 对 Hash 表结构均进行了优化，HashBucket 中数据存放更加紧凑，并对低基数 Group Key 使用 ARRAY 优化，分组及聚合结果内存连续存放等优化等
3）oceanbase的特化实现优化：特化实现优化，主要是利用模版，针对不同场景进行更加高效的实现，比如 Hash Join 特化实现了将多列定长 join key 编码为一个定长列，并且将 join key 数据放入到 bucket 中，对数据预期也进行了优化，减少了多列数据访问时数据 Cache Miss；支持聚合计算特化实现，不同的聚合计算进行特化分开实现，从而减少每次计算聚合函数指令及分支判断，执行效率大幅提升
4）存储层全面支持新的向量化格式，对于投影、谓词下压、聚合下压和 groupby 下压更多地使用 SIMD。投影定长和变长数据时，按列类型、列长度，以及是否包含 null 等信息定制化模板，按批浅拷投影。计算下压谓词时，对于简单的谓词计算，直接在列编码上进行；复杂的谓词，投影成新向量化格式在表达式上按批计算。聚合下压充分利用了中间层的预聚合信息，如 count、sum、max、min 等。groupby 下压则利用充分利用编码数据信息，对于字典类型的编码，加速效果非常明显
5）最大限度按照branchless编码、内存预取、SIMD指令直到原则进行工程化编码：Hash Join通过hash表的构建和探测，实现两个表（R和S表）的hash查找。当hash表的大小超过CPU的level2的cache时，hash表随机访问会引擎memory stall，影响执行效率。Cache的优化是Hash Join的一个重要方向，重点考虑了cache miss对性能的影响，通过向量计算hash value和内存预取的方式避免cache miss和memory stall。先通过partition分区构建hash表，探测hash表阶段，通过批量计算方式得到向量数据的hash，通过预取把该批数据对应的hash bucket数据装载到CPU cache中，最后按照join链接条件比较结果。通过控制向量的大小，保证预取的一批数据可以装载到CPU 的level2 cache中，从而最大程度避免比较时的cache miss和memory stalling。
6）sort merge group by聚合操作，要求数据有序，group by通过比较数据是否相同找到分组边界，然后计算相同分组内的数据。向量化引擎中，将比较和聚合计算分开，先比较，找到分组所有数据个数，由于分组内数据相同，针对sum/count等聚合计算可以做进一步优化，sum可以通过1*8，把8次累加变成1次成分，count则可以直接加8即可。这里需要注意是怎么计算得到组内元组个数的。另外，引入二分等方法，如果向量大小是16，则第一次推进的step是8，比较c1列的第0行和第7行的数据，数据相对，则直接对c1列的前8个数据求和。第二次推进的step位8，比较第7行和第15行的数据，数据不相等，则回退4行再比较数据是否相同，直到找到分组边界。通过二分比较，可以在重复数据较多的场景下跳过重复数据的比较。重复数据较少场景下存在bad case，可以通过数据NDV等统计信息在执行期决定是否开启二分比较。
3、doris/starrocks向量化执行中的优化
1）分配内存时一下子申请一个batch的内存进行整块内存分配，而不是每行去申请，减少碎片化的内存分配。尤其是hash join/hash agg和sort agg时。
2）自动向量化的几条建议：
（1）足够简单的for循环，循环体应该尽量简单，以便编译器能够更容易识别和优化
（2）避免在for循环中进行函数调用和分支跳转：例如避免在循环中使用if判断、break语句等，这些操作会增加编译器自动向量化的难度
（3）避免数据依赖，如果下一个计算结果依赖于上一个循环的结果，编译器将无法进行自动向量化
（4）连续的内存和对齐的内存，SIMD指令对内存的要求较高，能够一次性加载多个数据。如果数据存储在不连续的内存中，SIMD将无法进行连续加载。此外，内存对齐也会影响向量化指令的执行效率
3）如何识别代码编译器的自动向量化生效?
（1）编译器的Hint提示，-fopt-info-vec-all:打印所有编译器进行向量化的信息，如果循环代码被向量化了，会打印如下信息：main.pp:5:note:LOOP VETORIZED。-fopt-info-vec-missed：没有被向量化的原因，-fdump-tree-vect-all:进一步分析没有被向量化的原因
（2）通过perf/objdump查看生成的汇编代码，向量化指令通常以字母“v”开头，如“vmovaps”、“vaddps”等，通过查看这些指令，可以确认是否进行了向量化。另外还可以查看使用了那些寄存器，x86架构中，128位寄存器是XMM，256位寄存器是YMM，512位寄存器是ZMM。
4）SIMD的双调排序
5）join计算的排序
6）runtime filter
7）字符串的子串搜索加速
8）operation on encoded data技术
9）Bitmap精确去重
4、向量化引擎中的“小文件合并”
问题：向量化执行为什么会产生小Data Chunk呢？执行计划里面有些算子比如 Join/Filter会产生小的 Data Chunk。Filter产生小 Data Chunk很容易理解，因为它会把输入的Data Chunk里面一些不符合 Filter 条件的数据过滤掉，从而产生小的 Data Chunk。有人可能会说不一定啊，Filter 确实会过滤掉一些数据，但是我可以把符合条件的数据先缓存起来等他们足够多了之后构造一个新的 Data Chunk，那么这个 Data Chunk 不就足够大了吗？你说的没错，这样确实就避免了小文件问题了，但是这是有代价的，因为这里的“缓存”、“构造新的 Data Chunk”操作都涉及到对输入Data Chunk的复制。大多执行引擎是不会这么做的，它们会利用一个叫做 Selection Vector 的结构来实现“延迟物化”。
延迟物化的好处是只要Data Chunk里面有效的数据不是太少，下游的算子依然可以充分享受向量化架构的好处，同时又没有发生数据的复制，性能是非常好的。但也不能无脑的延迟物化，否则后续针对无效数据计算的代价就比较大了。
这篇论文的优化：注意这里是在向量化中的优化，左表的一个batch依次针对内表的hash表一级进行探测，第二轮探测第二级，依次后推

Join算子的探测端（外表的一个batch即DataChunk）会根内表多个Data Chunk进行组合产生小data Chunk，这些小data chunk可能共享同一个探测端的data chunk。比如探测端的一个Lbatch和内部两个Rbatch1（上图hash表的第一列）和Rbatch2（hash表的第2列）进行join，join的结果都比较小，那么可以将聚合join条件的两个结果的select vector合并，使用一个select vector来表示，Rbatch1和Rbatch2的符合join条件的值重新拷贝到一个batch中，并使用另外一个select vector进行表示：Selection Vector 记录的是 Data Chunk 里面有效数据条目的下标

效果也不错，这种方式已经在duckdb中实现了，需要进一步看下duckdb中使用场景，在什么场景下适合使用这种方式。

Data Chunk Compaction in Vectorized Execution：SIGMOD 2025

https://github.com/duckdb/duckdb/pull/14956

5、stonedb向量化引擎中的优化

1）在 64 位操作系统中，CPU 从缓存中读取数据时按照 8 Bytes 对齐访问。如下图所示桔黄色为有效数据，数据被存放在 0x000000 ~ 0x00000F 一段连续内存中，偏移量为 0x000004，长度为 8 。CPU 会发出两个加载指令读取 0x00000 ~ 0x000007 和 0x000008 ~ 0x00000F 两个内存单元。然后通过位移操作后将两部分数据合并。如下图所示

所以读取未对齐的数据会有额外的读取成本和寄存器操作成本，在高性能计算时尽量将数据对齐至 8 Bytes 读取，这样才能获得最好的性能。

2）循环展开

现代的编译器也会自动的做循环展开优化，值得注意的是循环展开将增加代码体积，特别对于循环体较大的代码，循环展开反而会降低性能。

3）内联优化

在介绍内联前，我们先要了解代码空洞的概念。如下图一段程序编译后，二进制可执行文件中依次包含 func funcA funcB 函数。在执行 func 函数时调用了 funcB 函数，此时需要 CPU 跳过一段内存空间加载并执行 funcB 函数。在本次执行过程中，我们称跳过的部分为代码空洞。在执行过程中代码空洞越小，代码指令加载效率越高。

内联是指在编译器将函数内容展开到调用方的函数体中，这是一种解决代码空洞的方法。某个方法是否内联需要充分考虑，比如某个函数在低频的分支中调用，内联反而会加剧高频分支路径的空洞。内联还会造成代码膨胀，不推荐过长的函数内联到其它函数中

6、TDSQL向量化引擎中的优化

做了一个提前物化和延迟物化的物化策略，如下图

提前物化，很好理解，上图的(b)：join结果的投影列包括表C的C1、C2和表D的D1、D2，join字段为C1=D1，扫描时将C和D表的所有列都进行扫描出来，然后进行join并输出join结果。

延迟物化，上图的(a)，扫描时仅扫描C表的C1，然后和D表扫描出的数据进行join，根据join结果的selects数组，然后去扫描C表的C2列并进行过滤。将select下推到列存表C，根据列存的min/max/布隆等信息可以降低IO，从而减少需要物化的tuple数量；当然如果C是数据shuffle而来，那么通过这个select也可以减少网络压力。