《MySQL是怎样运行的》一书十一、十二章的相关笔记。掺入了一些自己的理解。
连接基础
MySQL中的连接使用嵌套子循环实现，其中有两个角色：
- 驱动表：子循环中处于外层的表
- 被驱动表：子循环中处于内层的表
而一个连接可以看作是对于驱动表中的每一条满足条件的记录，都对被驱动表使用连接属性进行一次查询，将查询到的结果与驱动表中的记录连接，并添加到结果集中。所以，在一次连接查询中，驱动表被访问一次，被驱动表被访问多次，它的访问次数取决于驱动表中满足条件的记录条数。
对于左连接，右连接这种指定方向的连接，驱动表由用户选择，其它情况下，MySQL会根据具体情况来选择一个驱动表。在整个连接的决策过程中，MySQL会根据实际情况和统计数据动态的在各种决策间进行比较，而且MySQL还有针对连接的一些优化，这些细节后面都会谈到。
连接中
ON和WHERE的区别：对于内连接，它两个的行为没啥区别，而对于外连接，无论ON中的条件是否满足，驱动表中的记录还是会出现在结果集中，ON过滤掉的只是被驱动表的记录。
对于一次两表连接，大致的过程可以看作：
- 根据驱动表的过滤条件，选择一个最佳的对驱动表查询的方法
- 对于驱动表中查询到的每行记录，拿其连接字段上的值，作为被驱动表连接字段上的一个等值查询条件
- 根据这个条件以及被驱动表上的其它条件，选择一个最佳的对被驱动表查询的方法
驱动表和被驱动表的说法太绕嘴了，而且体现在文字上容易混淆，下面我们都说主表和子表。
连接优化：Join Buffer
如果对于主表中的每一条记录都去子表进行一次查询，极端情况下，比如子表没有用到索引，每次查询它时都必须执行一次全表扫描，这会带来一些问题
- 对于主表中的每一行数据，子表都要进行一次全表扫描，磁盘访问次数太多。
- 对于当前外层的主表循环中正在处理的记录，它所在的页面在内存中的缓存可能会由于对子表的全表扫描而被冲出缓存，这样的话对于主表中的每一条数据都要额外多一次磁盘页访问。
实际上，全表扫描只是我举得一个例子，只要子表的访问类型不是const，这个问题都会存在。比如MySQL会在子表的访问是all、index、range等访问类型时使用Join Buffer优化。
Join Buffer就是为了解决这些问题而存在的，它先将主表中的若干条记录放在Join Buffer中，然后在对子表的一次全表扫描中，对这些记录分别进行连接，以降低磁盘访问次数。
连接优化：成本分析
不论是在执行单表查询还是连接查询时，MySQL都有大量的途径来完成一个相同的查询，它们的成本不同，所以MySQL会计算各个途径的成本，择优选择一个来生成执行计划。
- I/O成本：将磁盘页从磁盘加载到内存上用到的成本，一个页面花费
1.0 - CPU成本：在内存中的磁盘页上检索记录用到的成本，一条记录花费
0.2
1.0、0.2，这些数字是InnoDB设计者定的，不用太过纠结。计算成本的时候会使用这些数字作为权重进行计算。
由于连接查询可以看成多个单表查询的嵌套，所以我们先学习单表成本计算。
单表成本计算
对于一个单表查询的成本进行计算的大致过程就是：
- 根据WHERE条件以及其中的索引情况，计算出可能使用的索引
- 对全表扫描进行成本分析
- 对每一个可能使用的索引进行成本分析
- 取其中成本最小的
计算可能使用的索引
举个例子
当前已有的索引：
id：主键（查询中并没给出该列）key1：非唯一二级索引key2：唯一二级索引key3：非唯一二级索引keypart1, keypart2, keypart3：非唯一联合索引
对于该查询，如果使用key1，索引的扫描范围被限制在[a, a]、[b, b]、[c, c]这三个单点区间上，如果使用key2，索引扫描范围被限制在(10, 1000)这个范围区间上，如果使用key3，由于比较的另一端并非常数值，所以扫描范围是一(-inf, +inf)，key_part1由于不符合最左前缀原则，扫描范围也是(-inf, +inf)。这个查询的possible_keys = [key1, key2]。
对全表扫描进行成本分析
如果使用全表扫描，IO成本等于该表所占用的所有磁盘页，CPU成本就等于该表中的记录条数 x 0.2。
MySQL中维护了每个表的一些统计信息，其中包含每个表的记录条数Rows和每个表占用的存储空间字节数Data_Length。这些统计信息由存储引擎收集并上报，对于InnoDB来说，这些数据都是预估值。
所以，全表扫描的成本：
IO成本：\(1.0 \times (Data\_Length \div PageSize) + 1.1\)CPU成本：\(0.2 \times Rows + 1.0\)总成本：IO成本 + CPU成本
我们注意到，成本计算中的后面都有一个附加项，
1.1或1.0，这是一些微调值，后面也会见到，不用过多在意它们，也不用纠结于它们起了什么作用。
对使用索引进行成本分析
对于索引进行成本分析就没有那么简单了，除了对索引自身的扫描带来的成本进行分析，还要考虑对于每一个索引项回表扫描的成本。
先看索引自身的IO成本以及CPU成本
MySQL设计者粗略地认为，一个索引扫描区间的成本就是读取一个磁盘页的成本，无论在索引的物理存储中，这个区间实际上跨越了多少磁盘页。
而CPU成本则依赖这个区间中具体有多少索引项，InnoDB实际在B+树中找到区间的最左边界所在的页，再找出最右边界所在的页，由于所有索引页都被连成了一个链表，只需要从左到右依次访问并读取其页面Page Header中的PAGE_N_RECS属性，得到页面中的记录数即可。如果左到右相差不到10个页，就来精确的累加，否则只取前10个页，计算每个页包含的记录数的平均值，再乘以二者中间差的页面数量即可。要统计这个数量，可以找它们的父节点之间隔着几条记录，如果它们已经不属于一个父节点，就递归查找父节点的父节点，大概就是按照这个思路来计算。这种实际进行索引扫描来确定索引项个数的方式被称为index dive，可能意思就是潜入索引结构中一探究竟的意思吧。
那么现在，索引自身的成本如下：
IO成本：\(1.0 \times ScanRegionCnt\) （扫描区间个数）CPU成本：\(0.2 \times IndexEntryCnt + 0.01\) （索引项个数）
下面看回表扫描的成本
IO成本：\(1.0 \times IndexEntryCnt\) （每个匹配的索引项都要回表）CPU成本：\(0.2 \times IndexEntryCnt\)
所以，总成本就是将这四个成本加起来。
其实你无需理解MySQL计算成本的细节，你就知道它为了计算成本需要干什么，哪些是计算成本时需要考虑的就行了呗。
MySQL还有索引合并优化，引入这一优化后，成本的计算要考虑的东西更多了，这里不考虑。
基于统计信息计算索引成本
计算索引的成本时，我们需要估算（或者实际计算）出有多少索引项，这需要最多进行十个（如果涉及到父节点会更多）磁盘页的扫描，一般的查询索引条件不会生成大量的扫描区间，但也有一些极端用法，比如：
SELECT x FROM t WHERE c IN (
1, 2, 3,
... 19997 more ...
)
上面的索引生成了20000个扫描区间，对于上面提到的成本计算方式，这个区间量是不可忍受的。
在扫描区间的数量大于eq_range_index_dive_limit设定的值时，使用统计信息计算索引成本，而不是实际真正的使用index dive进行扫描。
MySQL中同样维护了索引的一些统计数据，SHOW INDEX FROM <表名>可以找出一个表中所有索引的统计数据。我们主要使用索引统计信息中的Cardinality这个信息，也就是索引选择率，它描述了索引中不重复数据量占数据总量的比率。当它为100，索引中全都是不重复数据，当它为1，索引中的数据都是重复的。选择率越高，索引效率越高。
然后，每个区间中的索引项数量可以用\(Rows \div Cardinality\)计算，Rows从表统计数据中拿，就像上面所说的。