MySQL Hash Join实现分析
提示：公众号展示代码会自动折行，建议横屏阅读
「前言」
连接操作是一种数据库中最基本的操作，连接算法的执行效率直接影响到整个数据库的效率、吞吐和资源。通常商业数据库系统一般有三种主流的连接实现：Nested Loop Join、Hash Join和Sort Merge Join。本文概述目前主流的Hash Join实现方式，以及分析MySQL中Hash Join的实现方式。
MySQL 8.0.18 版本增加了对Hash Join算法的支持，在此之前，连接算法仅支持嵌套循环连接 Nested Loop Join。Nested Loop Join 是一个双重循环的结构，外层循环遍历外表(outer table，又称驱动表、左表)，对于外表的每一行记录，内层循环遍历内表（inner table，又称被驱动表、右表）来判断是否符合连接条件。假设外表存储在M个page上有m条记录，内表存储在N个page上有n条记录。可以得知，Nested Loop Join的IO代价为M+(m*N)。
Hash Join 可以通过Hash的方式降低复杂度：根据连接条件对外表建hash表，对于内表的每一行记录也根据连接条件计算hash值，只需要验证对应hash值是否能否匹配就完成了连接操作。那么，外表分别读了两遍写了一遍，而内表只遍历了“一趟”，IO代价为3*M+N。这种简单直接的哈希连接称为Basic Hash Join。
如果外表较大，或者可供Hash Join计算使用的内存过小，以至于外表不能全部加载到内存，就需要相对复杂的分批处理。Grace Hash Join利用多层Hash，使得切分后的分片能够存储于内存中。On-disk Hash Join不断迭代左表，每当填充满内存时暂停迭代左表，接下来探测完所有右表数据。清空内存后继续迭代左表，反复上述流程直到处理完所有左表中的数据。我们结合MySQL的实现，具体介绍这几种哈希连接的实现方式。
「第一部分 几种Hash Join概述」
参考MySQL介绍Hash Join的示例，例如SQL：
1234 | SELECT given_name,country_nameFROM persons JOIN countries ON persons.country_id= countries.country_id; |
|---|
1.1 Basic Hash Join（In-memory Hash Join）
内存能够存储外表时，可以直接依赖内存执行Basic Hash Join，所以又被称为In-memory Hash Join。执行Hash Join一般包括两个过程，创建hash表的build过程，和探测hash表的probe过程。
1). build过程：遍历外表，以连接条件为key，查询需要的列作为value创建hash表。
2). probe过程：逐行遍历内表，对于内表的每行记录，根据连接条件计算hash值，并在hash表中查找。如果匹配到外表的记录，则输出，否则跳过，直到遍历完成所有内表的记录。
如图所示，左侧是build过程，对应的countries表是外表；右侧是probe过程，对应的persons表是内表。其中，country_id是连接条件，两表由此计算hash值。
1.2 On-disk Hash Join
Basic Hash Join的限制在于内存需要装载整个外表。所以，一般选择参与join的两个表(经过其他条件过滤后的结果集)中较小的表作为外表，使得内存更容易存放hash表。在MySQL中，Join可以使用的内存通过参数join_buffer_size控制。如果维护外表的hash table所需的内存超过join_buffer_size，那么Basic Hash Join就需要调整为On-disk Hash Join。
On-disk Hash Join为了控制内存占用，将外表分成若干片段执行，使得内存能够容纳单个分片。每当外表填充满hash表时就截断build过程。然后，针对每个被截断的分片，都执行一遍内表全量数据的Proble过程。假设外表分成了k片，那么将扫描k次内表，总体IO代价是3*M+k*N。
这种“多趟”执行的方式导致内表IO开销较大，整体性能差。但是，对于上层算子需要尽快返回数据时就不见得性能差。比如，上层存在Limit算子，只需要5行计算结果，可能第一个分段就能产生所需的5行记录，相当于外表只做了部分的build工作，内表也在产生5行结果以后停止了probe过程。
想要避免“多趟”操作时，Build阶段可以用hash算法将数据存入磁盘中对应的分区文件中；然后在probe阶段，对于内表使用同样的hash算法进行分区。由于使用分片hash函数相同，那么key相同(join条件相同)必然在同一个分片编号的分区文件中。接下来，再对外表和内表中相同分片编号的数据进行Basic Hash Join计算，所有分片计算完成后，整个join过程结束。这种算法的代价是，外表和内表在build阶段进行一次读IO和一次写IO，在probe阶段进行了一次读IO，所以整体IO开销是3*(M+N)。相对于之前需要k次扫描内表的方式，当前算法更优。
在MySQL8.0.22中，前者和后者两种算法都有涉及，具体实现我们在后面展开。
左上侧图是外表的build+分片过程，右上侧图是内表的Probe+分片存储过程，最下面的图是对分片进行probe过程。
1.3 Grace Hash Join
Grace Hash Join能够解决内存不足下的连接问题，利用分治思想，先将外表和内表按哈希，切分到不同分片。然后在外表和内表对应的分片上做 Basic Hash Join。如果对应分片仍然超过内存大小则对分片继续执行一次 Grace Hash Join，直到可以存入内存。
这个过程与MySQL中的Hash Join类似，主要的区别在于内存不足时的解决方法。当出现join_buffer_size不足时，MySQL会对外表进行分片，然后再进行Basic Hash Join。但极端情况下，如果数据严重倾斜，可能哈希后的分片仍然超过可用内存大小。MySQL的规避方式是参考On-disk Hash Join的方式分批处理：读满hash表后停止build过程，然后执行一趟probe。处理这批数据后，清空hash表，在上次build停止的位点继续build过程来填充hash表，填充满再做一趟内表分片完整的probe。直到处理完所有build数据。
Grace Hash Join在遇到这种情况时，继续执行一次 Grace Hash Join，直到可以存入内存。
1.4 Hybrid Hash Join
历史经验告诉我们，磁盘IO和重复计算应尽量避免。Basic Hash Join 完全利用内存，避免了磁盘IO；同时，数据只看一遍，避免了重复计算。Grace Hash Join 解决了内存不足问题，但对于磁盘IO优化不足。Hybrid Hash Join 正是继承Grace Hash Join的分治思想来解决内存不足问题，又学习Basic Hash Join 高效利用内存的优势：在Build阶段，在内存中尽可能保留一些完整的分片，不能够被保存在内存中的分片才被落盘；在Probe时，内存中完整的外表分片可以被直接探测，这部分分片做到了和Basic Hash Join一样的效率。参考Grace Hash Join，其余的不能完整存放在内存中的分片再继续处理。从Build阶段最小化磁盘IO的角度，On-disk Hash Join的章节中可以发现MySQL中也保留了一份内存大小的hash表，避免了这部分数据的IO。
接下来，我们介绍MySQL中Hash Join的使用场景及具体实现方法。
「第二部分 可使用场景（基于规则）」
等值连接、笛卡尔积、非等值连接（容易产生误解）
2.1 join on上的等值与非等值条件
hash join将join on上条件分为了等值连接条件和非等值连接条件
- 等值连接条件用来构建两表连接时使用的hash 函数
- 非等值连接条件作为额外的表达式（extra conditions）
mysql> explain format = tree select * from tt1 left join tt2 on tt1.c2 = tt2.c2 and tt1.c1 > tt2.c1;+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| EXPLAIN |+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| -> Left hash join (tt2.c2 = tt1.c2), extra conditions: (tt1.c1 > tt2.c1) (cost=1.13 rows=6) -> Table scan on tt1 (cost=0.45 rows=2) -> Hash -> Table scan on tt2 (cost=0.28 rows=3) |+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+1 row in set (0.00 sec)hash join允许用户仅指定非等值连接条件，这时hash join的等值连接条件为no condition，extra conditions（存储非等值连接条件）
mysql> explain format = tree select * from tt1 left join tt2 on tt1.c1 > tt2.c1;+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| EXPLAIN |+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| -> Left hash join (no condition), extra conditions: (tt1.c1 > tt2.c1) (cost=1.13 rows=6) -> Table scan on tt1 (cost=0.45 rows=2) -> Hash -> Table scan on tt2 (cost=0.28 rows=3) |+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+1 row in set (0.00 sec)2.2 内连接时，非等值连接条件构建成单独的Filter iterator
mysql> explain format = tree select * from tt1 inner join tt2 on tt1.c2= tt2.c2 and tt1.c1 > tt2.c1;+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| EXPLAIN |+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| -> Filter: (tt1.c1 > tt2.c1) (cost=1.30 rows=2) -> Inner hash join (tt2.c2 = tt1.c2) (cost=1.30 rows=2) -> Table scan on tt2 (cost=0.18 rows=3) -> Hash -> Table scan on tt1 (cost=0.45 rows=2) |+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+1 row in set (0.00 sec)即使inner join仅有一个非等值连接条件
mysql> explain format = tree select * from tt1 inner join tt2 on tt1.c1 > tt2.c1;+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| EXPLAIN |+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| -> Filter: (tt1.c1 > tt2.c1) (cost=1.30 rows=2) -> Inner hash join (no condition) (cost=1.30 rows=2) -> Table scan on tt2 (cost=0.18 rows=3) -> Hash -> Table scan on tt1 (cost=0.45 rows=2) |+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+1 row in set (0.00 sec)对于OR谓词连接的join on条件，即使都是等值连接条件，都作为整体放入extra conditions（外连接）或Filter iterator（内连接），这里实际缺少union的改写（or 改为union 连接的两个SQL）
mysql> explain format = tree select * from tt1 inner join tt2 on tt1.c2 = tt2.c2 or tt1.c1 = tt2.c1;+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| EXPLAIN |+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| -> Filter: ((tt2.c2 = tt1.c2) or (tt2.c1 = tt1.c1)) (cost=1.30 rows=3) -> Inner hash join (no condition) (cost=1.30 rows=3) -> Table scan on tt2 (cost=0.21 rows=3) -> Hash -> Table scan on tt1 (cost=0.45 rows=2) |+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+1 row in set (0.00 sec)
mysql> explain format = tree select * from tt1 left join tt2 on tt1.c2 = tt2.c2 or tt1.c1 = tt2.c1;+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| EXPLAIN |+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+| -> Left hash join (no condition), extra conditions: ((tt2.c2 = tt1.c2) or (tt2.c1 = tt1.c1)) (cost=1.13 rows=6) -> Table scan on tt1 (cost=0.45 rows=2) -> Hash -> Table scan on tt2 (cost=0.28 rows=3) |+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+1 row in set (0.00 sec)「第三部分 自动使用的场景」
目前，MySQL 8.0.22中采用基于规则的判断来决定使用何种连接算子。
/**For a given slice of the table list, build up the iterator tree correspondingto the tables in that slice. It handles inner and outer joins, as well assemijoins (“first match”).
The join tree in MySQL is generally a left-deep tree of inner joins,so we can start at the left, make an inner join against the next table,join the result of that against the next table, etc..**/
AccessPath *ConnectJoins(){ // sql_executor.cc
// If this is a BNL, we should replace it with hash join. We did decide // during create_access_paths that we actually can replace the BNL with a // hash join, so we don't bother checking any further that we actually can // replace the BNL with a hash join. const bool replace_with_hash_join = //标记是否能够转为hash join UseHashJoin(qep_tab) && !QueryMixesOuterBKAAndBNL(qep_tab->join()) && !PushedJoinRejectsHashJoin(qep_tab->join(), left_tables, right_tables, JoinType::INNER);
//…………
//最终贪心生成最优计划 if (is_bka) { path = CreateBKAAccessPath(); } else if(replace_with_sort_merge_join) { // TO DO: case for interesting order } else if (replace_with_hash_join) { // The numerically lower QEP_TAB is often (if not always) the smaller // input, so use that as the build input. path = CreateHashJoinAccessPath();
// Attach any remaining non-equi-join conditions as a filter after the join. path = PossiblyAttachFilter(); } else { path = CreateNestedLoopAccessPath(); SetCostOnNestedLoopAccessPath(); }
}MySQL 8.0.22中已经存在Hash Join代价的计算模型，只是非常不完善的计算方式，计算代价只用作返回给上层算子（及explain输出）并未实际影响连接算子的选择。
double joined_rows = outer->num_output_rows * inner->num_output_rows;path->num_output_rows = joined_rows * pos_outer->filter_effect;path->cost = inner->cost + pos_outer->read_cost +cost_model.row_evaluate_cost(joined_rows)「第四部分 生成Hash Join路径」
4.1 连接表达式
连接表达式归类为：
- 等值连接条件（hash join conditions），用作构建Hash Key，用来构建和探测Hash Table
- 其它条件（extra conditions），包括非等值连接条件和其它不能下压的单表条件
4.2 是否允许Hash Table落盘
左表（build/right input table）构建Hash Table时，是否允许落盘直接决定了Hash Join返回第一行的时间：
- 不允许落盘时，需要立即执行Probe探测当前Hash Table，从而“尽快”返回上层算子执行结果；探测完成一遍后，需要重复填充Hash Table，探测再重新执行
- 允许落盘时，左表“一次性”执行完成build hash table 过程，从而“较晚”返回上层算子执行结果，但是探测过程可以“一口气”执行完成
是否允许allow_spill_to_disk主要基于规则：上层算子是否期望所有结果集。具体来说：
- 如果查询中有Limit，查询优化器将不允许哈希连接溢出到磁盘。这样做的效果是，hash join将更早地开始生成结果行，从而更快地达到Limit的结果。即，Hash Join不落盘时需要立即处理当前Hash Table中的数据，形成连接结果来返回上层，而不是对build input table（左表，构建hash table）全部构建好以后才探测。理想情况下，这应该在优化过程中决定。
- 但是有两种情况查询优化器总是允许Hash Join溢出到磁盘，即查询中有分组或排序时。因为在这些情况下，上层的迭代器（Group By & aggregation）很可能会以任何方式消耗整个结果集。换句话说，上层很可能需要所有Hash Join产生的结果集，而不是limit那种几行就可能满足的情况。
- 如果此表是pushed join query的一部分，则必须读取从属子表中的行，同时定位子表所依赖的pushed祖先表中的行。所以，不允许中间落盘。
4.3 Filter算子构建
在#1.2.节中已经展示了需要额外构建Filter iterator的情况
「第五部分 执行流程」
5.1 整体流程
volcano style iterator：init() →build_hash_table() 我们将这个过程标记为①
read()，其中read()具体实现了一个状态机的转换过程，我们将具体的实现标记为②~⑥
int HashJoinIterator::Read() {for (;;) { switch (m_state) { case State::READING_ROW_FROM_PROBE_ITERATOR: ReadRowFromProbeIterator ② case State::READING_FIRST_ROW_FROM_HASH_TABLE: case State::READING_FROM_HASH_TABLE: ReadNextJoinedRowFromHashTable(); ③ case State::LOADING_NEXT_CHUNK_PAIR: ReadNextHashJoinChunk() ④ case State::READING_ROW_FROM_PROBE_CHUNK_FILE: ReadRowFromProbeChunkFile() ⑤ case State::READING_ROW_FROM_PROBE_ROW_SAVING_FILE: ReadRowFromProbeRowSavingFile() ⑥}5.2 具体实现
为了在内存可控的情况下支持大表连接，Hash Join实现类似Grace Hash Join，依赖join_buffer_size（system variable）参数控制内存中hash table大小，依赖allow_spill_to_disk（查询优化器控制）参数控制是否允许执行过程中落盘，这两个参数直接影响了hash join的实现的方式。前者决定了何时需要停止往内存中加载数据，后者决定了Hash Join执行方式以“多趟”的block hash join还是以类似On-disk Hash Join方式执行。
5.2.1 Build Hash Table
总计有三个地方会调用HashJoinIterator::BuildHashTable() 函数，分别在Hash Table Iterator::Init()时、HashJoinIterator::ReadRowFromProbeIterator() 时和HashJoinIterator::ReadRowFromProbeRowSavingFile() 时，后两者在Probe阶段执行，我们可以先关注算子Init时执行的build hash table。
具体来看
bool HashJoinIterator::BuildHashTable() { //当不允许hash table写盘时（allow_spill_to_disk=false），完整的执行hash join可能会需要“多趟”填充内存的hash table（可以理解为是否需要“多趟”由Limit等上层算子决定，即第一趟填充hash table后，probe阶段如果返回了足够Limit使用的行，则不再需要“多趟”） //如果确需“多趟”执行，需要关注build/left input table最后的一行返回值情况： // Restore the last row that was inserted into the row buffer. This is // necessary if the build input is a nested loop with a filter on the inner // side, like this: // // +---Hash join---+ // | | // Nested loop t1 // | | // t3 Filter: (t3.i < t2.i) // | // t2 // // 直观来说，为了正确返回左表的下一行记录，需要还原左表recode0当时的状态，比如t3.i，这时调用左表的read（）时，才能正确找到t2的下一行匹配的位置
for (;;) { // Termination condition within loop. //一直迭代左表，直到完成或当前hash table填满（>join_buffer_size） int res = m_build_input->Read();
if (res == -1) { return false; //没有其他行，完成 }
const hash_join_buffer::StoreRowResult store_row_result = m_row_buffer.StoreRow(thd(), reject_duplicate_keys, store_rows_with_null_in_join_key); //构建 hash key，存储<hash key, row> switch (store_row_result) { case hash_join_buffer::StoreRowResult::ROW_STORED: //继续，不超join_buffer_size阈值 break; case hash_join_buffer::StoreRowResult::BUFFER_FULL: { //超阈值 if (!m_allow_spill_to_disk) { //判断是否允许 if (m_join_type != JoinType::INNER) { // 需要注意，外连接时，未产生连接的记录仍需要保留，以留给下一趟 hash table探测 InitWritingToProbeRowSavingFile(); } return false; //开始Probe }
if (InitializeChunkFiles() { //根据估计值构建chunk file，目标使得最大的文件不超过 join_buffer_size大小 return true; }
//这里有两种方式，作者选的是：将build table 剩余的行 写出到块文件。然后，将在Proble table是否与已写入哈希表的行匹配后也将Probe的记录写入块文件 //另一种方法将所有行都写到块文件。Probe table也写到磁盘。但作者不想浪费已经存储在内存中的行。 if (WriteRowsToChunks(thd(), m_build_input.get(), m_build_input_tables, //这里m_build_input.get() 直接将bulid input指针传给WriteRowsToChunks（），使其直接独立完成剩余所有行的处理 m_join_conditions, kChunkPartitioningHashSeed, &m_chunk_files_on_disk, true /* write_to_build_chunks */, false /* write_rows_with_null_in_join_key */, m_tables_to_get_rowid_for, &m_temporary_row_and_join_key_buffer)) { return true; }
return false; } } }}另外，在构建hash key 和存储当前row时，作者使用了重用了同一段缓冲区
static bool WriteRowToChunk() { bool null_in_join_key = ConstructJoinKey(thd, join_conditions, tables.tables_bitmap(), join_key_and_row_buffer);//这里的join_key_and_row_buffer根据join_conditions(等值连接条件)提取了拼接的join key
const uint64_t join_key_hash = MY_XXH64(join_key_and_row_buffer->ptr(), join_key_and_row_buffer->length(), xxhash_seed); //构建hash key const size_t chunk_index = join_key_hash & (chunks->size() - 1); ChunkPair &chunk_pair = (*chunks)[chunk_index]; if (write_to_build_chunk) { return chunk_pair.build_chunk.WriteRowToChunk(join_key_and_row_buffer, //虽然传了join_key_and_row_buffer，但是WriteRowToChunk()函数中会重置，并拷贝表缓存中的记录到join_key_and_row_buffer，然后拷贝到对应的文件中 row_has_match); } else { return chunk_pair.probe_chunk.WriteRowToChunk(join_key_and_row_buffer, row_has_match); }}首先根据等值连接条件构建Key，然后拼接一整行row，最后存储当前<key,row>到hash table。8.0.23前的代码比较容易理解：
StoreRowResult HashJoinRowBuffer::StoreRow(THD *thd, bool reject_duplicate_keys,bool store_rows_with_null_in_condition) { m_buffer.length(0); for (const HashJoinCondition &hash_join_condition : m_join_conditions) { bool null_in_join_condition = hash_join_condition.join_condition()->append_join_key_for_hash_join( thd, m_tables.tables_bitmap(), hash_join_condition, &m_buffer); //首先根据所有的等值连接条件构建Key } const size_t join_key_size = m_buffer.length(); uchar *join_key_data = nullptr; if (join_key_size > 0) { join_key_data = m_mem_root.ArrayAlloc<uchar>(join_key_size); memcpy(join_key_data, m_buffer.ptr(), join_key_size); //为了重用m_buffer这个变量，这里做了一次拷贝，感觉上并不需要（直接存成单独的Key 和 row） } if (StoreFromTableBuffers(m_tables, &m_buffer)) { //m_buffer被写进所有列数据， StoreFromTableBuffers函数会首先重置m_buffer，然后处理blob字段、和其它字段，类似于filesort，为了内存开销将列做pack return StoreRowResult::FATAL_ERROR; }
const size_t row_size = m_buffer.length(); uchar *row = nullptr; if (row_size > 0) { row = m_mem_root.ArrayAlloc<uchar>(row_size); memcpy(row, m_buffer.ptr(), row_size); //这里又做了一次拷贝 } m_last_row_stored = m_hash_map->emplace(Key(join_key_data, join_key_size), //执行插入<Key,row> BufferRow(row, row_size)); if (m_mem_root.allocated_size() > m_max_mem_available) { //插入后判断空间 return StoreRowResult::BUFFER_FULL; }}这里有明显的多次拷贝代价，8.0.23版本中已经做了优化。StoreFromTableBuffers拆分为两个函数；一个调整字符串缓冲区大小，另一个实际写入值。后者可以被重用，以便直接写入MEM_ROOT，减少重复拷贝问题。
5.2.2 Probe Hash Table
Probe阶段入口函数利用状态机来控制具体的调用流程，状态转换如下
从流程②开始执行，读到内表(右表，probe_input)一行数据后，在HashTable中定位当前行匹配的区间，用迭代器的begin和end表示，并交给流程③。
③中负责迭代begin到end，判断是否符合额外的条件（extraConditions）。这时候决定如何对外输出结果：inner 和outer符合条件的行对外输出并保存在Saving file；semi join则直接输出一行结果。
Probe过程中有两点实现比较难理解，一点是ReadRowFromProbeRowSavingFile，另外一点是外连接的实现。
⑥ReadRowFromProbeRowSavingFile有两个作用场景，服务于外连接：
- 在做On-disk Hash Join时，对于内存仍然保存不下一个chunk时
- 在做‘多趟’ Basic Hash Join时
先处理当前已经加载到Hash Table中的记录，Probe对应的probe.chunk_file（场景1）或probe_input_table(场景2）。当连接类型为Semi Join和Anti Join并且已经在Hash Table中找到了匹配的记录时，即当前Probe的记录能明确如何处理，所以我们无需关心未加载到Hash Table中的数据即可处理当前记录，即当前记录只需要“看”这一遍。除此之外（内连接、外连接、半连接但未匹配），每行记录仍有可能与当前不在Hash Table中的记录存在匹配，所以暂时存储在ReadRowFromProbeRowSavingFile中。等到Probe侧全部探测结束，这时Probe中需要“再看一次”的记录也已经存储到了ReadRowFromProbeRowSavingFile中。接下来，Hash Table清空，继续从build.chunk_file上次填充满的位置(场景1）或Build_input_table（场景2）加载到Hash Table，这时候只需要探测ReadRowFromProbeRowSavingFile而不是整个Probe.chunk_file或Probe_input_table。
外连接的实现：
从Probe过程看，有三类Probe路径：Probe_input_table(ReadRowFromProbeIterator，即基表）、Probe.chunk_file(READING_ROW_FROM_PROBE_CHUNK_FILE，即On-disk Hash Join 分片）和Probe.ReadRowFromProbeRowSavingFile(ReadRowFromProbeRowSavingFile，过程⑥）。
根据是否能立即输出结果，可以分为两类：
- 前两种，在不存在第三种时（On-disk Hash Join能够存入内存 或 Basic Hash Join build_input能一次存入内存），可以直接输出结果，否则外连接需要处理第三种路径才能输出结果
- 第三种，在过程⑥中，每次加入ProbeRowSavingFile时，标记了此行记录是否被匹配过，这时才能清楚如何处理每一行记录是否置NULL输出
这里会看到m_build_input→SetNullRowFlag，只会出现在build_input，是因为在查询优化阶段已经调整了连接顺序。例如 T1 left join T2，这时会在T2侧构建Hash Table（即上文build_input)，T1探测。而T1 right join T2，会被转换成T2 left join T1。所以，置NULL操作只需要出现在build_input侧。对于Full Outer Join/ Full Join，MySQL不支持，所以Hash Join也并未实现。
我们以一个例子来说明外连接的执行过程，例如：
Table A | ||
|---|---|---|
a | b | |
记录1 | 1 | 1 |
记录2 | 2 | 2 |
Table B | ||
|---|---|---|
a | b | |
记录1 | 1 | 1 |
记录2 | 2 | 2 |
SQL：SELECT * FROM A LEFT JOIN B ON A.a = B.a; 假如内存Hash表只能存一行记录，那么Build过程Hash表中存储一行。（这里假设hash 函数是%10）
HashTable | |
|---|---|
hash(a) | value(a,b) |
1 | (1,1) |
Probe Table B时， 1）读到 B的记录1，已存在连接，不需要存储到ProbeRowSavingFile 2）读到 B的记录2，需要存储到ProbeRowSavingFile，因为不确定Table A剩余的没存储在HashTable中的记录是否还存在a=2的值。
Probe结束后，清空HashTable后再填充HashTable，加入Table A中的记录2：
HashTable | |
|---|---|
hash(a) | value(a,b) |
2 | (2,2) |
接下来探测ProbeRowSavingFile，而无需重新做一遍整个Probe input。
「第六部分 总结」
从MySQL 8.0.18到8.0.27，Hash Join不断优化，已经初具雏形，填补了Nested Loop Join的不足。对于大表连接、选择率比较低的连接，以及Nested Loop Join无法构建ref的场景，Hash Join有明显的性能优势。但是，现有的Hash Join仍然比较原始，在Hash Table存储、磁盘对应分片的探测、探测计算下推方面还有很多提升的空间。
腾讯数据库技术团队对内支持QQ空间、微信红包、腾讯广告、腾讯音乐、腾讯新闻等公司自研业务，对外在腾讯云上依托于CBS+CFS的底座，支持TencentDB相关产品，如TDSQL-C(原CynosDB)、TencentDB for MySQL(CDB)、CTSDB、MongoDB、CES等。腾讯数据库技术团队专注于持续优化数据库内核和架构能力，提升数据库性能和稳定性，为腾讯自研业务和腾讯云客户提供“省心、放心”的数据库服务。此公众号旨在和广大数据库技术爱好者一起推广和分享数据库领域专业知识，希望对大家有所帮助。