MySQL(16-20)

16. “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;

这个语句看上去逻辑很清晰，但是它的执行流程是怎样的呢？今天，我们就来学习这个语句是怎么执行的，以及有什么参数会影响执行的行为。

全字段排序
为了避免全表扫描，我们需要在city字段加上索引。
在city字段上创建索引之后，我们用explain命令来看看这个语句的执行情况：

图1. 使用explain命令查看语句的执行情况

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

为了说明这个SQL查询语句的执行过程，我们先来看一下city这个索引的示意图。

图2. city字段的索引示意图

从图中可以看到，满足city=’杭州’条件的行，是从IDX到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行返回给客户端。

我们暂且把这个排序过程，称为全字段排序，执行流程的示意图如下图所示：

图3. 全字段排序

图中“按name排序”这个动作，可能在内存中完成，也可能需要使用外部排序，这取决于排序所需的内存和参数sort_buffer_size。

sort_buffer_size，就是MySQL为排序开辟的内存（sort_buffer）的大小。如果要排序的数据量小于sort_buffer_size，排序就在内存中完成。但如果排序数据量太大，内存放不下，则不得不利用磁盘临时文件辅助排序。

你可以用下面介绍的方法，来确定一个排序语句是否使用了临时文件。

-- 打开optimizer_trace，只对本线程有效
SET optimizer_trace='enabled=on';
-- @a 保存 Innodb_rows_read的初始值
select VARIABLE_VALUE into @a from  performance_schema.session_status where variable_name = 'Innodb_rows_read';
-- 执行语句
select city, name, age from t where city = '杭州' order by name limit 1000;
-- 查看OPTIMIZER_TRACE输出
select * from `information_schema`.`OPTIMIZER_TRACE`\G;
-- @b 保存Innodb_rows_read的当前值
select VARIABLE_VALUE into @b from performance_schema.session_status where variable_name = 'Innodb_rows_read';
-- 计算Innodb_rows_read差值
select @b-@a

这个方法是通过查看OPTIMIZER_TRACE的结果来确认的，你可以从number_of_tmp_files中看到是否使用了临时文件。

图4. 全排序的OPTIMIZER_TRACE部分结果

number_of_tmp_files表示的是，排序过程中使用的临时文件数。这里使用12个尾部文件。内存放不下时，就需要使用外部排序，外部排序一般使用归并排序算法。可以这么简单理解，MySQL将需要排序的数据分成12份，每一份单独排序后存在这些临时文件中。然后把这12个有序文件再合并成一个有序的大文件。

如果sort_buffer_size超过了需要排序的数据量的大小，number_of_tmp_files就是0，表示排序可以直接在内存中完成。

否则就需要放在临时文件中排序。sort_buffer_size越小，需要分成的份数越多，number_of_tmp_files的值就越大。

sort_mode里面的packed_additional_fields的意思是，排序过程中字符串做了“紧凑”处理。即使name字段的定义是varchar(16)，在排序过程中还是要按照实际长度来分配空间的。

同时，最后一个查询语句select @b-@a的返回结果是4000，表示排序过程中还是按照实际长度来分配空间的。

这里需要注意的是，为了避免对结论造成干扰，我把internal_tmp_disk_storage_engine设置成MyISAM。否则，select @b-@a的结果会显示为4001。

这是因为查询OPTIMIZER_TRACE这个表时，需要用到临时表，而internal_tmp_disk_storage_engine的默认值是InnoDB。如果使用的是InnoDB引擎的话，把数据从临时表取出来的时候，会让Innodb_rows_read的值加1。

rowid排序
在上面这个算法过程里面，只对原表的数据读了一遍，剩下的操作都是在sort_buffer和临时文件中执行的。但这个算法有一个问题，就是如果查询要返回的资源很多的话，那么sort_buffer里面要放的字段数太多，这样内存里能够同时放下的行数很少，要分成很多个临时文件，排序的性能会很差。

所以如果单行很大，这个方法效率不够好。

那么，如果MySQL排序的单行长度太大会怎么做呢？

接下来，可以修改一个参数，让MySQL采用另外一钟算法。

SET max_length_for_sort_data = 16;

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

city、name、age这三个字段的定义总长度是36，把max_length_for_sort_data设置为16，再来看看计算过程有什么改变。

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

但这时，排序的结果就因为少了city和age字段的值，不能直接返回了，整个执行流程就变成如下所示的样子：

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排序。

图5. rowid排序

对比图3的全字段排序流程不难发现，rowid排序多访问了一次表t的主键索引，就是步骤7。

需要说明的是，最后的“结果集”是一个逻辑概念，实际上MySQL服务端从排序后的sort_buffer中依次取出id，然后到原表查到city、name和age这三个字段的结果，不需要再服务端再耗费内存存储结果，是直接返回给客户端的。

再看看现在的结果。

图6. rowid排序的OPTIMIZER_TRACE部分输出

从OPTIMIZER_TRACE的结果中，examined_rows的值还是4000，表示用于排序的数据是4000行。但是select @b-@a这个语句的值变成5000了。因为这时候除了排序过程外，在排序完成后，还要根据id去原表取值。由于语句是limit1000，因此会多读1000行。

你还能看到另外两个信息也变了。

sort_mode变成了，表示参与排序的只有name和id这两个字段。

number_of_tmp_files变成10了，是因为这时候参与排序的行数虽然仍然是4000行，但是每一行都变小了，因此需要排序的总数据量就变小了，需要的临时文件也相应地变少了。

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

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

这也就体现了MySQL的一个设计思想：如果内存够，就要多利用内存，尽量减少磁盘访问。

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

到这里，我们了解到MySQL的排序是一个成本比较高的操作。那么，是不是所有的order by都需要排序操作呢？如果不排序就能得到正确的结果，那对系统的消耗会小很多，语句的执行时间也会变得更短。

其实，并不是所有的order by语句，都需要排序操作。从上面分析的执行过程，我们可以看到，MySQL之所以需要生成临时表，并且在临时表做排序操作，其原因是原来的数据都是无序的。

你可以设想下，如果能够保证从city这个索引上取出来的行，天然就是按照name递增排序的话，是不是就可以不用再排序了。

确实是这样的。

所以，我们可以在这个市民表上创建一个city和name的联合索引，对应的SQL语句是：

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

作为与city索引的对比，我们来看看这个索引的示意图。

图7. city和name联合索引示意图

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

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

1. 从索引 (city, name) 找到第一个满足city=’杭州’条件的主键id；
2. 到主键id索引取出整行，取name、city、age三个字段的值，作为结果集的一部分直接返回；
3. 从索引 (city, name) 取下一个记录主键id；
4. 重复步骤2、3，直到查到第1000条记录，或者是不满足city=’杭州’条件时循环结束。

图8. 引入 (city, name)联合索引后，查询语句的执行计划

可以看到，这个查询过程不需要临时表，也不需要排序。接下来，我们用explain的结果来印证一下。

图9. 引入 (city, name) 联合索引后，查询语句的执行计划

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

按照覆盖索引的概念，这个语句的执行流程还可以再次优化。
针对这个查询，我们可以创建一个city、name和age的联合索引，对应的SQL语句就是：

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

这时，对于city字段的值相同的行来说，还是按照name字段的值递增排序的，此时的查询语句也就不再需要排序了。这样整个查询语句的执行流程就变成了：

1. 从索引 (city name, age) 找到第一个满足city=’杭州’条件的记录，取出其中的city、name和age这三个字段的值，作为结果集的一部分直接返回；
2. 从索引 (city, name, age) 取下一个记录，同样取出这三个字段的值，作为结果集的一部分直接返回；
3. 重复执行步骤2，直到查到第1000条记录，或者是不满足city=’杭州’条件时循环结束。

图10. 引入 (city, name, age) 联合索引后，查询语句的执行流程

小结
这一节我们学习了MySQL中order by语句的几种算法流程。
在开发系统的时候，总是不可避免地会使用到order by语句。心理要清楚每个排序逻辑是怎么实现的，还要能够分析出在最坏情况下，每个语句对系统资源的消耗，这样才能做到下笔如有神，不犯低级错误。

小问题
假设表里面已经有了city_name(city, name)这个联合索引，然后要查杭州和苏州两个城市中所有的市民的姓名，并且按名字排序，显示前100条记录。如果SQL查询语句是这么写的：

select * from t where city in ('杭州'," 苏州 ") order by name limit 100;

那么，这个语句执行的时候会有排序过程吗，为什么？
如果在业务端代码由你来开发，需要实现一个在数据库端不需要排序的方案，你会怎么实现呢？
进一步地，如果有分页需求，要显示第101页，也就是说语句最后要改成“limit 10000, 100”，你的实现方法又会是什么呢？
解析：
虽然有 (city, name) 联合索引，对于单个city内部，name是递增的。但是由于这条SQL语句不是要单独差一个city的值，而是同时查了“杭州”和“苏州”两个城市，因为所有满足条件的name就不是递增的。也就是说，这条SQL语句需要排序。

那么如何避免排序呢？
这里，我们要用到 (city, name) 联合索引的特性，把这一条语句拆成两条语句，执行流程如下：

1. 执行 select * from where city = '杭州' order by name limit 100;这个语句不是需要排序的，客户端用一个长度为100 的内存数组A保存结果。
2. 执行select * from where city = '苏州' order by name limit 100;用相同的方法，假设结果被存进了内存数组B；
3. 现在A和B是两个有序数组，然后可以用归并排序的思想，得到name最小的前100值，就是我们需要的结果了。

如果把这天语句里“limit 100”改成“limit 10000, 100”的话，处理方式其实也差不多，即：要把上面的两条语句改写成：

select * from t where city = '杭州' order by name limit 10100;

和

select * from t where city = '杭州' order by name limit 10100;

这时候数据量较大，可以同时起两个连接一行行读结果，用归并排序算法拿到这两个结果集，按顺序取第10001~10100的name值，就是需要的结果了。

当然这个方案有一个明显的损失，就是从数据库返回给客户端的数据量变大了。
所以，如果数据的单行比较大的话，可以考虑把这两条SQL语句改成下面这种写法：

select id, name from t where city = '杭州' order by name limit 10100;

和

select id, name from t where city = '杭州' order by name limit 10100;

然后，再用归并排序取得name顺序第10001~10100的name、id的值，然后拿着这100个id到数据库中去查出所有记录。

17. 如何正确地显示随机消息？

场景引入
一款英语学习APP首页有一个随机显示单词的功能，也就是根据每个用户的级别有一个单词表，然后这个用户每次访问首页的时候，都会随机滚动显示三个单词。开发者发现随着单词表变大，选单词这个逻辑变得越来越慢，甚至影响到了首页的打开速度。

现在，如果让你来设计这个SQL语句，你会怎么写呢？

为了便于理解，对这个例子进行一下简化：去掉每个级别的用户都有一个对应的单词表这个逻辑，直接就是从一个单词表中随机选出三个单词。这个表的建表语句和初始数据的命令如下：

CREATE TABLE `words` (
 `id` int(11) NOT NULL AUTO_INCREMENT,
 `word` varchar(64) DEFAULT NULL,
 PRIMARY KEY (`id`)
) ENGINE=InnoDB;
delimiter ;;
create procedure idata()
begin
 declare i int;
 set i=0;
 while i<10000 do
 insert into words(word) values(concat(char(97+(i div 1000)), char(97+(i % 1000 div 1
 set i=i+1;
 end while;
end;;
delimiter ;
call idata();

在这个表里插入了10000行记录。接下来，我们就来看看要随机选择3个单词，有什么方法实现，存在什么问题以及如何改进。

内存临时表
首先，可以使用order by rand()来实现这个逻辑。

select word from words order by rand() limit 3;

这个语句的意思很直白，随机排序取前3个。虽然这个SQL语句写法很简单，但执行流程却有点复杂。
我们先用explain命令来看看这个语句的执行情况。

图11. 使用explain命令查看语句的执行情况

Extra字段显示Using temporary，表示使用临时表；Using filesort，表示需要执行排序操作。即这个查询需要临时表，并且需要在临时表上排序。

对于InnoDB表来说，执行全字段排序会减少磁盘访问，因此会被优先选择。
对于InnoDB引擎的内存表来说，回表过程只是简单地根据数据行的位置，直接访问内存得到数据，根本不会导致多访问磁盘。优化器没有了这一层顾虑，就是用于排序的行越小越好了，所以，MySQL这时就会选择rowid排序。

这条语句的执行流程是这样的：

1. 创建一个临时表。这个临时表使用的是Memory引擎，表里有两个字段，第一个字段是double类型，为了后面描述方便，记为字段R，第二个字段是varchar(64)类型，记为字段W。并且，这个表没有建索引。
2. 从words表中，按主键顺序取出所有的word值。对于每一个word值，调用rand()函数生成一个大于0小于1的随机小数，并把这个随机小数和word分别存入临时表的R和W字段中，至此，扫描行数是10000。
3. 现在临时表有10000行数据了，接下来你要在这个没有索引的内存临时表上，按照字段R排序。
4. 初始化sort_buffer。sort_buffer中有两个字段，一个是double类型，另一个是整型。
5. 从内存临时表中一行一行地取出R值和位置信息，分别存入sort_buffer中的两个字段里。这个过程要对内存临时表做全表扫描，此时扫描行数增加10000，变成了20000。
6. 在sort_buffer中根据R的值进行排序。注意，这个过程没有涉及表操作，所以不会增加扫描行数。
7. 排序完成后，取出前三个结果的位置信息，依次到内存临时表中取出word值，返回给客户端。这个过程中，访问了表的三行数据，总扫描行数变成了20003。

接下来，我们通过慢查询日志（slow log）来验证一下。
老师MySQL5的执行结果：

# Query_time: 0.900376 Lock_time: 0.000347 Rows_sent: 3 Rows_examined: 20003
SET timestamp=1541402277;
select word from words order by rand() limit 3;

其中，Rows_examined: 20003就表示这个语句执行过程中扫描了20003行，也就验证了我们分析得出的结论。

Mark，下面是我用MySQL8的执行结果：

# Query_time: 0.003284  Lock_time: 0.000091 Rows_sent: 3  Rows_examined: 10003
SET timestamp=1637993654;
select word from words order by rand() limit 3;

完整的排序执行流程如下：

图12. 随机排序完整流程图1

图中的pos就是位置信息，这里的“位置信息是什么概念”？

这时候，我们回到一个基本问题：MySQL的表是用什么方法来定位“一行数据”的。
对于InnoDB表，如果你创建的表没有主键或者把一个表的主键删掉了，那么InnoDB会自己生成一个长度为6字节的rowid来作为主键。
这也就是排序模式里面，rowid名字的来历。实际上它表示的是：每个引擎用来唯一标识数据行的信息。

• 对于有主键的InnoDB表来说，这个rowid就是主键ID；
• 对于没有主键的InnoDB表来说，这个rowid就是由系统生成的。
• Memory引擎不是索引组织表。在这个例子中，可以认为它就是一个数组，这个rowid就是数组的下标。

到此，总结一下：order by rand()使用了内存临时表，内存临时表排序的时候使用了rowid排序方法。

磁盘临时表
那么，是不是所有的临时表都是内存表呢？

其实不是的。tmp_table_size这个配置限制了内存临时表的大小，默认值是16M。如果临时表大小超过了tmp_table_size，那么内存临时表就会转成磁盘临时表。
磁盘临时表使用的引擎默认是InnoDB，是由参数internal_tmp_disk_storage_engine控制的。
当你使用磁盘临时表的时候，对应的就是一个没有显式索引的InnoDB表的排序过程。
为了复现这个过程，我把tmp_table_size设置成1024，把sort_buffer_size设置成 32768, 把max_length_for_sort_dat 设置成 16。

set tmp_table_size=1024;
set sort_buffer_size=32768;
set max_length_for_sort_data=16;
/* 打开 optimizer_trace，只对本线程有效 */
SET optimizer_trace='enabled=on'; 
/* 执行语句 */
select word from words order by rand() limit 3;
/* 查看 OPTIMIZER_TRACE 输出 */
SELECT * FROM `information_schema`.`OPTIMIZER_TRACE`\G

图13. OPTIMIZER_TRACE部分结果

然后，我们来看这一次OPTIMIZER_TRACE的结果。
因为将max_length_for_sort_data设置成16，小于word字段的长度定义，所以我们看到sort_mode里面显示的rowid排序，这个是符合预期的，参与排序的是随机值R字段和rowid字段组成的行。
这里，R字段粗放的随机值就8个字节，rowid是6个字节，数据总行数是10000，这样算出来就有140000字节，超过了sort_buffer_size定义的32768字节了。但是，number_of_tmp_files的值居然是0，说明没有使用临时文件。

这个SQL语句的排序确实没有用到临时文件，采用的是MySQL5.6版本引入的一个新的排序算法，即：优先队列排序算法。
其实，我们现在的SQL语句，只需要取R值最小的3个rowid。但是，如果使用归并排序算法，虽然最终也能得到前3个值，但是这个算法结束后，已经将10000行数据都排好序了。
也就是说，后面的997行也是有序的了。但，我们的查询并不需要这些数据是有序的。所以，想一下就明白了，这浪费了非常多的计算量。
而优先队列算法，就可以精确地只得到三个最小值，执行流程如下：

1. 对于这10000个准备排序的 (R, rowid)，先取前三行，构造出一个堆；
2. 取下一个行 (R′, rowid′)，跟当前堆里面最大的R比较，如果R′小于R，把这个 (R, rowid) 从堆中去掉，换成 (R′, rowid′)；
3. 重复第2步，直到第10000个 (R′, rowid′) 完成比较。

图13的OPTIMIZER_TRACE结果中，filesort_priority_queue_optimization这个部分的chosen=ture就表示使用了优先队列排序算法，这个过程不需要临时问价，因此对应的number_of_tmp_files是0。
这个流程结束后，我们构造的堆里面，就是这个10000行里面R值最小的三行。然后，依次把它们的rowid取出来，去临时表里面拿到word字段，这个过程就跟上一篇文章的rowid排序的过程一样了。

我们再看一下上面一篇文章的SQL查询语句：

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

那么这里也用到了limit，为什么没用优先队列排序算法呢？原因是，这条SQL语句是limit 1000，如果使用优先队列算法的话，需要维护的堆的大小就是1000行的 (name, rowid)，超过了我设置的sort_buffer_size大小，所以只能使用归并排序算法。
总之，不论是使用哪种类型的临时表，order by rand()这种写法都会让计算过程非常复杂，需要大量的扫描行数，因此排序过程的资源消耗也会很大。

随机排序方法
我们先把问题简化一下，如果只随机选择1个word值，思路上这样的：

1. 取得这个表的主键id的最大值M和最小值N；
2. 用随机函数生成一个最大值到最小值之间的数X=(M-N) * rand() + N；
3. 取不小于X的第一个ID的行。

我们把这个算法，暂时称作随机算法1，执行语句的序列如下：

select max(id),min(id) into @M,@N from t ;
set @X= floor((@M-@N+1)*rand() + @N);
select * from t where id >= @X limit 1;

这个方法效率很高，因为取max(id)和min(id)都是不需要扫描索引的，而第三步的select也可以用索引快速定位，可以认为就只扫描了3行。但实际上，这个算法本身并不严格满足题目的随机要求，因为ID中间可能有空洞，因此选择不同行的概率不一样，不是真正的随机。

为了得到严格随机的结果，可以用下面这个流程：

1. 取得整个表的行数，并记为C；
2. 取得Y=floor(C * rand())。floor函数用于取整；
3. 再用limit Y, 1取得1行。

我们把这个算法，称为随机算法2，执行语句的序列如下：

select count(*) into @C from t;
set @Y = floor(@C * rand());
set @sql = concat("select * from t limit ", @Y, ",1");
prepare stmt from @sql;
execute stmt;
DEALLOCATE prepare stmt;

由于limit后面的参数不能直接跟变量，所以使用了prepare+execute的方法。

这个随机算法2，解决了算法1里面明显的概率不均匀问题。
MySQL处理limit Y, 1的做法就是按顺序一个一个地读出来，丢掉前Y个，然后把下一个记录作为返回结果，因此这一步需要扫描Y+1行。再加上，第一步扫描的C行，总共需要扫描C+Y+1行，执行代价比随机算法1的代价要高。

当然，随机算法2跟直接order by rand()比起来，执行代价还是小很多的。
如果按照随机算法2的思路，要随机取3个值，可以这么做：

1. 取得整个表的行数，记为C；
2. 根据相同的随机方法得到得到Y1、Y2、Y3；
3. 再执行三个limit Y, 1语句得到三行数据。

我们把这个算法，称为随机算法3，执行语句的序列如下：

select count(*) into @C from t;
set @Y1 = floor(@C * rand());
set @Y2 = floor(@C * rand());
set @Y3 = floor(@C * rand());
-- 在应用代码里面取 Y1、Y2、Y3 值，拼出 SQL 后执行
select * from t limit @Y1, 1;
select * from t limit @Y2, 1;
select * from t limit @Y3, 1;

小结
这一节通过随机排序的需求学习了MySQL对临时表的执行过程。
如果直接使用order by rand()，这个语句需要Using temporary和Using filesort，查询的执行代价往往是比较大的。所以，在设计的时候要尽量避开这种写法。
在这一节的需求中，我们不是仅仅在数据库内部解决问题，还会让应用代码配合拼接SQL语句。在实际应用的过程中，比较规范的用法就是：尽量将业务逻辑写在业务代码中，让数据库只做“读写数据”的事情。

小问题
上面的随机算法3的总扫描行数是C+(Y1+1) +(Y2+1) +(Y3+1)，实际上它是可以继续优化来进一步减少扫描行数的。你有什么解决方案呢？
解析：
取Y1、Y2和Y3里面最大的一个数，记为M，最小的一个数即为N，然后执行下面这条SQL语句：

select * from t limit N, M-N+1;

再加上整个表总行数的C行，这个方案的扫描行数总共只需要C+M+1行。

18. 为什么这些SQL语句逻辑相同，性能却差异巨大？

案例一：条件字段函数操作
假设你现在维护了一个交易系统，其中交易记录表tradelog包含交易流水号（tradeid）、交易员id（operator）、交易时间（t_modified）等字段。为了便于描述，我们先忽略其他字段。这个表的建表语句如下：

CREATE TABLE `tradelog` (
 `id` int(11) NOT NULL,
 `tradeid` varchar(32) DEFAULT NULL,
 `operator` int(11) DEFAULT NULL,
 `t_modified` datetime DEFAULT NULL,
 PRIMARY KEY (`id`),
 KEY `tradeid` (`tradeid`),
 KEY `t_modified` (`t_modified`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

假设，现在已经记录了从2016年初到2018年底的所有数据，运营部门有一个需求是，要统计发生在所有年份中7月份的交易记录总数。这个逻辑看上去并不复杂，你的SQL可能会这么写：

select count(*) from tradelog where month(t_modified) = 7;

t_modified的索引结构如下：

图14. t_modified索引示意图

如果SQL语句条件用的是where t_modified=’2018-7-1’的话，引擎就会按照上面绿色箭头的路线，快速定位到t_modifid=’2018-7-1’需要的结果。但是，如果计算month()函数的话，传入7的时候，在树的第一层就不知道该怎么办了。
也就是说，对索引字段做函数操作，可能会破坏索引值的有序性，因此优化器就决定走树搜索功能。
需要注意的是，优化器并不是要放弃使用这个索引。
在这个例子里，放弃了树搜索功能，优化器可以选择遍历主键索引，也可以选择遍历索引t_modified，优化器对比索引大小后发现，索引t_modifid更小，遍历这个索引比遍历主键索引来得更快。因此最终还是会选择索引t_modified。
但是，由于在t_modified字段加了month()函数操作，导致了全索引扫描。为了能够用上索引的快速定位能力，我们就要把SQL语句改成基于字段本身的范围查询。按照下面这个下发，优化器就能按照我们预期的，用上t_modified索引的快速定位能力了。

select count(*) from tradelog 
where (t_modified >= '2016-7-1' and t_modified<'2016-8-1') 
or (t_modified >= '2017-7-1' and t_modified<'2017-8-1') 
or (t_modified >= '2018-7-1' and t_modified<'2018-8-1');

案例二：隐式类型转换
我们看一下这条SQL语句：

select * from tradelog where tradeid=110717;

交易编号tradeid这个字段，本来就有索引，但是explain的结果显示，这条语句需要走全表扫描。tradeid的字段类型是varchar(32)，而输入的参数是整形，所以需要做类型转换。

那么，现在就有两个问题：

1. 数据类型转换的规则是什么？
2. 为什么有数据类型转换，就需要走全索引扫描？

在MySQL中，字符串和数字做比较的话，是将字符串抓换为数字。
这时，这个全表扫描的语句对于优化器来说，就相当于：

select * from tradelog where CAST(tradid AS signed int) = 110717;

也就是说，这条语句触发了我们上面说到的规则：对索引字段做函数操作，优化器会放弃走树功能。

案例三：隐式字符编码转换
假设系统里还有另外一个表trade_detail，用于记录交易的操作细节。为了便于量化分析和复现，我往交易日志表tradelog和交易详情表trade_detail这两个表里插入一些数据：

CREATE TABLE `trade_detail` (
 `id` int(11) NOT NULL,
 `tradeid` varchar(32) DEFAULT NULL,
 `trade step` int(11) DEFAULT NULL, /* 操作步骤 */
 `step_info` varchar(32) DEFAULT NULL, /* 步骤信息 */
 PRIMARY KEY (`id`),
 KEY `tradeid` (`tradeid`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
insert into tradelog values(1, 'aaaaaaaa', 1000, now());
insert into tradelog values(2, 'aaaaaaab', 1000, now());
insert into tradelog values(3, 'aaaaaaac', 1000, now());
insert into trade_detail values(1, 'aaaaaaaa', 1, 'add');
insert into trade_detail values(2, 'aaaaaaaa', 2, 'update');
insert into trade_detail values(3, 'aaaaaaaa', 3, 'commit');
insert into trade_detail values(4, 'aaaaaaab', 1, 'add');
insert into trade_detail values(5, 'aaaaaaab', 2, 'update');
insert into trade_detail values(6, 'aaaaaaab', 3, 'update again');
insert into trade_detail values(7, 'aaaaaaab', 4, 'commit');
insert into trade_detail values(8, 'aaaaaaac', 1, 'add');
insert into trade_detail values(9, 'aaaaaaac', 2, 'update');
insert into trade_detail values(10, 'aaaaaaac', 3, 'update again');
insert into trade_detail values(11, 'aaaaaaac', 4, 'commit');

这时候，如果要查询id=2的交易的所有操作步骤信息，SQL语句可以这么写：

-- SQL语句Q1
select d.* from tradelog l, trade_detail d 
where d.tradeid=l.tradeid and l.id=2;

图15. 语句Q1的explain结果

上图是语句Q1的执行计划：

1. 第一行显示优化器会先在交易记录表tradelog上查到id=2的行，这个步骤用上了主键索引，rows=1表示只扫描一行；
2. 第二行key=NULL，表示没有用上交易详情表trade_detail上的tradeid索引，进行了全表扫描。

在这个执行计划里，是从tradelog表中取tradeid字段，再去trade_detail表里查询匹配字段。因此，我们把tradelog称为驱动表，把trade_detail称为被驱动表，把tradeid称为关联字段。
接下来，我们看下这个explain结果标识的执行流程：

图16. 语句Q1的执行过程

图中：
第1步，是根据id在tradelog表里找到L2这一行；
第2步，是从L2中取出tradeid字段的值；
第3步，是根据tradeid值到trade_detail表中查找条件匹配的行。
explain的结果里面第二行的key=NULL表示的就是，这个过程是通过遍历主键索引的方式，一个一个地判断tradeid的值是否匹配。

进行到这里，可以发现第3步不符合我们的预期。因为表trade_detail里tradeid字段上是有索引的，我们本来是希望使用tradeid索引能够快速定位到等值的行。但，这里并没有。
原因就是，这两个表的字符集不同，tradelog是utf8mb4，trade_detail是utf8，所以做表连接查询的时候用不上关联字段的索引。

那么，为什么字符集不同就用不上索引呢？
可以把执行步骤的第3步单独改成SQL语句：

select * from trade_detail 
where tradeid = $L2.tradeid.value;

其中，$L2.tradeid.value的字符集是utf8mb4。
字符集utf8mb4是utf8的超集，所以当两个类型的字符串做比较的时候，MySQL内部的操作是，先把utf8字符串转成utf8mb4字符集，再做比较。

utf8mb4是utf8 的超集。类似地，在程序设计语言里面，做自动类型转换的时候， 为了避免数据在转换过程中由于截断导致数据错误，也都是“按数据长度增长的方向”进行转换的。

因此，在执行上面这个语句的时候，需要将被驱动数据表里的字段一个个地转换成utf8mb4，再跟L2做比较。
也就是说，这个语句实际上等同于下面这个写法：

select * from trade_detail 
where CONVERT(traideid USING utf8mb4) = $L2.tradeid.value;

CONVERT()函数，在这里的意思是把输入的字符串转成utf8mb4字符集。
这就再次触发原则：对索引字段做函数操作，优化器会放弃走树搜索功能。

作为对比验证，我们看另外一个需求，“查找trade_detail表里id=4的操作，对应的操作者是谁”，再来看看这个语句和它的执行计划：

-- SQL语句Q2
select l.operator from tradelog l, trade_detail d
where d.tradeid = l.tradeid and d.id = 4;

图17. 语句Q2的explain结果

上图是Q2的执行计划，在这个语句中国trade_detail表成了驱动表，但是explain结果的第二行显示，这次的查询操作用上了被驱动表tradelog里的索引tradeid，扫描行数是1。

这也是两个tradeid字段的join操作，为什么这次能用上被驱动表tradeid索引呢？

假设驱动表trade_detail里id=4的行即为R4，那么在连接的时候（图5的第3步），被驱动表tradelog上执行的就是类型这样的SQL语句：

select operator from tradelog where traideid = $R4.tradeid.value;

这时候$R4.tradeid.value的字符集是utf8，按照字符集转换规则，要转成utf8mb4，所以这个过程就被改写成：

select operator from tradelog
where traideid = CONVERT($R4.tradeid.value USING utf8mb4);

注意，这里的CONVERT函数是加在输入参数上的，这样就可以用上被驱动表的tradeid索引。

理解了原理之后，就可以用来指导操作了。如果要优化语句

select d.* from tradelog l, trade_detail d 
where d.tradeid=l.tradeid and l.id=2;

的执行过程，有两种做法：
比较常见的优化方法是，把trade_detail表上的tradeid字段的字符集也改成utf8mb4，这样就没有字符集转换的问题了。

alter table trade_detail modify tradeid varchar(32) CHARACTER SET utf8mb4 default null;

如果能够修改字段的字符集的话，是最好不过了。但是如果数据量不较大，或者业务上暂时不能做这个DDL的话，那就只能采用修改SQL语句的方法了。

select d.* from tradelog l , trade_detail d 
where d.tradeid=CONVERT(l.tradeid USING utf8) and l.id=2;

图18. SQL语句优化后的explain结果

这里，我主动把l.tradeid转成utf8，就避免了被驱动表上的字符编码转换，从explain结果可以看到，这次索引走对了。

小结
这一节使用三个例子说明：对索引字段做函数操作，可能会破坏索引值的有序性，因此优化器就决定放弃走树搜索功能。
第二个例子是隐式类型转换，第三个例子是隐式字符编码转换，它们都跟第一个例子一样，因为要求在索引字段上做函数操作而导致了全索引扫描。
第二个例子是隐式类型转换，第三个例子是隐式字符编码转换，它们都跟第一个例子一样，因为要求在索引字段上做函数操作而导致了全索引扫描。

小问题
表结构如下：

CREATE TABLE `table_a` (
 `id` int(11) NOT NULL,
 `b` varchar(10) DEFAULT NULL,
 PRIMARY KEY (`id`),
 KEY `b` (`b`)
) ENGINE=InnoDB;

假设现在表里面有100万行数据，其中10万行数据的b的值是’1234567890’，假设现在执行语句是这么写的：

select * from table_a where b='1234567890abcd';

这时候，MySQL会怎么执行呢？
解析：
最理想的情况是，MySQL看到字段b定义的是varchar(10)，那肯定返回空。可惜，MySQ不会这么做。
这条SQL语句的执行很慢，流程是这样的：

1. 在传给引擎执行的时候，做了字符截断。因为引擎里面这个行之定义了长度是10，所以直截了前10个字节，就是’1234567890’进去做匹配；
2. 这样满足条件的数据有10万行；
3. 因为是select *，所以要做10万次回表；
4. 但是每次回表以后查出整行，到server层一判断，b的值都不是’1234567890’；
5. 返回结果是空。

19. 为什么我只查一行的语句，也执行这么慢？

场景引入
有些情况下，“查一行”，也会执行得特别慢。
构造一个表，这个表有两个字段id和c，并且在里面插入10万行记录。

CREATE TABLE `t` (
  `id` int(11) NOT NULL,
  `c` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;
delimiter ;;
create procedure idata()
begin
  declare i int;
  set i=1;
  while(i<=100000) do
    insert into t values(i,i);
    set i=i+1;
  end while;
end;;
delimiter ;
call idata();

第一类：查询长时间不返回
如下所示，在表t执行下面的SQL语句：

select * from t where id = 1;

查询结果长时间不返回。

图19. 查询长时间不返回

一般碰到这种情况的话，大概率是表t被锁住了。接下来分析原因的时候，一般都是执行以下show processlist命令，看看当前语句处于什么状态。
然后我们再针对每种状态去分析它们产生的原因、如何复现，以及如何处理。

等MDL锁
如下图所示，就是使用show processlist命令查看Waiting for table metadata lock的示意图。

图20. waiting for table metadata lock状态示意图

出现这个状态表示的是，现在有一个线程正在表t上请求或者持有MDL写锁，把select语句堵住了。

在MySQL 5.7版本下复现这个场景，如下步骤所示。

图21. MySQL5.7中waiting for table metadata lock的复现步骤

session A通过lock table命令持有表t的MDL写锁，而session B的查询需要获取MDL读锁。所以，session B进入等待状态。

这类问题的处理方式，就是找到谁持有MDL写锁，然后把它kill掉。
但是，由于在show processlist的结果里面，session A的Command列是”Sleep”，导致查找起来很不方便。不过有了performance_schema和sys系统库以后，就方便多了。（MySQL启动时需要设置performance_schema=on。）
通过查询sys.schema_table_lock_waits这张表，我们就可以直接找出阻塞的process_id，把这个连接kill命令断开即可。

图22. 查询加表锁的线程id

等flush
接下来，列举另外一种查询被堵住的情况。
在表t上，执行下面的SQL语句：

select * from information_schema.processlist where id = 1;

查出来这个线程的状态是Waiting for table flush。

图23. Waiting for table flush状态示意图

这个状态表示的是，现在有一个线程正要对表t做flush操作。MySQL里面对表t做flush操作的用法，一般有以下两个：

flush tables t with read lock;
flush tables t with write lock;

这两个flush语句，如果指定表t的话，代表的是只关闭表t；如果没有指定具体的表名，则表示关闭MySQL里所有打开的表。
但是正常情况下这两个语句执行起来都很快，除非它们也被别的线程堵住了。
所以，出现Waiting for table flush状态的可能情况是：有一个flush tables命令被别的语句堵住了，然后它又堵住了我们的select语句。

可以按照如下步骤复现这种情况：

图23. Waiting for table flush的复现步骤

在session A中，故意每行都调用一次sleep(1)，这样这个语句默认要执行10万秒，在这期间表t一直是被session A打开着。然后，session B的flush tables命令要再去关闭表t，就需要等session A的查询结束。这样，sessionC要再次查询的话，就会被flush命令堵住了。
下图是这个复现步骤的show pocesslist结果。

图24. Waiting for table flush的show pocesslist结果

等行锁
现在，经过表级锁的考验，select语句终于来到引擎里。

select * from t where id = 1 lock in share mode;

由于访问id=1这个记录时要加读锁，如果这时候已经有一个事务在这行记录上持有一个写锁，我们的select语句就会被堵住。

复现步骤和现场如下：

图25. 行锁复现

显然，session A启动了事务，占有写锁，还不提交，是导致session B被堵住的原因。

这个问题并不难分析，但问题是查出是谁占着这个写锁。如果你用的是MySQL5.7版本，可以通过sys.innodb_lock_waits表查到。
查询方法是：

select * from t sys.innodb_lock_waits where locked_table=t\G

图26. 通过sys.innob_lock_waits查行锁

可以看到，这个信息很全，4号线程是造成堵塞的罪魁祸首。而干掉这个罪魁祸首的方式就是KILL 4，直接断开这个连接，连接被断开的时候，会自动回滚这个连接里面正在执行的线程，也就释放了id=1上的行锁。

第二类：查新慢
先来看一条语句：

select * from t where c = 50000 limit 1;

由于字段c上没有索引，这个语句只能走id主键顺序扫描，因此需要扫描5万行。
作为确认，你可以看一下慢查询日志。注意，这里为了把所有语句记录到slowlog里，我在连接里先后执行：

set long_query_time = 0;

将慢查询日志的时间阈值设置为0。

# Query_time: 0.025036  Lock_time: 0.000101 Rows_sent: 1  Rows_examined: 50000
SET timestamp=1638171219;
select * from t where c=50000 limit 1;

Rows_examined显示扫描了50000行。虽然这个查询只用了25毫秒，但是坏查询不一定是慢查询。这个例子中只有10万行记录，数据量大起来的话，执行时间就线性涨上去了。

扫描行数多，所以执行慢，这个很好理解。
但是，再看一个只扫描一行，但是执行很慢的语句：

select * from t where id = 1;

虽然扫描行数是1，但执行时间却长达800毫秒。

# Query_time: 0.804400  Lock_time: 0.000101 Rows_sent: 1  Rows_examined: 1
SET timestamp=1638171320;
select * from t where id = 1;

这个地方很奇怪，这些时间花在哪里呢？
继续看slowlog的下一个语句，select * from t where id = 1，执行时扫描行数也是1行，执行时间是0.2毫秒。

# Query_time: 0.000258  Lock_time: 0.000132 Rows_sent: 1  Rows_examined: 1
SET timestamp=1638171509;
select * from t where id = 1 lock in share mode;

这里看上去更加奇怪了，按理说lock in share mode还要加锁，时间应该更长才对。

其实这个场景很容易复现出来：

图27. 复现步骤

可以看到，session A先用start transaction with consistent snapshot命令启动了一个事务，之后session B才开始执行update语句。
session B执行完100万次update语句后，id=1这一行所处的状态，可以从下图中找到答案。

图28. id=1的数据状态

session B更新完100万次，生成了100万个回滚日志（undo log）。
带lock in share mode的SQL语句，是当前读，因此会直接读到1000001这个结果，所以速度很快；而select * from t where id = 1这个语句是一致性读，因此需要从1000001开始，一次执行undo log，执行了100万次以后，才将1这个结果返回。

小结
这一节列举了一个在简单的表上，执行“查一行”，可能会出现的被锁住和执行慢的例子。

小问题
下面的SQL语句：

begin;
select * from t where c=5 for update;
commit;

这个语句序列是怎么加锁的呢？加的锁又是什么时候释放呢？
解析：
这个语句会命中c=5所在的行，加的是行锁，等待commit时释放。

20. 幻读是什么，幻读有什么问题？

场景引入
使用一个小一点的表说明本节的问题，建表和初始化语句如下：

CREATE TABLE `t` (
`id` int(11) NOT NULL,
`c` int(11) DEFAULT NULL,
`d` int(11) DEFAULT NULL,
PRIMARY KEY (`id`),
KEY `c` (`c`)
) ENGINE=InnoDB;
insert into t values(0,0,0),(5,5,5),
(10,10,10),(15,15,15),(20,20,20),(25,25,25);

同上期的问题，下面的语句序列，如何加锁，何时释放？

begin;
select * from t where d = 5 for update;
commit

这个语句会命中d=5这一行，对应的主键id=5，因此在select语句执行完成后，id=5这一行会加一个写锁，而且由于两阶段锁协议，这个写锁会在执行commit语句的时候释放。
由于字段d上没有索引，因此这条查询语句会做全表扫描。那么，其他被扫描到的，但是不满足条件的5行记录上，会不会被加锁呢？
InnoDB的默认事务隔离级别是可重复读，本节没有特殊说明的部分都是设定在可重复读隔离级别下。

幻读是什么
现在，我们就来分析一下，如果只在id=5这一行加锁，而其他行的不加锁的话，会怎么样。
下面先来看一下这个场景：

图29. 假设只在id=5这一行加行锁

可以看到，session A里执行了三次查询，分别是Q1、Q2和Q3。它们的SQL语句相同，都是查询d=5的行，使用的是当前读，并且加上写锁。
其中，Q3读到id=1这一行的现象，被称为“幻读”。也就是说，幻读指的是一个事务在前后两次查询同一个范围的时候，后一次查询看到了前一次查询没有看到的行。
这里，对幻读做一个说明：

1. 在可重复读隔离级别下，普通的查询是快照读，是不会看到别的事务插入的数据的。因此，幻读在当前读下才会出现。
2. 上面session B的修改结果，被session A之后的select语句用当前读看到，不能称为幻读，幻读仅专指“新插入的行”。

幻读有什么问题
首先是语义上的。session A在T1时刻就声明了：我要把所有d=5的行锁住，不准别的事务进行读写操作。而实际上，这个语义被破坏了。
我们来看一个更明显的破坏场景：

图30. 假设只在id=5这一行加行锁—语义被破坏

session B的第二条语句update t set c = 5 where id = 0，语义是“我把id=0、d=5这一行的c值，改成了5”。
由于在T1时刻，session A还只是给id=5这一行加了行锁，并没有给id=0这行加上锁。因此，session B在T2时刻，是可以执行这两天update语句的。这样，就破坏了session A里Q1语句要锁住所有d=5的行的加锁声明。
session C也是一样的道理，对id=1这一行的修改，也是破坏了Q1的加锁声明。

其次，是数据一致性的问题。
我们知道，锁的设计是为了保证数据的一致性。而这个一致性，不止是数据库内部数据状态在此刻的一致性，还包括了数据和日志在逻辑上的一致性。
为了说明这个问题，给session A在T1时刻再加一个更新语句，即：update set d=100 where d=5。

图31. 假设只在id=5这一行加行锁-数据一致性问题

update的加锁语义和select…for update是一致的，所以这时候加上这条update语句也很合理。session A声明说“要给d=5的语句加上锁”，就是为了要更新数据，新加的这条update语句就是把它认为加上了锁的这一行的d值修改成了100。

现在，我们来分析一下图31执行完成以后，数据库里会是什么结果。

1. 经过T1时刻，id=5这一行变成了(5,5,100)，当然这个结果最终是在T6时刻正式提交的；
2. 经过T2时刻，id=0这一行变成(0,5,5)；
3. 经过T4时刻，表里面多了一行(1,5,5)；
4. 其他行跟这个执行序列无关，保持不变。

这样看，这些数据也没啥问题，但是我们再来看看这时候binlog的内容。

1. T2时刻，session B事务提交，写入了两条语句；
2. T4时刻，session C事务提交，写入了两条语句；
3. T6时刻，session A事务提交，写入了update t set d = 100 where d = 5这条语句。

统一放到一起的话，就是这样的：

update t set d = 5 where id = 0; /*(0,0,5)*/
update t set c = 5 where id = 0; /*(0,5,5)*/
insert into t value(1,1,5); /*(1,1,5)*/
update t set c = 5 where id = 1; /*(1,5,5)*/
update t set d = 100 where d = 5; /*所有d=5的行，d改成100*/

这个序列，不论是拿到备库去执行，还是以后来克隆一个库，这三行的结果，都变成了(0,5,100)、(1,5,100)和(5,5,100)。
也就是说，id=0和id=1这两行，发生了数据不一致。这个问题很严重，是不行的。

通过分析问题，这是我们假设“select * from t where d = 5 for update这条语句只给d=5这一行，也就是id=5的这一行加锁”导致的。
所以我们认为，上面的设定不合理，要改。
我们把扫描过程中碰到的行，也都加上写锁，再来看看执行效果。

图32. 假设扫描到的行都被加上了行锁

由于session A把所有的行都加上了写锁，所以session B在执行第一个update语句的时候被锁住了。需要等待T6时刻session A提交以后，session B才能继续执行。

这样对于id=0这一行，在数据库里的最终结果还是(0,5,5)。在binlog里面，执行序列是这样的：

insert into t values(1,1,5); /*(1,1,5)*/
update t set c = 5 where id = 1; /*(1,5,5)*/
update t set d = 100 where d = 5; /*所有d=5的行，d改成100*/
update t set d = 5 where id = 0; /*(0,0,5)*/
update t set c = 5 where id = 0; /*(0,5,5)*/

可以看到，按照日志顺序执行，id=0这一行的最终结果也是(0,5,5)。所以，id=0这一行的问题解决了。
但是，id=1这一行，在数据库里面的结果是(1,5,5)，而根据binlog的执行结果是(1,5,100)，也就是说幻读的问题还是没有解决。

为什么我们把所有的记录都上了锁，还是无法阻止id=1这一行的插入和更新呢？
原因很简单，在T3时刻，我们给所有行加锁的时候，id=1这一行还不存在，不存在也就加不上锁。
也就是说，即使把所有的记录都加上锁，还是阻止不了新插入的记录。

如何解决幻读
产生幻读的原因是，行锁只能锁住行，但是新插入记录这个动作，要更新的是记录之间的“间隙”。因此，为了解决幻读问题，InnoDB只好引入新的锁，也就是间隙所（Gap Lock）。
顾名思义，间隙锁，锁的就是两个值之间的空隙。比如这一节开头的表t，初始化了6个记录，这就产生了7个间隙。

图33. 表t主键索引上的行锁和间隙锁

这样，当你执行select * from t where d = 5 for update的时候，就不止是给数据库中已有的6个记录加上了行锁，还同时加了7个间隙锁。这样就确保了无法再插入新的记录。
也就是说这时候，在一行行扫描的过程中，不仅将给行加上了行锁，还给两边的空隙，也加上了间隙锁。

因此，数据行是可以加上锁的实体，数据行之间的间隙也是可以加上锁的实体。
比如行锁，分为读锁和写锁：

也就是说，跟行锁有冲突关系的是“另外一个行锁”。
但是间隙锁不一样，跟间隙锁存在冲突关系的，是“往这个间隙中插入一个记录”这个操作。间隙锁之间都不存在冲突关系。

举个例子：

图34. 间隙锁之间不互斥

这里session B并不会被堵住。因为表t里没有c=7这个记录，因此session A加的是间隙锁(5, 10)。而session B也是在这个间隙加的间隙锁。它们有共同的目标，即：保护这个间隙，不允许插入值。但，它们之间是不冲突的。

间隙锁和行锁合称为next-key lock，每个next-key lock都是前开后闭区间。也就是说，我们的表t初始化以后，如果用select * from t for update要把整个表所有记录锁起来，就形成了7个next-key lock，分别是(-∞,0]、(0,5]、(5,10]、(10,15]、(15,20]、(20, 25]、(25, +supremum]。

本节没有特殊说明，把间隙锁记为开区间，把next-key lock记为前开后闭区间。

因为+∞是开区间。实现上，InnoDB给每个索引加了一个不存在的最大值supremum，这样才符合“前开后闭区间”。
间隙锁和next-key lock的引入，帮我们解决了幻读问题，但同时也带来了一些困扰。

业务逻辑是这样的：任意锁住一行，如果这一行不存在的话就插入，如果存在这一行就更新它的数据，代码如下：

begin;
select * from where id = N for update;
-- 如果这行不存在
insert into t values(N,N,N);
-- 如果这行存在
update t set d = N where id = N;
commit;

可能你会说，这个不是insert … on duplicate key update就能解决吗？
但其实在有多个唯一键的时候，这个方法是不能满足这个需求的。

这个逻辑一旦有并发，就会碰到死锁。
这里使用两个session来模拟并发，并假设N=9。

图35. 间隙锁导致的死锁

按照语句顺序来分析一下：

1. session A执行select … for update语句，由于id=9这一行并不存在，因此会加上间隙锁(5, 10)；
2. session B执行select … for update语句，同样会加上间隙锁(5, 10)，间隙锁之间不会冲突，因此这个语句可以执行成功；
3. session B试图插入一行(9,9,9)，被session A的间隙锁挡住了，只好进入等待；
4. session A试图插入一行(9,9,9)，被session B的间隙锁挡住了。

至此，两个session进入互相等待状态，形成死锁。当然，InnoDB的死锁检测马上就发现了这对死锁关系，让session A的insert语句报错返回了。

因此，间隙锁的引入，可能会导致同样的语句锁住更大的范围，这其实是影响了并发度的。

小结
这一节主要学习了幻读问题和间隙锁的解决方式。
行锁确实比较直观，判断规则也相对简单，间隙锁的引入会影响系统的并发度，也增加了锁分析的复杂度，但也有章可循。

小问题

图36. 事务进入锁等待状态

这里的session B和session C的insert语句都会进入锁等待状态，为什么？
解析：

1. 由于是order by c desc，第一个要定位的是索引c上最右边的c=20行，加上next-key lock(15, 20]和next-key lock(20, 25]，由于25不满足等值条件，退化为间隙锁(20, 25)，所以加锁为next-key lock(15, 20]和间隙锁(20, 25)。
2. 在索引c上向左遍历，扫描到c=15，继续扫描到第一个不满足条件的行c=10，所以next-key lock会加到(5, 10]和(10, 15]。
3. 在扫描过程中，c=20、c=15和c=10这三行都存在值，由于是select *，所以会在主键id上加三个行锁。

因此，session A的select语句加锁范围是：

1. 索引c上(5, 25)；
2. 主键索引上id=10、id=15和id=20三个行锁。