MySQL8.0 新特性 Hash Join

概述&背景

mysql一直被人诟病没有实现hashjoin，最新发布的8.0.18已经带上了这个功能，令人欣喜。有时候在想，mysql为什么一直不支持hashjoin呢？我想可能是因为mysql多用于简单的oltp场景，并且在互联网应用居多，需求没那么紧急。另一方面可能是因为以前完全靠社区，这种演进速度毕竟有限，oracle收购mysql后，mysql的发版演进速度明显加快了很多。

hashjoin本身算法实现并不复杂，要说复杂，可能是优化器配套选择执行计划时，是否选择hashjoin，选择外表，内表可能更复杂一点。不管怎样现在已经有了hashjoin，优化器在选择join算法时又多了一个选择。mysql本着实用主义，相信这个功能增强也回应了一些质疑，有些功能不是没有能力做好，而是有它的优先级。

在8.0.18之前，mysql只支持nestloopjoin算法，最简单的就是simple nestloop join，mysql针对这个算法做了若干优化，实现了block nestloop join，index nestloop join和batched key access等，有了这些优化，在一定程度上能缓解对hashjoin的迫切程度。下文会单独拿一个章节讲mysql的这些join优化，下面先讲hashjoin。

hash join算法

nestloopjoin算法简单来说，就是双重循环，遍历外表(驱动表)，对于外表的每一行记录，然后遍历内表，然后判断join条件是否符合，进而确定是否将记录吐出给上一个执行节点。从算法角度来说，这是一个m*n的复杂度。hashjoin是针对equal-join场景的优化，基本思想是，将外表数据load到内存，并建立hash表，这样只需要遍历一遍内表，就可以完成join操作，输出匹配的记录。如果数据能全部load到内存当然好，逻辑也简单，一般称这种join为chj(classic hash join)，之前mariadb就已经实现了这种hashjoin算法。如果数据不能全部load到内存，就需要分批load进内存，然后分批join，下面具体介绍这几种join算法的实现。

in-memory join(chj)

hashjoin一般包括两个过程，创建hash表的build过程和探测hash表的probe过程。

1).build phase

遍历外表，以join条件为key，查询需要的列作为value创建hash表。这里涉及到一个选择外表的依据，主要是评估参与join的两个表(结果集)的大小来判断，谁小就选择谁，这样有限的内存更容易放下hash表。

2).probe phase

hash表build完成后，然后逐行遍历内表，对于内表的每个记录，对join条件计算hash值，并在hash表中查找，如果匹配，则输出，否则跳过。所有内表记录遍历完，则整个过程就结束了。过程参照下图，来源于mysql官方博客

    

左侧是build过程，右侧是probe过程，country_id是equal_join条件，countries表是外表，persons表是内表。

on-disk hash join

chj的限制条件在于，要求内存能装下整个外表。在mysql中，join可以使用的内存通过参数join_buffer_size控制。如果join需要的内存超出了join_buffer_size，那么chj将无能为力，只能对外表分成若干段，每个分段逐一进行build过程，然后遍历内表对每个分段再进行一次probe过程。假设外表分成了n片，那么将扫描内表n次。这种方式当然是比较弱的。在mysql8.0中，如果join需要内存超过了join_buffer_size，build阶段会首先利用hash算将外表进行分区，并产生临时分片写到磁盘上；然后在probe阶段，对于内表使用同样的hash算法进行分区。由于使用分片hash函数相同，那么key相同(join条件相同)必然在同一个分片编号中。接下来，再对外表和内表中相同分片编号的数据进行chj的过程，所有分片的chj做完，整个join过程就结束了。这种算法的代价是，对外表和内表分别进行了两次读io，一次写io。相对于之之前需要n次扫描内表io，现在的处理方式更好。

                     

                                   

左上侧图是外表的分片过程，右上侧图是内表的分片过程，最下面的图是对分片进行build+probe过程。

grace hash join

主流的数据库oracle，sqlserver，postgresql早就支持了hashjoin。join算法都类似，这里介绍下oracle使用的grace hash join算法。其实整个过程与mysql的hashjoin类似，主要有一点区别。当出现join_buffer_size不足时，mysql会对外表进行分片，然后再进行chj过程。但是，极端情况下，如果数据分布不均匀，导致大量的数据hash后都分布在一个分桶中，导致分片后，join_buffer_size仍然不够，mysql的处理方式是一次读分片读若干记录构建hash表，然后probe对应的外表分片。处理完一批后，清理hash表，重复上述过程，直到这个分片的所有数据处理完为止。这个过程与chj在join_buffer_size不足时，处理逻辑相同。

gracehash在遇到这种情况时，会继续分片进行二次hash，直到内存足够放下一个hash表为止。但是，这里仍然有极端情况，如果输入join条件都相同，那么无论进行多少次hash，都没法分开，那么这个时候gracehashjoin也退化成和mysql的处理方式一样。

hybrid hash join

与gracehashjoin的区别在于，如果缓存能缓存足够多的分片数据，会尽量缓存，那么就不必像gracehash那样，严格地将所有分片都先读进内存，然后写到外存，然后再读进内存去走build过程。这个是在内存相对于分片比较充裕的情况下的一种优化，目的是为了减少磁盘的读写io。目前oceanbase的hashjoin采用的是这种join方式。

mysql-join算法优化

在mysql8.0.18之前，也就是在很长一段时间内，mysql数据库并没有hashjoin，主要的join算法是nestloopjoin。simplenestloopjoin显然是很低效的，对内表需要进行n次全表扫描，实际复杂度是n*m，n是外表的记录数目，m是记录数，代表一次扫描内表的代价。为此，mysql针对simplenestloopjoin做了若干优化，下面贴的图片均来自。

blocknestloopjoin(bnlj)

mysql采用了批量技术，即一次利用join_buffer_size缓存足够多的记录，每次遍历内表时，每条内表记录与这一批数据进行条件判断，这样就减少了扫描内表的次数，如果内表比较大，间接就缓解了io的读压力。

                                                  

indexnestloopjoin(inlj)

如果我们能对内表的join条件建立索引，那么对于外表的每条记录，无需再进行全表扫描内表，只需要一次btree-lookup即可，整体时间复杂度降低为n*o(logm)。对比hashjoin，对于外表每条记录，hashjoin是一次hashtable的search，当然hashtable也有build时间，还需要处理内存不足的情况，不一定比inlj好。

batched key access

indexnestloopjoin利用join条件的索引，通过btree-lookup去匹配减少了遍历内表的代价。如果join条件是非主键列，那么意味着大量的回表和随机io。bka优化的做法是，将满足条件的一批数据按主键排序，这样回表时，从主键的角度来说就相对有序，缓解随机io的代价。bka实际上是利用了mrr特性(multirangeread)，访问数据之前，先将主键排序，然后再访问。主键排序的缓存大小通过参数read_rnd_buffer_size控制。

      

总结

mysql8.0以后，server层代码做了大量的重构，虽然优化器相对于oracle还有很大差距，但一直在进步。hashjoin的支持使得mysql优化器有更多选择，sql的执行路径也能做到更优，尤其是对于等值join的场景。虽然mysql之前对于join做过若干优化，比如nblj，inlj以及bka等，但这些代替不了hashjoin的作用。一个好用的数据库就应该具备丰富的基础能力，利用优化器分析出合适场景，然后拿出对应的基础能力以最高效的方式响应请求。

参考文档

https://en.wikipedia.org/wiki/hash_join