MySQL SQL抖动、排序、随机显示消息

一条SQL语句，正常执行的时候特别快，但是有时也不知道怎么回事，它就会变得特别慢，并且这样的场景很难复现，它不只随机，而且持续时间还很短。看上去，这就像是数据库“抖”了一下。

SQL语句为什么变“慢”了

InnoDB在处理更i性能语句的时候，只做了写redo日志的磁盘操作，在更新内存写完redo log后，就返回给客户端，本次更新成功。把内存里的数据写入磁盘的过程叫flush；当内存数据页跟磁盘数据页内容不一致的时候，我们称这个内存页为“脏页”。内存数据写入到磁盘后，内存和磁盘上的数据页的内容就一致了，称为“干净页，不论是脏页还是干净页，都在内存中；不难想象，平时执行很快的更新操作，其实就是在写内存和日志，而MySQL偶尔“抖”一下的那个瞬间，可能就是在刷脏页（flush）。

那么，什么情况会引发数据库的flush过程呢？
场景1：

InnoDB的redo log 写满了，这时候系统会停止所有更新操作，把checkpoint往前推进，redo log留出空间可以继续写

checkpoint可不是随便往前修改一下位置就可以的。比如图中，把checkpoint位置从CP推进到CP’,就需要将两个点之间的日志（浅绿色部分），对应的所有脏页都flush到磁盘上。之后，图中从write pos到CP’之间就是可以再写入的redo log的区域。

场景2：

系统内存不足，需要新的内存页，而内存不够用的时候，就要淘汰一些数据页，空出的内存给别的数据页使用。如果淘汰的是“脏页”，就要先将脏页写回磁盘；
思考：这个时候就不能直接把内存淘汰掉，下次需要请求的时候，从磁盘读入数据页，然后拿redo log出来应用不就行了？这里其实是从性能考虑的。如果刷脏页一定会写盘，就保证了每个数据页有两种状态：
- 一种是内存里存在，内存里就肯定是正确的结果，直接返回；
- 另一种是内存里没有数据，就可以肯定数据文件上是正确的结果，读入内存后返回。这样的效率最高。

场景3：

MySQL认为系统“空闲”的时候，即便系统很忙，但是redo log 快满的时候，也要见缝插针地找时间，只要有机会就刷一点“脏页”

场景4:
MySQL正常关闭的情况。这时候，MySQL会把内存的脏页都flush到磁盘上，这样下次MySQL启动的时候，就可以直接从磁盘上读数据，启动速度会很快。

4种场景对性能的影响，其中，第三种情况是属于MySQL空闲时的操作，这时系统没什么压力，而第四种场景是数据库本来就要关闭了；第一种是“redo log写满了，要flush脏页”，这种情况是InnoDB要尽量避免的。因为出现这种情况的时候，整个系统就不能再接受更新了，所有的更新都必须堵住。如果你从监控上看，这时候更新数会跌为0。
第二种是“内存不够用了，要先将脏页写到磁盘”，这种情况其实是常态。InnoDB用缓冲池（buffer pool）管理内存，缓冲池中的内存页有三种状态：

第一种是，还没有使用的；
第二种是，使用了并且是干净页；
第三种是，使用了并且是脏页。

InnoDB的策略是尽量使用内存，因此对于一个长时间运行的库来说，未被使用的页面很少。

而当要读入的数据页没有在内存的时候，就必须到缓冲池中申请一个数据页。这时候只能把最久不使用的数据页从内存中淘汰掉：如果要淘汰的是一个干净页，就直接释放出来复用；但如果是脏页呢，就必须将脏页先刷到磁盘，变成干净页后才能复用。

所以，刷脏页虽然是常态，但是出现以下这两种情况，都是会明显影响性能的：

一个查询要淘汰的脏页个数太多，会导致查询的响应时间明显变长；

日志写满，更新全部堵住，写性能跌为0，这种情况对敏感业务来说，是不能接受的。

所以，InnoDB需要有控制脏页比例的机制，来尽量避免上面的这两种情况。

InnoDB刷脏页的控制策略

首先，你要正确地告诉InnoDB所在主机的IO能力，这样InnoDB才能知道需要全力刷脏页的时候，可以刷多快。

这就要用到innodb_io_capacity这个参数了，它会告诉InnoDB你的磁盘能力。这个值我建议你设置成磁盘的IOPS。磁盘的IOPS可以通过fio这个工具来测试，下面的语句是我用来测试磁盘随机读写的命令：

 fio -filename=$filename -direct=1 -iodepth 1 -thread -rw=randrw -ioengine=psync -bs=16k -size=500M -numjobs=10 -runtime=10 -group_reporting -name=mytest

其实，因为没能正确地设置innodb_io_capacity参数，而导致的性能问题也比比皆是。之前，就曾有其他公司的开发负责人找我看一个库的性能问题，说MySQL的写入速度很慢，TPS很低，但是数据库主机的IO压力并不大。经过一番排查，发现罪魁祸首就是这个参数的设置出了问题。

他的主机磁盘用的是SSD，但是innodb_io_capacity的值设置的是300。于是，InnoDB认为这个系统的能力就这么差，所以刷脏页刷得特别慢，甚至比脏页生成的速度还慢，这样就造成了脏页累积，影响了查询和更新性能。

虽然我们现在已经定义了“全力刷脏页”的行为，但平时总不能一直是全力刷吧？毕竟磁盘能力不能只用来刷脏页，还需要服务用户请求。所以接下来，我们就一起看看InnoDB怎么控制引擎按照“全力”的百分比来刷脏页。
如果刷太慢，会出现什么情况？首先是内存脏页太多，其次是redo log写满
所以，InnoDB的刷盘速度就是要参考这两个因素：一个是脏页比例，一个是redo log写盘速度。
InnoDB会根据这两个因素先单独算出两个数字。

参数innodb_max_dirty_pages_pct是脏页比例上限，默认值是75%。InnoDB会根据当前的脏页比例（假设为M），算出一个范围在0到100之间的数字，计算这个数字的伪代码类似这样：

F1(M)
{
  if M>=innodb_max_dirty_pages_pct then
      return 100;
  return 100*M/innodb_max_dirty_pages_pct;
}

InnoDB每次写入的日志都有一个序号，当前写入的序号跟checkpoint对应的序号之间的差值，我们假设为N。InnoDB会根据这个N算出一个范围在0到100之间的数字，这个计算公式可以记为F2(N)。F2(N)算法比较复杂，你只要知道N越大，算出来的值越大就好了。

然后，根据上述算得的F1(M)和F2(N)两个值，取其中较大的值记为R，之后引擎就可以按照innodb_io_capacity定义的能力乘以R%来控制刷脏页的速度。

InnoDB会在后台刷脏页，而刷脏页的过程是要将内存页写入磁盘。所以，无论是你的查询语句在需要内存的时候可能要求淘汰一个脏页，还是由于刷脏页的逻辑会占用IO资源并可能影响到了你的更新语句，都可能是造成你从业务端感知到MySQL“抖”了一下的原因。

要尽量避免这种情况，你就要合理地设置innodb_io_capacity的值，并且平时要多关注脏页比例，不要让它经常接近75%。
其中，脏页比例是通过Innodb_buffer_pool_pages_dirty/Innodb_buffer_pool_pages_total得到的，具体的命令参考下面的代码：

mysql> select VARIABLE_VALUE into @a from global_status where VARIABLE_NAME = 'Innodb_buffer_pool_pages_dirty';
select VARIABLE_VALUE into @b from global_status where VARIABLE_NAME = 'Innodb_buffer_pool_pages_total';
select @a/@b;

一旦一个查询请求需要在执行过程中先flush掉一个脏页时，这个查询就可能要比平时慢了。而MySQL中的一个机制，可能让你的查询会更慢：在准备刷一个脏页的时候，如果这个数据页旁边的数据页刚好是脏页，就会把这个“邻居”也带着一起刷掉；而且这个把“邻居”拖下水的逻辑还可以继续蔓延，也就是对于每个邻居数据页，如果跟它相邻的数据页也还是脏页的话，也会被放到一起刷。

在InnoDB中，innodb_flush_neighbors 参数就是用来控制这个行为的，值为1的时候会有上述的“连坐”机制，值为0时表示不找邻居，自己刷自己的。

找“邻居”这个优化在机械硬盘时代是很有意义的，可以减少很多随机IO。机械硬盘的随机IOPS一般只有几百，相同的逻辑操作减少随机IO就意味着系统性能的大幅度提升。

而如果使用的是SSD这类IOPS比较高的设备的话，我就建议你把innodb_flush_neighbors的值设置成0。因为这时候IOPS往往不是瓶颈，而“只刷自己”，就能更快地执行完必要的刷脏页操作，减少SQL语句响应时间。

在MySQL 8.0中，innodb_flush_neighbors参数的默认值已经是0了。

小结：
WAL技术，数据库将随机写转换成了顺序写，大大提升了数据库的性能。由此也带来了内存脏页的问题
脏页会被后台线程自动flush，也会由于数据页淘汰而触发flush，而刷脏页的过程由于会占用资源，可能会让你的更新和查询语句的响应时间长一些
脏页控制策略：innodb_io_capacity 默认200，可以改为iops(这里可以视为是硬盘每秒的读写次数) ；innodb_flush_neighbors MySQL8.0是默认是0，建议设置为0，防止“连坐”效应；

Innodb 通过对比每个数据页头部的LSN（8字节，每次修改都会变大）与checkpoint的LSN，比checkpoint的LSN小的一定是干净页；

Order By 排序原理

全字段排序
- 为避免全表扫描，我们需要在字段加上索引，用explain分析的时候 Extra这一列 Using filesort,表示的就是需要排序，MySQL会给每个线程分配一块内存用于排序称为sot_buffer
- 执行流程：select city,name,age from t where city='杭州' order by name limit 1000 ; 有普通索引city。
- 初始化sort_buffer，确定放入name、city、age这三个字段；
- 从索引city找到第一个满足city='杭州’条件的主键id。
- 到主键id索引取出整行，取name、city、age三个字段的值，存入sort_buffer中。
- 从索引city取下一个记录的主键id；
- 重复步骤3、4直到city的值不满足查询条件为止；
- 对sort_buffer中的数据按照字段name做快速排序；
- 按照排序结果取前1000行返回给客户端。
  我们暂且把这个排序过程，称为全字段排序；“按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; //4000

结果：filesort_summary:{
"rows":4000,
"examined_rows"4000,
"number_of_tmp_files":12,
"sort_buffer_size":32664,
"sort_mode":"<sort_key,packded_additional_fields>"
}

这个方法是通过查看 OPTIMIZER_TRACE 的结果来确认的，你可以从 number_of_tmp_files中看到是否使用了临时文。，件number_of_tmp_files表示的是，排序过程中使用的临时文件数。你一定奇怪，为什么需要12个文件？内存放不下时，就需要使用外部排序，外部排序一般使用归并排序算法。可以这么简单理解，MySQL将需要排序的数据分成12份，每一份单独排序后存在这些临时文件中。然后把这12个有序文件再合并成一个有序的大文件。如果sort_buffer_size超过了需要排序的数据量的大小，number_of_tmp_files就是0，表示排序可以直接在内存中完成，否则就需要放在临时文件中排序。sort_buffer_size越小，需要分成的份数越多，number_of_tmp_files的值就越大。我们的示例表中有4000条满足city='杭州’的记录，所以你可以看到 examined_rows=4000，表示参与排序的行数是4000行。sort_mode 里面的packed_additional_fields的意思是，排序过程对字符串做了“紧凑”处理。即使name字段的定义是varchar(16)，在排序过程中还是要按照实际长度来分配空间的。同时，最后一个查询语句select @b-@a 的返回结果是4000，表示整个执行过程只扫描了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字段的值，不能直接返回了，整个执行流程就变成如下所示的样子：

初始化sort_buffer，确定放入两个字段，即name和id；
从索引city找到第一个满足city='杭州’条件的主键id；
到主键id索引取出整行，取name、id这两个字段，存入sort_buffer中；
从索引city取下一个记录的主键id；
重复步骤3、4直到不满足city='杭州’条件为止；
对sort_buffer中的数据按照字段name进行排序；
遍历排序结果，取前1000行，并按照id的值回到原表中取出city、name和age三个字段返回给客户端。

跟全字段排序排序相比，rowid排序多访问了一次表t的主键索引，就是步骤7，需要说明的是，最后的“结果集”是一个逻辑概念，实际上MySQL服务端从排序后的sort_buffer中依次取出id，然后到原表查到city、name和age这三个字段的结果，不需要在服务端再耗费内存存储结果，是直接返回给客户端的。
根据这个说明过程和图示，你可以想一下，这个时候执行select @b-@a，结果会是多少呢？

现在，我们就来看看结果有什么不同。
filesort_summary:{
"rows":4000,
"examined_rows"4000,
"number_of_tmp_files":10,
"sort_buffer_size":32728,
"sort_mode":"<sort_key,rowid>"
}
首先，examined_rows的值还是4000，表示用于排序的数据是4000行。但是select @b-@a这个语句的值变成5000了。因为这时候除了排序过程外，在排序完成后，还要根据id去原表取值。由于语句是limit 1000，因此会多读1000行。
从OPTIMIZER_TRACE的结果中，你还能看到另外两个信息也变了。

sort_mode变成了<sort_key, rowid>，表示参与排序的只有name和id这两个字段。
number_of_tmp_files变成10了，是因为这时候参与排序的行数虽然仍然是4000行，但是每一行都变小了，因此需要排序的总数据量就变小了，需要的临时文件也相应地变少了。

全字段排序 VS rowid排序

如果MySQL实在是担心排序内存太小，会影响排序效率，才会采用rowid排序算法，这样排序过程中一次可以排序更多行，但是需要再回到原表去取数据。
如果MySQL认为内存足够大，会优先选择全字段排序，把需要的字段都放到sort_buffer中，这样排序后就会直接从内存里面返回查询结果了，不用再回到原表去取数据
MySQL的一个设计思想：如果内存够，就要多利用内存，尽量减少磁盘访问。
对于InnoDB表来说，rowid排序会要求回表多造成磁盘读，因此不会被优先选择。

其实，并不是所有的order by语句，都需要排序操作的。从上面分析的执行过程，我们可以看到，MySQL之所以需要生成临时表，并且在临时表上做排序操作，其原因是原来的数据都是无序的。如果能够保证从city这个索引上取出来的行，天然就是按照name递增排序的话，是不是就可以不用再排序了呢？
所以，我们可以在这个市民表上创建一个city和name的联合索引，对应的SQL语句是：

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

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

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

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

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

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

重复步骤2、3，直到查到第1000条记录，或者是不满足city='杭州’条件时循环结束。
我们用explain的结果来印证一下，这个查询过程不需要临时表，也不需要排序。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,age)找到第一个满足city='杭州’条件的记录，取出其中的city、name和age这三个字段的值，作为结果集的一部分直接返回；

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

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

然后，我们再来看看explain的结果。Extra字段里面多了“Using index”，表示的就是使用了覆盖索引，性能上会快很多。

当然，这里并不是说要为了每个查询能用上覆盖索引，就要把语句中涉及的字段都建上联合索引，毕竟索引还是有维护代价的。这是一个需要权衡的决定。

小结:

order by 排序算法有两种
- packed_additional_fields, 全字段排序，排序过程对字符串做了“紧凑”处理,按照实际长度来分配空间的
  - 缺点：数据字段多，内存里能够同时放下的行数很少，要分成很多个临时文件，排序性能差
  - 优点：减少磁盘访问量
- rowid，当单行的长度超过max_length_for_sort_data值就用rowid算法
  - 缺点：排序之后，再次根据id读表，
优化方案：覆盖索引-覆盖索引是指，索引上的信息足够满足查询请求，不需要再回到主键索引上去取数据。

随机显示

学习App首页有一个随机显示单词的功能，也就是根据每个用户的级别有一个单词表，然后这个用户每次访问首页的时候，都会随机滚动显示三个单词，如果是你这么设计？

表结构
 CREATE TABLE `words` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `word` varchar(64) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

方法：内存临时表、磁盘临时表

内存临时表：
- select word from words order by rand() limit 3;
- 用explain 去分析，Extra字段里有Using temporary；Using filesort
  Extra字段显示Using temporary，表示的是需要使用临时表；Using filesort，表示的是需要执行排序操作。
  因此这个Extra的意思就是，需要临时表，并且需要在临时表上排序。对于内存表，回表过程只是简单地根据数据行的位置，直接访问内存得到数据，根本不会导致多访问磁盘。优化器没有了这一层顾虑，那么它会优先考虑的，就是用于排序的行越少越好了，所以，MySQL这时就会选择rowid排序
- sql执行流程
  - 创建一个临时表。这个临时表使用的是memory引擎，表里有两个字段，第一个字段是double类型，为了后面描述方便，记为字段R，第二个字段是varchar(64)类型，记为字段W。并且，这个表没有建索引。
  - 从words表中，按主键顺序取出所有的word值。对于每一个word值，调用rand()函数生成一个大于0小于1的随机小数，并把这个随机小数和word分别存入临时表的R和W字段中，到此，扫描行数是10000。
  - 现在临时表有10000行数据了，接下来你要在这个没有索引的内存临时表上，按照字段R排序。
  - 初始化 sort_buffer。sort_buffer中有两个字段，一个是double类型，另一个是整型。
  - 从内存临时表中一行一行地取出R值和位置信息（我后面会和你解释这里为什么是“位置信息”），分别存入sort_buffer中的两个字段里。这个过程要对内存临时表做全表扫描，此时扫描行数增加10000，变成了20000。
  - 在sort_buffer中根据R的值进行排序。注意，这个过程没有涉及到表操作，所以不会增加扫描行数。
  - 排序完成后，取出前三个结果的位置信息，依次到内存临时表中取出word值，返回给客户端。这个过程中，访问了表的三行数据，总扫描行数变成了20003。
    接下来，我们通过慢查询日志（slow log）来验证一下我们分析得到的扫描行数是否正确。
```
# 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;
```

为了弄清楚位置信息是什么意思，我们就要回到一个基本概念：MySQL的表是用什么方法来定位“一行数据”的。
如果你创建的表没有主键，或者把一个表的主键删掉了，那么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_data 设置成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

然后，我们来看一下这次OPTIMIZER_TRACE的结果。

因为将max_length_for_sort_data设置成16，小于word字段的长度定义，所以我们看到sort_mode里面显示的是rowid排序，这个是符合预期的，参与排序的是随机值R字段和rowid字段组成的行。

这时候你可能心算了一下，发现不对。R字段存放的随机值就8个字节，rowid是6个字节（至于为什么是6字节，就留给你课后思考吧），数据总行数是10000，这样算出来就有140000字节，超过了sort_buffer_size 定义的 32768字节了。但是，number_of_tmp_files的值居然是0，难道不需要用临时文件吗？

这个SQL语句的排序确实没有用到临时文件，采用是MySQL 5.6版本引入的一个新的排序算法，即：优先队列排序算法。接下来，我们就看看为什么没有使用临时文件的算法，也就是归并排序算法，而是采用了优先队列排序算法。

其实，我们现在的SQL语句，只需要取R值最小的3个rowid。但是，如果使用归并排序算法的话，虽然最终也能得到前3个值，但是这个算法结束后，已经将10000行数据都排好序了。

也就是说，后面的9997行也是有序的了。但，我们的查询并不需要这些数据是有序的。所以，想一下就明白了，这浪费了非常多的计算量。

而优先队列算法，就可以精确地只得到三个最小值，执行流程如下：

对于这10000个准备排序的(R,rowid)，先取前三行，构造成一个堆；
（对数据结构印象模糊的同学，可以先设想成这是一个由三个元素组成的数组）

取下一个行(R’,rowid’)，跟当前堆里面最大的R比较，如果R’小于R，把这个(R,rowid)从堆中去掉，换成(R’,rowid’)；

重复第2步，直到第10000个(R’,rowid’)完成比较。

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

取得这个表的主键id的最大值M和最小值N;
用随机函数生成一个最大值到最小值之间的数 X = (M-N)*rand() + N;

取不小于X的第一个ID的行。

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中间可能有空洞，因此选择不同行的概率不一样，不是真正的随机。
比如你有4个id，分别是1、2、4、5，如果按照上面的方法，那么取到 id=4的这一行的概率是取得其他行概率的两倍。

如果这四行的id分别是1、2、40000、40001呢？这个算法基本就能当bug来看待了。

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

取得整个表的行数，并记为C。

取得 Y = floor(C * rand())。 floor函数在这里的作用，就是取整数部分。

再用limit Y,1 取得一行。

我们把这个算法，称为随机算法2。下面这段代码，就是上面流程的执行语句的序列。

mysql> 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;

现在，我们再看看，如果我们按照随机算法2的思路，要随机取3个word值呢？你可以这么做：

取得整个表的行数，记为C；

根据相同的随机方法得到Y1、Y2、Y3；

再执行三个limit Y, 1语句得到三行数据。

我们把这个算法，称作随机算法3。下面这段代码，就是上面流程的执行语句的序列。

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

进一步优化：
取Y1、Y2和Y3里面最大的一个数，记为M，最小的一个数记为N，然后执行下面这条SQL语句：

mysql> select * from t limit N, M-N+1;
再加上取整个表总行数的C行，这个方案的扫描行数总共只需要C+M+1行。

当然也可以先取回id值，在应用中确定了三个id值以后，再执行三次where id=X的语句也是可以的