关于后端:排序相关问题

本篇博客在 B 站做了外部分享, 题目为「排序相干问题」

MySQL 的 ORDER BY 有两种排序实现形式：

1. 利用有序索引获取有序数据
2. (不得不进行)文件排序

在 explain 中剖析时，利用有序索引获取有序数据显示Using index，文件排序显示Using filesort。

<font color=”orange”>1. 可能 利用有序索引获取有序数据 的条件比拟刻薄 </font>

以下几种优化形式, 可能使 order by 利用到索引, 而无需进行 filesort：

1、ORDER BY 的索引优化。如果一个 SQL 语句形如：SELECT [column1],[column2],…. FROM [TABLE] ORDER BY [sort];
在 [sort] 这个栏位上建设索引就能够实现利用索引进行 order by 优化。2、WHERE + ORDER BY 的索引优化，形如：SELECT [column1],[column2],…. FROM [TABLE] WHERE [columnX] = [value] ORDER BY [sort];
建设一个联结索引 (columnX,sort) 来实现 order by 优化。留神：如果 columnX 对应多个值，如上面语句就无奈利用索引来实现 order by 的优化
SELECT [column1],[column2],…. FROM [TABLE] WHERE [columnX] IN ([value1],[value2],…) ORDER BY[sort];
 
3、WHERE+ 多个字段 ORDER BY
SELECT * FROM [table] WHERE uid=1 ORDER x,y LIMIT 0,10;
建设索引 (uid,x,y) 实现 order by 的优化, 比建设 (x,y,uid) 索引成果要好得多。

<font size=3>Order By 不能应用索引来优化排序的状况:</font>

• 对不同的索引键做 ORDER BY：(key1,key2 别离建设索引)

      SELECT * FROM t1 ORDER BY key1, key2;

• 在非间断的索引键局部上做 ORDER BY：(key_part1,key_part2 建设联结索引;key2 建设索引)

      SELECT * FROM t1 WHERE key2=constant ORDER BY key_part2;

• 同时应用了 ASC 和 DESC：(key_part1,key_part2 建设联结索引)

      SELECT * FROM t1 ORDER BY key_part1 DESC, key_part2 ASC;

• 用于搜寻记录的索引键和做 ORDER BY 的不是同一个：(key1,key2 别离建设索引)

      SELECT * FROM t1 WHERE key2=constant ORDER BY key1;

• 如果在 WHERE 和 ORDER BY 的栏位上利用表达式 (函数) 时，则无奈利用索引来实现 order by 的优化

      SELECT * FROM t1 ORDER BY YEAR(logindate) LIMIT 0,10;

CREATE TABLE `weekxxxxxnor_detail` (`id` int(11) unsigned NOT NULL AUTO_INCREMENT COMMENT '主键 id',
  `mid` int(11) NOT NULL DEFAULT '0' COMMENT '用户 ID',
  `hid` int(11) NOT NULL DEFAULT '0' COMMENT '荣誉 ID',
  `word` varchar(10) NOT NULL DEFAULT ''COMMENT' 字 ',
  `text` varchar(20) NOT NULL DEFAULT ''COMMENT' 文案 ',
  `description` varchar(40) NOT NULL DEFAULT ''COMMENT' 阐明 ',
  `xxxxx_date` date NOT NULL DEFAULT '0000-00-00' COMMENT 'xx 生成日期(每周日)',
  `ctime` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创立工夫',
  `mtime` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '更新工夫',
  PRIMARY KEY (`id`),
  KEY `ix_mtime` (`mtime`),
  KEY `ix_mid_honor_date` (`mid`,`honor_date`)
) ENGINE=InnoDB AUTO_INCREMENT=149628474 DEFAULT CHARSET=utf8 COMMENT='xxxxxx 详情记录'


具体参见 https://note.youdao.com/web/#/file/WEB00c9fc9e542b90ea18d0c3cc53e74d96/note/WEBcb79302cc9f9cadb9d543963f9793baf/

搜寻 ENGINE=InnoDB AUTO_INCREMENT=149628474 DEFAULT CHARSET=utf8 COMMENT=

<font color=”orange”>2. filesort</font>

<font color=”33ccff”>2.1 在内存中可能用 堆排序或疾速排序，</font>

具体应用哪一种排序形式是优化器决定的，根本准则如下

疾速排序算法：大量排序
堆排序算法：排序量不大

疾速排序和堆排序都是不稳固的排序算法，对于反复值不能保障程序。这就是 Order by 排序可能会不稳固的起因

之前遇到的坑：

<font color=”33ccff”>2.1.1 在把数据加载到 BUFFER 外部时有两种形式：</font>

• 双路排序：(rowid 排序 / 二次拜访排序 / 回表排序模式)

首先依据相应的条件取出相应的排序字段和能够间接定位行数据的行指针信息，而后在 sort buffer 中进行排序。排序后再把查问字段按照行指针取出，共执行两次磁盘 io。

• 单路排序：MySQL4.1 之后新增(全字段排序 / 一次拜访排序)

一次性取出满足条件行的所有字段，而后在 sort buffer 中进行排序。执行一次磁盘 io。代价是对内存占用大

应用哪种形式，取决于设定的零碎参数 max_length_for_sort_data(默认为 1K) 和 Query 语句所取出的 字段 <font color=”red”> 类型 </font> 大小总和 的大小关系，来断定是应用双路排序还是单路排序。

如果单行的长度超过max_length_for_sort_data 的值，MySQL 就认为单行太大，应用双路排序形式；

如果 max_length_for_sort_data更大，则应用第二种优化后的算法。

所以如果心愿 ORDER BY 操作的效率尽可能的高，肯定要留神 max_length_for_sort_data 参数的设置。

<font color=”33ccff”>2.2 在内部应用多路归并排序算法：</font>

<font color=”33ccff”>2.3 整个 filesort 的过程如下:</font>

（1）依据表的索引或者全表扫描，读取所有满足条件的记录。

（2）对于每一行，存储一对值到缓冲区（排序列和行记录指针，或者是排序列和查问须要的所有列），缓冲区的大小为 sort_buffer_size 大小(默认为 1M)。

（3）当缓冲区满后，运行一个疾速排序（qsort；数据量不大时也可能用堆排序）来将缓冲区中数据排序，并将排序完的数据存储到一个临时文件，并保留一个存储块的指针，当然如果缓冲区不满，则不会重建临时文件了。

（4）反复以上步骤，直到将所有行读完，并建设相应的有序的临时文件。

（5）对块级进行排序，应用归并排序算法，通过对几个临时文件的指针来一直替换数据，最终达到几个文件，都是有序的。

（6）反复 5 直到所有的数据都排序结束。

（7）采取程序读的形式，将每行数据读入内存（这里读取数据时并不是一行一行读），并取出数据传到客户端，读取缓存大小由 read_rnd_buffer_size 来指定。

参考：

https://dev.mysql.com/doc/refman/5.7/en/order-by-optimization…

本文由 mdnice 多平台公布