《MySQL实战45讲》——学习笔记17 “随机排序、内存临时表“

拼搏现实的明天。 2023-09-24 14:13 40阅读 0赞

本篇主要通过在一个排序场景下，使用到临时表的业务场景示例，介绍在MYSQL排序时用到的内存临时表/磁盘临时表的相关知识；还包括一个特殊的场景，即参与排序的数据超过了sort\_buffer\_size 但MySQL却未使用临时文件（归并排序算法）的情况，这是因为MySQL5.6版本引入了一个新的排序算法，即：优先队列排序算法（堆排序）；

对于本文引用的业务场景例子——随机排序后取TopN，实际上不适合使用MySQL来解决业务问题，因为会消耗MYSQL宝贵的IO和CPU资源；业界一般是配合缓存，放在服务器内存（JVM）中计算；**本文仅仅是刚好用这个例子来方便介绍相关知识点**；

#### 业务场景示例 ####

场景说明：某个英语学习App首页有一个随机显示单词的功能，用户每次访问首页的时候，都会随机滚动显示三个单词；为了便于理解，对这个例子进行了简化：**从一个单词表中随机选出三个单词**；

这个表的建表语句和初始数据的命令如下，表数据初始化后里面有10000条记录：

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();

问题：发现随着单词表变大，选单词这个逻辑变得越来越慢，甚至影响到了首页的打开速度；

#### 内存临时表 ####

**方案**：通过MySQL内置函数 **rand()** ，对每一条记录计算一个random值，对改值排序取前3个记录；

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

虽然这个SQL语句写法很简单，但执行流程却有点复杂，先用explain命令来看看这个语句的执行情况；

![b4cfbc1401fb49bcb95cc3ba1ab7f5bc.png][]

Extra字段显示 **Using temporary**，表示的是需要使用**临时表**；Using filesort，表示的是需要执行排序操作；分析下来，意思就是：**需要对每条记录及random值记入临时表，并且需要在临时表上排序**；

根据[上篇文章][Link 1]的结论：**对于InnoDB表来说，执行全字段排序会减少磁盘访问，因此会被优先选择；当内存不够时，才会使用rowid排序再回表**；那么这里，针对的是存入random值的**内存表**，会使用那种算法呢？

结论是：根据rowid排序；因为对于内存表，回表过程只是简单地根据数据行的位置，直接访问内存得到数据，根本**不会导致多访问磁盘**；那么优化器就没有了磁盘IO这一层顾虑，因此它会优先考虑的，就是**用于排序的行越小越好**，所以，MySQL 这时就会选择 rowid 排序；

这条语句的执行流程（同时分析一下语句的扫描行数）：

（1）创建一个临时表；这个临时表使用的是memory引擎（这个引擎类型由配置参数 internal\_tmp\_disk\_storage\_engine 控制），表里有两个字段，第一个字段是double类型（random的值），为了后面描述方便，记为字段R，第二个字段是varchar(64)类型（word的值），记为字段W；并且，这个表没有建索引；

（2）从words表中，按主键顺序取出所有的word值；对于每一个word值，调用rand()函数生成一个大于0小于1的随机小数，并把这个随机小数和word分别存入临时表的R和W字段中，**到此，扫描行数是10000**；

（3）现在临时表有10000行数据了，接下来你要在这个没有索引的内存临时表上，按照字段R排序；初始化sort\_buffer；

（4）sort\_buffer中有两个字段，一个是double类型（参与排序的random的值），另一个是整型（rowid）；

（5）从内存临时表中一行一行地取出random的值和位置信息rowid，分别存入sort\_buffer中的两个字段里；这个过程要对内存临时表做全表扫描，**此时扫描行数增加10000，变成了20000**；

（6）在sort\_buffer中根据R的值进行排序；注意，这个过程**没有涉及到表操作，所以不会增加扫描行数**；

（7）排序完成后，取出前三个结果的位置信息rowid，依次到内存临时表中取出word值，返回给客户端；这个过程中，**访问了表的3行数据，总扫描行数变成了20003**；

![6348a4cdf55e4af4876e79e0cb741bf1.png][]

小结一下**：order by rand() 语句使用了内存临时表，而内存临时表排序的时候使用了rowid排序方法；**扫描行数 = 初始化内存临时表时扫描原表的行数 + 排序时扫描内存临时表的行数 + 取rowid回内存临时表查数据的行数；

#### MySQL的表是用什么方法来定位“一行数据”的？——rowid ####

可以看到，图里有个数据行的位置信息pos，其实就是rowid；实际上它表示的是：**每个引擎用来唯一标识数据行的信息**；

[上篇文章][Link 1]的场景中，主键ID就是排序过程中给的rowid，你可能会有疑问：如果创建的表没有主键，或者把一个表的主键删掉了，rowid如何取值？这种情况下，**InnoDB会自己生成一个长度为6字节的rowid来作为主键**；

>  *  对于有主键的InnoDB表来说，这个rowid就是主键ID；
>  *  对于没有主键的InnoDB表来说，这个rowid就是由系统生成的；
>  *  MEMORY引擎不是索引组织表；在这个例子里面，可以认为它就是一个数组；因此，这个rowid其实就是数组的下标；

#### 磁盘临时表 ####

[上篇文章][Link 1]中提到了，当sort\_buffer的内存空间不够时，会借助磁盘临时文件，使用外部排序+归并；内存临时表也与之类似，tmp\_table\_size这个配置限制了内存临时表的大小（默认值是16M），**如果临时表大小超过了tmp\_table\_size，那么内存临时表就会转成磁盘临时表**；

下面修改MySQL的配置，让这条语句走磁盘临时表，并通过OPTIMIZER\_TRACE查看其执行过程信息：

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

![68c59306aad3495aac73d016a9fe2320.png][]

分析：

（1）因为将max\_length\_for\_sort\_data设置成16，小于word字段的长度定义，所以sort\_mode里面显示的是rowid排序，这个是符合预期的，即**参与排序的是随机值R字段和rowid字段组成的行**；

（2）**number\_of\_tmp\_files的值居然是0，与预期不符**；意味着没有用到临时磁盘文件排序，明明tmp\_table\_size的值是不够的：row\_size=14，10000条数据就是140000字节，说明排序占用的空间超过了sort\_buffer\_size定义的32768字节了，理论上应该用临时文件排序啊？

**原因是这里采用**是MySQL5.6版本引入的一个新的排序算法，即：**优先队列排序算法**，而非使用临时文件时采用的归并排序算法；

其实，这个SQL语句只需要取R值最小的3个rowid；但是，如果使用归并排序算法的话，虽然最终也能得到前3个值，但是这个算法结束后，已经将10000行数据都排好序了，也就是说，后面的9997行也是有序的了；但实际上，我们的查询并不需要这些数据是有序的；所以，想一下就明白了，如果使用归并算法，这会浪费了非常多的计算成本；

> 从10000个值中取R值最小的3个rowid，这**本质上是一个topK问题**，解决此类问题的经典方案就是**堆排序**；而优先队列排序算法采用的正是大顶堆排序；

这里我们再看一下上面一篇文章中使用归并排序的SQL查询语句：

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

**你可能会问，这里也用到了limit，为什么没用优先队列排序算法呢？**

原因是，这条SQL语句是limit 1000，如果使用优先队列算法的话，需要维护的**堆的大小就是1000行的(name,rowid)**，**超过了我设置的sort\_buffer\_size大小，所以只能使用归并排序算法**；

> 总的来说，**SQL语句中使用 order by 排序且使用limit N子句时**，如果limit后的数值N不是很大从而可以**满足这N条记录能全部放于sort\_buffer中，则MySQL会使用优先队列排序算法**，否则sort\_buffer不够用，就只能使用磁盘临时文件+归并排序算法了；

#### 其他的基于MySQL的随机排序方案 ####

通过上面的分析，不论是使用哪种类型的临时表（内存/磁盘临时表），**order by rand()** 这种写法都会让计算过程非常复杂，需要大量的扫描行数，因此排序过程的资源消耗也会很大；

不妨换个思路，最初的目的是随机的找到3条记录，而唯一标识记录的就是他的主键ID，因此可以**将问题转换成从表中随机计算出3个主键ID的值**即可；

**方案A**：（1）取得这个表的主键id的最大值M和最小值N；（2）用随机函数生成一个最大值到最小值之间的数X=(M-N)\*rand()+N；（3）取不小于X的第一个ID的行；依次找3个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中间可能有空洞，因此选择不同行的概率不一样**，不是真正的随机；

比如表里有4个id，分别是1、2、4、5，如果按照上面的方法，随机值算出来X=1~5的概率是相同的，但是由于ID=3的记录不存在，因此随机值算出的X=3和X=4都对应主键ID=4的这条记录，因此每条记录被选中的概率不等；

方案A问题的关键在于可能存在主键非自然数连续，因此可以使用真实的行数来计算随机值，并且使用limit语句找到第X行记录，**方案B**如下：（1）取得整个表的行数，并记为C；（2）取得Y = floor( C \* rand() )；floor函数在这里的作用，就是取整数部分；（3）再用limit Y,1取得第Y+1行记录；

方案B解决了方案A的概率不均匀问题；MySQL处理limit Y,1的做法就是按顺序一个一个地读出来，丢掉前Y个，然后把下一个记录作为返回结果，因此这一步需要扫描Y+1行；再加上，第一步扫描的C行，总共需要扫描C+Y+1行，执行代价比方案A的代价要高；当然，跟直接order by rand() 比起来，方案B执行代价还是小很多的（**无需用到内存临时表和排序**）；

这篇文章，其实是借着随机排序的业务场景需求，介绍MySQL对临时表排序的执行过程；如果直接使用order by rand()，这个语句需要Using temporary和Using filesort，查询的执行代价往往是比较大的；所以，在设计的时候你要尽量避开这种写法；

在实际应用的过程中，比较规范的用法就是：**尽量将业务逻辑写在业务代码中，让数据库只做“读写数据”的事情；不要尝试让MySQL去解决业务逻辑问题！**

下篇文章：[《MySQL实战45讲》——学习笔记18 “索引失效、函数/隐式转换“【建议收藏】][MySQL_45_18]

本章参考：[17 | 如何正确地显示随机消息？-极客时间][17 _ _-]

[b4cfbc1401fb49bcb95cc3ba1ab7f5bc.png]: https://img-blog.csdnimg.cn/img_convert/b4cfbc1401fb49bcb95cc3ba1ab7f5bc.png
[Link 1]: https://blog.csdn.net/minghao0508/article/details/127789228
[6348a4cdf55e4af4876e79e0cb741bf1.png]: https://img-blog.csdnimg.cn/6348a4cdf55e4af4876e79e0cb741bf1.png
[68c59306aad3495aac73d016a9fe2320.png]: https://img-blog.csdnimg.cn/68c59306aad3495aac73d016a9fe2320.png
[MySQL_45_18]: https://blog.csdn.net/minghao0508/article/details/127868878
[17 _ _-]: https://time.geekbang.org/column/article/73795