MySQL复习（一）：MySQL基础架构、InnoDB体系架构、MySQL日志、MySQL索引

一、MySQL基础架构

MySQL可以分为Server层和存储引擎层两部分

Server层包括连接器、查询缓存、分析器、优化器、执行器等，涵盖MySQL的大多数核心服务功能，以及所有的内置函数（如日期、时间、数学和加密函数等），所有跨存储引擎的功能都在这一层实现，比如存储过程、触发器、视图等

存储引擎层负责数据的存储和提取。其架构模式是插件式的，支持InnoDB、MyISAM、Memory等多个存储引擎。现在最常用的存储引擎是InnoDB，它从MySQL 5.5.5版本开始成为了默认存储引擎

不同的存储引擎共用一个Server层

1、连接器

连接器负责跟客户端建立连接、获取权限、维持和管理连接。连接命令一般是：

mysql -h$ip -P$port -u$user -p

连接命令中的mysql是客户端工具，用来跟服务端建立连接。在完成TCP握手后，连接器就要开始认证身份

• 如果用户名或密码不对，就会收到一个"Access denied for user"的错误，然后客户端程序结束执行
• 如果用户名密码认证通过，连接器回到权限表里面查出你拥有的权限。之后，这个连接里面的权限判断逻辑，都将依赖于此时读到的权限

一个用户成功建立连接后，即使用管理员帐号对这个用户的权限做了修改，也不会影响已经存在连接的权限。修改完成后，只有再新建的连接才会使用新的权限设置

连接完成后，如果没有后续的动作，这个连接就处于空闲状态，可以在show processlist命令中查看

Command为Sleep表示此连接是一个空闲连接

客户端如果太长时间没动静，连接器就会自动将它断开。这个时间是由参数wait_timeout控制的。默认值是8小时

如果在连接被断开之后，客户端再次发送请求的话，就会收到一个错误提示：Lost connection to MySQL server during query。这时候就需要重新连接，然后在执行请求了

数据库里面，长连接是指连接成功后，如果客户端持续有请求，则一直使用同一个连接。短连接则是指每次执行完很少的几次查询就断开连接，下次查询再重新建立一个

建立连接的过程通常是比较复杂的，所以建议尽量使用长连接

但是全部使用长连接后，有些时候MySQL占用内存涨得特别快，这是因为MySQL在执行过程中临时使用的内存是管理在连接对象里面的。这些资源会在连接断开的时候才释放。所以如果长连接累计下来，可能导致内存占用太大，被系统强行杀掉（OOM），从现象看就是MySQL异常重启了

可以通过以下两种方案解决这个问题：

• 定期断开长连接。使用一段时间，或者程序里面判断执行过一个占用内存的大查询后，断开连接，之后要查询再重连

• 如果使用的是MySQL5.7+，可以在每次执行一个比较大的操作后，通过执行mysql_reset_connection来重新初始化连接资源。这个过程不需要重连和重新做权限验证，但是会将连接恢复到刚刚创建完时的状态

2、查询缓存

MySQL拿到一个查询请求后，会先到查询缓存看看，之前是不是执行过这条语句。之前执行过的语句及其结果可能会以key-value对的形式，被直接缓存在内存中。key是查询的语句，value是查询的结果。如果查询能够直接在这个缓存中找到key，那么这个value就会被直接返回给客户端

如果语句不在查询缓存中，就会继续后面的执行阶段。执行完成后，执行结果会被存入查询缓存中。如果查询命中缓存，MySQL不需要执行后面的复杂操作，就可以直接返回结果

但是大多数情况下不建议使用查询缓存，因为查询缓存的失效非常频繁，只要对一个表的更新，这个表上所有的查询缓存都会被清空。对于更新压力大的数据库来说，查询缓存的命中率会非常低

MySQL8.0版本直接将查询缓存的整块功能删掉了

3、分析器

分析器会先做词法分析。输入的是由多个字符串和空格组成的一条SQL语句，MySQL需要识别出里面的字符串分别是什么，代表什么

select * from T where ID=10；

MySQL从输入的select这个关键字识别出来，这是一个查询语句。它也要把字符串T识别成表名T，把字符串ID识别成列ID

做完了这些识别以后，就要做语法分析。根据词法分析的结果，语法分析器会根据语法规则，判断这个SQL语句是否满足MySQL语法

4、优化器

优化器是在表里面有多个索引的时候，决定使用哪个索引；或者在一个语句有多表关联的时候，决定各个表的连接顺序

5、执行器

执行器阶段，开始执行语句。开始执行的时候，要先判断一下你对这个表T有没有执行查询的权限，如果没有，就会返回没有权限的错误；如果有权限，就打开表继续执行

select * from T where ID=10；

打开表的时候，执行器就会根据表的引擎定义，去使用这个引擎提供的接口

比如在表T中，ID字段没有索引，那么执行器的执行流程是这样的：

1）调用InnoDB引擎接口取这个表的第一行，判断ID值是不是10，如果不是则跳过；如果是则将这个行存在结果集中

2）调用引擎接口取下一行，重复相同的判断逻辑，直到取到这个表的最后一行

3）执行器将上述遍历过程中所有满足条件的行组成的记录集作为结果集返回给客户端

二、InnoDB体系架构

InnoDB主要包括了内存池、后台线程以及存储文件

1、后台线程

InnoDB存储引擎是多线程的模型

1）、Master Thread

Master Thread主要负责将缓存池中的数据异步刷新到磁盘，保证数据的一致性，包括脏页的刷新、合并插入缓冲（Insert Buffer）、undo页的回收等

2）、IO Thread

在InnoDB中大量使用了AIO来处理写IO请求，而IO Thread的工作主要是负责这些IO请求的回调处理。IO Thread分为write、read、insert buffer和log IO thread四种

3）、Purge Thread

事务被提交后，其所使用的undo log可能不再需要，因此需要Purge Thread来回收已经使用并分配的undo页

4）、Page Cleaner Thread

Page Cleaner Thread是一个用于协助Master Thread刷新脏页到磁盘的线程

2、内存

1）、缓冲池（Buffer Pool）

InnoDB存储引擎是基于磁盘存储的，而缓冲池是一块内存区域，通过内存的速度来弥补磁盘速度较慢对数据库性能的影响

在数据库中进行读取页的操作，首先将从磁盘读到的页存放在缓冲池中。下一次再读相同的页时，首先判断该页是否在缓冲池中。若在缓冲池中，称该页在缓冲池中被命中，直接读取该页。否则，读取磁盘上的页

对于数据库中页的修改操作，则首先修改在缓冲池中的页，然后再以一定的频率刷新到磁盘上。页从缓冲池刷新回磁盘的操作并不是在每次页发生更新时触发，而是通过一种称为Checkpoint的机制刷新回磁盘

缓冲池中缓存的数据页类型有：索引页、数据页、undo页、插入缓冲（insert buffer）、自适应哈希索引、InnoDB存储的锁信息、数据字典信息等

2）、LRU List、Free List和Flush List

1）LRU List

InnoDB缓冲池的内存管理使用最近最少使用（LRU）算法并在此基础上做了优化：

在InnoDB实现上，按照5：3的比例把整个LRU链表分成了young区域和old区域。图中LRU_old指向的就是old区域的第一个位置，是整个链表的5/8处。也就是说，靠近链表头部的5/8是young区域，靠近链表尾部的3/8是old区域

1.上图中状态1，要访问数据页P3，由于P3在young区域，因此和优化前的LRU算法一样，将其移到链表头部，变成状态2

2.之后要访问一个新的不存在于当前链表的Pm，但是新插入的数据页Px，是放在LRU_old处

3.处于old区域的数据页，每次被访问的时候都要做下面这个判断：

• 若这个数据页在LRU链表中存在的时间超过了1秒，就把它移动到链表头部
• 如果这个数据页在LRU链表中存在的时间短于1秒，位置保持不变。1秒这个时间，是由参数innodb_old_blocks_time控制的。默认值是1000，单位是毫秒

这个优化策略就是为了处理类似全表扫描的操作量身定制的：

1.扫描过程中，需要新插入的数据页，都被放到old区域

2.一个数据页里面有多条记录，这个数据页会被多次访问到，但由于是顺序扫描，这个数据页第一次被访问和最后一次被访问的时间间隔不会超过1秒，因此还是会被保留在old区域

3.再继续扫描后续的数据，之前的这个数据页之后也不会再被访问到，于是始终没有机会移到链表头部，很快就会被淘汰出去

这个优化策略最大的收益就是在扫描大表的过程中，虽然也用到了缓冲池，但是对young区域完全没有影响，从而保证了缓冲池响应正常业务的查询命中率

2）Free List

当需要从缓冲池中分页时，首先从Free列表中查找是否有可用的空闲页，若有则将该页从Free列表中删除，放入到LRU列表中。否则，根据LRU算法，淘汰LRU列表末尾的页，将该内存空间分配给新的页

3）Flush List

在LRU列表中的页被修改后，称该页为脏页，即缓冲池中的页和磁盘上的页的数据产生了不一致。这时数据库会通过Checkpoint机制将脏页刷新回磁盘，而Flush列表中的页即为脏页列表

脏页既存在于LRU列表中，也存在于Flush列表中。LRU列表用来管理缓冲池中页的可用性，Flush列表用来管理奖页刷新回磁盘，二者互不影响

3、redo log buffer（重做日志缓冲）

InnoDB首先将redo log放入到redo log buffer，然后按一定频率将其刷新到redo log file

下列三种情况下会将redo log buffer刷新到redo log file：

• Master Thread每一秒将redo log buffer刷新到redo log file
• 每个事务提交时会将redo log buffer刷新到redo log file
• 当redo log缓冲池剩余空间小于1/2时，会将redo log buffer刷新到redo log file

4、额外的内存池

在对一些数据结构本身的内存进行分配时，需要从额外的内存池中进行申请，当该区域的内存不够时，会从缓冲池中进行申请。例如，分配了缓冲池，但是每个缓冲池中的帧缓冲还有对应的缓冲控制对象，这些对象记录了一些诸如LRU、锁、等待等信息，而这个对象的内存需要从额外内存池中申请

5、插入缓冲

1）、Insert Buffer

在进行插入操作时，数据页的存放是按主键进行顺序存放的，但是对于非主键索引叶子节点的插入不再是顺序的了，这时就需要离散地访问非主键索引页，由于磁盘随机读取而导致了插入操作性能下降

Insert Buffer和数据页一样，也是物理页的一个组成部分。对于非主键索引的插入或更新操作，不是每一次直接插入到索引页中，而是先判断插入的非主键索引页是否在缓冲池中，若在，则直接插入；若不在，则先放入到一个Insert Buffer对象中，然后再以一定的频率和情况进行Insert Buffer和非主键索引页子节点的merge（合并）操作，这时通常能将多个插入合并到一个操作中（因为在一个索引页中），这就大大提高了对于非主键索引插入的性能

Insert Buffer的使用需要同时满足以下两个条件：

• 索引是非主键索引
• 索引不是唯一的

2）、Change Buffer

InnoDB对DML操作——Insert、Delete、Update都进行缓冲，分别是Insert Buffer、Delete Buffer、Purge Buffer。Change Buffer的适用对象依然是非唯一的非主键索引

3）、Merge Insert Buffer

merge的执行流程：

1.从磁盘读入数据页到内存（老版本的数据页）

2.从Change Buffer里找出这个数据页的Change Buffer记录（可能有多个），依次应用，得到新版数据页

3.写redo log。这个redo log包含了数据的变更和Change Buffer的变更

到这里merge过程就结束了。这时候，数据页和内存中Change Buffer对应的磁盘位置都还没有修改，属于脏页，之后各自刷回自己的物理数据，就是另外一个过程了

redo log主要节省的是随机写磁盘的IO消耗（转成顺序写），而Change Buffer主要节省的是随机读磁盘的IO消耗

​

三、MySQL日志

1、 redo log（重做日志）

MySQL里常说的WAL技术，全称是Write Ahead Log，即当事务提交时，先写redo log，再修改页。也就是说，当有一条记录需要更新的时候，InnoDB会先把记录写到redo log里面，并更新Buffer Pool的page，这个时候更新操作就算完成了

Buffer Pool是物理页的缓存，对InnoDB的任何修改操作都会首先在Buffer Pool的page上进行，然后这样的页将被标记为脏页并被放到专门的Flush List上，后续将由专门的刷脏线程阶段性的将这些页面写入磁盘

InnoDB的redo log是固定大小的，比如可以配置为一组4个文件，每个文件的大小是1GB，循环使用，从头开始写，写到末尾就又回到开头循环写（顺序写，节省了随机写磁盘的IO消耗）

Write Pos是当前记录的位置，一边写一边后移，写到第3号文件末尾后就回到0号文件开头。Check Point是当前要擦除的位置，也是往后推移并且循环的，擦除记录前要把记录更新到数据文件

Write Pos和Check Point之间空着的部分，可以用来记录新的操作。如果Write Pos追上Check Point，这时候不能再执行新的更新，需要停下来擦掉一些记录，把Check Point推进一下

当数据库发生宕机时，数据库不需要重做所有的日志，因为Check Point之前的页都已经刷新回磁盘，只需对Check Point后的redo log进行恢复，从而缩短了恢复的时间

当缓冲池不够用时，根据LRU算法会溢出最近最少使用的页，若此页为脏页，那么需要强制执行Check Point，将脏页刷新回磁盘

2、binlog（归档日志）

MySQL整体来看就有两块：一块是Server层，主要做的是MySQL功能层面的事情；还有一块是引擎层，负责存储相关的具体事宜。redo log是InnoDB引擎特有的日志，而Server层也有自己的日志，称为binlog

binlog记录了对MySQL数据库执行更改的所有操作，不包括SELECT和SHOW这类操作，主要作用是用于数据库的主从复制及数据的增量恢复

使用mysqldump备份时，只是对一段时间的数据进行全备，但是如果备份后突然发现数据库服务器故障，这个时候就要用到binlog的日志了

binlog格式有三种：STATEMENT，ROW，MIXED

1）、STATEMENT模式

binlog里面记录的就是SQL语句的原文。优点是并不需要记录每一行的数据变化，减少了binlog日志量，节约IO，提高性能。缺点是在某些情况下会导致master-slave中的数据不一致

2）、ROW模式

不记录每条SQL语句的上下文信息，仅需记录哪条数据被修改了，修改成什么样了，解决了STATEMENT模式下出现master-slave中的数据不一致。缺点是会产生大量的日志，尤其是alter table的时候会让日志暴涨

3）、MIXED模式

以上两种模式的混合使用，一般的复制使用STATEMENT模式保存binlog，对于STATEMENT模式无法复制的操作使用ROW模式保存binlog，MySQL会根据执行的SQL语句选择日志保存方式

3、redo log和binlog的不同

• redo log是InnoDB引擎特有的；binlog是MySQL的Server层实现的，所有引擎都可以使用
• redo log是物理日志，记录的是在某个数据也上做了什么修改；binlog是逻辑日志，记录的是这个语句的原始逻辑，比如给ID=2这一行的c字段加1
• redo log是循环写的，空间固定会用完；binlog是可以追加写入的，binlog文件写到一定大小后会切换到下一个，并不会覆盖以前的日志

4、两阶段提交

create table T(ID int primary key, c int);

update T set c=c+1 where ID=2;

执行器和InnoDB引擎在执行这个update语句时的内部流程：

1.执行器先找到引擎取ID=2这一行。ID是主键，引擎直接用树搜索找到这一行。如果ID=2这一行所在的数据也本来就在内存中，就直接返回给执行器；否则，需要先从磁盘读入内存，然后再返回

2.执行器拿到引擎给的行数据，把这个值加上1，得到新的一行数据，再调用引擎接口写入这行新数据

3.引擎将这行新数据更新到内存中，同时将这个更新操作记录到redo log里面，此时redo log处于prepare状态。然后告知执行器执行完成了，随时可以提交事务

4.执行器生成这个操作的binlog，并把binlog写入磁盘

5.执行器调用引擎的提交事务接口，引擎把刚刚写入的redo log改成提交状态，更新完成

update语句的执行流程图如下，图中浅色框表示在InnoDB内部执行的，深色框表示是在执行器中执行的

将redo log的写入拆成了两个步骤：prepare和commit，这就是两阶段提交

四、MySQL索引

1、InnoDB的索引模型

InnoDB存储引擎表是索引组织表，即表中数据按照主键顺序存放。InnoDB使用了B+树索引模型，所以数据都是存储在B+树中的。每一个索引在InnoDB里面对应一棵B+树

有一个主键列为ID的表（表1），表中有字段k，并且在k上有索引。这个表的建表语句如下：

create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;

表中R1~R5的(ID,k)值分别为(100,1)、(200,2)、(300,3)、(500,5)和(600,6)，两棵树的示意图如下：

根据叶子节点的内容，索引类型分为主键索引和非主键索引

主键索引的叶子节点存的是整行数据，也被称为聚簇索引；非主键索引的叶子节点内容是主键的值，也被称为辅助索引或者二级索引

主键索引与非主键索引不同的是，叶子节点存放的是否是一整行的信息

基于主键索引和普通索引的查询有什么区别？

• 如果语句是select * from T where ID=500，即主键查询方式，则只需要搜索ID这棵B+树
• 如果语句是select * from T where k=5，即普通索引查询方式，则需要先搜索k索引树，得到ID的值为500，再到ID索引树搜索一次。这个过程称为回表

基于非主键索引的查询需要多扫描一棵索引树。因此，在应用中应该尽量使用主键查询

强制指定索引查询：

select * from `order` force index(PRIMARY) where id=1 and order_no=1

2、B+树

B+树索引并不能找到一个给定键值的具体行。B+树索引能找到的只是被查找数据行所在的页。然后数据库通过把页读入到内存，再在内存中进行查找，最后得到要查找的数据

B+树相对于B树的优势：

• B+树的内部节点（索引节点）不存储数据，只存储索引，数据都存储在叶子节点，单一节点存储的元素更多，使得查询的IO次数更少，所以也就使得它更适合做为数据库MySQL的底层数据结构了
• 所有的查询都要查找到叶子节点，查询性能是稳定的；而B树每个节点都可以查找到数据，所以不稳定
• 所有的叶子节点形成了一个有序链表，更加便于范围查找

3、索引维护

B+树为了维护索引有序性，在插入新值的时候需要做必要的维护

以上图为例，如果插入新的行ID值为700，则只需要在R5的记录后面插入一个新纪录

如果新插入的ID值为400，需要逻辑上挪动后面的数据，空出位置。如果R5所在的数据页已经满了，根据B+树的算法，这时候需要申请一个新的数据页，然后挪动部分数据过去。这个过程称为页分裂。页分裂不仅会影响性能，还会影响数据页的利用率。原本放在一个页的数据，现在分到两个页中，整体空间利用率降低大约50%

当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程可以认为是分裂过程的逆过程

自增主键的插入数据模式，正好符合递增插入的场景。每次插入一条新纪录，都是追加操作，都不涉及到挪动其他记录，也不会触发叶子节点的分裂。而有些业务逻辑的字段做主键，则往往不容易保证有序插入，这样写数据成本相对较高

除了考虑性能外，还可以从存储空间的角度来看。假设表中有一个唯一字段，比如字符串类型的身份证号，如果用身份证号做主键，由于每个非主键索引的叶子节点上都是主键的值，那么每个二级索引的叶子节点占用约20个字节，而如果用整型做主键，则只要4个字节，如果是长整型则是8个字节

主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小

从性能和存储空间方面考虑，自增主键往往是更合理的选择

在只有一个索引，该索引必须是唯一索引的场景下适合用业务字段直接做主键

4、覆盖索引

create table T (
ID int primary key,
k int NOT NULL DEFAULT 0, 
s varchar(16) NOT NULL DEFAULT '',
index k(k))
engine=InnoDB;

对于表T来说，如果执行的语句是select ID from T where k between 3 and 5，这时只需要查ID的值，而ID的值已经在k索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引k已经覆盖了我们的查询需求，称为索引覆盖

由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段

5、最左前缀原则

B+树这种索引结构，可以利用索引的最左前缀来定位记录

CREATE TABLE `tuser` (
  `id` int(11) NOT NULL,
  `id_card` varchar(32) DEFAULT NULL,
  `name` varchar(32) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  `ismale` tinyint(1) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `id_card` (`id_card`),
  KEY `name_age` (`name`,`age`)
) ENGINE=InnoDB；

以表tuser的(name,age)这个联合索引为例来分析

索引项是按照索引定义里面出现的字段顺序排序的

如果要查的是所有名字是"张三"的人，可以快速定位到ID4，然后向后遍历得到所有需要的结果

如果要查的是所有名字第一个字是"张"的人，SQL语句的条件是where name like '张%'，也能够用上这个索引，查找到第一个符合条件的记录是ID3，然后向后遍历，直到不满足条件位置

只要满足最左前缀，就可以利用索引来加速检索。这个最左前缀可以是联合索引的最左N个字段，也可以是字符串索引的最左M个字符

在建立联合索引的时候，如何安排索引内的字段顺序？

第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的

在tuser上创建 (身份证号，姓名)这个联合索引，并用这个索引支持"根据身份证号查询地址"的需求

如果既有联合查询，又有基于a、b各自的查询，需要同时维护(a,b)、(b)这两个索引。考虑的原则就是空间了，name字段是比age字段大的，那么可以创建一个(name,age)的联合索引和一个(age)的单字段索引

6、索引下推

以表tuser的联合索引(name,age)为例，如果要检索出表中名字第一个字是"张"，而且年龄是10岁的所有男孩，SQL语句如下：

select * from tuser where name like '张%' and age=10 and ismale=1;

根据索引前缀规则，所以这个语句在搜索索引树的时候，只能用"张"，找到第一个满足条件的记录ID3，然后判断其他条件是否满足

在MySQL5.6之前，只能从ID3开始一个回表。到主键索引上找到数据行，再对比字段值

MySQL5.6引入的索引下推优化，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数

无索引下推执行流程图：

索引下推执行流程图：

上面两个图中，每一个虚线箭头表示回表一次

无索引下推执行流程图中，这个过程InnoDB并不会去看age的值，只是按顺序把name第一个字是“张”的记录一条条取出来回表。因此，需要回表4次

索引下推执行流程图中，InnoDB在(name,age)索引内部就判断了age是否等于10，对于不等于10的记录，直接判断并跳过

7、join语句算法及优化

1）、join语句算法

创建两个表t1和t2

CREATE TABLE `t2` (
  `id` int(11) NOT NULL,
  `a` int(11) DEFAULT NULL,
  `b` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `a` (`a`)
) ENGINE=InnoDB;

CREATE DEFINER=`root`@`%` PROCEDURE `idata`()
BEGIN
	declare i int;
  set i=1;
  while(i<=1000)do
    insert into t2 values(i, i, i);
    set i=i+1;
  end while;
END

create table t1 like t2;
insert into t1 (select * from t2 where id<=100);

这两个表都有一个主键索引id和一个索引a，字段b上无索引。存储过程idata()往表t2里插入了1000行数据，在表t1里插入的是100行数据

1）Index Nested-Loop Join（NLJ）

select * from t1 straight_join t2 on (t1.a=t2.a);

如果直接使用join语句，MySQL优化器可能会选择表t1或t2作为驱动表，通过straight_join让MySQL使用固定的连接方式执行查询，在这个语句里，t1是驱动表，t2是被驱动表

被驱动表t2的字段a上有索引，join过程用上了这个索引，因此这个语句的执行流程是这样的：

1.从表t1中读入一行数据R

2.从数据行R中，取出a字段到表t2里去查找

3.取出表t2中满足条件的行，跟R组成一行，作为结果集的一部分

4.重复执行步骤1到3，直到表t1的末尾循环结束

这个过程可以用上被驱动表的索引，称之为Index Nested-Loop Join，简称NLJ

在这个流程里：

1.对驱动表t1做了全表扫描，这个过程需要扫描100行

2.而对于每一行R，根据a字段去表t2查找，走的是树搜索过程。由于我们构造的数据都是一一对应的，因此每次的搜索过程都只扫描一行，也是总共扫描100行

3.所以，整个执行流程，总扫描行数是200

假设不使用join，只能用单表查询：

1.执行select * from t1，查出表t1的所有数据，这里有100行

2.循环遍历这100行数据：

• 从每一行R取出字段a的值$R.a
• 执行select * from t2 where a=$R.a
• 把返回的结果和R构成结果集的一行

这个查询过程，也是扫描了200行，但是总共执行了101条语句，比直接join多了100次交互。客户端还要自己拼接SQL语句和结果。这么做还不如直接join好

在这个join语句执行过程中，驱动表是走全表扫描，而被驱动表是走树搜索。假设被驱动表的行数是$M$M。每次在被驱动表查一行数据，要先搜索索引a，再搜索主键索引。每次搜索一棵树近似复杂度是$log_2M$log2​M，所以在被驱动表上查一行的时间复杂度是$2*log_2M$2∗log2​M

假设驱动表的行数是$N$N，执行过程就要扫描驱动表$N$N行，然后对于每一行，到被驱动表上匹配一次。因此整个执行过程，近似复杂度是$N+N*2*log_2M$N+N∗2∗log2​M。N对扫描函数的影响更大，因此应该用小表来做驱动表

在可以使用被驱动表的索引的情况下：

• 使用join语句，性能比强行拆成多个单表执行SQL语句的性能要好
• 如果使用join语句的话，需要让小表做驱动表

2）Simple Nested-Loop Join

select * from t1 straight_join t2 on (t1.a=t2.b);

由于表t2的字段b上没有索引，因此每次到t2去匹配的时候，就要做一次全表扫描。这个算法叫做Simple Nested-Loop Join

这样算来，这个SQL请求就要扫描表t2多达100次，总共扫描100*100=10万行

MySQL没有使用这个Simple Nested-Loop Join算法，而是使用了另一个叫作Block Nested-Loop Join的算法，简称BNL

3）Block Nested-Loop Join（BNL）

被驱动表上没有可用的索引，算法的流程如下：

1.把表t1的数据读入线程内存join_buffer中，由于这个语句中写的是select *，因此是把整个表t1放入了内存

2.扫描表t2，把表t2中的每一行取出来，跟join_buffer中的数据作比对，满足join条件的，作为结果集的一部分返回

在这个过程中，对表t1和表t2都做了一次全表扫描，因此总的扫描行数是1100。由于join_buffer是以无序数组的方式组织的，因此对表t2中的每一行，都要做100次判断，总共需要在内存中做的判断次数是100*1000=10万次

使用Simple Nested-Loop Join算法进行查询，扫描行数也是10万行。因此，从时间复杂度上来说，这两个算法是一样的。但是，Block Nested-Loop Join算法的这10万次判断是内存操作，速度上会快很多，性能也更好

假设小表的行数是$N$N，大表的行数是$M$M，那么在这个算法里：

1）两个表都做一次全表扫描，所以总的扫描行数是$M+N$M+N

2）内存中的判断次数是$M*N$M∗N

这时候选择大表还是小表做驱动表，执行耗时是一样的

join_buffer的大小是由参数join_buffer_size设定的，默认值是256k。如果放不下表t1的所有数据话，策略很简单，就是分段放

1）扫描表t1，顺序读取数据行放入join_buffer中，假设放到第88行join_buffer满了

2）扫描表t2，把t2中的每一行取出来，跟join_buffer中的数据做对比，满足join条件的，作为结果集的一部分返回

3）清空join_buffer

4）继续扫描表t1，顺序读取最后的12行放入join_buffer中，继续执行第2步

由于表t1被分成了两次放入join_buffer中，导致表t2会被扫描两次。虽然分成两次放入join_buffer，但是判断等值条件的此时还是不变的

假设，驱动表的数据行数是$N$N，需要分成$K$K段才能完成算法流程，被驱动表的数据行数是$M$M。这里的$K$K不是常数，$N$N越大$K$K就会越大，因此把$K$K表示为$λ*N$λ∗N，λ的取值范围是$(0,1)$(0,1)。所以，在这个算法的执行过程中：

1.扫描行数是$N+λ*N*M$N+λ∗N∗M

2.内存判断$N*M$N∗M次

考虑到扫描行数，$N$N小一些，整个算式的结果会更小。所以应该让小表当驱动表

4）能不能使用join语句？

• 如果可以使用Index Nested-Loop Join算法，也就是说可以用上被驱动表上的索引，其实是没问题的

• 如果使用Block Nested-Loop Join算法，扫描行数就会过多。尤其是在大表上的join操作，这样可能要扫描被驱动表很多次，会占用大量的系统资源。所以这种join尽量不要用

5）如果使用join，应该选择大表做驱动表还是选择小表做驱动表

1.如果是Index Nested-Loop Join算法，应该选择小表做驱动表

2.如果是Block Nested-Loop Join算法：

• 在join_buffer_size足够大的时候，是一样的
• 在join_buffer_size不够大的时候，应该选择小表做驱动表

在决定哪个表做驱动表的时候，应该是两个表按照各自的条件过滤，过滤完成以后，计算参数join的各个字段的总数据量，数据量小的那个表，就是小表，应该作为驱动表

2）、join语句优化

创建两个表t1、t2

create table t1(id int primary key, a int, b int, index(a));
create table t2 like t1;

CREATE DEFINER = CURRENT_USER PROCEDURE `idata`()
BEGIN
	declare i int;
  set i=1;
  while(i<=1000)do
    insert into t1 values(i, 1001-i, i);
    set i=i+1;
  end while;
  
  set i=1;
  while(i<=1000000)do
    insert into t2 values(i, i, i);
    set i=i+1;
  end while;

END;

在表t1中，插入了1000行数据，每一行的a=1001-id的值。也就是说，表t1中字段a是逆序的。同时，在表t2中插入了100万行数据

1）Multi-Range Read（MRR）优化

Multi-Range Read（MRR）优化主要的目的是尽量使用顺序读盘

select * from t1 where a>=1 and a<=100;

主键索引是一棵B+树，在这棵树上，每次只能根据一个主键id查到一行数据。因此，回表是一行行搜索主键索引的

如果随着a的值递增顺序查找的话，id的值就变成随机的，那么就会出现随机访问，性能相对较差

因为大多数的数据都是按照主键递增顺序插入得到的，所以如果按照主键的递增顺序查询，对磁盘的读比较接近顺序读，能够提升读性能

这就是MRR优化的设计思路，语句的执行流程如下：

1.根据索引a，定位到满足条件的记录，将id值放入read_rnd_buffer中

2.将read_rnd_buffer中的id进行递增排序

3.排序后的id数组，依次到主键id索引中查记录，并作为结果返回

read_rnd_buffer的大小是由read_rnd_buffer_size参数控制的。如果步骤1中，read_rnd_buffer放满了，就会先执行完步骤2和3，然后清空read_rnd_buffer。之后继续找索引a的下个记录，并继续循环

如果想要稳定地使用MRR优化的话，需要设置set optimizer_switch="mrr_cost_based=off"

explain结果中，Extra字段多了Using MRR，表示的是用上了MRR优化。由于在read_rnd_buffer中按照id做了排序，所以最后得到的结果也是按照主键id递增顺序的

MRR能够提升性能的核心在于，这条查询语句在索引a上做的是一个范围查询，可以得到足够多的主键id。这样通过排序以后，再去主键索引查数据，才能体现出顺序性的优势

2）Batched Key Access（BKA）

MySQL5.6引入了Batched Key Access（BKA）算法。这个BKA算法是对NLJ算法的优化

NLJ算法流程图：

NLJ算法执行的逻辑是从驱动表t1，一行行地取出a的值，再到被驱动表t2去做join

BKA算法流程图：

BKA算法执行的逻辑是把表t1的数据取出来一部分，先放到一个join_buffer，一起传给表t2。在join_buffer中只会放入查询需要的字段，如果join_buffer放不下所有数据，就会将数据分成多段执行上图的流程

如果想要使用BKA优化算法的话，执行SQL语句之前，先设置

set optimizer_switch='mrr=on,mrr_cost_based=off,batched_key_access=on';

其中前两个参数的作用是启用MRR，原因是BKA算法的优化要依赖与MRR

3）BNL算法的性能问题

InnoDB对Buffer Pool的LRU算法做了优化，即：第一次从磁盘读入内存的数据页，会先放在old区域。如果1秒之后这个数据页不再被访问了，就不会被移动到LRU链表头部，这样对Buffer Pool的命中率影响就不大

如果一个使用BNL算法的join语句，多次扫描一个冷表，而且这个语句执行时间超过1秒，就会在再次扫描冷表的时候，把冷表的数据页移到LRU链表头部。这种情况对应的，是冷表的数据量小于整个Buffer Pool的3/8，能够完全放入old区域的情况

如果这个冷表很大，就会出现另外一种情况：业务正常访问的数据页，没有机会进入young区域。

由于优化机制的存在，一个正常访问的数据页，要进入young区域，需要隔1秒后再次被访问到。但是，由于join语句在循环读磁盘和淘汰内存页，进入old区域的数据页，很可能在1秒之内就被淘汰了。这样就会导致MySQL实例的Buffer Pool在这段时间内，young区域的数据页没有被合理地淘汰

BNL算法对系统的影响主要包括三个方面：

1.可能会多次扫描被驱动表，占用磁盘IO资源

2.判断join条件需要执行$M*N$M∗N次对比，如果是大表就会占用非常多的CPU资源

3.可能会导致Buffer Pool的热数据被淘汰，影响内存命中率

4）BNL转BKA

一些情况下，我们可以直接在被驱动表上建索引，这时就可以直接转成BKA算法了

如果碰到一些不适合在被驱动表上建索引的情况，可以考虑使用临时表。大致思路如下：

select * from t1 join t2 on (t1.b=t2.b) where t2.b>=1 and t2.b<=2000;

1.把表t2中满足条件的数据放在临时表tmp_t中

2.为了让join使用BKA算法，给临时表tmp_t的字段b加上索引

3.让表t1和tmp_t做join操作

SQL语句写法如下：

create temporary table temp_t(id int primary key, a int, b int, index(b))engine=innodb;
insert into temp_t select * from t2 where b>=1 and b<=2000;
select * from t1 join temp_t on (t1.b=temp_t.b);

8、order by是怎么工作的

在市民表中，要查询城市是杭州的所有人名字，并且按照姓名排序返回前1000个人的姓名、年龄

表定义如下：

CREATE TABLE `t` (
  `id` int(11) NOT NULL,
  `city` varchar(16) NOT NULL,
  `name` varchar(16) NOT NULL,
  `age` int(11) NOT NULL,
  `addr` varchar(128) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `city` (`city`)
) ENGINE=InnoDB;

SQL语句如下：

select city,name,age from t where city='杭州' order by name limit 1000;

1）、全字段排序

city字段上创建索引之后，用explain命令查看这个语句的执行情况：

Extra这个字段中的Using filesort表示的就是需要排序，MySQL会给每个线程分配一块内存用于排序，称为sort_buffer

city索引示意图：

从上图中可以看到，满足city='杭州’条件的行，是从ID_X到ID_(X+N)的这些记录

这个语句执行流程如下：

1.初始化sort_buffer，确定放入name、city、age这三个字段

2.从索引city找到第一个满足city='杭州’条件的主键id，也就是图中的ID_X

3.到主键id索引取出整行，取name、city、age三个字段的值，存入sort_buffer

4.从索引city取下一个记录的主键id

5.重复步骤3、4直到city的值不满足查询条件为止，对应的主键id也就是图中的ID_Y

6.对sort_buffer中的数据按照字段name做快速排序

7.按照排序结果取前1000行返回给客户端

全字段排序流程图：

按name排序这个动作，可能在内存中完成，也可能需要使用外部排序，这取决于排序所需的内存和参数sort_buffer_size。sort_buffer_size就是MySQL为排序开辟的内存的大小。如果要排序的数据量小于sort_buffer_size，排序就在内存中完成。但如果排序数据量太大，内存放不下，则不得不利用磁盘临时文件辅助排序

2）、rowid排序

全字段排序算法有个问题，如果查询要返回的字段很多的话，那么sort_buffer里面放的字段数太多，这样内存里能够同时放下的行数很少，要分成很多个临时文件，排序的性能会很差

SET max_length_for_sort_data = 16;

max_length_for_sort_data是MySQL中专门控制用于排序的行数据的长度的一个参数。它的意思是，如果单行的长度超过这个值，MySQL就认为单行太大，要换一个算法

新的算法放入sort_buffer的字段，只有要排序的列和主键id

整个执行流程如下：

1.初始化sort_buffer，确定放入两个字段，即name和id

2.从索引city找到第一个满足city='杭州’条件的主键id，也就是ID_X

3.到主键id索引取出整行，取name、id这两个字段，存入sort_buffer

4.从索引city去下一个记录的主键id

5.重复3、4直到不满足city='杭州’条件为止，也就是ID_Y

6.对sort_buffer中的数据按照字段name进行排序

7.遍历排序结果，取前1000行，并按照id的值回到原表中取出city、name和age三个字段返回个客户端

rowid排序流程图：

对比全字段排序流程图，rowid排序多访问一次表t的主键索引

3）、全字段排序 vs rowid排序

如果MySQL担心排序内存太小，会影响排序效率，才会采用rowid排序算法，这样排序过程中一次可以排序更多行，但是需要再回到原表去取数据

如果MySQL认为内存足够大，会优先选择全字段排序，把需要的字段都放在sort_buffer中，这样排序后就会直接从内存里面返回查询结果了，不用再回到原表去取数据

MySQL的设计思想：如果内存够，就要多利用内存，尽量减少磁盘访问

对于InnoDB表来说，rowid排序会要求回表多造成磁盘读，因此不会被优先选择

4）、使用联合索引

在这个市民表上创建一个city和name的联合索引，对应的SQL语句如下：

alter table t add index city_user(city, name);

在这个索引里面，依然可以用树搜索的方式定位到第一个满足city='杭州’的记录，并且额外确保了，接下来按顺序取下一条记录的遍历过程中，只要city的值是杭州，name的值就一定是有序的

整个查询过程的流程就变成了：

1.从索引(city,name)找到第一个满足city='杭州’条件的主键id

2.到主键id索引取出整行，取name、city、age三个字段的值，作为结果集的一部分直接返回

3.从索引(city,name)取下一个记录主键id

4.重复2、3，直到查到第1000条记录，或者是不满足city='杭州’条件时循环结束

这个查询过程不需要临时表，也不需要排序

从图中可以看到，Extra字段中没有Using filesort了，也就是不需要排序了。而且由于(city,name)这个联合索引本身有序，所以这个查询也不用把4000行全都读一遍。在这个例子只需要扫描1000次

5）、使用覆盖索引

覆盖索引是指索引上的信息足够满足查询请求，不需要再回到主键索引上去取数据

创建一个city、name和age的联合索引，对应的SQL语句如下：

alter table t add index city_user_age(city, name, age);

1.从索引(city, name, age)找到第一个满足city='杭州’的记录，取出其中的city、name和age这三个字段的值，作为结果集的一部分直接返回

2.从索引(city, name, age)取下一个记录，同样取出这三个字段的值，作为结果集的一部分直接返回

3.重复执行步骤2，直到查到第1000条记录，或者是不满足city='杭州’条件时循环结束

Extra字段里面多了Using index，表示的就是使用了覆盖索引，性能上会快很多