MySQL怎样运行的

MYSQL记录行格式

记录头信息中各二进制位代表的详细信息

MYSQL为每个记录默认添加的列

在COMPACT行格式中，所有变长字段的真实数据占用的字节数都存放在记录的开头位置，从而形成一个变长字段长度列表，各变长字段的真实数据占用的字节数以及NULL值列表的二进制位按照对应的列的顺序逆序存放。
InnoDB表的主键生成策略:优先使用用户自定义的主键作为主键，如果用户没有定义主键，则选取一个不允许存储NULL值的UNIQUE键作为主键，如果表中连不允许存储NULL值的UNIQUE键都没有，则InnoDB会为表默认添加一个名为row_id的隐藏列作为主键(序号全局递增)
MYSQL5.7版本下默认的行格式为DYNAMIC，它与COMPACT行格式几乎一致，只不过在处理溢出列的数据时有不同的地方。COMPACT在记录的真实数据处会存储该溢出列真实数据的前768个字节的数据，而DYNAMIC不会，只存储20字节大小的指向溢出页的地址。Mysql规定，一个数据页中最少需要存储两条记录。

InnoDB数据页格式

Infimum和Supremum

这两条检录是默认创建的记录，他们的heap_no值分别为0和1，虽然他两没有主键值，但是MYSQL规定，Infimum记录是一个页面中最小的记录，Supremum记录是一个页面中最大的记录。

Page Directory页目录

它将所有正常的记录(包括Infimum和Supremum，但不包括已经移除到垃圾链表的记录)划分为几个组，每个组的最后一条记录(也就是组内最大的那条记录)相当于“带头大哥”，组内其余的记录相当于“小弟”。“带头大哥”记录的头信息中的n_owned属性表示该组内共有几条记录。将每个组中最后一条记录在页面中的地址偏移量(就是该记录的真实数据与页面中第0个字节之间的距离)单独提取出来，按顺序存储到靠近页尾部的地方。这个地方就是Page Directory。页目录中的这些地址偏移量成为槽，每个槽占用2字节，页目录就是由多个槽组成的。

Page Header(页面头部)

File Header(文件头部信息)

索引相关观念

索引下推

索引条件下推优化（Index Condition Pushdown (ICP) ）是MySQL5.6添加的，用于优化数据查询，减少回表次数。

• 不使用索引条件下推优化时存储引擎通过索引检索到数据，然后返回给MySQL服务器，服务器然后判断数据是否符合条件。
• 当使用索引条件下推优化时，如果搜索语句中存在某些_被索引的列的判断条件时，MySQL服务器将这一部分判断条件传递给存储引擎，然后*由存储引擎通过判断索引是否符合MySQL服务器传递的条件*_，只有当索引符合条件时才会将数据检索出来返回给MySQL服务器。索引条件下推优化可以减少存储引擎查询基础表的次数，也可以减少MySQL服务器从存储引擎接收数据的次数。

适用条件

1. 需要整表扫描的情况。比如：range, ref, eq_ref, ref_or_null 。适用于InnoDB 引擎和 MyISAM 引擎的查询。（5.6版本不适用分区表查询，5.7版本后可以用于分区表查询）。
2. 对于InnDB引擎只适用于二级索引，因为InnDB的聚簇索引会将整行数据读到InnDB的缓冲区，这样一来索引条件下推的主要目的减少IO次数就失去了意义。因为数据已经在内存中了，不再需要去读取了。
3. 引用子查询的条件不能下推。
4. 调用存储过程的条件不能下推，存储引擎无法调用位于MySQL服务器中的存储过程。
5. 触发条件不能下推。

工作过程

既然是优化，我们要清楚优化了些什么就要了解原本是如何工作的，所以分为两部分来描述工作过程。

不使用索引条件下推优化时的查询过程

获取下一行，首先读取索引信息，然后根据索引将整行数据读取出来。
然后通过where条件判断当前数据是否符合条件，符合返回数据。

使用索引条件下推优化时的查询过程

获取下一行的索引信息。
检查索引中存储的列信息是否符合索引条件，如果符合将整行数据读取出来，如果不符合跳过读取下一行。
用剩余的判断条件，判断此行数据是否符合要求，符合要求返回数据。

EXPLAN分析
当使用explan进行分析时，如果使用了索引条件下推，Extra会显示Using index condition。并不是Using index因为并不能确定利用索引条件下推查询出的数据就是符合要求的数据，还需要通过其他的查询条件来判断。

覆盖索引

如果一个索引包含(或覆盖)所有需要查询的字段的值，称为‘覆盖索引’。即只需扫描索引而无须回表。
只扫描索引而无需回表的优点：
1.索引条目通常远小于数据行大小，只需要读取索引，则mysql会极大地减少数据访问量。
2.因为索引是按照列值顺序存储的，所以对于IO密集的范围查找会比随机从磁盘读取每一行数据的IO少很多。
3.一些存储引擎如myisam在内存中只缓存索引，数据则依赖于操作系统来缓存，因此要访问数据需要一次系统调用
4.innodb的聚簇索引，覆盖索引对InnoDB表特别有用。(InnoDB的二级索引在叶子节点中保存了行的主键值，所以如果二级主键能够覆盖查询，则可以避免对主键索引的二次查询)

覆盖索引必须要存储索引列的值，而哈希索引、空间索引和全文索引不存储索引列的值，所以mysql只能用B+tree索引做覆盖索引。

表空间结构

1.独立表空间结构

为了更好地管理表空间的页，MYSQL提出了区的概念，对于16KB的页来说，连续的64个页就是一个区，也就是说一个区默认占用1MB空间大小，无论是系统表空间还是独立表空间，都可以看成是由若干个连续的区组成的，每256个区被划分为一组。

第一个组最开始的3个页面类型是固定的，也就是说exten0这个区最开始的3个页面的类型是固定的，分别如下

• FSP_HDR:这个类型的页面用来登记整个表空间的一些整体属性以及本组所有的区的属性，整个表空间只有一个FSP_HDR类型的页面
• IBUF_BITMAP:这个类型的页面用来存储关于Change Buffer的一些信息

• INODE:这个类型的页面存储了关于INODE Entry的数据结构

    为什么要引入区这个概念，是因为如果以页为单位分配数据时，由于B+树中双向链表中相邻的两个页的物理位置不连续，对于传统的机械硬盘来说，需要重新定位磁头位置，也就是会产生随机I/O，这样会影响磁盘的性能。所以我们应该尽量让页面链表中相邻的页的物理位置也相邻，这样在扫描叶子节点中大量的记录时才可以使用顺序I/O。因此引入了区的概念，一个区就是在物理位置上连续的64个页(区里页面的页号都是连续的)，在表中的数据量很大时，为某个索引分配空间的时候就不再按照页为单位分配了，而是按照区为单位进行分配。甚至在表中的数据非常多的时候，一次性分配多个连续的区。虽然这可能造成一点点空间的浪费(数据不足以填充满整个区)，但是从性能角度看，可以消除很多的随机I/O。
  
    我们在使用B+树执行查询时只是在扫描叶子结点的记录，而如果不区分叶子结点和非叶子节点，统统把节点代表的页面放入到申请的区中，扫描效果就大打折扣了，因此MYSQL对叶子节点和非叶子节点进行了区分。也就是说叶子结点有自己独有的区，非叶子节点也有自己独有的区，存放叶子结点的区的集合称作一个段，存放非叶子节点的区的集合也算是一个段，也就是说一个索引会生成两个段，一个叶子节点段和一个非叶子节点段。
  

碎片区:在一个碎片区中，并不是所有的页都是为了存储同一个段的数据而存在的，碎片区中的页可以用于不同的目的，比如有些页属于段A，有些页属于段B，有些页甚至不属于任何段。碎片区直属于表空间，并不属于任何一个段。

为某个段分配存储空间的策略是这样的：

• 在刚开始向表中插入数据时，段是从某个碎片区以单个页面为单位来为数据分配存储空间
• 当某个段已经占用了32个碎片区页面之后，就会以完整的区为单位来为数据分配存储空间(原先占用的碎片区页面并不会被复制到新申请的完整的区中)

因此，段不能仅定义为某些区的集合，更精确的来说，应该是某些零散的页面以及一些完整的区的集合。

XDES Entry

为了方便管理区，MYSQL设计了一个称为XDES Entry的结构，每个区都对应着一个XDES Entry结构，这个结构记录了对应的区的一些属性。

XDES Entry结构有40字节，大致分为4个部分

• Segment ID:每一个段都有一个唯一的编号，用ID表示。Segment字段表示的就是该区所在的段，前提是该区已经被分配给某个段了，不然该字段的值没有意义。
• ListNode:这个部分可以将若干个XDES Entry结构串联成一个链表
• State:这个字段表明区的状态，可选的值有FREE、FREE_FRAG、FULL_FRAG、FSEG，分别代表当前区是空闲的，当前区是有剩余空闲页面的碎片区，当前区是没有剩余空闲页面的碎片区，当前区附属于某个段的区。
• Page State Bitmap:这个部分共占用16字节，也就是128位，一个区默认有64个页，这128位被划分为64个部分，每个部分有2位，对应区中的1个页，这2个位中的第1位表示对应的页是否是空闲的，第2位还没有用到。

XDES Entry链表

为了减少我们寻找不同状态的区的复杂度，MYSQL通过XDES Entry中的List Node将每个不同状态的XDES Entry链接为一个双向链表，具体有如下三种

• 通过List Node把状态为FREE的区对应的XDES Entry结构连接成一个链表，这个链表成为FREE链表
• 通过List Node把状态为FREE_FRAG的区对应的XDES Entry结构连接成一个链表，这个链表成为FREE_FRAG链表
• 通过List Node把状态为FULL_FRAG的区对应的XDES Entry结构连接成一个链表，这个链表成为FULL_FRAG链表

同时为了快速找到某个段内的区，MYSQL又为每个段中的区对应的XDES Entry结构建立了3个链表

• FREE链表:同一个段中，所有页面都是空闲页面的区对应的XDES Entry结构会被加入到这个链表中。注意，这与直属于表空间的FREE链表区别开了，此处的FREE链表是附属于某个段的链表
• NOT_FULL链表:同一个段中，仍有空闲页面的区对应的XDES Entry结构会被加入到这个链表中。
• FULL链表:同一个段中，已经没有空闲页面的区对应的XDES Entry结构会被加入到这个链表中。

INODE Entry

与每个区都有对应的XDES Entry来记录这个区中的属性一样，MYSQL为每个段都定义了一个INODE Entry结构来记录这个段中的属性

INODE Entry结构中各个部分的含义如下

• Segment ID:这个INODE Entry结构对应的段的编号
• NOT_FULL_N_USED:在NOT_FULL链表中已经使用了多少个页面
• 3个List Base Node:分别为段的FREE链表、NOT_FULL链表、FULL链表定义了List Base Node，这样当想查找某个段的某个链表的头结点和尾节点时，可以直接到这个部分找到对应链表的List Base Node。
• Magic Number:用来标记这个INODE Entry是否已经被初始化(即把各个字段的值都填进去了)，如果这个数字的值时97937874，则表明已经被初始化
• Fragment Array Entry:每个Fragment Array Entry结构对应着一个零散的页面，这个结构一共4字节，表示一个零散页面的页号。

FSP_HDR

表空间内第一个组的第一个页面，即页号为0的页面，这个页面的类型就是FSP_HDR，它存储了表空间的一些整体属性以及第一个组内256个区对应的XDES Entry结构

File Space Header部分

这里重点讲一下List Base Node for SEG_INODES_FULL List与List Base Node for SEG_INODES_FREE List属性，每个段对应的INODE Entry结构会集中存放到一个类型为INODE的页中，如果表空间中的段特别多，则会有多个INODE Entry结构，此时可能一个页放不下，就需要多个INODE类型的页面，这些INODE类型的页会构成下面两种链表

• SEG_INODES_FULL链表:在该链表中，INODE类型的页面都已经被INODE Entry结构填充满，没有空闲空间存放额外的INODE Entry
• SEG_INODES_FREE链表:在该链表中，INODE类型的页面仍有空闲空间来存放INODE Entry结构

XDES

除了第一个组以外，其他组的第一个页面只需要记录本组内所有的区对应的XDES Entry结构即可，不需要再记录表空间的属性。为了与FSP_HDR类型进行区别，我们把之后每隔分组中第一个页面的类型定义为XDES，它的结构与FSP_HDR类型非常相似。

IBUF_BITMAP

每个分组中第二个页面的类型都是IBUF_BITMAP。我们平时说向表中插入一条记录，其实本质上是向每个索引对应的B+树中插入记录。该记录首先插入聚簇索引页面，然后再插入每个二级索引页面。这些页面在表空间中随机分布，将会产生大量的随机I/O，严重影响性能，对于UPDATE和DELETE操作来说，也会带来许多的随机I/O。因此MYSQL引入了一种称为Change Buffer的结构，其本质上也是表空间的一颗B+树，它的根节点存储在系统表空间中。在修改非唯一二级索引页面时，如果该页面尚未被加载到内存中，那么该修改将先被暂时缓存到Change Buffer中，之后服务器空闲或者其他什么原因导致对应的页面从磁盘上加载到内存中时，再将修改合并到对应页面。此外，在很久之前的版本中只会缓存INSERT操作对二级索引页面所做的修改，所以Change Buffer以前被称作Insert Buffer，所以在各种命名上延续了之前的叫法，比方说IBUF其实是Insert Buffer的缩写。

INODE

第一组的第一个区的第三页存放的是每个表空间的第一个INODE类型数据

重点看一下List Node for INODE Page List，如果一个表空间中存在的段超过85个，那么一个INODE类型的页面不足以存储所有的段对应的INODE Entry结构，所以就需要额外的INODE类型的页面来存储这些结构。为了方便管理这些INODE类型的页面，MYSQL讲这些INODE类型的页面串联成两个不同的链表。

• SEG_INODES_FULL链表:在该链表中，INODE类型的页面中已经没有空闲空间来存储额外的INODE Entry结构。
• SEG_INODES_FREE链表:在该链表中，INODE类型的页面中还有空闲空间来存储额外的INODE Entry结构

这两个链表的基节点就存储在FSP_HDR类型页面的File Space Header中。

存储INODE Entry的过程大致如下所示

• 先看看SEG_INODES_FREE链表是否为空，如果不为空，直接从该链表中获取一个节点，也就相当于获取到一个仍有空闲空间的INODE类型的页面，然后把该INODE Entry结构放到该页面中。当该页面中无剩余空间时，就把该页放到SEG_INODES_FULL链表中。
• 如果SEG_INODES_FREE链表为空，则需要从表空间的FREE_FRAG(有剩余空间的碎片区)链表中申请一个页面，并将该页面的类型修改为INODE，把该页面放到SEG_INODES_FREE链表中，与此同时把该INODE Entry结构放入该页面。

Segment Header

一个索引产生两个段，分别是叶子节点段和非叶子节点段，而每个段都会对应一个INODE Entry结构，我们怎么知道某个段对应哪个INODE Entry结构呢？所以得将这个对应关系记录在某个地方。在数据页中的Page Header部分，存在以下两个属性

这两个属性都占用10个字节，其实对应着一个名为Segment Header的结构如下

各个部分的具体含义如下

• Space ID of the INODE Entry:INODE Entry结构所在的表空间ID
• Page Number of the INODE Entry:INODE Entry结构所在的页面页号
• Byte Offset of the INODE Entry:INODE Entry结构在该页面中的偏移量

单表访问方法

访问方法

1.const

SELECT * FROM single_table WHERE id=1438;

通过主键或者唯一二级索引列与常数的等值比较来定位一条记录，如果主键或者唯一二级索引的索引列是由多个列构成的，则只有在索引列中的每一个列都与常数进行等值比较时，这个const访问方法才有效。

2.ref

SELECT * FROM single_table WHERE key1='abc';

由于普通二级索引并不限制索引列值的唯一性，因此对于某一个值来说二级索引记录可能有多条，MYSQL把这种搜索条件为二级索引列与常数进行等值比较，形成的扫描区间为单点扫描区间，采用二级索引来执行查询的访问方法称为ref。

3.ref_or_null

SELECT * FROM single_table WHERE key1='abc' OR key1 IS NULL;

当使用二级索引执行查询构成的扫描区间包含null时，这时所使用的的访问方法就称为ref_or_null，ref_or_null访问方法只是比ref访问方法多扫描了一些值为null的二级索引记录。(值为null的记录会被放在索引的最左边)

4.range

SELECT * FROM single_table WHERE key2 IN (1438,6328) OR (key2>=38 AND key2<=79);

在对索引列与某一个常数进行等值比较时，才会使用到以上几种方法。在使用索引执行查询时，对应的扫描区间为若干个单点扫描区间或者范围扫描区间的访问方法称为range(仅包含一个单点扫描区间或者扫描区间为$(-\infty,+\infty)$的访问方法都不能称为range访问方法，两个单点区间中包含null的除外)。

5.index

SELECT key_part1,key_part2,key_part3 FROM single_table WHERE key_part2='abc';

当执行查询的筛选条件为某一联合索引中的值，并且该联合索引的某几列就是我们所需要的数据，此时MYSQL就会遍历该二级索引所有记录，并直接从二级索引中取到我们所需要的数据，而不会进行回表操作，(简而言之就是当可以使用覆盖索引，但需要扫描全部的索引记录)MYSQL将这种扫描全部二级索引记录的访问方法称为index访问方法。此外，在InnoDB引擎下进行全表扫描时，如果添加了ORDER BY 主键的语句，那么该语句会在执行时也被认为是使用了index访问方法。

6.all

全表扫描，也就是直接扫描全部的聚簇索引记录。

索引合并

1.Intersection索引合并

SELECT * FROM single_table WHERE key1='a' AND key3='b';

Intersection索引合并指的就是对从不同索引中扫描到的记录的id(主键)值取交集，只为这些id值执行回表操作。如果使用Intersection索引合并的方式执行查询，并且每个使用到的索引都是二级索引的话，则要求从每个索引中获取到的二级索引记录都是按照主键值排序的，原因有以下两点:

• 从两个有序集合中取交集比从两个无需集合中取交集要容易的多
• 如果获取到的id值是有序排列的，则在根据这些id值执行回表操作时就不再是进行单纯的随机I/O，从而会提高效率。

2.Union索引合并

SELECT * FROM single_table WHERE key1='a' OR key3='b';

在执行以上搜索语句时，MYSQL会根据两个筛选条件，分别从两个二级索引中找到满足的条件的记录，再根据二级索引记录的id值在两者的结果中进行去重，再根据去重后的id值执行回表操作，这样重复的id值只需会表一次，这种方案就是所谓的Union索引合并。与Intersection索引合并类似，如果要使用Union索引合并，则要求每个使用到的二级索引中记录都是按照主键值排序的，原因有以下:

• 从两个有序集合执行去重操作比从两个无序集合中执行去重操作容易一些。
• 如果获取到的id值是有序的话，那么根据这些id值执行回表操作时就不是进行单纯的随机I/O，从而会提高效率

3.Sort-Union索引合并

Union索引合并的使用条件太苛刻，它必须保证从各个索引中扫描到的记录的主键值是有序的，因此MYSQL又设计了一种方法，先将从各个索引中扫描到的记录的主键值进行排序，再按照执行Union索引合并的方式执行查询，这种方法也被称为Sort-Union索引合并。显然，Sort-Union索引合并比单纯的Union合并多了一步对二级索引记录的主键值进行排序的过程。

表连接原理

基于块的嵌套循环连接

在连接查询的过程中，驱动表结果集中有多少条记录，就可能把被驱动表从磁盘加载到内存中多少次。我们是否可以在把被驱动表中的记录加载到内存中时，一次性地与驱动表中的多条记录进行匹配呢？这样就可以大大减少重复从磁盘上加载被驱动表的代价了。所以MYSQL提出了一个名为Join Buffer(连接缓冲区)的概念。Join Buffer就是在执行连接查询前申请的一块固定大小的内存。先把若干条驱动表结果集中的记录装在这个Join Buffer中，然后开始扫描被驱动表，每一条被驱动表的记录一次性地与Join Buffer中的多条驱动表记录进行匹配。由于匹配的过程都是在内存中完成的，所以这样可以显著减少被驱动表的I/O代价。这种加入了Join Buffer的嵌套循环连接算法称为基于块的嵌套循环连接算法。

Join Buffer中并不会存放驱动表记录的所有列，只有查询列表中的列和过滤条件中的列才会被放到Join Buffer中。

表查询成本统计

扫描区间成本

查询优化器在计算二级索引的某个扫描区间包含多少条记录时，通常有两种策略

1. 如果区间最左的记录与最右的记录之间相隔小于10个页面，则只需要统计一下这几个页面的记录数之和。
2. 如果区间最左的记录与最右的记录之间相隔大于10个页面，则只沿着区间最左记录向右读取10个页面，计算每个页面包含记录数的平均值，再用这个平均值乘以相隔的页数即可。

多个单点扫描区间成本

有时在使用索引执行查询时会有许多单点扫描区间，使用IN语句就很容易产生非常多的单点扫描区间，在索引不是唯一二级索引的情况下，并不能确定一个单点扫描区间内对应的二级记录的条数有多少，因此需要通过扫描二级索引来进行统计。这种通过直接访问索引对应的B+树来计算某个扫描区间内对应的索引记录条数的方式称为index dive。

如果通过IN语句生成的单点扫描区间的数量少于200个，将使用index dive来计算各个单点扫描区间对应的记录条数，如果大于或等于200个，就要使用索引统计数据来进行估算，也就是以下两个数据。

• 在每个索引中都保存着一个Cardinality的属性，该属性翻译过来是基数的意思，表示某个列中不重复的值的个数。需要注意的是，对于InnoDB来说，使用SHOW INDEX语句显示出来的某个列的Cardinality属性是一个估计值，并不准确。
• 在使用SHOW TABLE STATUS语句显示出来的Rows值，表示一个表中有多少条记录

结合以上两个数据，我们可以计算出在某一个列中一个值平均重复多少次，也就是Rows除以Cardinality的值。

使用统计数据来计算单点扫描区间对应的索引记录条数比index dive简单的多，但是它的致命弱点就是不精确。

InnoDB统计数据

InnoDB提供了两种存储统计数据的方式，分别是永久性地存储统计数据和非永久性地存储统计数据，不过目前不推荐使用基于内存方式存储统计数据。当我们选择把某个表以及该表索引的统计数据存放到磁盘上时，实际上是把这些统计数据存储到了两个表中

SHOW TABLES FROM mysql LIKE 'innodb%stats';

分别为innodb_table_stats与innodb_index_stats，前者存储关于表的统计数据，后者存储关于索引的统计数据

InnoDB_table_stats

其中的n_rows统计项的值是预估值，InnoDB在统计一个表中有多少行记录时，从聚簇索引中选取几个叶子结点页面，统计每个页面中包含的记录数量，然后计算一个页面中平均包含的记录数量，并将其乘以全部叶子结点的数量，结果就是n_rows的值。

在统计clustered_index_size与sum_of_other_index_sizes这两个项的值时，步骤如下：

1. 从数据字典中找到表的各个索引对应的根页面位置，系统表SYS_INDEXS中存储了各个索引对应的根页面信息
2. 从根页面的Page Header中找到叶子节点段和费叶子节点段对应的Segment Header，在每个索引的根页面的Page Header部分都有两个字段PAGE_BTR_SEG_LEAF与PAGE_BTR_SEG_TOP，这两个字段通过Segment Header格式存储，结构如下

1. 从叶子节点段和非叶子节点段的Segment Header中找到这两个段对应的INODE Entry结构
2. 针对某个段对应的INODE Entry结构，从中找出该段对应的所有零散页面的地址以及FREE、NOT_FULL和FULL链表的基节点
3. 直接统计零散的页面有多少个，然后从FREE、NOT_NULL、FULL这三个链表的List Length字段中读出该段占用的区的数量，所以就可以统计出整个段占用的页面。

innodb_index_stats

子查询优化

物化表

SELECT * FROM s1
     WHERE key1 IN(SELECT common_field FROM s2 WHERE key3='a');

对于不相关的IN子查询来说，如果子查询的结果集中的记录条数很少，那么把子查询和外层查询分别看成两个单独的单表查询，效率还是挺高的，但是如果单独执行子查询后的结果集太多，就会导致以下问题

• 结果集太多，可能内存中都放不下
• 对于外层查询来说，如果子查询的结果集太多，则意味着IN子句中的参数特别多，这将导致
  • 无法有效的使用索引，只能对外层查询进行全表扫描
  • 在对外层查询执行全表扫描时，如果IN子句中的参数太多，会导致在检测一条记录的IN表达式是否为TRUE时花费太多的时间。

为了解决以上问题，MYSQL提出了物化表的概念，不直接将不相关子查询的结果集当作外层查询的参数，而是将该结果集写入一个临时表中，在将结果集写入临时表时需要注意以下几点

• 该临时表的列就是子查询结果集中的列
• 写入临时表的记录会被去重(为了让临时表变得更小，节省空间)
• 如果子查询结果集不是很大，则为它建立基于MEMORY存储引擎的临时表，否则使用基于硬盘的存储引擎保存结果集

子查询转半连接

为了进一步优化子查询的效率，MYSQL提出了半连接的概念，首先我们判断如下SQL语句

SELECT * FROM s1
     WHERE key1 IN(SELECT common_field FROM s2 WHERE key3='a');

这个查询过程与以下SQL语句看起来非常相似

SELECT s1.* FROM s1 INNER JOIN s2
    ON s1.key1=s2.common_field
    WHERE s2.key3='a';

只不过我们不能保证对于s1表的某条数据来说，s2中有多少条记录满足s1.key1=s2.common_field，一般来说存在以下三种情况

1. 对于s1表中的某条记录来说，s2表中没有任何记录满足s1.key1=s2.common_field条件，那么该记录自然也不会加入到最终的结果集
2. 对于s1表中的某条记录来说，s2表中有且仅有一条记录满足s1.key1=s2.common_field条件，那么该记录会被加入到最终的结果集
3. 对于s1表中的某条记录来说，s2表中至少有两条记录满足s1.key1=s2.common_field条件，那么该记录会被多次加入到最终的结果集

对于s1表中的某条记录，我们只关心s2表中是否存在记录满足s1.key1=s2.common_field条件，而不关心具体有多少条记录与之匹配，又因为情况3的存在，因此子查询与两表连接查询并不完全等价，但是将子查询转换为连接又确实可以充分发挥优化器的作用，因此MYSQL提出了半连接的概念。将s1表和s2表进行半连接的意思就是，对于s1表中的某条记录来说，我们只关心s2表中是否存在与之匹配的记录，而不关心具体有多少条记录与之匹配，最终的结果集中只保留s1表的记录。

Table pullout(表上拉)

当子查询的查询列表出只有主键或者唯一索引列时，可以直接把子查询的表上拉到外层查询的FROM子句中，并把子查询中的搜索条件合并到外层查询的搜索条件中。

#原查询语句
SELECT * FROM s1
    WHERE key2 IN (SELECT key2 FROM s2 WHERE key3='a');

#表上拉之后的查询语句    
SELECT s1.* FROM s1 INNER JOIN s2
    ON s1.key2=s2.key2
    WHERE s2.key3='a';

由于主键或者唯一索引列不存在重复的值，因此也就不存在情况3了。

Duplicate Weedout(重复值消除)

在转换为半连接查询之后，s1表的某条记录可能在s2表中有多条匹配的记录，所以该条记录可能多次被添加到最后的结果集中，为了消除重复，我们可以建立一个临时表，这样在查询过程中，每当某条s1表中的记录要加入结果集时，就首先把这条记录的id临时加入到临时表中，如果添加成功，说明之前这条s1表中的记录并没有加入最终的结果集

LooseScan(松散扫描)

对于下面这个扫描

SELECT * FROM s1
    WHERE key3 IN(SELECT key1 FROM s2 WHERE key1>'a' AND key1<'b');

在子查询中，对于s2表的访问可以使用到key1列的索引，而子查询的查询列表处恰好就是key1列，这样在将该查询转换为半连接查询后，如果将s2作为驱动表执行查询，那么对于从s2查询到的值相同的二级索引记录，只需要取第一条记录的值到s1表中找匹配的记录。

Semi-join Materialization(半连接物化)

通过外层查询的表与IN子句中的不相关子查询物化的表进行连接，在本质上也算是一种半连接的实现方案，只不过物化表中没有重复的记录，因此可以直接将子查询转为连接查询。

FirstMatch(首次匹配)

首次匹配是一种最原始的半连接执行方式，即先取一条外层查询中的记录，然后到子查询的表中寻找符合匹配条件的记录，如果能找到一条，则将该外层查询的记录放入最终的结果集并且停止查找更多匹配的记录。

半连接的适用条件

1. 该子查询必须是与IN操作符组成的布尔表达式，并且在外层查询的WHERE或者ON子句中出现
2. 外层查询也可以有其他的搜索条件，只不过必须使用AND操作符与IN子查询的搜索条件连接起来
3. 该子查询必须是一个单一的查询，不能是由UNION连接起来的若干个查询
4. 该子查询不能包含GROUP BY、HAVING语句或者聚集函数

不适用于半连接的情况

1. 在外层查询的WHERE子句中，存在其他搜索条件使用OR操作符与IN子查询组成布尔表达式连接起来的情况
2. 使用NOT IN 而不是IN的情况
3. 位于SELECT子句中的IN子查询的情况
4. 子查询中包含GROUP BY、HAVING或者聚集函数的情况
5. 子查询中包含UNION的情况

如果IN子查询不满足转换为半连接的条件，又不能转换为物化表，或者转换为物化表的成本太高，那么它就会被转换为EXISTS子查询

EXPLAIN命令

BufferPool

由于Mysql中所有的数据都是存储在硬盘中的，因此我们在访问某个页的记录时，需要把整个页的数据加载到内存中，这样就可以进行读写访问了，而且为了方便下一次的读写，并不着急把该页在内存中占用的空间释放掉，而是引用了缓冲池的技术，缓存在内存中，这样下次再有访问相同页的请求时，就可以省下磁盘IO的开销。内存中的缓存页与与表空间的页面大小一致，都是16k。

为了在访问数据时快速判断当前数据所在的页面是否已经加载到缓存池中，即需要快速定位到某一个页对应的控制块，因此我们把表空间+页号作为key，控制块的地址作为value来创建一个哈希表。这样在以后需要访问某个页的数据时，根据表空间号+页号看看哈希表中是否有对应的缓存页，如果有则直接访问缓存池中对应的缓存页，否则从FREE链表中取出一个控制块，并从磁盘加载相应的页面数据到缓存页中。

FREE链表

为了区分Buffer Pool中哪些缓冲页是空闲的，哪些已经被使用了，MYSQL将所有空闲的缓冲页对应的控制块作为一个节点放到一个链表中，这个链表被称为free链表。并且通过一个基节点来管理这个链表，它里面包含链表的头结点地址、尾节点地址，以及当前链表中节点的数量等信息。

每当需要从磁盘中加载一个页到Buffer Pool中时，就从free链表中取一个空闲的缓冲页，并且把该缓冲页对应的控制块的信息填上(也就是该页所在的表空间、页号之类的信息)，然后把该缓冲页对应的free链表节点从链表中移除，表示该缓冲页已经被使用了。

FLUSH链表

如果Buffer Pool中某个缓冲页的数据被修改了，就与磁盘上的页不一致，这样的缓冲页也被称为脏页(dirty page)，如果每次修改之后都立即将其刷新到磁盘，那么会严重影响性能。因此，MYSQL又引入了一个FLUSH链表，凡是被修改过的缓冲页对应的控制块都会作为一个节点加入到这个链表中，后续根据各种策略延迟刷新到磁盘中。

LRU链表

Buffer Pool对应的内存大小毕竟是有限的，需要缓存的页占用的内存大小总有一天会超过了Buffer Pool的大小，因此MYSQL为了解决这个问题，引入了LRU链表，即把某些旧的(不频繁使用的)缓冲页从Buffer Pool中移除，然后再把新的页面放进来。

在设计LRU链表时，经历了以下几个阶段

1.简单的LRU链表

• 如果该页不在Buffer Pool中，在把该页从磁盘加载到Buffer Pool中的缓冲页时，就把该缓冲页对应的控制块作为节点塞到LRU链表的头部；
• 如果该页已经被加载到Buffer Pool中，则直接把该页对应的控制块移动到LRU链表的头部。

2.划分区域的LRU链表

在以上简单LRU链表的使用过程中很快就发现了问题，原因就是MYSQL存在着预读的现象，以及全表扫描状况下的大量页面读取。

• 线性预读:如果顺序访问的某个区的页面超过innodb_read_ahead_threshold这个系统变量的值，就会触发一次异步读取下一个区中全部的页面到Buffer Pool中的请求
• 随机预读:如果某个区的13个连续的页面都被加载到了Buffer Pool中，无论这些页面是不是顺序读取的，都会触发一次异步读取本区中所有其他页面到Buffer Pool中的请求。该功能由innodb_random_read_ahead变量控制是否开启。

简而言之，可能降低Buffer Pool命中率的两种情况如下

• 加载到Buffer Pool中的页不一定被用到
• 如果有非常多的使用频率偏低的页被同时加载到Buffer Pool中，则可能会把那些使用频率非常高的页从Buffer Pool中淘汰掉

为了规避这个问题，MYSQL将LRU链表划分为两部分(old区域默认占用比例为37%)

• 一部分存储使用频率非常高的缓冲页，这一部分链表也被称为热数据，或者称为young区域
• 另一部分存储使用频率不是很高的缓冲页，这一部分链表也被称为冷数据，或者称为old区域

同时针对全表扫描，还有一些细节上的改进，详见书P285。

3.更进一步优化LRU链表

对于young区域的缓冲页来说，每次访问一个缓冲页都要把它移动到LRU链表的头部，这样开销会很大，因此为了解决这个问题，MYSQL规定，只有被访问的缓冲页位于young区域1/4的后面时，才会被移动到LRU链表的头部。

刷新脏页到磁盘

后台有专门的的线程负责每隔一段时间就把脏页刷新到磁盘，这样可以不影响用户线程处理正常的请求，刷新方式主要有下面两种

1. 从LRU链表的冷数据中刷新一部分页面到磁盘
2. 从FLUSH链表中刷新一部分页面到磁盘

补充

在多线程环境下，访问Buffer Pool中各种链表需要加锁处理，这样会导致性能下降，因此在Buffer Pool比较大时，将它拆分为若干个小的Buffer Pool，每个Buffer Pool都称为一个实例，他们都是独立的，互不影响，从而提高了并发处理能力。

为了支持在服务器运行过程中调整Buffer Pool的大小，MYSQL决定不再一次性为某个Buffer Pool实例申请一大片连续的内存空间，而是以一个chunk为单位向操作系统申请空间。也就是说，一个Buffer Pool实例其实是由若干个chunk组成的，一个chunk就代表一片连续的内存空间，里面包含了若干缓冲页与其对应的控制块。

Redo日志

基础概念

有上一节知道，我们对数据库中进行增删改查的操作首先会对BufferPool中缓存的数据进行修改，并且在缓存池数据修改之后的脏页并不会立即刷新回磁盘中。那么如果我们在某个事务提交之后，事务对数据的修改还未持久化到磁盘时系统发生了崩溃，那么这个事务对数据库做的修改就会被丢失。那么如果我们在事务提交之后，立即将相应的缓存池脏页刷新回磁盘中可行吗？其实还是存在着两个问题

1. 假如我们当前事务仅修改了某个页面中的一个字节，但是InnoDB是以页为单位来进行磁盘IO的，也就是为了保存这一字节的修改内容，我们不得不把16KB字节的数据一次性刷新到磁盘上，显然这样做非常浪费性能。
2. 另一个问题是由于在一个事务中包含的所有语句中，可能修改了许多页面，而且这些页面可能不是相邻的，这也就意味着在将这个事务修改BufferPool中的缓存页所产生的脏页刷新回磁盘上时会进行随机IO，这样也会导致性能下降。

因此，为了使已经提交了的事务对数据库中的数据所做的修改能永久生效，且避免性能下降，MYSQL想到了可以把每次提交事务时该事务修改的内容进行记录，因此引入了redo日志，redo日志具有以下优点

• 占用的空间小
• redo日志本身是按照生成的顺序写入磁盘的，也就是使用顺序IO，因此速率较快。

redo日志本身只是记录了一下事务对数据库进行了哪些修改，MYSQL针对不同的场景设计了多种类型的redo日志，但是绝大多数的redo日志都有以下结构

• type:这条redo日志的类型(一共53种)
• spaceID：表空间ID
• page number：页号
• data：这条redo日志的具体内容

redo日志记录修改记录可以选择两种方案：

• 方案一：在每个修改的地方都记录一条redo日志，这种方案的缺点是假如某一页需要修改的数据过多的话，可能redo日志占用的空间比整个页面占用的空间都要多
• 方案二：将整个页面第一个被修改的字节到最后一个被修改的字节之间所有的数据当成一条物理redo日志中的具体内容。这种方案的缺点在于假如两个修改的字节之间存在大量没有被修改过的内容，这样把数据存储在redo日志就会导致空间的浪费。

因此为了redo日志灵活地存储各种情况下的修改记录，Mysql引入了许多类型的redo日志格式。从物理层次看，这些日志都指明了对哪个表空间的哪个页进行修改；从逻辑层面看，在系统崩溃后重启时，并不能直接根据这些日志中的记载在页面内的某个偏移量处恢复某个数据，而是需要根据Mysql某些函数对redo日志的处理，才可以将页面恢复成系统崩溃前的样子。

Mini-Transaction

在一条记录被修改时，往往需要修改多个索引页面的数据，Mysql规定，一条语句对某个索引页面的修改内容所记录的redo日志必须是原子完整的，也就是说根据这条redo日志记录，对当前页面的数据必须要么能够完整的恢复，要么干脆不进行记录。这样一组完整的redo日志称作Mini-Transaction。

有时候一个索引页记录的redo日志只存在一条，有时候存在多条，在redo日志的type字段最高位标明了这个redo日志构成的Mini-Transaction是由多条redo日志组成的，还是单条组成的。如果是由多条组成的，那么组内最后一条redo日志会以MLOG_MULTI_REC_END类型的redo日志(只有单个type字段)作为结尾。

一个事务可以包含若干条语句，一条语句又包含若干个MTR，每一个MTR又可以包含若干条redo日志

redo日志持久化

为了更好的管理redo日志，在Mysql中所有通过MTR生成的redo日志都保存在大小为512字节的页中，我们暂且把这个页称作redo log block，其结构如下：

• LOG_BLOCK_HDR_NO:每一个block都有一个大于0的唯一编号，该属性就代表该编号值
• LOG_BLOCK_HDR_DATA_LEN:表示block中已经使用了多少字节
• LOG_BLOCK_FIRST_REC_GROUP:该block中第一个MTR生成的redo日志记录组的偏移量。也就是第一条redo日志记录的偏移量。
• LOG_BLOCK_CHECKPOINT_NO:checkPoint的序号
• LOG_BLOCK_CHECKPOINT_NO:用于正确性校验

log buffer

与BufferPool的使用目的一样，redo日志的页面也需要暂时存放在内存中，服务器在启动时就申请了一大片的被称作redo log buffer(redo日志缓冲区)的连续内存空间，这片空间被划分为若干个redo log block。每一个MTR产生的一组redo日志必须按顺序依次保存在缓冲区中，不同MTR可以交替存放，但是不同MTR下的redo日志不能交替存放。

redo日志刷盘时机

• log buffer空间不足时
• 事务提交时
• 后台有一个线程，大约以每秒一次的频率将logbuffer中的redo日志刷新到磁盘
• 正常关闭服务器时
• 做checkpoint时

redo日志存储的文件格式

Mysql的数据目录下保存着存储redo日志的文件，他们的命名格式为ib_logfilex(x从0开始依次递增)，文件的个数可以自己设置，单个文件默认大小为48MB，redo日志从第一个文件依次向后存储，当所有文件存储满以后又返回第一个文件进行存储(覆盖旧数据)，内部文件的存储格式如下：

每个文件的前四个block都是用来存储一些全局信息，注意:checkpoint的信息只会存储在日志文件组的第一个文件中。

比较重要的属性有

• LOG_HEADER_START_LSN(8字节):标记本redo日志文件偏移量为2048字节处对应的 lsn值，也就是当前文件最旧的修改版本值
• LOG_CHECKPOINT_NO(8字节):服务器执行checkpoint的编号，每执行一次checkpoint该值就加一
• LOG_CHECKPOINT_LSN(8字节):服务器在结束checkpoint时对应的checkpoint_lsn值，系统在崩溃后恢复时将从该值开始。
• LOG_CHECKPOINT_OFFSET(8字节):上个checkpoint之后的checkpoint_lsn值对应于redo日志文件组中的偏移量。

lsn

Mysql设计了一个lsn的全局变量，用来统计当前一共生成的redo日志的数量，lsn的初始值为8704，并且该值在递增时不仅包含redo日志数据占用的字节数，还包括log block的头部和尾部。

我们知道存储在文件中的redo日志并不是需要一直存储，一旦它所记录的数据修改已经从BufferPool刷新到了磁盘中，那么当前redo日志就可以被覆盖掉了，因此为了判断当前磁盘中哪些redo日志记录是可以覆盖掉的，引入了以下全局变量

• buf_next_to_write:表示lsn小于这个值的所有redo日志都已经被刷新到磁盘中了。
• flushed_to_disk_lsn:表示刷新到磁盘中的redo日志量，当该值与lsn的值相同时说明所有的数据都已经刷新到了磁盘中。

在缓冲页面数据的BufferPool中的控制块中，存储着两个属性

• oldest_modification:第一次修改当前缓冲页时的MTR开始前对应的lsn值
• newest_modification:每修改一次页面就会将修改该页面的MTR结束时对应的lsn值写入这个属性，也就是当前页面最近一次修改后对应的lsn值

BufferPool中的flash链表中会将所有控制块节点按照newest_modification属性进行排序，newest_modification越大的排的越靠前，即修改越晚的越靠近链表头结点。

checkpoint

由于redo日志的文件组容量是有限的，因此当redo日志存满文件组以后需要循环使用文件，但是这样会导致新写入的日志覆盖最先写入的日志。但是redo日志的主要作用是为了系统崩溃时候恢复脏页用的，如果脏页已经刷新到了磁盘中，那么对应的redo日志也就没有了存在的必要，他所占用的文件空间就可以被覆盖。为了判断哪些日志可以被覆盖，Mysql引入了checkpoint的机制，在介绍它之前先介绍一个全局变量:checkpoint_lsn，这个变量用来表示当前系统中可以被覆盖的redo日志lsn是多少，初值为8704。

执行一次checkpoint可以分为两个步骤:

步骤一：计算当前系统中可以被覆盖的redo日志对应的lsn值最大是多少，也就是把FLUSH链表中最后一个节点(最早修改的脏页)的oldest_modification值赋值给checkpoint_lsn。

步骤二：将checkpoint_lsn与对应的redo日志文件组偏移量以及此次checkpoint的编号写到日志文件的管理信息(也就是checkpoint1与checkpoint2)

数据恢复

在根据redo日志恢复数据时，为了提高效率，Mysql将所有日志按照spaceID与page number属性计算出哈希值，哈希值相同的redo日志放入同一个槽中，用链表项链，这样恢复同一页数据时就可以一次性完成，避免了随机IO。并且恢复时还需要按照日志的lsn顺序进行恢复。

Undo日志

由上一节知道，redo日志的作用是为了保证一次事务内所做的所有修改，在事务提交之后持久化在磁盘中。这一节我们需要考虑的问题是如果发生了事务回滚，我们需要怎么记录回滚操作并保证它回滚成功呢？MySQL将为了回滚而记录的东西称为撤销日志(undo log)，undo日志大致分为三种，即插入、删除、修改。

事务id

对于只读事务，只有它第一次对某个用户创建的临时表执行增删改查操作时，才会为这个事务分配一个事务id，否则是不分配事务的。

对于读写事务，只有他第一次对某个表执行增删改查操作时，才会为这个事务分配一个事务id。

对于不需要分配事务id的情况，默认也会分配一个为0的事务id

这个事务id本质上就是一个数字，它存储在表空间中页号为5的页面中，每当需要为一个事务分配一个id时，都会把当前变量的值赋值给该事务，并且自身进行加一操作。每当它的数量为256倍数时才会刷新到表一次，因此事务执行越晚，它的id越大。

之前我们在介绍记录的行格式时，有三个隐藏字段，其中 一个被称作trx_id，这个字段就用来表示当前记录最后一次被事务修改时事务的id。

INSERT操作对应的undo日志

• undo no在一个事务中是从0开始递增的，也就是说，只要事务没提交，每生成一条undo日志，那么该条日志的undo no就递增1
• 如果记录中的主键只包含一列，那么类型为TRX_UNDO_INSERT_REC的undo日志中，只需要把该列所占用的存储空间大小和真实值记录下来。如果记录中的主键包含多个列，那么每个列占用的存储空间大小和对应的真实值都需要记录下来。

当我们向某个表中插入一条记录时，实际上需要向聚簇索引和所有二级索引都插入一条记录，不过再记录undo日志时，我们只需要针对聚簇索引记录来记录一条undo日志就好了。聚簇索引记录与二级索引记录是一一对应的，我们在回滚INSERT操作时，只需要知道这条记录的主键信息，然后根据主键信息进行对应的删除操作。在执行删除操作时，就会把聚簇索引和二级索引中相应的记录都删掉，后续的DELETE和UPDATE操作也是针对聚簇索引记录的改动来记录undo日志的。

DELETE操作对应的undo日志

再删除一条记录时往往需要经历两个阶段

1. 仅仅将记录的delete_flag标识位设置为1，其他的不做修改，这个阶段称为delete mark
2. 当该删除语句所在的事务提交后，会有专门的线程来真正地把记录删除掉，即把该记录从正常记录链表中移除，并且放到垃圾链表的头结点，随后还要调整一些页面的其他信息，比如页面中的用户记录数量PAGE_N_RECS、上次插入记录的位置PAGE_LAST_INSERT、垃圾链表头结点的指针PAGE_FREE、页面中可重用的字节数量PAGE_GARBAGE，以及页目录的一些信息等，这个阶段称为purge。

与类型为TRX_UNDO_INSERT_REC的undo日志不同，类型为TRX_UNDO_DEL_MARK_REC的undo日志还多了一个索引列各列信息的内容，也就是说，如果某个列被包含在某个索引中，那么他的相关信息就应该记录到这个索引列各列的信息部分。所谓的”相关信息”包括该列在记录中的位置(pos)，该列占用的存储空间的大小(len),该列实际值(value)。所以，索引列各列信息存储的内容实质上就是的一个列表。这部分信息主要是在事务提交后使用，用来对中间状态的记录进行真正的删除(purge阶段)。

UPDATE操作对应的undo日志

在执行UPDATE语句时，InnoDB对更新主键和不更新主键这两种情况有截然不同的处理方案。

1.不更新主键

不更新主键的情况下，又可以细分为被更新的列占用的存储空间不发生变化与发生变化两种情况

1.1就地更新

在更新记录时，对于被更新的每个列来说，如果更新后的列与更新前的列占用的存储空间一样大，那么就可以进行就地更新，也就是在原纪录的基础上修改对应列的值。

1.2先删后插

如果有任何一个被更新的列在更新前和更新后占用的存储空间大小不一致，那么就需要先把这条旧记录从聚簇索引页面中删除(真正的删除)，然后再根据更新后列的值创建一条新的记录并插入到页面中。

2.更新主键

针对UPDATE语句中更新了记录主键值的这种情况，InnoDB分了两步进行处理

1. 将旧记录进行delete mark操作(在事务提交后才真正删除，为了实现MVCC功能)。
2. 根据更新后各列的值创建一条新纪录，并将其插入到聚簇索引中。由于更新后的记录主键值发生了变化，所以需要重新从聚簇索引中定位这条记录所在的位置，然后把它插进去

针对UPDATE语句更新记录主键值的这种情况，在对该记录进行delete mark操作时，会记录一条类型为TRX_UNDO_DEL_MARK_REC的undo日志，之后插入新纪录时，会记录一条类型为TRX_UNDO_INSERT_REC的undo日志，也就是说每一条记录的主键值进行修改，都会记录2条undo日志。

FIL_PAGE_UNDO_LOG页面

Undo Page Header

FIL_PAGE_UNDO_LOG类型的页面专门用来存放undo日志的，这种页面的结构如上，Undo Page Header是Undo页面特有的，结构如下

其中各个属性的意思如下：

• TRX_UNDO_PAGE_TYPE:本页面准备存储什么类型的undo日志,undo日志大致分为两类，第一种是TRX_UNDO_INSERT，一般由insert语句产生，update语句中有更新主键的情况时也会产生此类型的undo日志;第二种是TRX_UNDO_UPDATE，除了第一种日志，其他的都属于这个大类，一般由delete与update语句产生。

之所以把undo日志分为两类是因为类型为TRX_UNDO_INSERT_REC的undo日志在事务提交后可以直接删除掉，而其他类型的undo日志还需要为MVCC服务，不能直接删除掉，因此它们的处理需要区别对待。

• TRX_UNDO_PAGE_START:表示在当前页面中从什么位置开始存储undo日志，或者说表示第一条undo日志在本页面中的起始偏移量。
• TRX_UNDO_PAGE_FREE:与上面的TRX_UNDO_PAGE_START对应，表示当前页面中存储的最后一条undo日志结束时的偏移量，或者说从这个位置开始，可以继续写入新的undo日志
• TRX_UNDO_PAGE_NODE:代表一个链表结构，将多个FIL_PAGE_UNDO_LOG页连接起来。

由于事务执行过程中会产生大量的undo日志，所以存在一个页面放不下的情况，因此MYSQL引入了undo日志链表的概念，其中链表第一个节点的undo页面称为first undo page，它内部除了包含Undo Page Header之外，还会包含其他的管理信息，如Undo Log Segment Header

Undo Log Segment Header

MYSQL规定，每个Undo页面链表都对应着一个段，称为Undo Log Segment，链表中的页面都是从这个段申请的，所以在Undo页面链表的第一个页面中设计了一个名为Undo Log Segment Header的部分，这个部分包含了该链表对应的段的Segment Header信息，以及其他一些关于这个段的信息。

该结构中各个属性如下

• TRX_UNDO_STATE:本Undo页面处于什么状态，可能的状态有活跃状态、被缓存状态、等待被释放状态、等待被purge状态等
• TRX_UNDO_LAST_LOG:本Undo页面链表中最后一个Undo Log Header的位置
• TRX_UNDO_FSEG_HEADER:本Undo页面链表对应的段的Segment Header信息(通过这个信息可以找到该段对应的INODE Entry)
• TRX_UNDO_PAGE_LIST:Undo页面链表的基节点

Undo Log Header

一个事务在向Undo页面写入undo日志时，是紧接着上一条undo日志堆放的，各条undo日志亲密无间。同时同一个事务向一个undo页面链表中写入的undo日志算是一个组。在每写入一组undo日志时，都会在这组undo日志前先记录一下关于这个组的一些信息。存储这些属性的地方就称为Undo Log Header(也即日志页面链表中Undo Log Header不止一个，每个为一组)。所以Undo页面链表的第一个页面在真正写入undo日志前，其实都会被填充Undo Page Header、Undo Log Segment Header、Undo Log Header这三个部分。

各个属性的含义如下：

• TRX_UNDO_TRX_ID:生成本组undo日志的事务id
• TRX_UNDO_TRX_NO:事务提交后生成的一个序号，该序号用来标记事务的提交顺序
• TRX_UNDO_DEL_MARKS:标记本组undo日志中是否包含由delete mark操作产生的undo日志
• TRX_UNDO_LOG_START:表示本组undo日志中第一条undo日志在页面中的偏移量
• TRX_UNDO_XID_EXISTS:本组undo日志是否包含XID信息
• TRX_UNDO_DICT_TRANS:标记本组undo日志是不是由DDL语句产生的。
• TRX_UNDO_TABLE_ID:如果上一个属性为真，则本属性表示DDL语句操作的表的table id
• TRX_UNDO_NEXT_LOG:下一组undo日志在页面中开始的偏移量
• TRX_UNDO_PREV_LOG:上一组undo日志在页面中开始的偏移量
• TRX_UNDO_HISTORY_NODE:一个12字节的链表节点结构，代表一个名为History链表的节点

一般来说，一个Undo页面链表只存储一个事务执行过程中产生的一组undo日志。但是在某些情况下，可能会在一个事务提交后，后续开启的事务又重新利用这个undo页面链表，这会导致一个Undo页面中可能存放多组undo日志。

重用Undo页面

一个Undo页面链表如果可以被重用，那么它需要符合下面两个条件

• 该链表中仅包含一个Undo页面
• 该Undo页面已经使用的空间小于整个页面空间的3/4；

同时，按照存储的undo日志所属的大类，Undo页面链表可以被分为insert undo链表和update undo链表，这两种链表被重用时，策略也是不同的

• insert undo链表:由于insert undo链表中只存储类型为TRX_UNDO_INSERT_REC的undo日志(即插入操作的undo日志)，这种类型的undo日志在事务提交之后就没用了，可以被清除掉，因此在某个事务提交后，在重用这个事务的insert undo链表(这个链表只有一个页面)时，可以直接把之前事务写入的一组undo日志覆盖掉，从头开始写入新事务的一组undo日志。
• update undo链表：为了实现MVCC功能，update undo链表中的undo日志不能立即删除，因此之后的事务想重用该链表时，只能在原有内容后边追加Undo Log Header，以及新的undo日志。

回滚段

一个事务在执行过程中最多可以分配4个Undo页面链表，在同一时刻，不同事务拥有的Undo页面链表是不一样的，系统在同一时刻其实可以存在许多个Undo页面链表，为了更好地管理这些链表，MYSQL设计了一个名为Rollback Segment Header的页面，这个页面中存放了各个Undo页面链表的first undo page的页号，这些页号称为undo slot。

• TRX_RSEG_MAX_SIZE:这个回滚段中管理的所有Undo页面链表中的Undo页面数量之和的最大值。也就是说所有Undo页面链表中的Undo页面数量之和不能超过该值。
• TRX_RSEG_HISTORY_SIZE:History链表占用的页面数量
• TRX_RSEG_HISTORY:History链表的基节点。
• TRX_RSEG_FSEG_HEADER:这个回滚段对应的10字节大小的Segment Header结构，通过它可以找到本回滚段对应的INODE Entry
• TRX_RSEG_UNDO_SLOTS:各个Undo页面链表的first undo page的页号集合，也就是undo slot集合。一个页号占用4字节，对于大小为16KB的页面来说，这个部分共存储了1024个undo slot，所以共需4096字节。

InnoDB中最多可以配置128个回滚段，并且这128个回滚段分为两大类，第0号、第33-127号回滚段属于一类，其中第0号回滚段必须在系统表空间中。第1-32号回滚段属于一类，这些回滚段必须在临时表空间中。将回滚段分为这两类的原因在于，Undo页面本身也只是一个普通的页面，在Undo页面写入undo日志本身也是一个写页面的过程，所以对Undo页面做的任何改动都会记录相应类型的redo日志。但是对于临时表来说，因为修改临时表而产生的的undo日志只需在系统运行过程中有效。如果系统发生崩溃，那么重启时也不需要恢复这些undo日志所在的页面。

记录的roll_pointer字段

其中各个属性的含义如下

• is_insert:表示该指针指向的undo日志是否是TRX_UNDO_INSERT大类的undo日志
• rseg_id:表示该指针指向的undo日志的回滚段编号，由于最多有128个回滚段，他们的编号范围是0-127，因此用7比特表示足够了
• page number:表示该指针指向的undo日志所在页面的页号
• offset:表示该指针指向的undo日志在页面中的偏移量

事务隔离级别与MVCC

脏写:如果一个事务修改了另一个未提交事务修改过的数据，就意味着发生了脏写现象。

脏读:如果一个事务读到了另一个未提交事务修改过的数据，就意味着发生了脏读现象。

不可重复读:如果一个事务修改了另一个未提交事务读取的数据，就意味着发生了不可重复读现象。

幻读:如果一个事务先根据某些搜索条件查询出一些记录，在该事务未提交时，另一个事务写入了一些符合那些搜索条件的记录，就意味着发生了幻读现象。

MVCC

每一条聚簇索引记录都包含以下两个隐藏列

• trx_id:一个事务每次对某条聚簇索引记录进行改动时，都会把该事务的事务id赋值给trx_id隐藏列。
• roll_pointer:每次对某条聚簇索引记录进行改动时，都会把旧的版本写入到undo日志中，这个隐藏列就相当于一个指针，可以通过它找到该记录修改前的信息。

由于记录的每一次改动都会记录一条undo日志，且每个日志也都有一个roll_pointer属性(除了INSERT操作产生的undo日志)，通过这个属性，可以将这些undo日志串成一个链表。

在每次更新记录后，都会将旧值放到一条undo日志中，随着更新次数的增多，所有的版本都会被roll_pointer属性连接成一个链表，这个链表称为版本链。版本链的头结点就是当前记录的最新值。另外，每个版本中还包含生成该版本时对应的事务id。之后会利用这个记录的版本链来控制并发事务访问相同记录时的行为，这种机制称之为多版本并发控制(Multi-Version-Concurrency,MVCC)。

MVCC在MySQL InnoDB中的实现主要是为了提高数据库并发性能，用更好的方式去处理读-写冲突，做到即使有读写冲突时，也能做到不加锁，非阻塞并发读

ReadView

对于使用READ UNCOMMITTED隔离级别的事务来说，由于可以读到未提交事务修改过的记录，所以直接读取记录的最新版本就好了；对于使用SERIALIZABLE隔离级别的事务来说，MYSQL规定使用加锁的方式来访问记录。而对于使用READ COMMITTED和REPEATABLE READ隔离级别的事务来说，都必须保证读到已经提交的事务修改过的记录。也就是说假如另一个事务已经修改了记录但是尚未提交，则不能直接读取最新版本的记录。为了确定版本链中哪个版本是当前事务可见的，MYSQL引入了一个新的概念:Read View，它包含4个比较重要的内容。

• m_ids:在生成ReadView时，当前系统中活跃的读写事务的事务id列表
• min_trx_id:在生成ReadView时，当前系统中活跃的读写事务中最小的事务id，也就是m_ids中最小的值。
• max_trx_id:在生成ReadView时，系统应该分配给下一个事务的事务id值。
• creator_trx_id:生成该ReadView的事务的事务id。

只有对表中的记录进行改动时，也即增删改操作，才会为该事务分配唯一的事务id,否则一个事务的事务id值都默认为0

通过ReadView，在访问某条记录时，只需要按照下面的步骤来判断记录的某个版本是否可见

• 如果被访问版本的trx_id属性值与ReadView中的creator_trx_id值相同，意味着当前事务在访问它自己修改过的记录，所以该版本可以被当前事务访问。
• 如果被访问版本的trx_id属性值小于ReadView中的min_trx_id值，表示生成该版本的事务在当前事务生成ReadView前已经提交，所以该版本可以被当前事务访问
• 如果被访问版本的trx_id属性值大于或等于ReadView中的max_trx_id值，表明生成该版本的事务在当前事务生成ReadView之后才开启，所以该版本不可以被当前事务访问。
• 如果被访问版本的trx_id属性值在ReadView的min_trx_id和max_trx_id之间，则需要判断trx_id属性值是否在m_ids列表中。如果在，说明创建ReadView时生成该版本的事务还是活跃的，该版本不可以被访问；如果不在，说明创建ReadView时生成该版本的事务已经被提交，该版本可以被访问。

在MYSQL中，READ COMMITTED和REPEATABLE READ隔离级别之间一个非常大的区别就是它们生成ReadView的时机不同

• READ COMMITTED:每次读取数据前都生成一个Read View
• REPEATABLE READ:在第一次读取数据时生成一个Read View，并且之后的读取操作都重用这个Read View

二级索引与MVCC

由于只有在二级索引中才有trx_id和roll_poi二级索引nter隐藏列，因此，对于使用索引索引来执行的查询来说，判断可见性是有以下两个步骤。

1. 二级索引页面的Page Header部分有一个名为PAGE_MAX_TRX_ID的属性，每当对该页面中的记录执行增删改操作时，如果执行该操作的事务的事务id大于PAGE_MAX_TRX_ID属性值，就会把PAGE_MAX_TRX_ID属性设置为执行该操作的的事务的事务id。这也意味着PAGE_MAX_TRX_ID属性值代表着修改该二级索引页面的最大事务id。当SELECT语句访问某个二级索引记录时，首先会看一下对应的ReadView的min_trx_id是否大于该页面的PAGE_MAX_TRX_ID属性值。如果大于，说明该页面中的所有记录都对该ReadView可见，否则就得执行步骤2，在回表之后再判断可见性。
2. 利用二级索引记录中的主键值进行回表操作，得到对应的聚簇索引记录后再按照前面讲过的方式找到对该ReadView可见的第一个版本，然后判断该版本中对应的二级索引列的值是否与利用该二级索引查询时的值相同。如果相同，则将该记录发送给客户端，否则跳过这条记录。

关于purge

update undo日志在事务提交时先把当前这一组undo日志作为一个节点插入到回滚段部分的History链表中，

insert undo日志在事务提交之后就可以释放掉了，而update undo日志由于还需要支持MVCC，因此不能立即删除。为了支持MVCC，delete mark操作仅仅是在记录上打了一个删除标记，而没有真正地将记录删除。那么这些日志与记录在什么时候才能彻底删除呢？

update undo日志和被标记为删除的记录只是为了支持MVCC而存在的，只要系统中最早产生的那个Read View不再访问它们，它们的使命就结束了。因此MYSQL需要判断一个ReadView在什么时候才肯定不会访问某个事务执行过程中产生的undo日志，即保证生成ReadView时某个事务已经提交，那么该ReadView肯定就不需要访问该事务运行过程中产生的undo日志了。

因此，MYSQL执行了以下操作

• 在一个事务提交时，会为这个事务生成一个事务no的值，该值用来表示事务提交的顺序，先提交的事物的事务no值小，后提交的事务的事务no值大。

在一组undo日志中对应的Undo Log Header部分有一个名为TRX_UNDO_TRX_NO的属性。当事务提交时，就把该事务对应的事务no值填到这个属性中。因为事务no代表着各个事务提交的顺序，而History链表又是按照事务提交的顺序来排列各组undo日志的，所以History链表中的各组undo日志也是按照对应的事务no来排序的。

• 一个Read View结构除了包含前面几个属性以外，还会包含一个事务no的属性。在生成一个Read View时，会把当前系统中最大的事务no值还大1的值赋值给这个属性。

此外，MYSQL还将当前系统中所有的Read View按照创建时间连成了一个链表。当执行purge操作时，就把系统中最早生成的ReadView取出来，如果当前系统中不存在ReadView，就现场创建一个，新创建的这个ReadView的事务no值比当前已经提交的事务的事务no值大。然后从各个回滚段的History链表中取出事务no值较小的各组undo日志。如果一组undo日志的事务no值小于当前系统中最早生成的ReadView的事务no属性值，就意味着该组undo日志没有用了，就会从History链表中移除，并且释放掉它们占用的存储空间。