英语学习 App性能问题。另一种排序需求。首页随机显示三个单词（根据用户级别）。单词表变大，选单词越来越慢
简化：去掉用户级别对应单词表，随机选。
insert into words(word) values(concat(char(97+(i div 1000)), char(97+(i % 1000 div
100)), char(97+(i % 100 div 10)), char(97+(i % 10))));
插入了 10000 行记录。
一、内存临时表
select word from words order by rand() limit 3;
随机排序取前 3 个。执行流程复杂。
Using temporary需临时表；Using filesort需要执行排序。Extra ：在临时表上排序
对于 InnoDB 表，全字段排序会减少磁盘访问，优先。
内存表，回表过程只是简单地根据数据行的位置，直接访问内存得到数据，根本不会导致多访问磁盘。优化器没有这顾虑，、排序行越小越好，选择 rowid 排序。执行流程：
1. 创建临时表。memory 引擎，字段R（double），W varchar(64) 。没有索引。
2. 按主键顺序取出所有word。调用 rand() 生成0 到1 随机数，存入临时表 R 和 W 字段中，扫描行数10000。
3. 没有索引内存临时表上，按 R 排序。
4. 初始化 sort_buffer
5. 一行行地取出 R 值和位置信息，存入 sort_buffer 。对内存临时表做全表扫描，扫描行数 10000变20000。
6. sort_buffer 中R 排序。没有涉及到表，不会增加扫描行数。
7. 排序完成后，取前三位置信息，到临时表中取出 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;
pos位置信息：定位“一行数据”。rowid：每个引擎用来唯一标识数据行的信息。
有主键rowid 就是主键ID；没有rowid 系统生成（6 字节）；
MEMORY 引擎不是索引组织表。 rowid 其实就是数组的下标。
order by rand()用内存临时表（rowid 排序）。
二、磁盘临时表
tmp_table_size默认16M，限制内存临时表大小，超过tmp_table_size，内存临时表转成磁盘临时表（默认InnoDB，internal_tmp_disk_storage_engine控制）。
磁盘临时表时，没显式索引InnoDB 排序。为了复现
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
max_length_for_sort_data 16，小于 word 字段长度定义 rowid 排序，符合预期，参与排序的是随机值 R 字段和 rowid 字段组成的行。
R 8 字节，rowid 6 字节，总行数 10000，算出140000 字节，sort_buffer_size的 32768 字节了。number_of_tmp_files 0，没用临时文件，filesort_priority_queue_optimization chosen=true，表示优先队列排序
取 R 值最小3 个 rowid。归并排10000 行数据。浪费计算量。优先队列算法：
1. 10000 (R,rowid)，取前三行，构造堆；
2. 取下个行 (R’,rowid’)，跟当前堆最大的 R 比较，R’小于 R， (R,rowid) 换成 (R’,rowid’)；
3. 重复第 2 步，10000 个。
如果limit 1000，超过sort_buffer_size 大小，用归并排序算法。
不论哪种临时表，order by rand() 计算复杂，要大量扫描行数，资源消耗大。
三、随机排序方法
随机算法 1，随机选择 1 个 word 值:
1. 取得主键 id 的最大值 M 和最小值N;
2. 随机函数生成(最大到最小值之间数)X =(M-N)*rand() + N
3. 取不小于 X 第一个 ID 行。
mysql> 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 中可能有空洞，不是真正随机
id是 1、2、4、5，取到 id=4 概率是其他两倍。
id 是 1、2、40000、40001，基本 bug
随机算法 2，严格随机结果流程:
1. 取整表行数，记为 C。
2. 取得 Y = floor(C * rand())。 floor 取整数部分。
3. limit Y,1 取一行。
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;
解决1概率不均匀问题，limit 后参数不能直接跟变量，用prepare+execute 方法。把拼接 SQL 写程序中，更简单。
处理 limit Y,1丢掉前 Y 个，扫描 Y+1 行。加上 C 行，总C+Y+1 行，代价高。
跟直接 order by rand() 比代价小。
C=10000，随机大Y 值，跟 20000 差不多，接近 order by rand()？
随机算法 3，2 思路，随机取 3 个：
1. 整表行，记为 C；
2. 随机方法得 Y1、Y2、Y3；
3. 执行三个 limit Y, 1 得三行
小结
借随机排序需求，MySQL 对临时表排序执行过程。
直接用 order by rand()，需Using temporary 和 Using filesort，查询代价大。设计时避开。
今天例子，不仅数据库内部解决问题，还配合拼接 SQL 语句。实际规范用法：业务逻辑写业务代码中，数据库只“读写”。
思考题
随机算法 3 ，总扫描行数：C+(Y1+1)+(Y2+1)+(Y3+1)，怎么减少扫描行？
（1）Y1、Y2 和 Y3 最大为M，最小为 N，执行：mysql> select * from t limit N, M-N+1;
总 C+M+1 行。
（2）先取 id 值，确定以后，再执行三次 where id=X
（3）装jdk或redis缓存：量不多，随机访问数组好。单词10字节，10*10000，1M装下。
（4）表里存无空洞自增值，用数据库，方案1好，单词库不变，把空洞处理调。原在A表，新建B表 ，insert into B(word) select word from A. B的id自增，生成连续主键。量大禁用，RR隔离级别会锁A表
（5）rowid 方法：增加主键字段,记录每行rowid，连续一万随机，回表查行记录
（6）id 迭代往下，主键索引有序性：按Y排序，第一取完，拿到对应id，where id大于xxx，limit y2-y1，1
