mysql8.0中關于hash join的檔案有以下幾個，一個個來分析。
mysql8.0 hash join源碼分析hash_join_chunkhash_join_bufferhash_join_iterator
hash_join_chunk
HashJoinChunk是用來存儲行并落盤的類型，表分區成小檔案時也可以用。
将列寫入 HashJoinChunk 時，我們使用 StoreFromTableBuffers 将必要的列轉換為适合存儲在磁盤上的格式。
友善的是，StoreFromTableBuffers 建立了一個連續的位元組範圍和相應的長度，可以輕松有效地将其寫到檔案中。從檔案中讀回行時，LoadIntoTableBuffers() 用于将行放回表記錄緩沖區。
具體用法如下：
HashJoinChunk chunk;
// 初始化chunk來儲存給定表的資料，比對标志設定為false
// 第一個參數用來指定存儲的哪張表的資料，第二個參數用來指定每行需不需要有比對标志
chunk.Init(tables, /*uses_match_flags=*/false);
// 表和chunk之間複制資料用的緩沖區
String buffer;
while (iterator->Read() == 0) {
// 将buffer中記錄的資料轉到chunk中
// 如果這個chunk被初始化為比對标志為true,我們會在行前加一個比對标志
chunk.WriteRowToChunk(&buffer, /*matched=*/false);
};
// 準備讀取chunk中的第一行資料
chunk.Rewind();
bool match_flag;
// 将chunk中的資料導到buffer中
// 如果chunk被初始化為使用比對标志，則行讀取的比對标志将存儲在“match_flag”中。
chunk.LoadRowFromChunk(&buffer, &match_flag);
HashJoinChunk擁有幾個接口：
// 初始化接口
bool Init(const pack_rows::TableCollection &tables, bool uses_match_flags);
// 傳回chunk中存儲的行數
ha_rows num_rows() const { return m_num_rows; }
// 将row寫入chunk
bool WriteRowToChunk(String *buffer, bool matched);
// 從chunk中讀入row
bool LoadRowFromChunk(String *buffer, bool *matched);
//重新整理檔案緩沖區，并準備讀取檔案。
bool Rewind();
看了一下WriteRowChunk的源碼，思路還是很清楚的：
hash_join_buffer
HashJoinBuffer是用來存儲一批行資料的。
行資料會存儲在哈希表中，HashJoinBuffer會維護自己的MEM_ROOT，所有資料都會配置設定在這裡。
考慮下面的sql:
SELECT t1.data FROM t1 JOIN t2 ON (t1.key = t2.key);
假設表“t2”存儲在 HashJoinBuffer 中。這種情況下，t2.key就将作為哈希表鍵值，如果on條件中有多個等式，那麼這些等式将一起組合為哈希表的鍵值。
使用函數接口 StoreFromTableBuffers來存儲行資料。
HashJoinBuffer能存儲的資料量由參數join_buffer_size來限制，當然，為了檢查資料量是不是超過join_buffer_size,可能會需要一些更多的記憶體空間。
哈希鍵值是由join的on條件來決定的，比如 (t1.col1 = t2.col1 AND t1.col2 = t2.col2)，那麼哈希鍵值就是(col1, col2)，實際上轉成什麼類型也是由join條件決定的，比如有字元串和整數，那麼整數就會被轉為字元串存儲。是以應該使用共有的結構來比較，這裡就直接一個個字元（byte-by-byte）來哈希和比較，存儲的時候也是如此。
對于類似UPPER(t1.col1) = UPPER(t2.col1)這種on條件，會把UPPER(t1.col1)作為哈希鍵值
這裡的Key類型的結構體定義如下，很簡單：
class Key {
public:
/// Note that data can be nullptr if size is 0.
Key(const uchar *data, size_t size) : m_data(data), m_size(size) {}
bool operator==(const Key &other) const {
if (other.size() != size()) {
return false;
} else if (size() == 0) {
return true;
}
return memcmp(other.data(), data(), size()) == 0;
}
const uchar *data() const { return m_data; }
size_t size() const { return m_size; }
private:
const uchar *m_data;
const size_t m_size;
};
主體的HashJoinRowBuffer類，主要包含下面的成員變量：
// 存儲的join條件
const std::vector<HashJoinCondition> m_join_conditions;
// 一行資料可以由來自不同表的部分組成。 這個結構告訴我們涉及哪些表。
const pack_rows::TableCollection m_tables;
// 所有的哈希鍵值都會存儲在MEM_ROOT，配置設定在堆上。
MEM_ROOT m_mem_root;
// 這個MEM_ROOT結構僅用于存儲插入哈希表的最後一行資料，目的是為了保證不會溢出記憶體
MEM_ROOT m_overflow_mem_root;
// 存儲行值的哈希表
std::unique_ptr<hash_map_type> m_hash_map;
// 通過join條件建構key時用的緩沖區
String m_buffer;
size_t m_row_size_upper_bound;
// The maximum size of the buffer, given in bytes.
const size_t m_max_mem_available;
// 存儲在哈希表中的最後一行，如果哈希表為空，則為 nullptr。
LinkedImmutableString m_last_row_stored{nullptr};
// 擷取相關列，組成一行資料後，作為LinkedImmutableString類型存儲到哈希表中
LinkedImmutableString StoreLinkedImmutableStringFromTableBuffers(
LinkedImmutableString next_ptr, bool *full);
主體的HashJoinRowBuffer類，接口如下：
// 初始化一個HashJoinRowBuffer，代表已經準備好存儲行資料
// 這個接口可以調用很多次，每調用一次會清除現有的行資料
bool Init();
// 用來存儲行資料
// THD:處理線程
// reject_duplicate_keys：如果為 true，則拒絕具有重複鍵的行。被拒絕後，仍将傳回 ROW_STORED
// store_rows_with_null_in_condition：是否存儲NULL行
// 傳回值類型：
// ROW_STORED： 行已經被存儲了
// BUFFER_FULL：行被存儲了，但是緩沖區已經滿了
// FATAL_ERROR：錯誤
StoreRowResult StoreRow(THD *thd, bool reject_duplicate_keys,
bool store_rows_with_null_in_condition);
// 傳回哈希表的狀态
size_t size() const { return m_hash_map->size(); }
bool empty() const { return m_hash_map->empty(); }
bool inited() const { return m_hash_map != nullptr; }
// 傳回查找哈希鍵值key的疊代器
hash_map_iterator find(const Key &key) const { return m_hash_map->find(key); }
hash_map_iterator begin() const { return m_hash_map->begin(); }
hash_map_iterator end() const { return m_hash_map->end(); }
// 擷取最後一行插入到哈希表中的行
LinkedImmutableString LastRowStored() const {
assert(Initialized());
return m_last_row_stored;
}
// 和inited()作用差不多
bool Initialized() const { return m_hash_map.get() != nullptr; }
// 檢視是否包含某個key值
bool contains(const Key &key) const { return find(key) != end(); }
hash_join_iterator
這個檔案裡介紹了一下目前hash join的工作原理。
未超過記憶體限制的 hash join
join操作可以看做有兩個輸入，一個是 build input，一個是probe input。從名字可以看出來，build input是需要用來建構哈希表的，而probe input就是用來一行一行讀取并和哈希表比對的。
是以hash join的流程如下：
- 将兩個input，指定其中一個為build input，指定另外一個為probe input。通常都會指定表大小比較小的表作為build input(而不是指定行數比較少的表，這裡應該是為了記憶體中能存儲下)
-
将build input的表全部讀取到記憶體中建構哈希表，哈希鍵值是根據on條件來計算的，比如SELECT * FROM lineitem
INNER JOIN orders ON orders.o_orderkey = lineitem.l_orderkey;
其中“orders”表作為build input，那麼哈希鍵值就根據o_orderkey來做，當然優化器也會識别join中的隐式條件，比如，
SELECT * FROM orders, lineitem
WHERE orders.o_orderkey = lineitem.l_orderkey;
這個也會識别出o_orderkey。
- 每行每行的讀取probe input中的資料，對于每一行來計算對應的哈希鍵值，上面的例子是l_orderkey，采用相同的哈希計算函數來計算哈希值，并從哈希表中查找到對應值。關于行資料是如何存儲和恢複的細節，可以看pack_rows::StoreFromTableBuffers
當然，記憶體有限，限制于join_buffer_size。
沒有超過記憶體的部分仍然按照上述步驟來做。
如果超過了限制，那麼就按照下面的步驟來做
超過記憶體限制的 hash join
- build input中，沒有被建構成hash table的其餘行，會被分成給定數量n的檔案，存儲在HashJoinChunk中。對于build input 和 probe input，都會開n個chunk檔案，這n個chunk檔案是為了存儲兩張表的表資料的，因為記憶體放不下，同樣會用到哈希，不過用的是不同的哈希函數。
- 然後開始從probe input一行一行的讀取資料，先和記憶體中的hashtable做比對，也就是走一遍上面的hash join步驟。然後使用另一個哈希函數來計算哈希值，确定這行資料要存到那個chunk檔案中，因為這行資料之後還要和build input的其他表做比對。
- 講過上面的步驟，因為用的是一樣的哈希函數分區，可以保證build input和probe input比對的行肯定在同一個chunk中。是以開始對每個chunk的資料進行上面經典的hash join流程
上面的介紹都是對inner join的介紹，對于semi join來說，也差不多。
semi join 的hash join
- 因為semi join隻需要比對一行資料就行，是以建構哈希表時不需要存儲重複值。
- 輸出所有能在哈希表中找到比對的行。如果記憶體存不下，變成落盤的hash join，那麼隻需要把probe input未能在哈希表中比對的行進行落盤
hash join的注意點
- hash join隻适用于等值條件，對于有其他條件的join來說，哈希比對後，還要保證其他條件也能夠比對。
- 如果on-disk的hash join，産生的chunk檔案仍然過大，比如有一個很偏的資料集，那麼肯定會有這種情況。
- 寫磁盤時會設定一個"kMaxChunks"，用來表示最大chunk檔案數量，這個是為了不消耗完所有檔案描述符。
- 還會有一個設定值來避免寫磁盤，如果不落盤，那麼就一遍遍的建構哈希表，然後一遍遍的讀取probe input的資料。有的場景其實是不羅盤更好，但是mysql沒有針對這個的成本優化，要不要落盤隻能通過參數來控制。
HashJoinIterator類
初始化一個HashJoinIterator需要下面的參數：
// thd：處理線程
// build_input：build input疊代器
// build_input_tables：build input涉及到的表
// estimated_build_rows:build input的預估行數
// probe_input：probe input疊代器
// probe_input_tables：probe input涉及到的表
// store_rowids：bool類型，是否儲存rowid，僅在清除操作時使用
// tables_to_get_rowid_for：一個map，存儲需要調用position()的表
// max_memory_available：就是join_buffer_size
// join_conditions:join條件清單
// allow_spill_to_disk:是否允許落盤
// join_type：join類型，semi或者inner
// extra_conditions:不能被建構哈希表的額外條件，且由and連接配接
// probe_input_batch_mode：是否在probe input啟用批處理
// hash_table_generation：清除哈希表次數的計數器
HashJoinIterator(THD *thd, unique_ptr_destroy_only<RowIterator> build_input,
const Prealloced_array<TABLE *, 4> &build_input_tables,
double estimated_build_rows,
unique_ptr_destroy_only<RowIterator> probe_input,
const Prealloced_array<TABLE *, 4> &probe_input_tables,
bool store_rowids, table_map tables_to_get_rowid_for,
size_t max_memory_available,
const std::vector<HashJoinCondition> &join_conditions,
bool allow_spill_to_disk, JoinType join_type,
const Mem_root_array<Item *> &extra_conditions,
bool probe_input_batch_mode,
uint64_t *hash_table_generation);
HashJoinIterator類的接口如下：
// 使用build input的資料建構哈希表，記憶體存不下，剩餘資料就落盤
bool BuildHashTable();
// 從下一個chunk檔案中讀取資料到記憶體中建構哈希表
bool ReadNextHashJoinChunk();
// 從probe input讀取一行資料，如果目前已經開始落盤操作，那麼讀取到的資料會落盤
// 讀取完，疊代器的狀态會有如下改變：
// READING_FIRST_ROW_FROM_HASH_TABLE：這行資料已經讀取完放在記憶體裡了
// LOADING_NEXT_CHUNK_PAIR：probe input已經沒有資料可以讀取了
bool ReadRowFromProbeIterator();
// 從目前的probe chunk檔案中讀取一行資料到記憶體，疊代器的傳回狀态和上面相同
bool ReadRowFromProbeChunkFile();
// 從probe saving 檔案中讀取一行資料，我本來沒搞懂這個savingfile和上面的chunk file有什麼差別
// 看之前的看介紹可以知道，chunkfile是和build input成對的，落盤用的，結構是HashJoinChunk
// 而savingFile是為了記錄沒有比對到的資料的
// 比如semi join，是比對到就傳回的，如果哈希表被建構了多次，那麼probe input也會有多次，
// 那麼就會産生重複值，是以需要記錄沒有比對的資料，比對過的就不管了
bool ReadRowFromProbeRowSavingFile();
// 在哈希表中查找m_temporary_row_and_join_key_buffer的鍵值
void LookupProbeRowInHashTable();
// 判斷是否啟用了disk hash join
bool on_disk_hash_join() const { return !m_chunk_files_on_disk.empty(); }
// 如果允許落盤操作，将probe input的行寫到chunkfile中
bool WriteProbeRowToDiskIfApplicable();
// 判斷哈希比對成功的資料能不能滿足其他條件，都滿足就傳回true
bool JoinedRowPassesExtraConditions() const;
// 看能不能去掉哈希表中的重複鍵值
bool RejectDuplicateKeys() const
// 以下幾個初始化函數顧名思義
bool InitRowBuffer();
bool InitProbeIterator();
bool InitWritingToProbeRowSavingFile();
bool InitReadingFromProbeRowSavingFile();
// 設定probe input的疊代器狀态
void SetReadingProbeRowState();
// 找哈希表中下一個比對的資料，并檢視滿不滿足其他join條件,如果需要還會落盤
int ReadNextJoinedRowFromHashTable();
mysql的源碼注釋寫的非常詳細，弄懂這些接口，也就能明白mysql對于哈希join的處理了。
看mysql的源碼确實非常受益，看這些大神們是怎麼管理自己的代碼的，看他們對于記憶體管理怎麼做的，像join_buffer_size這種東西，實際上超沒超，肯定是插入資料之後才能看出來，最起碼我是這麼寫的，但是mysql的開發者們就很聰明的建立了個臨時緩存區，判斷無誤後才能放入buffer中，這樣就可以很便捷的管理記憶體了，類似這種思路，mysql中還有很多，确實能感受到設計的嚴謹，像我在實際寫記憶體限制的時候，這些細節就考慮不好，讀書有益，讀源碼也一樣的。