GreatSQL Hash Join 條件列長度對執行計劃的影響
作者：wuyy
調查生成 Join 的執行計劃代碼，發現在優化器執行JOIN::create_root_access_path_for_join的時候，有一個連接條件內部長度的判斷過程，這里用了一個固定長度1024作為內部長度的判斷，當超過這個長度的時候就要另外執行一次過濾器。
一、問題發現
在一次開發中發現當執行 Hash Join 用 VARCHAR 字段作為連接的時候，字段長度長短不同時候，執行計劃也不一樣。看下面3個例子。
1、連接條件字段長度為20的場景
greatsql> CREATE TABLE t1 (c1 INT, c2 varchar(20)) CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;
greatsql> INSERT INTO t1 VALUES (1,'aa'),(2,'bb'),(35,'cc'),(5,'dd'),(null,'eeff');
greatsql> CREATE TABLE t3 (ccc1 INT, ccc2 varchar(20)) CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;
greatsql> INSERT INTO t3 VALUES (1,'aa11bb'),(2,'dd1cc'),(3,'ee1dd'),(4,'dd2'),(null,'eeff');兩張表執行 Hash Join 連接，用 VARCHAR 作為連接條件的結果：
greatsql> EXPLAIN format=tree SELECT * FROM t1 JOIN t3 ON t1.c2=t3.ccc2;
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN |
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Innerhashjoin (t3.ccc2 = t1.c2) (cost=3.50rows=5)
-> Tablescanon t3 (cost=0.07rows=5)
-> Hash
-> Tablescanon t1 (cost=0.75rows=5)
|
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------+2、連接條件字段長度為1000的場景
greatsql> CREATE TABLE t1 (c1 INT, c2 varchar(1000)) CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;
greatsql> INSERT INTO t1 VALUES (1,'aa'),(2,'bb'),(35,'cc'),(5,'dd'),(null,'eeff');
greatsql> CREATE TABLE t3 (ccc1 INT, ccc2 varchar(1000)) CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;
greatsql> INSERT INTO t3 VALUES (1,'aa11bb'),(2,'dd1cc'),(3,'ee1dd'),(4,'dd2'),(null,'eeff');兩張表執行 Hash Join 連接，用 VARCHAR 作為連接條件的結果：
greatsql> EXPLAIN format=tree SELECT * FROM t1 JOIN t3 ON t1.c2=t3.ccc2;
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Filter: (t3.ccc2 = t1.c2) (cost=3.52rows=5) 這里另外需要一次過濾比較
-> Innerhashjoin (<hash>(t3.ccc2)=<hash>(t1.c2)) (cost=3.52rows=5)
-> Tablescanon t3 (cost=0.07rows=5)
-> Hash
-> Tablescanon t1 (cost=0.75rows=5)
|
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+3、連接條件字段類型為 BLOB 的場景
greatsql> CREATE TABLE t11 (c1 INT, c2 blob) CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;
greatsql> INSERT INTO t11 VALUES (1,'aa'),(2,'bb'),(35,'cc'),(5,'dd'),(null,'eeff');
greatsql> CREATE TABLE t13 (ccc1 INT, ccc2 blob) CHARSET=utf8mb4 COLLATE=utf8mb4_0900_ai_ci;
greatsql> INSERT INTO t13 VALUES (1,'aa11bb'),(2,'dd1cc'),(3,'ee1dd'),(4,'dd2'),(null,'eeff');兩張表執行 Hash Join 連接，用 BLOB 作為連接條件的結果：
greatsql> EXPLAIN format=tree SELECT * FROM t11 JOIN t3 ON t11.c2=t13.ccc2;
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| EXPLAIN |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Filter: (t13.ccc2 = t11.c2) (cost=3.52rows=5) 這里另外需要一次過濾比較
-> Innerhashjoin (<hash>(t13.ccc2)=<hash>(t11.c2)) (cost=3.52rows=5)
-> Tablescanon t13 (cost=0.07rows=5)
-> Hash
-> Tablescanon t11 (cost=0.75rows=5)
|
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+通過以上三個例子發現，當連接字段超過一定長度的時候，執行計劃會在 Hash Join 外面再套一層 FilterIterator 另外進行一次過濾比較。
二、問題調查過程
調查生成 Join 的執行計劃代碼，發現在優化器執行JOIN::create_root_access_path_for_join的時候，有一個連接條件內部長度的判斷過程，這里用了一個固定長度1024作為內部長度的判斷，當超過這個長度的時候就要另外執行一次過濾器。
// 調查代碼發現跟下面代碼的長度判斷有關，如果計算出來的內部長度超過1024最后還是要執行FilterIterator
HashJoinCondition::HashJoinCondition(Item_eq_base *join_condition,
MEM_ROOT *mem_root) {
m_store_full_sort_key = true;
constbool using_secondary_storage_engine =
(current_thd->lex->m_sql_cmd != nullptr &&
current_thd->lex->m_sql_cmd->using_secondary_storage_engine());
if ((join_condition->compare_type() == STRING_RESULT ||
join_condition->compare_type() == ROW_RESULT) &&
!using_secondary_storage_engine) {
const CHARSET_INFO *cs = join_condition->compare_collation();
// 這里的1024是開發者隨意寫的，但是決定了最后要不要在join外面再執行一次過濾，計算公式見下面三的表格
if (cs->coll->strnxfrmlen(cs, cs->mbmaxlen * m_max_character_length) > 1024) {
m_store_full_sort_key = false;
}
}
}
static AccessPath *CreateHashJoinAccessPath() {
// 下面這段跟連接條件的長度計算有關，如果超過1024長度會向hash_join_extra_conditions隊列插入condition，從而最后走過濾器
for (const HashJoinCondition &cond : hash_join_conditions) {
if (!cond.store_full_sort_key()) {
hash_join_extra_conditions.push_back(cond.join_condition());
}
}
}對比前兩個場景的執行計劃：
字段長度 | AccessPath | 參數 | 說明 |
20 | HashJoinIterator | m_build_input=TableScanIterator (t3表) m_probe_input=TableScanIterator (t1表) />m_row_buffer.m_join_conditions=Item_func_eq | HashJoinIterator內部創建一張hash表，hash表掃描第二張表的時候通過m_row_buffer.m_join_conditions進行數據過濾 |
1000 | FilterIterator | m_source=HashJoinIterator m_condition=Item_func_like | HashJoinIterator外面套一層filter，用m_condition再執行一次過濾 |
之所以做這個限制，具體原因可以看一下m_store_full_sort_key這個參數的注釋，這個解釋了為什么要加一個新的過濾。
下面的注釋翻譯如下，這個解釋已經很清楚了：
通常，我們將條件的full sort key作為鍵存儲在哈希表中。但是，如果字符串很長，或者我們有一個 PAD SPACE 排序規則，則可能導致排序鍵很大。如果我們檢測到這種情況可能發生在最壞的情況下，我們只會在鍵中存儲哈希值（因此我們對哈希值進行哈希處理）。如果是這樣，我們必須事后重新檢查，以防范哈希沖突。
// Normally, we store the full sort key for the condition as key in the hash
// table. However, if the string is very long, or we have a PAD SPACE
// collation, this could result in huge sort keys. If we detect that this
// could happen in the worst case, we store just a hash in the key instead (so
// we hash the hash). If so, we have to do a recheck afterwards, in order to
// guard against hash collisions.
bool m_store_full_sort_key;繼續看生成 key 的代碼可以發現，如果是長度超過1024的字段，會通過append_hash_for_string_value先把超長 key 轉為 hash 值，所以才有上面解釋里面的儲存 hash 值的 hash 值的說法。
static bool extract_value_for_hash_join() {
switch (comparator->get_compare_type()) {
case STRING_RESULT: {
if (join_condition.store_full_sort_key()) { 這里代表長度沒有超過1024
return append_string_value(
comparand, comparator->cmp_collation.collation,
join_condition.max_character_length(),
(thd->variables.sql_mode & MODE_PAD_CHAR_TO_FULL_LENGTH) > 0,
is_multi_column_key, join_key_buffer);
} else { 這里代表長度超過1024
return append_hash_for_string_value(
comparand, comparator->cmp_collation.collation, join_key_buffer);
}
}
}三、相關計算公式
判斷公式：
cs->coll->strnxfrmlen(cs, cs->mbmaxlen * m_max_character_length) > 1024
其中cs為字符集，cs->mbmaxlen為字符集的最大長度，m_max_character_length為字段長度
以上公式為真的話就在hashjoin外面另外套一層過濾器FilterIterator。部分字符集和 Hash Join 內部長度的計算公式表：
字符集 | 計算公式 | 說明 |
utf8mb4 | ((len + 3) / 4) * 2 | 其中4為字符集的最長長度 |
utf8mb3 | ((len + 2) / 3) * 2 | 其中3為字符集的最長長度 |
unicode_full_bin | ((len + 3) / cs->mbmaxlen) * 3 | cs->mbmaxlen為字符集的最長長度 |
注：表里的len=cs->mbmaxlen * m_max_character_length，其中cs為字符集，cs->mbmaxlen為字符集的最大長度，m_max_character_length為字段長度
這里我們舉一個例子計算一下：
假設有一個字段是c2 varchar(300)，字符集是my_charset_utf8mb4_0900_ai_ci，找到utf8mb4_0900相關的計算函數如下：
static size_t my_strnxfrmlen_uca_900(const CHARSET_INFO *cs, size_t len) {
constsize_t num_codepoints = (len + 3) / 4;
constsize_t max_num_weights_per_level = num_codepoints * 8;
size_t max_num_weights = max_num_weights_per_level * cs->levels_for_compare;
if (cs->coll_param && cs->coll_param->reorder_param) {
max_num_weights += max_num_weights_per_level;
}
return (max_num_weights + (cs->levels_for_compare - 1)) * sizeof(uint16_t);
}
因此strnxfrmlen的計算公式就是：
num_codepoints = (300 * 4 + 3 ) / 4 = 300;
max_num_weights_per_level = num_codepoints * 8 = 2400
max_num_weights = max_num_weights_per_level * cs->levels_for_compare = 2400 * 1 = 2400
strnxfrmlen = (max_num_weights + (cs->levels_for_compare - 1)) * sizeof(uint16_t) = (2400 + 1-1 )) * 2= 4800
最后由于4800大于1024，因此執行計劃需要在hashjoin外面另外套一層過濾器FilterIterator。
從上面的計算過程可以看出，如果不想套一層過濾器，那么varchar長度最大只能設置為64.四、問題總結
通過以上分析我們可以發現，執行 Hash Join 的時候，連接條件的字段字符集和長度不一樣的時候，最后的執行計劃結果也不一樣。究其原因是因為如果字段過長，hash 表只儲存 key 的 hash 值，這樣必須事后重新檢查，以防范哈希沖突。所以如果連接字段過長（比如 my_charset_utf8mb4_0900_ai_ci 字符集的情況下，varchar長度超過64），會比短字段（比如小于64長度）消耗更多資源和內存用來做查詢，因此在實際使用中，應該避免使用過長的字段進行 Hash Join 連接。
責任編輯：武曉燕
來源：
GreatSQL社區
