GreatSQL Hash Join 条件列长度对执行计划的影响

一、问题发现

在一次开发中发现当执行 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                                                                                                                                                           |
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| -> Inner hash join (t3.ccc2 = t1.c2)  (cost=3.50 rows=5)
    -> Table scan on t3  (cost=0.07 rows=5)
    -> Hash
        -> Table scan on t1  (cost=0.75 rows=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.52 rows=5) 这里另外需要一次过滤比较
    -> Inner hash join (<hash>(t3.ccc2)=<hash>(t1.c2))  (cost=3.52 rows=5)
        -> Table scan on t3  (cost=0.07 rows=5)
        -> Hash
            -> Table scan on t1  (cost=0.75 rows=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.52 rows=5) 这里另外需要一次过滤比较
    -> Inner hash join (<hash>(t13.ccc2)=<hash>(t11.c2))  (cost=3.52 rows=5)
        -> Table scan on t13  (cost=0.07 rows=5)
        -> Hash
            -> Table scan on t11  (cost=0.75 rows=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;

  const bool 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) {
  const size_t num_codepoints = (len + 3) / 4;
  const size_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 连接。

Enjoy GreatSQL :)

关于 GreatSQL

GreatSQL是适用于金融级应用的国内自主开源数据库，具备高性能、高可靠、高易用性、高安全等多个核心特性，可以作为MySQL或Percona Server的可选替换，用于线上生产环境，且完全免费并兼容MySQL或Percona Server。

相关链接： GreatSQL社区 Gitee GitHub Bilibili

GreatSQL社区：

社区有奖建议反馈： https://greatsql.cn/thread-54-1-1.html

社区博客有奖征稿详情： https://greatsql.cn/thread-100-1-1.html

（对文章有疑问或者有独到见解都可以去社区官网提出或分享哦~）

技术交流群：

微信&QQ群：

QQ群：533341697

微信群：添加GreatSQL社区助手（微信号：wanlidbc ）好友，待社区助手拉您进群。