在本文章之前，應該了解的概念：
連接的一些概念、NLJ、BNL、HashJoin算法。

關于join連接

該迭代器用于使用哈希匹配輸入的rows。該迭代器的所有操作在內存中執行，內部連接算法如下：

1、兩個輸入：一個probe，一個build。總大小最小的輸入當做bulid輸入。我認為其實就是驅動表和被驅動表。在之前的文章中有詳細的區分過程：https://blog.csdn.net/qq_42604176/article/details/115495328?spm=1001.2014.3001.5501

2、將build輸入中的所有行讀取到內存哈希表中。哈希表中使用的哈希key是根據join的屬性計算的。如下：我們將下面語句中的"orders"作為build輸入：

   SELECT * FROM lineitemINNER 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函數的范圍，導致本地的匹配標志丟失上次的信息。