mysql hash join

mysql 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的复杂度