关于rust:Databend-的-Group-By-聚合查询为什么跑的这么快实践篇-2

在这里次要向大家做一个 Databend 性能调优相干的分享，共会分为三次向大家介绍，如下所示：

1、根底篇：代码调优的前置常识（https://mp.weixin.qq.com/s/WT…）
2、实际篇 1：Databend 源码性能调优实际（https://mp.weixin.qq.com/s/hD…）
3、实际篇 2：Databend 的 Group By 聚合查问为什么跑的这么快？

背景

SELECT max(number),
sum(number) FROM numbers_mt(1000000000) GROUP BY number % 3,
number % 4, number % 5 LIMIT 10;

在晚期 Databend 的版本中，咱们为了掂量分组聚合性能，在性能测试上疏忽了 IO 的开销，但上述 SQL 的运行即便在内存表的场景下也运行的很低效，吞吐只约有 700MB/s，比照 clickhouse 的吞吐有 4GB/s，差距有七八倍左右。因而咱们花了很多精力在调优上述查问。本文将介绍下咱们如何调优 Databend 的 Group By 聚合查问的。

优化分组操作

下图所示，晚期的分组咱们引入了一个 hashmap，在查问分组的时候，咱们将 block 依照对应的 key 打散到不同的 value entry 中，每个 value entry 对应一个小的 block，这样咱们能够对小的 block 进行向量化 sum 的计算，sum 后的后果再和其余 blocks hash 打散 sum 后的后果按 hash key 进行 merge。

这个过程非常的天然且简略，但它工作的非常低效。

1. 首先是 block 打散成子 block，这里会波及屡次内存的调配和拷贝，将内存从大的 block 拷贝到新的 block 中。并且在 key 的规模很大的时候，这个调配拷贝的次数也会增多，性能进一步的降落。
2. 其次是尽管子的 block 咱们能够复用一下向量化的代码，但通过打散后子 block 的数据长度其实放大了很多，block 的个数也减少了很多，咱们晓得 simd 是为了吞吐设计的指令集，在这个场景下，屡次 simd 对小数据集进行求和 反而减少了计算的提早。

无论从内存还是计算的角度思考，下面的流程都非常不可取。因而咱们设计下以下新的流程：

新的流程中，咱们不会再去 Split blocks，也就是说 block 还是大的 block，不会再有额定的内存调配和拷贝。但咱们还是须要一个 hashmap 来存储分组 key 对应的数据，这里 hashmap 存储的 value 不再是一个 block 粒度，而是一个 AggregateState，代表聚合函数状态的值。

因而咱们的计算流程变为：

1. 遍历 block 的 key columns，为 block 为每行数据调配一个 hashkey
2. 第二次遍历 block，依据对应行的 key 去 hashmap 中找出对应的聚合状态值，如果没有，则调配默认的聚合状态；反之，咱们拿出曾经有的聚合状态，而后进行状态合并。
3. 将 block 级别的聚合状态进行二次合并。

这个流程中，尽管无奈沿用手动的向量化代码，但 hashmap 的压力大大的缩小了，咱们只有存储对应的状态值进行合并，整体测试下来，性能比上个版本进步了 3-4 倍，是一个十分有象征意义的优化点。

这里插入一个 Spark 新的执行引擎 Photon 在 group by 的一个优化点：

假如没有 hash 抵触的状况下，这里依据 key 从 hashmap probe 到的 value 进行了 merge 操作，这里尽管只有一个循环，但性能体现却不如人意，通过测试发现，66% 的开销在于 memory stalls, 也就是说 CPU 的计算在期待内存拜访的提早。

优化的形式是将 loop 拆成多个小的 loop，让 CPU 和内存拜访尽量解耦，来进步 CPU 流水线执行。

动静哈希算法

为了进一步优化分组聚合的性能，咱们察看到了，其实不同的 SQL GroupBy 的 keys 咱们能够用不同的 hash 算法来实现 hashkey 的生成。

在定长的场景下，能够用 u8–>u64 等不同的整形来存储 hashkey，整形 key 的寻址在 hashmap 上也有对应的优化点；在含有 String 的场景下，咱们再进化成字节数组的形式存储 hashkey。这样让 hashmap 针对不同的场景能针对性做内存的优化，让 SQL 运行更加高效。

内存池

hashmap 的 value 存储的是聚合 State，为了让 State 的拜访尽量触发 cpu cache，咱们将 State 调配在一个独立的内存池中，这里应用了 bumpalo 这个 rust crate。

状态合并

另外咱们留神到，如果有多个聚合函数，可能须要多个 hashmap 来存储对应的状态，或者 hashmap 对应的 value 须要存储一个聚合状态的数组，这样会减少 hashmap 存储的压力。

联合 SQL 分组查问的特点，即便是多个聚合函数的分组查问，聚合函数对应的 key 对 一行数据来说是惟一固定的，也就是说一个 key 能够对应 多个聚合状态。

那么，咱们能不能将多个聚合状态存在一起呢？显然是能够的：

能够把多个聚合状态当做是一个 Struct，独自的聚合状态作为 Struct 中的成员，这样咱们的 hashmap 只有存储 Struct 的地址就行了！通过 Struct 的地址后，咱们依据固定长度的 offset 偏移值能够拿到对应地位聚合状态的数据。

流水线 CPU 计算

在下面的 SQL 中，咱们发现数值运算中，除法操作或求模操作都存在性能瓶颈。

通过材料发现，除法运算符无奈施展 CPU 流水线执行，他须要 3-30 个 CPU 时钟的提早，并且除法外部也无奈乱序执行，发射工夫也和提早一样，除法的提早能达到加法的几十倍。

那咱们如何去优化 group by number % 3 .. 中的求模操作呢？

一个非凡的 case 就是 除数是一个 2^n, 求模操作能够优化为按位取与的操作，number & (2^ – 1)

在其余 case 下，参考了学术界的一些论文：

Blog: https://lemire.me/blog/2019/0…

Paper: https://arxiv.org/abs/1902.01961

能够将常量除数下的除法优化成乘法操作：

uint32_t d = ...;// your divisor > 0
uint64_t c = UINT64_C(0xFFFFFFFFFFFFFFFF) / d + 1;
// fastmod computes (n mod d) given precomputed c

uint32_t fastmod(uint32_t n) {
  uint64_t lowbits = c * n;
  return ((__uint128_t)lowbits * d) >> 64; 
}

工业界也有一些实现，比方：

Go: https://github.com/bmkessler/…

Rust: https://docs.rs/strength_redu…

Databend 中应用的是 Rsut 的 strength_reduce crate 来优化的。

总结

通过下面的若干的优化后，总体测试下来 group by 的性能曾经和 clickhouse 并驾齐驱了。下面很多细节的优化也参考了 clickhouse 中的实现，clickhouse 在很多方面的优化都做的十分的粗疏，源码十分值得一读。

当然，性能优化路线是无止境的，通常是一点点的优化能力积攒出一个好的成果，但有的时候 也要跳出一些定势思维，兴许不小心就陷入了一些死胡同。这里举荐两本书来作为本文的结尾：

1. CS:APP3e, Bryant and O’Hallaron (cmu.edu)
2. Optimizing software in C++ An optimization guide