设计：小艾
审核：丁奇、宇亭
编辑：宇亭
作者一：徐鑫强（花名：无花果）
电子科技大学 - 计算机技术 - 在读硕士、StoneDB 内核研发实习生
作者二：柳湛宇（花名：乌淄）
浙江大学 - 软件工程 - 在读硕士、StoneDB 内核研发实习生
一、MySQL 连贯形式简介
MySQL 反对天然连贯、等值连贯（内连贯）、左连贯、右连贯、穿插连贯五种连贯形式，不反对全外连贯，全外连贯能够通过 Union 并集操作实现。连贯算法：简略嵌套循环、索引嵌套循环、块嵌套循环以及哈希连贯。
简略嵌套循环（Simple Nested-Loop Join，SNLJ）
驱动表中的每一条记录与被驱动表中的所有记录顺次比拟判断，驱动表遍历一次，被驱动表遍历屡次。此算法开销十分大，假如驱动表的行数为 M，被驱动表的行数为 N，则算法工夫复杂度为 O(M*N)。实际上，MySQL 并不会应用此算法。
基于索引的嵌套循环（Indexed Nested-Loop Join，INLJ）
通过在被驱动表建设索引，缩小被驱动表的扫描次数。个别 B+ 树的高度为 3~4 层，也就是说匹配一次的 I/O 耗费也就 3~4 次，因而索引查问的老本是比拟固定的，故优化器都偏向于应用记录数少的表作为驱动表。在有索引的状况下，MySQL 会尝试应用此算法。整个过程如下图所示：
基于块的嵌套循环（Block Nested-Loop Join，BNLJ）
扫描一个表的过程其实是先把这个表从磁盘上加载到内存中，而后在内存中比拟匹配条件是否满足。但内存里可能并不能齐全寄存的下表中所有的记录。为了缩小拜访被驱动表的次数，咱们能够首先将驱动表的数据批量加载到 Join Buffer（连贯缓冲），而后当加载被驱动表的记录到内存时，就能够一次性和多条驱动表中的记录做匹配，这样可大大减少被驱动表的扫描次数，这就是 BNL 算法的思维。当被驱动表上没有建设索引时，MySQL 会尝试应用此算法。整体效率比拟：INLJ > BNLJ > SNLJ。整个过程如下图所示：
哈希连贯（Hash Join）
嵌套循环连贯对于被连贯的数据集较小的状况是较好的抉择，而对于大数据集 Hash Join 是更好的形式。优化器应用两个表中的较小表在内存中根据 Join Key 建设哈希表，而后顺次扫描较大表并探测哈希表，找出能与哈希表匹配的行。Hash Join 会毁坏表数据的有序性和局部性，因而它只能利用于等值连贯。
二、哈希连贯的优化方向简述
随着 MySQL 8.0 对 Hash Join 反对，在内表面均无索引或大表驱动小表的状况下，Hash Join 显然是比 BNLJ 更好的抉择，而在 AP 场景下，大量数据多表 Join 的刚需也使得 Hash Join 有了多种方向的优化门路。本章简要介绍一部分对 Hash Join 优化的方向和思路。
一个要害的前提是，前述介绍提到了 Hash Join 不适用于非等值连贯，因而当表连贯语句语句中未应用 ON <attr1>=<attr2> 款式的等值连贯办法或默认的天然等值连贯时，MySQL 不会应用 Hash Join。
首先该当明确 Hash Join 的工作流程，以 MySQL 为例 [1]，MySQL 就应用了经典的单线程 Hash Join 实现，它有建表（build）和探测（probe）生成后果两个步骤。
- 「建表」：如下图所示，建表就是遍历 OuterTable，将其等值连贯键计算哈希值并依据构造构建为一个哈希表：
- 「探测」：如下图所示，探测步骤就是遍历 InnerTable，计算每个 tuple 的值连贯键的哈希值并从哈希表中找到对应的桶（bucket），并通过比照决定是否能进行哈希连贯，进而实现整个 Hash Join 过程 [2]。
2.1 哈希算法的选取
哈希算法是 Hash Join 的根底，好的哈希算法能够极大晋升依赖哈希操作的程序的效率。优良的哈希函数会在随机性（体现产生哈希抵触的概率）和计算效率（单词计算哈希的速度）之间做 trade-off，因而不同偏重方向的数据库也该当抉择适合的哈希函数，如 Apache Doris[3]抉择了 CRC32 这一计算速度很快且能够通过 SIMD 减速的哈希函数，而 DuckDB 抉择了随机性更高的 MurmurHash[4]。
但时至今日，随着 XXhash[5]的问世，哈希函数的选取仿佛真正领有了银弹。对于绝大多数的 HashTable 这种哈希长度绝对较小的场景，XXHash 的不同长度变种仿佛都是最佳抉择：
2.2 哈希表的根底结构设计
哈希表根底结构设计的一个根底点就是其解决抵触的办法，经典的解决办法有凋谢寻址法（即在哈希抵触时应用线性探测、平方探测、重哈希等办法持续在哈希表中搜寻）和拉链法（在 bucket 中存储链表或均衡二叉树代表的抵触子项）。拉链法是更直观和更低哈希抵触率的做法，因而其多见于 Java/Go 等编程语言的哈希表实现。然而对于数据库内核中的哈希表，利用大数据量、管制内存使用量和 Cache Miss 率等都是优先级更高的需要，因而线性探测等凋谢寻址的抵触解决办法是构架哈希表的更优解。
另一个要害的根底结构设计是哈希表扩容的机制，大部分哈希表的扩容机制是在当已有元素站总容量比例超过肯定阈值（对于 DuckDB，这个阈值是默认是 50%，对于 Java 的 HashMap，这个阈值默认是 75%）后进行扩容。然而显然对于线性探测的抵触解决办法，哈希抵触的概率因为哈希汇集（hash clustering）的起因会随占用率进步而迅速减少，因而个别线性探测的抵触解决办法设定的阈值较低，这也导致了内存的节约。因而有一系列的工作[6] 通过 rehash 或保护细粒度数据结构等办法改善这一状况。
对于数据库内核这一畛域，内核的优化器能够为哈希表提供可用的构造优化和先验常识。如对于列式存储数据库，能够通过 build 过程下推，间接以内核中读取的压缩后的键进行哈希表的构建合并，缩小序列化和反序列化开销并减小 hash key 长度。此外，能够通过优化器的统计数据，将须要建表的数据剪去前缀，这也能进一步地缩小 hash key 长度，进而减速哈希函数计算速度。
2.3 对探测过程的优化
由上节能够看出，对于线性探测办法构建的哈希表，哈希抵触是探测操作是的性能瓶颈，因而能够引入一层过滤层，尽早过滤掉不在哈希表中的探测键值，从而缩小探测的次数，这一过滤层最经典的实现就是如下图所示的布隆过滤器[7]。
本文不再深刻论述布隆过滤器的算法原理和优化办法，读者只须要晓得，布隆过滤器能够通过若干个哈希函数（实际上，它们由一个根底哈希函数和位移、累加操作失去）操作一个 bitmap，通过对 OuterTable 的等值键遍历进行构建并由 Inner Table 探测。其特点是存在假阳性（False Positive），但不存在假阴性（False Negative），即通过布隆过滤器的记录并不一定真的可能匹配（可能存在哈希抵触），但被过滤掉的记录肯定不匹配。
在布隆过滤器的根底上，还有一系列的概率数据结构变种，如 Block Bloom Filter，Cuckoo Filter[8]等。不过对于不须要删除，操作绝对固定的 Hash Join 场景，实现简略，占用内存少的布隆过滤器是大部分状况下的最佳抉择。
2.4 对 Cache Miss 的优化
哈希表访存的随机性不可避免地会晋升 cache miss 率而不得不通过页表拜访内存，这会使得 Hash Join 遭逢性能瓶颈。古代计算机处理器的最大缓存粒度是 LLC（Last Layer Cache，在广泛应用的 Intel/AMD 处理器上，它是 L3 缓存），因而以 LLC 大小为单元的内存区域操作是对 Cache Miss 率优化的出发点。一个简略的办法是条件化预读取（Conditional Pre-fetching）：哈希表能够保护对于哈希抵触数量、占有率以及哈希抵触热点区域的元数据，并依据这些元数据判断一次 probe 是否可能产生大量的哈希抵触，并在可能产生抵触时以 LLC 大小为单位预读取若干个 bucket 到内存，这样线性探测办法将能够缩小 cache miss 数量。
更简单的办法则是按如下图的形式构建分区哈希表（Partitioned Hash Table），即依照肯定的规范（这个规范能够参考优化器提供的统计数据）将 Outer Table 在建表时放入不同的子哈希表（称为 Partition），而遍历 Inner Table 时，能够应用同样的规范将比拟的 key 路由到对应的 Partition 中进行哈希查找和比对。这样做意义有三点
- 首先就是通过让每个 Partition 可能被装入 LLC，使得解决一个 Partition 的构建和探测工作时大大降低 Cache Miss 率；
- 能够更细粒度地治理哈希表的内存应用，哈希表能够不以 2 的幂的模式分配内存（以 Partition 为根本调配单位），同时在极限状况下也能够开释局部空的 Partition 以移作他用；
- 使得并行构建哈希表成为可能，这部分由 2.5 节论述。
接下来的问题是，如果疾速且无效地将整个哈希表且分为若干分区表，为了保障这一过程的效率，Radix Hash Join[9]的流程被提出。
2.5 多线程哈希连贯的优化
MySQL 的 Hash Join 是单线程执行的。但通过例如上述构建布隆过滤器和分区哈希表的办法，咱们能够实现多线程执行。
布隆过滤器自身的构建和探测相似于哈希表的构建和探测，因而二者能够类比剖析。布隆过滤器的变种 Blocked Bloom Filter 通过数学证实能够与布隆过滤器有相似的效力，但能够通过开多线程并行构建每个 Block，并空值 Block 大小适配 CPU 核的缓存，并通过 SIMD 减速探测操作。Hash Join 的探测操作相似，将 Inner Table 的记录切为若干个线程并发解决的工作段后，并行地对哈希表进行探测，并在须要时将最初的后果进行 Merge 操作以保证数据有序性，这一点相似于排序 - 归并连贯的算法。
而构建操作则先失去更加简单，因为它存在写操作写操作，即便是对 Partitioned Hash Table，依然要进行 Partition-wise 或 Bucket-wise 的加锁 - 解锁操作能力并行执行。因而须要同步措施来保障线程之间数据的一致性和正确性，在目前的工业实际上，通过被大部分支流处理器反对的 cmpxchg 指令实现的 CAS（Compare And Swap）操作是 CPU 密集操作的最佳实际：
本图援用自互联网，侵权分割删除