表连接的原理

连接简介

连接的本质就是把各个连接表中的记录都取出来依次匹配的组合加入结果集并返回给用户。不论哪个表作为驱动表，两表连接产生的笛卡尔积肯定是一样的。而对于内连接来说，由于凡是不符合 ON 子句或WHERE 子句中的条件的记录都会被过滤掉，其实也就相当于从两表连接的笛卡尔积中把不符合过滤条件的记录给踢出去，所以对于内连接来说，驱动表和被驱动表是可以互换的，并不会影响最后的查询结果。但是对于外连接来说，由于驱动表中的记录即使在被驱动表中找不到符合 ON 子句连接条件的记录，所以此时驱动表和被驱动表的关系就很重要了，也就是说左外连接和右外连接的驱动表和被驱动表不能轻易互换。

连接的原理

1、嵌套循环连接（Nested-Loop Join）

对于两表连接来说，驱动表只会被访问一遍，但被驱动表却要被访问到好多遍，具体访问几遍取决于对驱动表执行单表查询后的结果集中的记录条数。对于内连接来说，选取哪个表为驱动表都没关系，而外连接的驱动表是固定的，也就是说左（外）连接的驱动表就是左边的那个表，右（外）连接的驱动表就是右边的那个表。

内连接的查询过程：
步骤1：选取驱动表，使用与驱动表相关的过滤条件，选取代价最低的单表访问方法来执行对驱动表的单表
查询。
步骤2：对上一步骤中查询驱动表得到的结果集中每一条记录，都分别到被驱动表中查找匹配的记录。

这个过程就像是一个嵌套的循环，所以这种驱动表只访问一次，但被驱动表却可能被多次访问，访问次数取决于对驱动表执行单表查询后的结果集中的记录条数的连接执行方式称之为 嵌套循环连接 （ Nested-Loop Join ），这是最简单，也是最笨拙的一种连接查询算法。

2、使用索引加快连接速度

在嵌套循环连接的步骤2中可能需要访问多次被驱动表，如果访问被驱动表的方式都是全表扫描的话，那得要扫描好多次，查询被驱动 表其实就相当于一次单表扫描，我们可以利用索引来加快查询速度哦。

eg：

SELECT * FROM t1, t2 WHERE t1.m1 > 1 AND t1.m1 = t2.m2 AND t2.n2 < 'd';

如果是嵌套循环连接：

查询驱动表 t1 后的结果集中有两条记录， 嵌套循环连接 算法需要对被驱动表查询2次：
 当 t1.m1 = 2 时，去查询一遍 t2 表，对 t2 表的查询语句相当于：
 SELECT * FROM t2 WHERE t2.m2 = 2 AND t2.n2 < 'd';
 当 t1.m1 = 3 时，再去查询一遍 t2 表，此时对 t2 表的查询语句相当于：
 SELECT * FROM t2 WHERE t2.m2 = 3 AND t2.n2 < 'd';

可以看到，原来的 t1.m1 = t2.m2 这个涉及两个表的过滤条件在针对 t2 表做查询时关于 t1 表的条件就已经确定了，所以我们只需要单单优化对 t2 表的查询了，上述两个对 t2 表的查询语句中利用到的列是 m2 和 n2 列，我们可以：

1、在 m2 列上建立索引，因为对 m2 列的条件是等值查找，比如 t2.m2 = 2 、 t2.m2 = 3 等，
所以可能使用到ref 的访问方法，假设使用 ref 的访问方法去执行对 t2 表的查询的话，
需要回表之后再判断 t2.n2 < d 这个条件是否成立。

ps：这里有一个比较特殊的情况，就是假设 m2 列是 t2 表的主键或者唯一二级索引列，
那么使用 t2.m2 = 常数值 这样的条件从 t2 表中查找记录的过程的代价就是常数级别的。
我们知道在单表中使用主键值或者唯一二级索引列的值进行等值查找的方式称之为 const ，
而MySQL在连接查询中对被驱动表使用主键值或者唯一二级索引列的值进行等值查找的查询执行方式称之为： eq_ref 。

2、在 n2 列上建立索引，涉及到的条件是 t2.n2 < 'd' ，可能用到 range 的访问方法，
假设使用 range 的访问方法对 t2 表的查询的话，需要回表之后再判断在 m2 列上的条件是否成立。

假设 m2 和 n2 列上都存在索引的话，那么就需要从这两个里边儿挑一个代价更低的去执行对 t2 表的查询。当然，建立了索引不一定使用索引，只有在 二级索引 + 回表 的代价比全表扫描的代价更低时才会使用索引。另外，有时候连接查询的查询列表和过滤条件中可能只涉及被驱动表的部分列，而这些列都是某个索引的一部分，这种情况下即使不能使用 eq_ref 、 ref 、 ref_or_null 或者 range 这些访问方法执行对被驱动表的查询的话，也可以使用索引扫描，也就是 index 的访问方法来查询被驱动表。所以我们建议在真实工作中最好不要使用 * 作为查询列表，最好把真实用到的列作为查询列表。

3、基于块的嵌套循环连接（Block Nested-Loop Join）

扫描一个表的过程其实是先把这个表从磁盘上加载到内存中，然后从内存中比较匹配条件是否满足。现实生活中的表成千上万条记录都是少的，几百万、几千万甚至几亿条记录的表到处都是。内存里可能并不能完全存放的下表中所有的记录，所以在扫描表前边记录的时候后边的记录可能还在磁盘上，等扫描到后边记录的时候可能内存不足，所以需要把前边的记录从内存中释放掉。我们前边又说过，采用嵌套循环连接算法的两表连接过程中，被驱动表可是要被访问好多次的，如果这个被驱动表中的数据特别多而且不能使用索引进行访问，那就相当于要从磁盘上读好几次这个表，这个 I/O 代价就非常大了，所以我们得想办法：尽量减少访问被驱动表的次数。

为了不至于读一个表好几次，可以在把被驱动表的记录加载到内存的时候，一次性和多条驱动表中的记录做匹配，这样就可以大大减少重复从磁盘上加载被驱动表的代价了。所以MySQL提出了一个join buffer 的概念， join buffer 就是执行连接查询前申请的一块固定大小的内存，先把若干条驱动表结果集中的记录装在这个 join buffer 中，然后开始扫描被驱动表，每一条被驱动表的记录一次性和 join buffer 中的多条驱动表记录做匹配，因为匹配的过程都是在内存中完成的，所以这样可以显著减少被驱动表的 I/O 代价。使用 join buffer 的过程如下图所示：

最好的情况是 join buffer 足够大，能容纳驱动表结果集中的所有记录，这样只需要访问一次被驱动表就可以完成连接操作了。这种加入了 join buffer 的嵌套循环连接算法称之为 基于块的嵌套连接（Block Nested-Loop Join）算法。

这个 join buffer 的大小是可以通过启动参数或者系统变量 join_buffer_size 进行配置，默认大小为 262144字节 （也就是 256KB ），最小可以设置为 128字节 。当然，对于优化被驱动表的查询来说，最好是为被驱动表加上效率高的索引，如果实在不能使用索引，并且自己的机器的内存也比较大可以尝试调大 join_buffer_size 的值来对连接查询进行优化。

另外需要注意的是，驱动表的记录并不是所有列都会被放到 join buffer 中，只有查询列表中的列和过滤条件中的列才会被放到 join buffer 中，所以再次提醒我们，最好不要把 * 作为查询列表，只需要把我们关心的列放到查询列表就好了，这样还可以在 join buffer 中放置更多的记录。

MySQL基于成本的优化

成本分类

I/O 成本

我们的表经常使用的 MyISAM 、 InnoDB 存储引擎都是将数据和索引都存储到磁盘上的，当我们想查询表中的记录时，需要先把数据或者索引加载到内存中然后再操作。这个从磁盘到内存这个加载的过程损耗的时间称之为 I/O 成本。

CPU 成本

读取以及检测记录是否满足对应的搜索条件、对结果集进行排序等这些操作损耗的时间称之为 CPU 成本。对于 InnoDB 存储引擎来说，页是磁盘和内存之间交互的基本单位，MySQL规定从磁盘读取一个页面花费的成本默认是 1.0；从内存读取花费的成本是0.25 ，读取以及检测一条记录是否符合搜索条件的成本默认是 0.1 。 1.0 、 0.25、0.1 这些数字称之为 成本常数，这两个成本常数我们最常用到。需要注意的是，不管读取记录时需不需要检测是否满足搜索条件，其成本都算是0.1。

单表查询的成本

还是以刚才的表为例，我用Navicat生成10000条数据：

CREATE TABLE single_table (
 id INT NOT NULL AUTO_INCREMENT,
 key1 VARCHAR(100),
 key2 INT,
 key3 VARCHAR(100),
 key_part1 VARCHAR(100),
 key_part2 VARCHAR(100),
 key_part3 VARCHAR(100),
 common_field VARCHAR(100),
 PRIMARY KEY (id),
 KEY idx_key1 (key1),
 UNIQUE KEY idx_key2 (key2),
 KEY idx_key3 (key3),
 KEY idx_key_part(key_part1, key_part2, key_part3)
) Engine=InnoDB CHARSET=utf8;

基于成本的优化步骤

在一条单表查询语句真正执行之前， MySQL 的查询优化器会找出执行该语句所有可能使用的方案，对比之后找出成本最低的方案，这个成本最低的方案就是所谓的 执行计划 ，之后才会调用存储引擎提供的接口真正的执行查询，这个过程总结一下就是这样：

1. 根据搜索条件，找出所有可能使用的索引
2. 计算全表扫描的代价
3. 计算使用不同索引执行查询的代价
4. 对比各种执行方案的代价，找出成本最低的那一个

eg：

SELECT * FROM single_table WHERE 
 key1 IN ('a', 'b', 'c') AND 
 key2 > 10 AND key2 < 1000 AND 
 key3 > key2 AND 
 key_part1 LIKE '%hello%' AND
 common_field = '123';

1、可能用到的索引

对于 B+ 树索引来说，只要索引列和常数使用 = 、 <=> 、 IN 、 NOT IN 、 IS NULL 、
IS NOT NULL 、 > 、 < 、 >= 、 <= 、 BETWEEN 、 != （不等于也可以写成 <> ）或者 LIKE 操作符
连接起来，就可以产生一个所谓的 范围区间 （ LIKE 匹配字符串前缀也行），
也就是说这些搜索条件都可能使用到索引，MySQL =把一个查询中可能使用到的索引称之为 possible keys 。

所以上面sql可能用到的索引有idx_key1、idx_key2。key3>key2因为不是常量间的比较，所以用不上索引

2、计算全表扫描的代价

对于 InnoDB 存储引擎来说，全表扫描的意思就是把聚簇索引中的记录都依次和给定的搜索条件做一下比较，把符合搜索条件的记录加入到结果集，所以需要将聚簇索引对应的页面加载到内存中，然后再检测记录是否符合搜索条件。由于查询成本= I/O 成本+ CPU 成本，所以计算全表扫描的代价需要两个信息：

聚簇索引占用的页面数
该表中的记录数

这两个信息从哪来呢？MySQL 为每个表维护了一系列的 统计信息 ，MySQL 给我们提供了 SHOW TABLE STATUS 语句来查看表的统计信息，如果要看指定的某个表的统计信息，在该语句后加对应的 LIKE 语句就好了，比方说我们要查看 single_table 这个表的统计信息可以这么写：

 SHOW TABLE STATUS LIKE 'single_table'

但如果直接这么运行命令可能会有问题：

很多数据会是0。这是由于这些信息是从 INFORMATION_SCHEMA.TABLES 里获取的。而里面看到的数据是有cache的，默认cache时长是 86400秒（即1天），修改参数 information_schema_stats_expiry 即可调整时长。也就是说，除非cache过期了，或者手动执行 ANALYZE TABLE 更新统计信息，否则不会主动更新。
这个参数（功能）是MySQL 8.0后新增的，所以这个问题在8.0之前的版本不存在。

该参数还可以在session级动态修改。我们直接在session级做修改好了：

set session information_schema_stats_expiry = 0;

修改后再运行：

这样可能不好看：

mysql> SHOW TABLE STATUS LIKE 'single_table'\G;
*************************** 1. row ***************************
           Name: single_table
         Engine: InnoDB
        Version: 10
     Row_format: Dynamic
           Rows: 9749
 Avg_row_length: 163
    Data_length: 1589248
Max_data_length: 0
   Index_length: 2424832
      Data_free: 4194304
 Auto_increment: 10001
    Create_time: 2022-11-24 14:58:04
    Update_time: 2022-11-24 15:17:29
     Check_time: NULL
      Collation: utf8mb3_general_ci
       Checksum: NULL
 Create_options:
        Comment:
1 row in set (0.00 sec)

ERROR:
No query specified

两个重要的字段：

Rows

本选项表示表中的记录条数。对于使用 MyISAM 存储引擎的表来说，该值是准确的，对于使用 InnoDB 存储引擎的表来说，该值是一个估计值。从查询结果我们也可以看出来，由于我们的 single_table 表是使用InnoDB 存储引擎的，所以虽然实际上表中有10000条记录，但是 SHOW TABLE STATUS 显示的 Rows 值只有9749条记录。

Data_length

本选项表示表占用的存储空间字节数。使用 MyISAM 存储引擎的表来说，该值就是数据文件的大小，对于使用 InnoDB 存储引擎的表来说，该值就相当于聚簇索引占用的存储空间大小，也就是说可以这样计算该值的大小：

 Data_length = 聚簇索引的页面数量 x 每个页面的大小

single_table 使用默认 16KB 的页面大小，而上边查询结果显示 Data_length 的值是 1589248 ，所以我们可以反向来推导出 聚簇索引的页面数量 ：

 聚簇索引的页面数量 = 1589248 ÷ 16 ÷ 1024 = 97

---------------------------------------------------画一条分割线---------------------------------------------------------

现在可以计算全表扫描成本了，但是MySQL 在真实计算成本时进行一些 微调 ，这些微调的值是直接硬编码到代码里的，所以知道这么一回事就行。

以下计算io成本的时候用的都是0.25，表示是从内存中拿，为什么不用1 。是因为我用1的话算出来的数对不上。哈哈哈哈哈，结果反推。而且在数据量越大的时候误差也会加大，可能是因为有别的因素吧，因为我数据量弄成50万的时候，这么算就不对了，会少了点，但下面的就是刚刚好的

I/O 成本
 97 x 0.25 + 1.1 = 25.35
97 指的是聚簇索引占用的页面数， 0.25 指的是加载一个页面的成本常数，后边的 1.1 是一个微调值，不用在意。

CPU 成本：
 9749 x 0.1 + 1.0 = 975.9
9693 指的是统计数据中表的记录数，对于 InnoDB 存储引擎来说是一个估计值， 0.1 指的是访问一条记录
所需的成本常数，后边的 1.0 是一个微调值，我们不用在意。
总成本：
 25.35 + 975.9 = 1001.25
综上所述，对于 single_table 的全表扫描所需的总成本就是 1001.25

ps：

我们知道表中的记录其实都存储在聚簇索引对应B+树的叶子节点中，所以只要我们通过根节点获得
了最左边的叶子节点，就可以沿着叶子节点组成的双向链表把所有记录都查看一遍。也就是说全表扫描
这个过程其实有的B+树内节点是不需要访问的，但是设计MySQL的大叔们在计算全表扫描成本时直接使
用聚簇索引占用的页面数作为计算I/O成本的依据，是不区分内节点和叶子节点的，有点儿简单暴力，
大家注意一下就好了。

3、计算使用不同索引执行查询的代价

上述查询可能使用到 idx_key1 和 idx_key2 这两个索引，我们需要分别分析单独使用这些索引执行查询的成本，最后还要分析是否可能使用到索引合并。这里需要提一点的是， MySQL 查询优化器先分析使用唯一二级索引的成本，再分析使用普通索引的成本，所以我们也先分析 idx_key2 的成本，然后再看使用idx_key1 的成本。

使用idx_key2执行查询的成本分析

idx_key2 对应的搜索条件是： key2 > 10 AND key2 < 1000

范围区间数量

不论某个范围区间的二级索引到底占用了多少页面，查询优化器粗暴的认为读取索引的一个范围区间的 I/O成本和读取一个页面是相同的。本例中使用 idx_key2 的范围区间只有一个： (10, 1000) ，所以相当于访问这个范围区间的二级索引付出的 I/O 成本就是：

 1 x 1.0 = 1.0

需要回表的记录数

书里一大串的介绍;我最后也是没看懂是怎样知道一个页里有几条数据的

所以根据先前的知识：EXPLAIN，查出满足这个条件的rows不是轻轻松松？

EXPLAIN SELECT * FROM single_table WHERE key2 > 10 AND key2 < 1000

所以有989 条二级索引记录。读取其需要付出的 CPU 成本就是：

989 x 0.1 + 0.01 = 98.91
其中 989 是需要读取的二级索引记录条数， 0.1 是读取一条记录成本常数， 0.01 是微调。

在通过二级索引获取到记录之后，还需要干两件事儿：

1、根据这些记录里的主键值到聚簇索引中做回表操作
MySQL 评估回表操作的 I/O 成本依旧很豪放，其认为每次回表操作都相当于访问一个页面，
也就是说二级索引范围区间有多少记录，就需要进行多少次回表操作，也就是需要进行多少次页面 I/O 。
我们上边统计了使用idx_key2 二级索引执行查询时，预计有 989 条二级索引记录需要进行回表操作，
所以回表操作带来的 I/O 成本就是：
989 x 0.25 = 247.25
其中 989 是预计的二级索引记录数， 0.25 是一个页面的 I/O 成本常数。


2、回表操作后得到的完整用户记录，然后再检测其他搜索条件是否成立
回表操作的本质就是通过二级索引记录的主键值到聚簇索引中找到完整的用户记录，然后再检测除
key2 > 10 AND key2 < 1000 这个搜索条件以外的搜索条件是否成立。因为我们通过范围区间获取
到二级索引记录共 989 条，也就对应着聚簇索引中 989 条完整的用户记录，读取并检测这些完整的用
户记录是否符合其余的搜索条件的 CPU 成本如下：

MySQL只计算这个查找过程所需的`I/O`成本，也就是我们上一步骤中得到的`989.0`，
在内存中的定位完整用户记录的过程的成本是忽略不计的。在定位到这些完整的用户记录后，需要检测
除`key2 > 10 AND key2 < 1000`这个搜索条件以外的搜索条件是否成立，这个比较过程花费的`CPU`成
本就是：
 989 x 0.1 = 98.9

其中`95`是待检测记录的条数，`0.1`是检测一条记录是否符合给定的搜索条件的成本常数。

使用 idx_key2 执行查询的成本就如下所示：
I/O 成本：
 1.0 + 989 x 0.25 = 248.25 (范围区间的数量 + 预估的二级索引记录条数)
CPU 成本：
 989 x 0.1 + 0.01 + 989 x 0.1 = 197.81 （读取二级索引记录的成本 + 读取并检测回表后聚簇索引记录的成本）
综上所述，使用 idx_key2 执行查询的总成本就是：
247.25+197.81=446.06

使用idx_key1执行查询的成本分析

idx_key1 对应的搜索条件是： key1 IN (‘a’, ‘b’, ‘c’) ，也就是说相当于3个单点区间：

['a', 'a']
['b', 'b']
['c', 'c']

范围区间数量
使用 idx_key1 执行查询时很显然有3个单点区间，所以访问这3个范围区间的二级索引付出的I/O成本就是：
 3 x 0.25 = 0.75
需要回表的记录数
3 x 0.1 + 0.01 = 0.31

根据这些记录里的主键值到聚簇索引中做回表操作
所需的 I/O 成本就是：
 3 x 0.25 = 0.75
回表操作后得到的完整用户记录，然后再比较其他搜索条件是否成立
此步骤对应的 CPU 成本就是：
 3 x 0.1 = 0.3
所以本例中使用 idx_key1 执行查询的成本就如下所示：
I/O 成本：
 0.75 + 0.75 = 1.5 (范围区间的数量 + 预估的二级索引记录条数)
CPU 成本：
 0.31 + 0.3 = 0.61（读取二级索引记录的成本 + 读取并检测回表后聚簇
索引记录的成本）
综上所述，使用 idx_key1 执行查询的总成本就是：
1.5 + 0.61 = 2.11

4、对比各种执行方案的代价，找出成本最低的那一个

2.11肯定小，所以索引选idx_key1。但是吧，这样算的话和mysql的cost差了一点是吧？但全表扫描是一样的：

所以是为什么呢？

在CSDN里看到这样一段话:
除了全表扫描的成本，使用索引的查询成本与自己计算的有较大出入，这是因为在MySQL的实际计算中，在和全文扫描比较成本时，使用索引的成本会去除掉读取和检测回表后聚簇索引记录的成本也就是说，我们通过MySQL看到的成本将会是idx_key1为1.81(2.11-0.3),idx_key2为346.41(446.06-99.65)。但是MySQL比较完成本后，会再计算一次使用索引的成本，此时就会加上前面去除的成本，也就是我们计算出来的值
https://blog.csdn.net/sermonlizhi/article/details/124534608

"considered_execution_plans": [
              {
                "plan_prefix": [
                ],
                "table": "`single_table`",
                "best_access_path": {
                  "considered_access_paths": [
                    {
                      "rows_to_scan": 3,
                      "access_type": "range",
                      "range_details": {
                        "used_index": "idx_key1"
                      },
                      "resulting_rows": 3,
                      "cost": 2.11,	//和我们算出来的成本一样
                      "chosen": true
                    }
                  ]
                },

基于索引统计数据的成本计算

略

连接查询的成本

记一部分

MySQL 中连接查询采用的是嵌套循环连接算法，驱动表会被访问一次，被驱动表可能会被访问多次，所以对于两表连接查询来说，它的查询成本由下边两个部分构成：

单次查询驱动表的成本
多次查询被驱动表的成本（具体查询多少次取决于对驱动表查询的结果集中有多少条记录）

我们把对驱动表进行查询后得到的记录条数称之为驱动表的 扇出 （英文名： fanout ）。很显然驱动表的扇出值
越小，对被驱动表的查询次数也就越少，连接查询的总成本也就越低。当查询优化器想计算整个连接查询所使用
的成本时，就需要计算出驱动表的扇出值，其实就是rows。

连接查询的成本计算公式是这样的：
连接查询总成本 = 单次访问驱动表的成本 + 驱动表扇出数 x 单次访问被驱动表的成本

对于左（外）连接和右（外）连接查询来说，它们的驱动表是固定的，所以想要得到最优的查询方案只需要：
分别为驱动表和被驱动表选择成本最低的访问方法。

可是对于内连接来说，驱动表和被驱动表的位置是可以互换的，所以需要考虑两个方面的问题：
不同的表作为驱动表最终的查询成本可能是不同的，也就是需要考虑最优的表连接顺序。
然后分别为驱动表和被驱动表选择成本最低的访问方法。

所以我们的优化重点其实是下边这两个部分：
尽量减少驱动表的扇出
对被驱动表的访问成本尽量低，尽量在被驱动表的连接列上建立索引

成本常数

前面说了两个 成本常数 ：
从磁盘读取一个页面花费的成本默认是 1.0，从内存中读取一个面的成本是0.25
检测一条记录是否符合搜索条件的成本默认是 0.2

其实除了这两个成本常数， MySQL 还支持好多呢，它们被存储到了 mysql 数据库的两个表中：

SHOW TABLES FROM mysql LIKE '%cost%';

mysql.server_cost表

SELECT * FROM mysql.server_cost;

mysql.engine_cost表

SELECT * FROM mysql.engine_cost;