随机排序

随机选择三个记录。

单词表

mysql> 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 100)), char(97+(i % 100 div 10)), char(97+(i % 10))));
    set i=i+1;
  end while;
end;;
delimiter ;

call idata();

内存临时表-小Memory\大InnoDB

随机排序取前3个。

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

id	select_type	table	partitions	type	possible_keys	key	key_len	ref	rows	filtered	Extra
1	SIMPLE	words	NULL	ALL	NULL	NULL	NULL	NULL	9980	100.00	Using temporary;Using filesort

• Extra字段显示Using temporary，表示的是需要使用临时表；Using filesort，表示的是需要执行排序操作。（需要临时表，并且需要在临时表上排序）

对于InnoDB表，执行全字段排序会减少磁盘访问。
对于内存表，回表过程只是简单的根据数据行的位置，直接访问内存得到数据，根本不会导致多访问磁盘。用于排序的行越小越好，优先选择rowid排序。
针对临时表，小的用memory引擎，大的用innodb引擎。

执行流程：

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。

---

MySQL的表定位“一行数据”的方法

如果创建的表没有主键，或者把一个表的主键删掉了，那么InnoDB会自己生成一个长度为6字节的rowid来作为主键(但是这个主键对Server层是透明的，优化器用不上)。每个引擎用主键来唯一标识数据行的信息。

• 有主键的InnoDB表，rowid就是主键ID；
• 没有主键的InnoDB表，rowid就是由系统生成的；
• MEMORY引擎不是索引组织表。可以认为它就是一个数组，rowid是数组的下标。

order by rand()使用了内存临时表，内存临时表排序的时候使用了rowid排序方法。

磁盘临时表-InnoDB

tmp_table_size这个配置限制了内存临时表的大小，默认值是16M。如果临时表大小超过了tmp_table_size，那么内存临时表就会转成磁盘临时表。

磁盘临时表使用的引擎默认是InnoDB，由参数internal_tmp_disk_storage_engine控制。

当使用磁盘临时表的时候，对应的就是一个没有显式索引的InnoDB表的排序过程。

磁盘临时表

-- 单位字节(Byte)。1Byte=8bit
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
```  

``` json  
"filesort_priority_queue_optimization":{
    "limit":3,
    "rows_estimate":1213,
    "row_size":14,
    "memory_available":32768,
    "chosen":true
},
"filesort_execution":[],
"filesort_summary":{
    "rows":4,
    "examined_rows":10000,
    "number_of_tmp_files":0,
    "sort_buffer_size":88,
    "sort_mode":"<sort_key,rowid>"
}

• 将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，表示不使用临时文件。

MySQL5.6引入优先队列排序算法。没有使用临时文件算法—归并排序算法(所有数据有序，浪费计算量)。

执行流程：

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

流程结束，堆中就是10000行中R值最小的三行，依次取出rowid，到临时表中拿到word字段。

OPTIMIZER_TRACE结果中，filesort_priority_queue_optimization.chosen=true；表示使用优先级队列排序算法，不需要临时文件，对应的filesort_summary.number_of_tmp_files=0。

limit参数，影响排序算法，最小堆的维护代价小于sort_buffer_size时采用优先队列排序。

随机排序方法

无论使用哪种类型的临时表，order by rand()都会让计算过程非常复杂，需要大量的的扫描行数，排序过程的资源消耗也很大。

随机算法1

1. 取表的主键ID的最大值M和最小值N；
2. 用随机函数生成一个最大值到最小值之间的数X=(M-N)*rand()+N;
3. 取不小于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行。

随机算法2

1. 取整个表的行数，记为C。
2. 取得Y=floor(C*rand())。floor函数取整数部分。
3. 用limitY,1取得一行。

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的概率不均匀问题。(算法1要求ID中间没有空洞，否则选择不同行的概率不一样)

MySQL处理limit Y,1的做法是按顺序一个一个的读出来，丢掉前Y个，然后把下一个记录作为返回结果，这一步需要扫描Y+1行。加上第一步扫描的C行，总共需要扫描C+Y+1行，执行代价比算法1高，比直接order by rand()低。

limit获取数据的时候是根据主键排序获取的，主键索引天然有序，比order by rand()方法组成临时表R字段排序再获取rowid代价小。

随机算法3

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

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；

总的扫描行数C+(Y1+1)+(Y2+1)+(Y3+1)。

随机算法4

取Y1、Y2、Y3里面最大的一个数，记为M，最小的一个数记为N。

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

总的扫描行数C+M+1。