前言

在线处理分析场景对于 YMatrix 而言具有十分重要的意义，如何在该场景上使性能有数量级的提升呢？我们通过向量化执行引擎和列存系统，实现了性能在 TPC-H 基准测试上达到 GPDB 的十倍。本文将以 Hash Join 为切入点，介绍向量化执行引擎的基本原理，并深入分析、探讨 Hash Join 的算法和工程实践。

作者：数据库内核研发工程师 申磊

TPC-H（注 1）是一套业内常用的决策支持基准测试，由 TPC 委员会制定发布，用于评测数据库的分析型查询能力。TPC-H 查询包含 8 张数据表、22 条复杂的 SQL 查询，大多数查询包含若干表 Join、子查询和 Group-by 聚合等。所选查询和数据库中的数据具有广泛的行业适用性。这个基准测试展示了决策支持系统的能力，可以检查大量数据、执行高度复杂查询、回答关键业务问题；同时反映了数据库系统处理查询的多方面能力。正因如此，我们选择 TPC-H 作为我们优化目标。

Greenplum （注 2）（以下简称 GPDB）是全球领先的开源、并行大数据平台，专为分析、机器学习和 AI 而打造。GPDB 大数据平台基于 MPP（大规模并行处理）架构，具有强大的内核技术，包括数据水平分布、并行查询执行、专业优化器、线性扩展能力、多态存储、资源管理、高可用、高速数据加载等。从商业智能（BI）、文本、GIS、图、图像、流式数据处理到各种机器学习算法都能支持。此外，GPDB 提供的查询优化器是业界第一个开源的基于代价的查询优化器，专为大数据负载而设计。它可以将交互式和批处理模式分析扩展到 PB 级的大型数据集，而不会降低查询性能和吞吐量。

YMatrix 是基于 PostgreSQL / Greenplum 经典系开源数据库开发的超融合数据库产品。当前主要针对时序场景，而大部分时序数据库的查询场景可以认为是在线分析处理（OLAP）场景，因此我们选择业界领先的分析数据平台 GPDB 作为比较对象。

在打造向量化执行引擎开始时，我们就定了第一个小目标：性能是 GPDB 十倍。原因很简单，数据库作为基础软件，替换成本比较高，包括前期评估、测试成本、数据层面迁移成本、业务层面迁移成本、对新数据库完全掌控的成本、对业务迭代影响的成本，以及相关配套工具改造成本等等。整个过程需要 DBA、基础架构团队和业务团队协作，如果只是为了得到 50% 或一倍的性能提升，并不值得大动干戈。

本文以 TPC-H 查询为主线，讨论分析 YMatrix 如何在这套基准测试上达到 GPDB 性能的 10 倍。（测试报告全文）

一 向量化执行引擎原理

首先，我们看一下 GPDB 的执行模型——火山模型——的优劣势。

1.1 火山模型

火山模型是数据库领域非常成熟的解释计算模型。该模型将关系代数中每一种操作抽象为一个 Operator，将整个查询构建成一个 Operator 树，从根节点到叶子节点自上而下地递归调用 next() 函数。

优势是实现简单，每个 Operator 单独实现即可。

缺点也很明显：

• 函数调用开销：每条 Tuple 在各个节点之间流动时会涉及大量函数调用，虽然对于单条 Tuple 而言开销并不大，但考虑到数据规模，火山模型整体函数调用开销是显著的。如果涉及虚函数、函数指针，开销会更大一些；

• 缓存不友好：火山模型每次处理一个 Tuple 的模式和过多的控制语句、函数调用等使得缓存失效的概率增加；

• 无法充分利用现代 CPU 超标量能力。

几十年前，这个模型与当时的硬件能力相适应，能够匹配当时 CPU 和内存之间的速度比例。经过几十年发展，硬件有了长足的进步，值得注意的有：

• 相比内存性能的提高，CPU 性能提高的更多；

• 磁盘容量增长比 I/O 带宽增长更快，带宽是更稀缺的资源。

为了弥补火山模型的不足，并充分发挥现代硬件的能力，列存系统和向量化执行引擎应运而生。它们通过改变架构解决了上述两点导致的性能瓶颈转移问题，从最早的研究原型，转变为如今的数据库标配。

所以，如果想要使 YMatrix 性能在 TPC-H 基准测试上达到 GPDB 的十倍，打造列存系统和向量化执行引擎是必然选择。本文关注点是向量化执行引擎。

1.2 基于火山模型的向量化执行引擎

和常见的向量化执行引擎一样，我们的做法是基于火山模型的微批处理模式。从逻辑控制角度看，仍旧是火山模型；从数据角度看，一次处理一批数据（N 个 Tuple）而不是一个 Tuple。

数据按列存放，带类型信息，紧密排布，一个简单的 for 循环就能高效地处理一批数据，如下图所示。

这就弥补了火山模型的劣势，也是向量化的优势：

• 减少函数调用开销：显而易见，函数调用开销被均摊了，只有原先的 1/N 。除了火山模型中最常见的 next() 之外，很多和业务相关的函数开销也被均摊了。比如写缓冲区，如果一次处理一个 Tuple，每次都必须检查缓冲区是否有足够的剩余空间；如果一次处理一批，成本就会被均摊，相当于 1/N 个 Tuple 检查一次缓冲区。

• 更好的缓存局部性：数据跳转和指令跳转是流水线的大敌，更好的局部性意味着更好的性能。比如数据都在 L1 中，直接读取比从 L2 读取数据快 14 倍（数据来源参考：注 3）。从数据缓存角度看，一个批次的大小设置成能放进缓存的大小是合适的。如果过大，超过 L1 缓存大小甚至超过全部共享缓存大小，数据需要从内存（或共享缓存）传输数据到 L1 缓存，使查询执行速度变慢。从指令缓存角度看，向量化函数的命令会迭代和批大小一样的次数，而不是像面向行的执行引擎那样执行 A 函数之后接着执行 B 函数等，指令局部性更好。

图以 select a + b from t where a % 2 = 0 为例演示了火山模型和向量化的执行流程。左上角方框表示数据在内存中的布局，一个是行存，一个是列存。算子左侧方框表示当前正在处理的数据。从图中可以看出，向量化数据和指令的局部性都更好，函数调用次数和 if-else 分支都更少。

此外，向量化的优势还有：

• 充分利用编译器能力：如上所述，通过循环遍历数据紧密排布的原始类型数组及一些编程技巧，我们可以让编译器将我们的 C/C++ 代码自动编译为 SIMD 指令等更高效的形式。后续小节会详细介绍 SIMD 指令；

• 自适应执行路径：我们根据运算的复杂程度选择不同的执行路径。对于像加法运算这样开销很低的算子，无论对应 Tuple 是否被过滤，向量化执行引擎都会对所有数据做处理。虽然会有些额外的运算，但是因为循环中没有 if-else 分支，所以能够生成 SIMD 指令，执行速度比针对有效数据一个一个计算效率要高。下面讲解微批的优势，同时也是一个动态选择路径的例子；

• 性能分析：由于均摊，收集性能数据的成本也比一次处理一个 Tuple 要小很多，这使得向量化引擎能够提供更详细的关于 CPU 开销的性能指标分析。如果面向行的执行引擎做同样细致分析，分析本身相对于处理的占比会增高，影响性能。通过更详细的性能分析做数据支持，更有助于做出正确的优化决策，从而提升性能，形成正向反馈;

• 并行内存访问：在现代 CPU 上向量化循环执行内存访问的算法能够针对向量中不同值生成多个待处理的缓存未命中（outstanding cache misses）。这是因为当缓存未命中发生时，现代 CPU 能够提前推测，可以同时有多个待处理的缓存未命中。现代计算机对此支持的很好，基于此，内存带宽才能更好地被利用。工程实践的第一小节“搜索优化”是一个很好的例子。

一批处理多少数据呢？上限应该满足输入数据、输出数据外加辅助信息都能够放到 L1 缓存中这个条件，目的是避免频繁读写内存，充分利用缓存将这一批数据处理完；下限是至少能够利用 SIMD 指令做计算，同时能够达到有效均摊附加开销的目的。

不管为表示一批数据是否为 NULL，还是为表示这批数据是否被过滤条件选中，都使用一个 bitmap 字段表示，本质上是一个 uint64 数组，其中每个比特表示一个 Tuple 是否为 NULL 或者被过滤掉了。多个算子的结果基于 bitmap 位运算完成。当需要对这些数据做处理时，以很低代价判断出数据特征，选择不同方式执行计算，尽可能减少分支跳转，同时利用编译器优化能力达到更好的性能。

if (bitmap.Full() && bitmap.AllSet()) { // 满批，且全匹配    // 编译器有机会进行循环展开、生成 SIMD 指令等优化处理    // 同时，这里不需要再对 bitmap 进行检查    for (auto i = 0; rowid < BATCH_SIZE; i++)        // do something} else if (bitmap.NoSet()) { // 不匹配    // do nothing} else if (bitmap.AllSet()) { // 不满批，但全匹配    // 这种情况可以省略 bitmap 检查    for (auto i = 0; rowid < end; i++)        // do something} else { // 不全匹配    for (auto i = 0; rowid < end; i++)        // 只能一个一个的检查再处理数据        if (check bit)            // do something}

函数设计方面，接口都是面向微批而不是面向行的，原因有二：一是函数实现是面向列的算法而不是面向行的算法，一旦面向行处理，就会在多个列之间跳转，列存数据局部性优势消失；二是面向微批的接口能够减少函数调用次数，特别是调用虚函数。

1.2.1 SIMD 指令

前文多次提到 SIMD 指令，也总强调要充分使用 SIMD 指令才能提高性能，那它到底是什么？为什么会快呢？

SIMD 全称是 Single Instruction Multiple Data，即单指令流多数据流。对一组数据（数据向量）的每一个数据分别执行相同的操作从而实现空间上的并行处理，即一次完成对若干个数据的计算。如下图所示，一个 pvaddd 指令就能完成四次普通加法要做的事。

SIMD 指令虽然非常高效，使用起来却比较麻烦，需要声明一个类似 __mm256d 类型的变量，手动填充数据，调用一个名字相当长的函数，导致代码可读性不高。而且由于不同 CPU 所支持的 SIMD 指令可能不同，不利于代码的移植性，需要对支持的指令比较熟悉之后才能编写好的代码。

使用现成的类库是一个可行的方案。经过调研，要找到能满足我们需求的类库比较困难，因为每个类库往往有自己的设计目标和适用场景，而在不同场合使用不同类库会增加向量化执行引擎的维护成本。

最终，我们选择编写合适的代码，让编译器自动生成 SIMD 指令，克服上述种种困难。比如上图中对应的代码是

void foo(int *a, int *b, int *c) {  for (int i = 0; i < BATCH_SIZE; i++) {    c[i] = a[i] + b[i];  }}

编译器会做循环展开，生成高效的 SIMD 指令。

为了使编译器生成 SIMD 指令，代码必须满足以下要求：

• 循环自增是 1，即遍历整个数据；

• 类型不能过长，不要使用类似于 int128 的类型；

• 数据之间不能有依赖，如 a[i] = a[i - 1] ，循环展开（也不要自作聪明地手动展开）之后数据存在依赖无法自动向量化；

• 循环里面不要有分支。

最后，举一个求某一 int 列之和的例子结束这一小节。假定这一列有 1M 行，传统写法是

int sum = 0;for (int i = 0; i < 1 * 1000 * 1000; i++)    sum += a[i];

该写法只能是线性（垂直方向）依次相加。如果使用一个 int state[BATCH_SIZE] 保存中间结果，将每一批的垂直相加改写为类似前面 foo 例子的水平相加，对于一个微批而言，能够生成了 SIMD 指令（参考前文例子）。

for (int i = 0; i < 1000 * 1000 / BATCH_SIZE; i++) {    // 由于 BATCH_SIZE 是编译期常量，编译器会进行优化    // 如循环展开、生成 SIMD 指令等    for (int j = 0; j < BATCH_SIZE; j++) {        state[j] += a[i * BATCH_SIZE + j];    }}
int sum = 0;for (int i = 0; i < BATCH_SIZE; j++)    sum += state[i];

上面代码的第二行，集中处理 BATCH_SIZE 个值，与前文图示类似，编译器循环展开之后生成 SIMD 指令，一次性处理若干个数据，效率高好几倍。

上述就是是向量化最基本的原理。假定我们已经有一个向量化执行引擎框架，为了达到 TPC-H 基准测试比 GPDB 快十倍的目标，应该优先实现哪些算子呢？或者说主要优化方向是什么？

在文章伊始谈及多个查询都涉及多表 Join。比如 TPC-H Q9，涉及六个表，五个 Join。

select    nation, o_year, sum(amount) as sum_profitfrom    (        select            n_name as nation,            extract(year from o_orderdate) as o_year,            l_extendedprice * (1 - l_discount) - ps_supplycost * l_quantity as amount        from            part, supplier, lineitem, partsupp, orders, nation        where            s_suppkey = l_suppkey            and ps_suppkey = l_suppkey            and ps_partkey = l_partkey            and p_partkey = l_partkey            and o_orderkey = l_orderkey            and s_nationkey = n_nationkey            and p_name like '%moccasin%'    ) as profitgroup by    nation, o_yearorder by    nation, o_year desc;

针对该查询，若我们能打造一个性能极致的 Join 算子，对实现目标很有助益。但 TPC-H 有 22 个查询，总体特征又是怎样的呢？好消息是前人帮我们分析好了，参考 Quantifying TPC-H Choke Points and Their Optimizations（注 4） 图 2 可知耗时最大的是 HashJoin，其次是 HashAgg，此两项占比接近 80%。

结论是，最佳优化方向就是实现一个非常高效的 HashJoin 和 HashAgg，能够最大程度提升执行引擎在 TPC-H 上的性能表现。由于 HashJoin 和 HashAgg 都是基于 Hash Map 实现的，共享很多基础组件，同时很多优化思路和指导原则都是共通的，所以下文以实现一个高效的 HashJoin 为切入点，介绍我们为实现极致性能做了哪些优化工作。

二 向量化的 HashJoin

实现一个功能或对一个功能进行优化的整体思路一致：先抓主要矛盾，从全局上观察问题，解决问题；其次是针对各个次要矛盾（一个局部，即一个更小的主题、问题）逐个击破。这是一个普适解决问题的思路。

2.1 算法

选择合适的算法是第一位的。针对一个问题，如果选择复杂度为 O(N) 的算法而不是最优的 O(lg N) 算法，即使工程上再优化，也不可能比后者快。

2.1.1 Join 顺序优化

对于 HashJoin 而言，Join 顺序正确是第一位的。假设两个表做 Join，行数分别是 100M 和 100K，假定 Join 类型允许任意选择 Join 的内表和外表，肯定要选择 100K 行的表作为内表。因为 100M 行有可能无法放到内存中，一旦涉及数据落盘，性能就会比较差；即使能够放到内存，使用 100M 行的表构建 HashMap 只搜索 100K 次的速度比构建 100K 行的 HashMap 搜索 100M 次要慢很多，原因有：

1. 前者占用内存更多，更不可能在缓存中，局部性更差；

2. 一般而言，对于一条数据，构建 HashMap 的成本比搜索高。

当一个查询涉及多个 Join，先后顺序就愈加关键，因此一个好的查询计划至关重要。

为了使优化器能够产生最佳的（至少是比较优秀的）查询计划，我们做了很多优化工作。诸如提升统计信息的准确度、提升估算的准确度，以及扩大搜索空间等等。这些优化不仅能够帮助向量化执行引擎运行的更快，也能大幅提升标量化（面向行的）执行引擎性能。

由于该文章关注点不在这些领域，在此只举一个和 Join 顺序紧密相关的例子，以展示算法层面优化的威力。

首先介绍一下 Postgres 是如何估算 Join 的选择率和结果行数的。

选择率是 NDV（不同值的数量， Number of distinct values ）的倒数。

两个表 t_1, t_2  进行 Join 运算，条件是 t1.a = t2.a ，用 Nt_i  表示表 i  的行数，最终 Join 结果的行数是

详细解释一下上面公式。不妨设 NDV(t1.a) 比较大，那么

最后一项的左边就是平均每一个值有多少行。Postgres 有一个假设，两个表的值域是包含关系，在这个例子中就表示 t2.a 的每一个值在 t1.a 里都能找到，也就是都能匹配上。t1.a 中每个值的平均行数乘以 t2 的行数，就是结果集的总行数。也可理解为笛卡尔积之后总行数乘以选择率（该公式的中间项），而这恰恰是 PG 的计算方式。

对于多列等值 Join，比如 t1.a = t2.a and t1.b = t3.b，通常使用 t1.a = t2.a 和 t1.b = t3.b 当作两个单独 Jion 条件做等价替换，将两个 Join 选择率相乘得到新的选择率，这里的隐含信息是：两列无关。沿用之前的“不妨设”，两个 Join 条件都是 t1 对应列的 NDV 比较大。选择率是

但是分母可能比 Nt_1  的总行数还多，导致选择率低估，结果就是总行数低估。

一个简单的修正是分母最大，也就是表的行数。

TPC-H Q9 是一个包含五个 Join 的查询，其中一个是多列等值 Join，修正之后查询计划变化很大，更接近最优计划，性能提升了 2 倍。

2.1.2 HashMap 的选择

假定 Join 顺序已经最优了，接下来考虑 Hash Join 算法。

假定表 S 是内表，表 R 是外表，算法分为两个阶段：构建 HashMap 和搜索。首先将构建一个 HashMap，键（Key）是表 S Join Key 对应的值（可能多列），值（Value）是对应的行号；第二个阶段是取出 R 每条 Tuple 的 Join Key，在 HashMap 中查找对应的行，然后由内外表数据组成结果。

现在问题出现了，如何选择 HashMap 的实现呢？最简单省事的方案就是使用 C++ STL 自带的 std::map；也可以选择业内成熟、顶尖级的 HashMap 实现，比如 Facebook 的 folly/F14Map、Abseil 的 absl::flat_hash_map；亦或是根据论文自己实现。

在调研竞品、阅读大量论文，以及性能分析对比之后，我们选择了两种实现：一是论文 Balancing Vectorized Query Execution with Bandwidth-Optimized Storage（注 5） 中 5.3 节描述的使用 first/next 两个数组组成的 HashMap（下面简称 FNHM）；二是论文 Memory-Efficient Hash Joins （注 6）中描述的 Concise Hash Table（下面简称 CHT）。

对于绝大部分场景，CHT 的内存占用量都更少，速度也更快，但是由于存在少数场景 CHT 会稍慢一些，所以实现了两个 HashMap，通过 GUC 控制，根据用户需要自由选择。

由于篇幅长度问题，这里不再展开讨论这两种 HashMap 的原理和实现细节。感兴趣的读者可以参考给出的论文。后续我们也会发布文章，更详细地介绍原理和工程实践的相关优化。

2.1.3 Runtime Filter

减少算法输入规模也能很大程度提升性能。如果能够用很小的代价降输入规模，比如规模减少为十分之一，对于线性复杂度算法，大约能提升十倍。如果是 O(n\lg n) 算法，则能提升更多。Runtime Filter 正是这个思想的体现。

前面说过，Join 的内表比较小，构建 Hash Map，外表比较大，计算哈希值、匹配过程都比较耗时。如果能对大表先进行过滤，则有可能获得加速。这里的做法是使用内表数据构建一个布隆过滤器（Bloom Filter），然后作用于外表，就能起到减少输入规模的作用。简而言之，关联谓词在 Hash Join 构建阶段转化成一个过滤条件应用于外表。这个用于过滤的集合运行时才确定，一般把这种机制称作 Runtime Filter，在应用于 Join 算子时也被称作 Dynamic Join Filter，也可看做是谓词下推。

下面以 Q17 为例，查询如下

select    sum(l_extendedprice) / 7.0 as avg_yearlyfrom    lineitem,    partwhere    p_partkey = l_partkey    and  p_brand = 'Brand#35'    and p_container = 'WRAP DRUM'    and l_quantity < (        select            0.2 * avg(l_quantity)        from            lineitem        where            l_partkey = p_partkey    );

partkey 的基数是 2,000,000，而加上两个过滤条件 p_brand = 'Brand#35' and p_container='WRAP DRUM'，基数小于 2,000，减少了三个数量级。通过 Runtime Filter，等价于过滤条件也作用在子查询的 Agg 算子和外层 Join 算子下的扫描节点，使得扫描节点向上层算子返回的结果规模大大减少，以提升性能。

布隆过滤器的特点并不完全等价于数据库中的谓词过滤，但是也能去除相当比例的无用数据。以 Q17 为例，输出结果集是原数据集的 1/80，整个查询性能提升了 8 倍。

2.2  工程实践

2.2.1 搜索优化

这里以 FNHM 为例。由于 Hash 的特性，天生的缓存不友好，但是应该尽可能地让加载数据到缓存的时间变短。下面的优化，就是利用现代硬件能够同时处理多个待处理缓存未命中的能力，优化搜索性能。

最简单直接的搜索方法是遍历一批数据中的每一行，在 HashMap 中找到结果。以下是伪代码：

foreach rowid in batch:    bktid = hashcode % n;    offset = first[bktid];    while(offset != 0 && !CheckEqual()）        offset = next[offset]

first[bktid]/next[offset] 大概率不在缓存中，需要等到从内存加载到缓存，然后才能继续后面的计算，比如 while 中赋值给 offset 必须等待之前的代码执行完成。这样没能利用微批处理的优势和现代硬件的能力。

稍加思考，不难发现一批中不同数据是相互独立的，如果能够并行搜索，就能更好地利用现代硬件的能力。

如果说第一种方法类似深度优先搜索，第二种方法就类似于广度优先搜索。如下是伪代码。和之前一样，first[bktid] 大概率不在缓存中，需要加载，不过后续代码（循环的下一次）不再依赖于 first[bktid]，如果编译器能循环展开，同时产生多个缓存未命中，处理器同时处理这些缓存未命中的数据。于是乎加载数据到缓存的效率比方法一提升很多。

foreach rowid in batch    bktid = hashcode % n;    if (first[bktid] != 0)        match[rowid] = first[bktid];        tocheck.add(rowid);
while(tocheck.size() > 0)    tochecktmp = tocheck    tocheck.clear();    foreach rowid in tochecktmp        if(!CheckEqual())            match[rowid] = next[match[rowid]];            if (match[rowid] != 0)                tocheck.add(rowid);

2.2.2 Join Key 类型

在第一版中，HashMap 中 Key 的类型只有两种，一种是 long，目的是处理 Join Key 数量唯一且其类型是整数的情况，另一种是 string，处理其他情况，比如两个 Join Key，先把这两列数据追加到 string 中，然后将其视作二进制来计算哈希值和判等。

仍旧以 Q9 为例，这里涉及五个 Join，四个是单列 Join，类型包含 int32 和 int16，一个是两列 Join，这两列的类型都是 int32。第一版设计的 Key 类型虽然能覆盖所有场景，但是和具体查询有一点差别，如果能消除这个差距的话性能肯定会有提升。

如果 Join Key 类型是 int，下层算子返回的是 BATCH_SIZE 个紧密排列的数 int，但是往 HashMap 插入时，参数是 long 数组，这里不得不拷贝一次，一行一行赋值。解法是拓展 Key 的类型，以避免拷贝，或者只需块级别拷贝一次。

如果 Join Key 有两个，都是整数，使用 string 作为 Key 类型，也需要拷贝，并且计算哈希值（详见下一小节）和判等都会比较慢。再次拓展 Key 类型，将两个整数 Key 放到一起，这时额外需要一个 bool，表示该给哪个 Key 进行赋值。这里还是有数据的拷贝，不过向 string 中拷贝是把整数当做二进制，使用 std::copy 处理，而新的 Key 类型是带类型的整数集合，直接用 = 赋值即可，编译结果是 mov 指令，比内存拷贝快很多。除了计算哈希值能快外，判等也是两个带类型的整数比较，比按二进制比较 string 快很多。

2.2.3 哈希值的计算

在整个 Hash Join 中，计算哈希值是很重要的，性能只是一个方面，哈希函数的质量（碰撞和随机性）也是重要指标。经过对性能和质量两个方面的实际测试，我们选择 xxHash（注 7） 的 XXH3 生成 std::uint64_t 类型的哈希值。

通过分析 TPC-H 查询，绝大多数都只是单列等值 Join，且类型是整数。如果能够提升计算整数类型哈希值的性能，基本上所有查询都能得到性能提升。

在一开始的实现中，不管是 string 还是整数值类型，都交给 xxHash 计算哈希值。xxHash 性能很好，不过对于整数值，也是当做二进制计算，没有利用到类型信息。简单地乘以一个大的质数作为哈希值是否可行呢？是否能更快呢？

经过性能测试，乘以大质数的速度是 xxHash 的 7 倍，能够进一步提升性能。利用 xxHash 自带的质量检测工具，质量和 xxHash 性能一致，甚至在有些高比特位上表现更好。

对于 std::uint8_t 和 std::uint16_t 两个类型，直接返回数值本身作为哈希值，同时，桶数设置为 256 = 2⁸, 65536 = 2¹⁶ 个。

读者可能会有疑问，如果 Join Key 是 std::uint32_t 或者 uint64_t 类型，为什么不能直接返回数值本身作为哈希值呢？

这两个类型的值域非常大，不可能像一字节和两字节整数一样，桶数等于值域集合大小，所以不得不从哈希值映射到对应的桶。我们选择 2 的幂次作为桶数，得到哈希值之后，通过与运算得到 bucketid，放到对应的桶里面。简单的与运算只用了低若干位的信息，而高位信息被丢弃了。

如果 Join Key 列的数值完全随机分散，直接使用整数值做为哈希值没有任何问题。但是实际生产场景分布往往与业务相关，在某些情况下，数据隐含某种规律，那么直接取低若干位可能会导致冲突率升高。如果计算一次哈希值，利用到所有比特的信息，会改变数据分布，更趋于完全随机分散，冲突率就会降低。对于 HashMap 而言，冲突率的高低是影响性能的一个重要因素。

对于上一个小节提到的将两个整数打包的 Hash Key 类型，计算哈希值的算法是

std::uint64_t hashcode() const {    auto h1 = data1_.hashcode();    auto h2 = data2_.hashcode();    return ((h1 << 5) + h1) ^ h2;}

这也比将两个整数拼接为字符串（四到十六字节）作为二进制让 xxHash 计算哈希值快好几倍。这里的实现是业界标准做法，不能直接异或的原因是：如果两个值相同，异或结果为零，那么两列值相同的行哈希值都是零，这会增加冲突率。

计算哈希值性能提升还有一个额外收益。HashMap 的实现包含一个 Entry 数组（有的实现中称为 Payload），存放键值对、哈希值等信息。由于计算很快，对于整数类型或者两个整数的复合类型，不再存放哈希值，这大幅减少数组大小，比如 Join Key 是 long 类型，值是行号，uint32_t 类型，总共 12 个字节，如果加上哈希值 8 个字节，就达到 20 个字节，大了三分之二，如果 Key 是 int 类型，加上哈希值会膨胀一倍！除了减少内存开销外，由于同样大小的缓存能放更多数据，性能有明显提升。代价是在 HashMap resize 时或者由于内存不足进行 Spill 时，需要再次计算哈希值。这两件事出现概率不大，即使不得不计算，代价也小于上述收益。

2.2.4 不同 Join 类型有不同的具体实现

每种 Join 类型都有各自特点，如果使用同一套接口、数据结构和算法实现所有类型的 Join 算法，可以肯定地说，无法将性能做到极致。

举一个具体例子。对于 inner join 而言，外表的一行有可能匹配多行，而 semi join 任意匹配一行即可，anti join 在没有匹配时反而需要输出一行。HashMap 如何返回这些信息呢？我们需要告诉上层要是否匹配，如果匹配，需要知道行号（可以通过行号是否为零判断是否匹配），对于 inner join 还需要知道匹配了哪些行。

由于接口是面向批的，对于 semi/anti join 而言，uint32_t match[BATCH_SIZE] 表示结果就足够了，不过对于 inner join 来说，还需要知道外表的某一行对应内表的哪些行，由于行数不固定，不得不使用 std::vector 这样的容器来存放数据。

如果接口一样，实现也一样，对于 semi join 而言，也需要往 std::vectorpush_back 数据，这显然是一种浪费。

进一步分析，对于 semi join 不需要填充重复数据的行号，那么 HashMap 就无需保存重复数据，构建 HashMap 时，发现重复值，直接忽略即可，减少不必要的内存和 CPU 开销；在搜索 HashMap 时也一样，无需处理重复值。

这些想法很容易通过 c++ 模板参数配合 if constexpr 或者模板特化实现，在编译期对每一种类型都生成最精简的代码。

如果仔细分析 TPC-H 查询，不难发现 inner join 出现的次数最多，耗时占比也最大。这个结论有点“显而易见”，原因是 inner join 就是最常用的 Join 类型。除了上述优化外，我们完全模板特化了和 inner join  相关的类，逐行审视其实现，确保没有一个无用的数据结构，没有一行无用的代码，尽全力做到极致。

2.2.5 NULL 值处理

TPC-H 的数据特征是没有 NULL 值，所以我们对 NULL 值的处理也有优化。

整个 HashJoin 的计算过程中仅仅记录了索引信息，比如外表的第二行匹配内表的第六行，当需要输出时，按照索引信息，逐列处理，拼接出结果。

这里介绍一个向量化引擎的内部概念 - Array，它是一个容器，存放一列数据，同时，有一个相同长度的 bitmap，表示对应行是否为 NULL。

逐列拼接结果时，首先 new 一个新的 Array，和原始 Array 同类型，同长度，根据索引信息，找到原始 Array 中的数据，追加到新 Array 中。但是，由于无法预测当前索引位置上的数据是否为 NULL，不得不读取 bitmap 然后 if-else 判断。读取信息和太多分支都会使性能变差。

bitmap 本质上就是一个 uint64 数组。利用 std::popcount 能以很小的成本知道 bitmap 中是全 NULL，没有 NULL 还是数据和 NULL 混杂。对于前面两种情况，处理数据时就无需再一次次判断数据是否为 NULL，也就是通过一个 if-else 分支代替成千上万次的 if-else，同时避免反复读取 bitmap。

这是一个通用的优化手段，在向量化执行引擎中大量使用。

2.2.6 精益求精

在整个向量化执行引擎的实现过程中，消除分支也是一个常用的优化手段。比如前面“NULL 值处理”小节，这里再举一个浮点数比较的小例子。

由于存在 NaN（Not a Number），不能简单地写一句 f1 < f2 比较两个浮点数，而是要考虑两个待比较的数中是否有 NaN。在 PG 中，它们被认为大于所有非 NaN 浮点数。

一个简单直接的解法是写两个 if 检查两个参数，最后再比较两个数。

不过我们巧妙地利用两次位运算来避免两次 if 分支，使比较函数运行地快一点点。

static int lessThan(double lhs, double rhs) {    return (~isnan(lhs)) & (isnan(rhs) | (lhs < rhs));}

读者可能会好奇，少两个 if 会差别很大吗？如果只调用一次或者十次，没有差别，也不可能被觉察。但是数据库需要处理海量数据，比如有 100M 行浮点数，不管是排序还是过滤，这个函数至少被调用上次亿，差距就会显现。

这个例子也很好地说明：

1. 工程实践的打磨是非常精细的，需要细致地打磨每一处代码；

2. 不积跬步无以至千里，也正是成百上千次微小的改动，最后造就性能极致的产品。

三 拾珠

我们讲解了向量化执行器的各个方面，还有两个对性能做到十倍贡献很大的组件——并行引擎和列存储引擎——没有分析。这里做一个概述。

3.1 并行

直到 2003 年左右，摩尔定律都基本成立，CPU 的性能每 18 个月翻一倍，程序员什么也不做，程序运行速度就能更快。不过这之后，CPU 单核能力基本到了上限，CPU 制造商的思路从构建更快、更复杂的单处理器变成了在芯片上放置多个相对简单的处理器，即多核处理器。这时，程序员什么也不做的话，程序运行速度就不会有变化了。

为了充分利用多核处理器的性能，YMatrix 引入了并行引擎。简单地说，对于同一个数据文件，起若干个进程（典型值是 3-4 个，这依赖于机器本身）同时处理数据。对数据进行划分，每个进程独立地处理一部分数据，相当于在一个分区之上又虚拟出了几个子分区。

3.2 存储

存储引擎是数据库系统的存储基座，数据库基于存储引擎进行数据的创建、查询、更新和删除等操作。根据需要，不同的存储引擎将提供不同的存储机制，在物理布局，索引类型，锁的粒度等不同维度进行设计。

在文章最开始提到“为了弥补火山模型的不足和充分利用现代硬件的能力，列存系统和向量化应运而生……它们通过改变架构解决了上述两点导致的性能瓶颈转移问题。”列存储引擎是非常重要的组件。针对时序场景，我们设计了 MARS2 存储引擎，支持压缩、列存、自动归档、预聚集等功能，在时序场景中表现优越。下面举一个向量化执行引擎和 MARS2 配合的例子。

假定我们有一个 MARS2 的表，有时间 ts 列和区域 region 列，在这些列上有 minmax 元信息，记录一个块（存储的最小单元，包含某列数据的若干行）的最大值和最小值。

我们想要查询今年某个区域的数据

SELECT * FROM fast_filter WHERE ts > '2022-01-01' AND region = 2;

从存储引擎角度看，如果一个块的 ts 上最大值小于 2022-01-01，存储引擎不再读取这一块，节省 I/O 资源，同时，也减少了执行引擎的计算量。

向量化执行引擎会也能利用 minmax 信息加速计算。比如某块 region 的最大值和最小值都是 2，执行引擎只会在该块应用谓词 ts > '2022-01-01' 过滤出符合条件的数据，而不会进行任何和 region 有关的运算，提高性能。

这两个点也告诉我们，性能具备整体性。单打独斗，只实现一个极致的向量化执行引擎是远远不够的。

四 展望

对性能的追求没有尽头，我们的目标始终是更快更快还是更快！

随着 YMatrix 5.0 发布，向量化执行引擎面世，但这只是起点，未来还需进一步提升性能，超越过去的自己。

从算法层面到工程实践，都有很多需要做的事情。比如当前还没有很好地实现 Merge Join 算法，而当数据已经有序或者上层算子需要有序输出时， Merge Join 可能是更好的选择。再比如文中提到的微批化处理的优劣势，可以大块（1000 行以上为一个处理单元）与微批相结合，利用好各自的优势。

除了执行引擎本身，还可以考虑和存储引擎深度整合。比如利用好列存系统的统计信息，简化诸如聚集等计算；也可以给压缩数据增加一些元数据，利用这些实现不解压直接计算，提升性能。

参考链接

-  注 1：

https://www.tpc.org/tpc_documents_current_versions/pdf/tpc-h_v3.0.1.pdf

-  注 2：

https://cn.greenplum.org/

-  注 3：

https://gist.github.com/jboner/2841832

-  注 4：

https://www.vldb.org/pvldb/vol13/p1206-dreseler.pdf

-  注 5：

https://ir.cwi.nl/pub/14075/14075B.pdf

-  注 6：

http://www.vldb.org/pvldb/vol8/p353-barber.pdf

-  注 7：

https://github.com/Cyan4973/xxHash

本文为 YMatrix 原创内容，未经允许不得转载。

欲了解更多超融合时序数据库相关信息，请访问 “YMatrix 超融合数据库” 官方网站