《MySQL 8.0.22执行器源码分析（3.2）关于HashJoinIterator》

《MySQL 8.0.22执行器源码分析（3.2）关于HashJoinIterator》

在本文章之前，应该了解的概念： 连接的一些概念、NLJ、BNL、HashJoin算法。

目录

​​关于join连接​​​​probe行保存概念​​​​Hashjoin执行流程（十分重要）​​​​HashJoinIterator成员函数讲解​​

​​1、BuildHashTable​​​​2、ReadNextHashJoinChunk​​​​3、ReadRowFromProbeIterator​​​​4、ReadRowFromProbeChunkFile​​​​5、ReadRowFromProbeRowSavingFile​​​​6、LookupProbeRowInHashTable​​​​7、ReadJoinedRow​​​​8、WriteProbeRowToDiskIfApplicable​​​​9、JoinedRowPassesExtraConditions​​​​10、RejectDuplicateKeys​​​​11、InitRowBuffer​​​​12、InitProbeIterator​​​​13、InitWritingToProbeRowSavingFile​​​​14、InitReadingFromProbeRowSavingFile​​​​15、SetReadingProbeRowState​​​​16、ReadNextJoinedRowFromHashTable​​

​​一些重要的成员变量​​

​​迭代器状态类型​​​​hash_join_buffer::HashJoinRowBuffer::hash_map_iterator​​​​hash_join_buffer::TableCollection​​​​HashJoinType​​​​m_probe_row_match_flag​​

关于join连接

该迭代器用于使用哈希匹配输入的rows。该迭代器的所有操作在内存中执行，内部连接算法如下：

1、两个输入：一个probe，一个build。总大小最小的输入当做bulid输入。我认为其实就是驱动表和被驱动表。在之前的文章中有详细的区分过程：​​javascript:void(0)​​

2、将build输入中的所有行读取到内存哈希表中。哈希表中使用的哈希key是根据join的属性计算的。如下：我们将下面语句中的"orders"作为build输入：

SELECT * FROM lineitem INNER JOIN orders ON orders.o_orderkey = lineitem.l_orderkey;

哈希值将根据列中的值进行计算key。

3、然后从probe输入中逐个读取行，对于每一行，通过probe输入计算哈希键，哈希函数与步骤2相同。

哈希键值对用于哈希表，给每个匹配生成一个输出行。此时来自probe输入的行已经位于表记录缓冲区中，哈希表中存储的存储的匹配航被返还给出处。具体是通过函数​​hash_join_buffer::StoreFromTableBuffers​​实现的。

内存哈希表的大小由系统变量控制，即join_buffer_size。如果在步骤二中内存不足，将内存中已经存在的数据使用常规哈希进行连接，其余部分使用磁盘上的哈希连接进行处理。

具体如下：

1） build输入中不适合哈希的行表被划分成给定数量的文件，称为HashJoinChunks。给两个输入创建等量的Chunks文件。然后与步骤2一样，计算得到join属性的哈希表，不过使用的是不同的哈希函数。

2）然后从probe输入中逐个读取行，在内存中的哈希表中进行匹配。同时也将这些行写入到磁盘中，因为在磁盘中可能也会存在与这些行相匹配的行。

3）当逐个probe输入读取完毕，对build和probe输入的Chunks文件对进行哈希连接。由于从build和probe输入的行数据是使用相同的哈希函数进行分区的，所以匹配的行必须位于同一个Chunks文件对中。

如果在内存中执行哈希连接，输出的顺序将与probe输入的排序相同。如果操作溢出到磁盘，就会失去合理的排序属性。

当一张表十分巨大，就需要多次read，读取probe输入文件重新加载到哈希表。

probe行保存概念

当哈希连接生成块不能完全放到内存中 或者 哈希连接不能延伸到磁盘 时。这两个共同点就是：probe输入行需要多次Read。对于一些连接类型，必须要保证同一probe行不会多次发送到客户端。probe行通过下面的步骤解决这个问题：

1、如果意识到要多次读取同一probe行，启用探测行保存。

2、当一个probe行被读取时，我们应该将该行写入一个probe行文件，因为这一行可能符合某些连接条件。如对于半连接，只保存不匹配的探测行。

3、在使用probe输入后，将交换_write_ file 和 read file 确保写入文件可以再次写入。

4、当要再次读取probe输入时，从probe行保存读取文件。

这样可以保证我们不会多次输出同一行probe row用于半连接。

关于何时启用probe行保存，具体取决与哈希连接类型HashJoinType：

IN_MEMORY ：probe行保存从未激活，因为probe输入是只读一次

SPILL_TO_DISK：如果build块文件不能全部放入内存中，就必须读取相应的probe块多次。此时启用probe行保存，并保持active，直到整个build块用完。读取一次probe块之后，交换probe行保存写入文件和probe行保存读取文件，以便从probe行保存读取文件中读取probe行。当移动到下一对区块文件，probe行保存就被停用。

IN_MEMORY_WITH_HASH_TABLE_REFILL：接着上一个情况说，一旦使用了一次probe 迭代器，就需要交换写文件和读文件。主要build输入没有被完全用完，就需要不停地执行交换文件操作，并且在每次的哈希表中填充这些文件，永远不会停用probe行保存。写文件的时候，总是写入整行。由于写入整行，所以可能只写匹配标志(匹配标志是啥？)如果在hash连接中只写匹配标志，我们将不得不多次读取probe迭代器。由于不能保证多次读取时，row的顺序是相同的。所以我们需要使用rowid作为key在查找结构中存储匹配标志。

Hashjoin执行流程（十分重要）

SELECT_LEX_UNIT::execute() ← 执行一个Query Unit |-SELECT_LEX_UNIT::ExecuteIteratorQuery |-THD_STAGE_INFO() ← 设置线程的状态为executing |-query_result->start_execution(thd) ← 设置为执行状态，Query result execution_started = true; |-query_result->send_result_set_metadata() ← 先将元数据发送给客户端 |-set_executed(); ← Unit executed = true; | |-m_root_iterator->Init() ← 所有Iterator递归Init，此处Iterator为HashJoinIterator | |-HashJoinIterator::Init() | | |-TableScanIterator::Init() | | | |-handler::ha_rnd_init() | | | |-HashJoinIterator::BuildHashTable() | | | |-TableScanIterator::Read() | | | | |-handler::ha_rnd_next() | | | | | |-ha_innobase::rnd_next() | | |-HashJoinIterator::InitProbeIterator() | | |-TableScanIterator::Init() | | | |-handler::ha_rnd_init() | | | | |-ha_innobase::rnd_init() | | ###while循环读取数据### |-m_root_iterator->Read() ← 所有Iterator递归Read，此处Iterator为HashJoinIterator | |-HashJoinIterator::Read() | |-HashJoinIterator::ReadRowFromProbeIterator() | | |-TableScanIterator::Read() | | | |-handler::ha_rnd_next() | | | | |-ha_innobase::rnd_next() | |-query_result->send_eof()

HashJoinIterator成员函数讲解

这里，不对其继承的成员进行讲解，详细可以回顾​​MySQL 8.0.22执行器源码分析（3.1）关于RowIterator​​

1、BuildHashTable

从build输入中读取所有行，然后将这些行存储到内存中的哈希表中。如果哈希表已满，则将其余的行写出到磁盘上的块文件中。

2、ReadNextHashJoinChunk

从下一个chunk 文件中读取所有行到内存中的哈希表

3、ReadRowFromProbeIterator

将probe迭代器输入中的一行读取到表的记录缓冲区中。如果此时已经溢出到磁盘上，那么该行也会被写到磁盘上的一个块文件中。

当表的记录缓冲区有一行已经ready，将迭代器状态设置为READING_FIRST_ROW_FROM_HASH_TABLE

当probe输入中没有行需要处理，将迭代器状态设置为LOADING_NEXT_CHUNK_PAIR.

4、ReadRowFromProbeChunkFile

从当前的probe chunk 文件读取一行数据到表的记录缓冲区。

状态设置与3一致。

5、ReadRowFromProbeRowSavingFile

从probe行保存文件中读取一行到表的记录缓冲区

6、LookupProbeRowInHashTable

为了匹配从build输入来的行数据，在哈希表中做一次查找。查找是通过计算来自probe输入的join key

，并且使用 join key 在哈希表中做查找。如果join key有一个或者更多的SQL NULL，行将不能被匹配，所以将会跳过这些行，并且迭代器的状态会被设置为READING_FIRST_ROW_FROM_HASH_TABLE。

当该函数被调用后，ReadJoinedRow函数将返回false，直到没有更多的匹配行去计算join key。

7、ReadJoinedRow

从哈希表中取出下一个匹配行，然后将该行放入build表的记录缓冲区。该函数希望LookupProbeRowInHashTable应该先于本函数运行。调用者必须调用本函数，只要本函数返回false。

返回值0表示一个匹配被找到并且row数据被放入build表记录缓冲区。

返回值-1表示哈希表中没有匹配行了。

8、WriteProbeRowToDiskIfApplicable

从probe输入读取最后一行数据到磁盘上的chunk文件。

对于内连接来说，我们必须将所有的probe行都读取到chunk文件中，因为我们需要将该行与build输入中写到chunk文件的行进行匹配。

对于半连接来说，我们只能将与哈希表中任何行都不匹配的probe行写入。在哈希表中写入probe行数据去匹配可能会导致该行数据被多次返回。

9、JoinedRowPassesExtraConditions

如果最后连接的行通过了所有的附加条件，返回true

10、RejectDuplicateKeys

如果返回值为true，拒收相同的keys到哈希表中。

对于半连接和反连接只对哈希表中第一个匹配的行感兴趣，所以我们可以为了省内存去避免存储相同的key。然而，一些情况下这个方法不能被采用，例如哈希表中第一个匹配航可能在一些意外情况失效。

11、InitRowBuffer

清除行buffer并且将多有迭代器重新指向它。当重新初始化rowbuffer时会多次调用。

12、InitProbeIterator

在一开始，准备从probe迭代器中读取数据，并且要保证批处理模式是可用的。迭代器状态不变。

13、InitWritingToProbeRowSavingFile

确保probe行保存是有效的，并且准备写入probe行保存文件。

14、InitReadingFromProbeRowSavingFile

从probe行保存文件中读取数据之前初始化，文件被倒回到初始状态。

15、SetReadingProbeRowState

设置迭代器状态READING_ROW_FROM_PROBE_，该状态取决于我们执行的哈希连接的类型。

16、ReadNextJoinedRowFromHashTable

从哈希表中读取一个已经连接的行，并且判断它是否通过一些意外情况。如果需要的话，最后一行probe行会被写到磁盘上。

返回值：

-1 ： 哈希表中没有匹配行

0 ：一个已连接的行已经准备了

1 ： 一个错误发生了

一些重要的成员变量

迭代器状态类型

由此我们可以看出一个row数据可能从iterator、chunk file、row saving file中读取，他们都属于input。

// We are reading a row from the probe input, where the row comes from the iterator.READING_ROW_FROM_PROBE_ITERATOR,// We are reading a row from the probe input, where the row comes from a chunk file.READING_ROW_FROM_PROBE_CHUNK_FILE,// We are reading a row from the probe input, where the row comes from a probe row saving file.READING_ROW_FROM_PROBE_ROW_SAVING_FILE,// The iterator is moving to the next pair of chunk files, where the chunk file from the build input will be loaded into the hash table.LOADING_NEXT_CHUNK_PAIR,// We are reading the first row returned from the hash table lookup that also passes extra conditions.READING_FIRST_ROW_FROM_HASH_TABLE,// We are reading the remaining rows returned from the hash table lookup.READING_FROM_HASH_TABLE,// No more rows, both inputs are empty.END_OF_ROWS

hash_join_buffer::HashJoinRowBuffer::hash_map_iterator

用于在哈希表中读取row数据的迭代器。

hash_join_buffer::HashJoinRowBuffer::hash_map_iterator m_hash_map_iterator; hash_join_buffer::HashJoinRowBuffer::hash_map_iterator m_hash_map_end;

hash_join_buffer::TableCollection

该结构包含哈希连接所需的表和列。在构造函数中过滤掉不需要的行/列。我们需要知道哪些表属于每个迭代器，以便在需要时计算连接键。

hash_join_buffer::TableCollection m_probe_input_tables; hash_join_buffer::TableCollection m_build_input_tables;

HashJoinType

对应三个情况

enum class HashJoinType { IN_MEMORY, SPILL_TO_DISK, IN_MEMORY_WITH_HASH_TABLE_REFILL };

IN_MEMORY：在内存中做所有操作，并且没有任何对哈希表的重新填充操作。每个输入都只读一次，不会对磁盘写入任何数据。

SPILL_TO_DISK：输入build输入不能全部放在内存中，将两个输入都写入一组chunk文件。在join属性上使用hash函数对两个输入进行分区，确保可以在同一组chunk文件中找到匹配的行。然后将每对chunk文件作为内存中的哈希连接进行处理。

IN_MEMORY_WITH_HASH_TABLE_REFILL：如果不允许溢出到磁盘上操作，并且build输入不能完全放入内存，就启用此选项。我们尽可能多地将build输入读入到哈希表中。然后读取整个probe输入，然后寻找哈希表中匹配的行，当probe输入返回eof时，哈希表将用第一次没有装入的行重新填充，再次读取整个probe输入，并重复此操作，直到整个build输入都使用完。

m_probe_row_match_flag

该标志为 ： 从chunk文件读取的最后一行probe行的匹配标志。

如果外连接使用到了磁盘，则需要这个标志。probe可能与我们尚未载入内存的build中的行相匹配。因此，当从chunk文件中读取probe行时，此变量将保留匹配标志。此标志必须为类成员，因为一个probe行可能与哈希表中的多个行匹配，每个匹配行之间的执行将超出迭代器Read函数的范围，导致本地的匹配标志丢失上次的信息。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。