MySQL8.0 优化器介绍（二）

• GreatSQL 社区原创内容未经授权不得随意使用，转载请联系小编并注明来源。

• GreatSQL 是 MySQL 的国产分支版本，使用上与 MySQL 一致。

• 作者： 奥特曼爱小怪兽

• 文章来源：GreatSQL 社区投稿

上一篇 MySQL8.0 优化器介绍（一）介绍了成本优化模型的三要素：表关联顺序，与每张表返回的行数（过滤效率），查询成本。而 join 算法又是影响表关联效率的首要因素。

join 算法（Join Algorithms）

join 在 MySQL 是一个如此重要的章节，毫不夸张的说，everything is a join。

截止到本文写作时，MySQL8.0.32 GA 已经发行，这里主要介绍三大 join：NL（Nested Loop），BNL（Block Nested Loop）,HASH JOIN

嵌套循环（Nested Loop）

MySQL5.7 之前，都只有 NL，它实现简单，适合索引查找。

几乎每个人都可以手动实现一个 NL。

SELECT CountryCode,        country.Name AS Country,         city.Name AS City,        city.District    FROM world.country    INNER JOIN world.city      ON city.CountryCode = country.Code    WHERE Continent = 'Asia';     ##执行计划类似如下：  -> Nested loop inner join     -> Filter: (country.Continent = 'Asia')         -> Table scan on country     -> Index lookup on city using CountryCode     (CountryCode=country.`Code`)      ##python 代码实现一个NL result = [] for country_row in country:     if country_row.Continent == 'Asia':         for city_row in city.CountryCode['country_row.Code']:             result.append(join_rows(country_row, city_row))

图示化一个 NL

NL 的限制：通常多个表 join，小表在前做驱动表，被驱动表有索引检索，效率会高一些。（官方手册上没有 full outer join ,full join 语法，实际支持 full join）

举个例子 多表 join 且关联表不走索引：

#人为干预计划，走性能最差的执行路径。SELECT /*+ NO_BNL(city) */       CountryCode,        country.Name AS Country,       city.Name AS City,        city.District  FROM world.country IGNORE INDEX (Primary)  INNER JOIN world.city IGNORE INDEX (CountryCode)    ON city.CountryCode = country.Code  WHERE Continent = 'Asia';    SELECT rows_examined, rows_sent,         last_statement_latency AS latency    FROM sys.session   WHERE thd_id =  PS_CURRENT_THREAD_ID()\G**************************** 1. row ****************************rows_examined: 208268 rows_sent: 1766 latency: 44.83 ms  ##对比一下优化器 自动优化后的 SELECT CountryCode,        country.Name AS Country,       city.Name AS City,        city.District  FROM world.country   INNER JOIN world.city     ON city.CountryCode = country.Code  WHERE Continent = 'Asia';    SELECT rows_examined, rows_sent,         last_statement_latency AS latency    FROM sys.session   WHERE thd_id =  PS_CURRENT_THREAD_ID()\G*************************** 1. row ***************************rows_examined: 2005 rows_sent: 1766 latency: 4.36 ms1 row in set (0.0539 sec)

块嵌套循环（Block Nested Loop）

块嵌套循环算法是嵌套循环算法的扩展。它也被称为 BNL 算法。连接缓冲区用于收集尽可能多的行，并在第二个表的一次扫描中比较所有行，而不是逐个提交第一个表中的行。这可以大大提高 NL 在某些查询上的性能。

hash join 是在 MySQL8.0.18 引进的，下面的 sql，使用了 NO_HASH_JOIN(country,city) 的提示，并且两表的 join 字段上的索引被忽略，目的是为了介绍 BNL 特性。

SELECT /*+ NO_HASH_JOIN(country,city) */       CountryCode,        country.Name AS Country,       city.Name AS City,        city.District FROM world.country IGNORE INDEX (Primary) INNER JOIN world.city IGNORE INDEX (CountryCode)   ON city.CountryCode = country.CodeWHERE Continent = 'Asia';
##使用python伪代码来解释一下 BNLresult = []join_buffer = []for country_row in country:     if country_row.Continent == 'Asia':     join_buffer.append(country_row.Code)     if is_full(join_buffer):         for city_row in city:             CountryCode = city_row.CountryCode             if CountryCode in join_buffer:                 country_row = get_row(CountryCode)                 result.append(                     join_rows(country_row, city_row))             join_buffer = []if len(join_buffer) > 0:     for city_row in city:     CountryCode = city_row.CountryCode     if CountryCode in join_buffer:         country_row = get_row(CountryCode)         result.append(join_rows(country_row, city_row))   join_buffer = []

图示化一个 BNL

注意图里的 join_buffer,在 MySQL5.7 上使用 sysbench 压测读写场景，压力上不去，主要就是因为 BNL 算法下，join_buffer_size 的设置为默认值。适当调整几个 buffer 后，tps 得到显著提高。join buffer 对查询影响，也可以用下面的例子做一个量化说明。

SELECT /*+ NO_HASH_JOIN(country,city) */       CountryCode,        country.Name AS Country,       city.Name AS City,        city.District FROM world.country IGNORE INDEX (Primary) INNER JOIN world.city IGNORE INDEX (CountryCode)   ON city.CountryCode = country.CodeWHERE Continent = 'Asia';
 SELECT rows_examined, rows_sent,         last_statement_latency AS latency    FROM sys.session   WHERE thd_id =  PS_CURRENT_THREAD_ID()\G*************************** 1. row ***************************rows_examined: 4318 rows_sent: 1766 latency: 16.87 ms1 row in set (0.0490 sec)
#人为干预计划，走性能最差的执行路径。SELECT /*+ NO_BNL(city) */       CountryCode,        country.Name AS Country,       city.Name AS City,        city.District  FROM world.country IGNORE INDEX (Primary)  INNER JOIN world.city IGNORE INDEX (CountryCode)    ON city.CountryCode = country.Code  WHERE Continent = 'Asia';    SELECT rows_examined, rows_sent,         last_statement_latency AS latency    FROM sys.session   WHERE thd_id =  PS_CURRENT_THREAD_ID()\G**************************** 1. row ****************************rows_examined: 208268 rows_sent: 1766 latency: 44.83 ms  在两表join，且join字段不使用索引的前提下，BNL +join_buffer 性能远大于 NL 

使用 BNL 有几个点需要注意。（我实在懒得全文翻译官方文档了）

• Only the columns required for the join are stored in the join buffer. This means that you will need less memory for the join buffer than you may at first expect. （不需要配置太高 buffer)

• The size of the join buffer is configured with the join_buffer_size variable. The value of join_buffer_size is the minimum size of the buffer! Even if less than 1 KiB of country code values will be stored in the join buffer in the discussed example, if join_buffer_size is set to 1 GiB, then 1 GiB will be allocated. For this reason, keep the value of join_buffer_size low and only increase it as needed.

• One join buffer is allocated per join using the block nested loop algorithm.

• Each join buffer is allocated for the entire duration of the query.

• The block nested loop algorithm can be used for full table scans, full index scans, and range scans.(适用 table access 方式）

• The block nested loop algorithm will never be used for constant tables as well as the first nonconstant table. This means that it requires a join between two tables with more than one row after filtering by unique indexes to use the block nested loop algorithm

可以通过 optimizer switch 配置 BNL() 、 NO_BNL()

BNL 特别擅长在 non-indexed joins 的场景，很多时候性能优于 hash join。As of version 8.0.20, block nested-loop joins are no longer used; instead, a hash join has replaced it.

哈希 join （Hash Join）

Hash Join 作为大杀器在 MySQL8.0.18 引入，期间有过引起内存和文件句柄大量消耗的线上问题，但是不妨碍它作为一个 join 算法的重大突破，特别适合大表与大表的无索引 join。某些场景甚至比 NL+index join 更快。（当然比起 oracle 上的 hash join 依然弱爆了，40w * 40w 的大表查询，MySQL 优化到极致在 10s 左右，oracle 在 1s 水平，相差一个数量级。

思考：MySQL、Oracle 都是 hash join，为何差距如此大？MySQL hash join 可以哪些方面进行性能提高？

业界主要有两大方向

1. 单线程 hash 优化算法和数据结构

2. NUMA 架构下，多线程 Hash Join 的优化主要是能够让读写数据尽量发生在当前 NUMA node

参考文档（https://zhuanlan.zhihu.com/p/589601705）

大家不妨看看 MySQL 工程师的 worklog， 内容很精彩（https://dev.mysql.com/worklog/task/?id=2241）

可以看出国外大厂强大的标准化的 it 生产能力，一个功能从需求到实现经历了哪些关键步骤。

MySQL 的 Hash join 是一个内存 hash+磁盘 hash 的混合扩展。为了不让 hash join 溢出 join buffer,需要加大内存设置，使用磁盘 hash 时，需要配置更多的文件句柄数。尽管有 disk hash ，但实际干活的还是 in-memory hash。

内存 hash 有两个阶段：

1. build phase. One of the tables in the join is chosen as the build table. The hash is calculated for the columns required for the join and loaded into memory.

2. probe phase. The other table in the join is the probe input. For this table, rows are read one at a time, and the hash is calculated. Then a hash key lookup is performed on the hashes calculated from the build table, and the result of the join is generated from the matching rows.

当 hashes of build table 不足以全部放进内存时，MySQL 会自动切换到 on-disk 的扩展实现（基于 GRACE hash join algorithm）。在 build phase 阶段，join buffer 满，就会发生 in-mem hash 向 on-disk hash 转换。

on-disk algorithm 包含 3 个步骤：

1. Calculate the hashes of all rows in both the build and probe tables and store them on disk in several small files partitioned by the hash. The number of partitions is chosen to make each partition of the probe table fit into the join buffer but with a limit of at most 128 partitions.

2. Load the first partition of the build table into memory and iterate over the hashes from the probe table in the same way as for the probe phase for the in-memory algorithm. Since the partitioning in step 1 uses the same hash function for both the build and probe tables, it is only necessary to iterate over the first partition of the probe table.

3. Clear the in-memory buffer and continue with the rest of the partitions one by one

无论是内存 hash 还是磁盘 hash，都使用 xxHash64 hash function。xxHash64 有足够快，hash 质量好（reducing the number of hash collisions）的特点

BNL 不会被选中的时候，MySQL 就会选用 hash join。

在整理这篇资料时，对要使用的哈希连接算法存在以下要求：

• The join must be an inner join.

• The join cannot be performed using an index, either because there is no available index or because the indexes have been disabled for the query.

• All joins in the query must have at least one equi-join condition between the two tables in the join, and only columns from the two tables as well as constants are referenced in the condition. （查询中的所有联接必须在联接中的两个表之间至少有一个等联接条件，并且在该条件中仅引用两个表中的列以及常量）

• As of 8.0.20, anti, semi, and outer joins are also supported. If you join the two tables t1 and t2, then examples of join conditions that are supported for hash join include

• t1.t1_val = t2.t2_val

• t1.t1_val = t2.t2_val + 2

• t1.t1_val1 = t2.t2_val AND t1.t1_val2 > 100

• MONTH(t1.t1_val) = MONTH(t2.t2_val)

用一个例子来说明一下 hash join：

SELECT CountryCode,        country.Name AS Country,       city.Name AS City,        city.District FROM world.country IGNORE INDEX (Primary) INNER JOIN world.city IGNORE INDEX (CountryCode)   ON city.CountryCode = country.CodeWHERE Continent = 'Asia';
#用一段伪代码翻译一下result = []join_buffer = []partitions = 0on_disk = Falsefor country_row in country:     if country_row.Continent == 'Asia':         hash = xxHash64(country_row.Code)         if not on_disk:             join_buffer.append(hash)             if is_full(join_buffer):             # Create partitions on disk               on_disk = True               partitions = write_buffer_to_disk(join_buffer)               join_buffer = []         else             write_hash_to_disk(hash)             if not on_disk:     for city_row in city:         hash = xxHash64(city_row.CountryCode)         if hash in join_buffer:             country_row = get_row(hash)             city_row = get_row(hash)             result.append(join_rows(country_row, city_row))else:     for city_row in city:         hash = xxHash64(city_row.CountryCode)         write_hash_to_disk(hash)              for partition in range(partitions):         join_buffer = load_build_from_disk(partition)         for hash in load_hash_from_disk(partition):         if hash in join_buffer:             country_row = get_row(hash)             city_row = get_row(hash)             result.append(join_rows(country_row, city_row)) join_buffer = []
与所使用的实际算法相比，所描述的算法稍微简化了一些。真正的算法必须考虑哈希冲突，而对于磁盘上的算法，某些分区可能会变得太大而无法放入连接缓冲区，在这种情况下，它们会被分块处理，以避免使用比配置的内存更多的内存

图示化一下 in-mem hash 算法：

量化一下 hash join 的成本

SELECT CountryCode,        country.Name AS Country,       city.Name AS City,        city.District FROM world.country IGNORE INDEX (Primary) INNER JOIN world.city IGNORE INDEX (CountryCode)   ON city.CountryCode = country.CodeWHERE Continent = 'Asia';
SELECT rows_examined, rows_sent,         last_statement_latency AS latency    FROM sys.session   WHERE thd_id =  PS_CURRENT_THREAD_ID()\G**************************** 1. row ****************************rows_examined: 4318 rows_sent: 1766 latency: 3.53 ms

从本文的例子中，rows_examined 的角度来看 index_join 下的 NL（2005） 优于 无索引 join 条件下的 BNL (4318）= 无索引 join 条件下的 hash join。但是当数据量发生变化，可能结果就不一样了，现实中也没有绝对的性能好坏规则（如果有，基于规则的成本计算就能很好处理的查询问题，实际上更值得信赖的是成本估算），hash join 与 NL,BNL 的优越比较，列出几点，当作纸上谈兵 ：

• For a join without using an index, the hash join will usually be much faster than a block nested join unless a LIMIT clause has been added. Improvements of more than a factor of 1000 have been observed.

• 参考:

• （https://mysqlserverteam.com/hash-join-in-mysql-8/）（https://dev.mysql.com/blog-archive/hash-join-in-mysql-8/）（http://www.slideshare.net/NorvaldRyeng/mysql-8018-latest-updates-hash-join-and-explain-analyze）

• For a join without an index where there is a LIMIT clause, a block nested loop can exit when enough rows have been found, whereas a hash join will complete the entire join (but can skip fetching the rows). If the number of rows included due to the LIMIT clause is small compared to the total number of rows found by the join, a block nested loop may be faster.

• For joins supporting an index, the hash join algorithm can be faster if the index has a low selectivity.

Hash Join 最大的好处在于提升多表无索引关联时的查询性能。具体 NL,BNL,HASH JOIN 谁更适合用于查询计划，实践才是最好的证明。

同样可以使用 HASH_JOIN() 和 NO_HASH_JOIN() 的 hint 来影响查询计划。

MySQL8.0 关于支持的三种 high-level 连接策略的讨论暂时到此结束。下来可以自己去查一下 anti, semi, and outer joins。

更多细节 参考

（https://dev.mysql.com/doc/refman/8.0/en/select-optimization.html）（https://dev.mysql.com/doc/refman/8.0/en/semijoins.html）

还有一些 关于 join 的 lower-level 优化值得考虑，下篇文章分解。

Enjoy GreatSQL :)

关于 GreatSQL

GreatSQL 是由万里数据库维护的 MySQL 分支，专注于提升 MGR 可靠性及性能，支持 InnoDB 并行查询特性，是适用于金融级应用的 MySQL 分支版本。

相关链接： GreatSQL社区 Gitee GitHub Bilibili

GreatSQL 社区：

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

技术交流群：

微信：扫码添加GreatSQL社区助手微信好友，发送验证信息加群。