0索引1概述2索引扫描排序和文件排序简介3索引扫描排序执行过程分析4文件排序5补充说明6参考资料1概述MySQL有两种实现ORDERBY的方式：1.通过索引扫描生成有序结果2.使用文件排序（filesort）围绕这两种排序方式，我们尝试理解ORDERBY的执行过程，并回答一些常见问题。（以下只讨论InnoDB存储引擎）2索引扫描排序和文件排序（filesort）简介我们知道InnoDB存储引擎使用B+树作为索引的底层实现。B+树的叶子节点存放所有数据页，内部节点不存放数据信息，所有叶节点组成一个（双向）链表。例如，假设在userinfo表的userid字段上有一个主键索引，userid的当前范围在1001到1006之间，则userid的索引B+树如下：（这里只是举例，下图忽略InnoDB数据页默认大小16KB，双向链表，假设B+树度数为3，userid顺序插入）现在我们要按照userid从小到大的顺序取出所有用户信息，执行以下SQLSELECT*FROMuserinfoORDERBYuserid;MySQL会直接遍历上述userid索引的叶子节点链表，不需要额外的排序操作。这是使用索引扫描进行排序。但是，如果userid字段上没有索引，图1中的B+树结构不存在，MySQL只能通过扫表过滤出符合条件的数据，然后将过滤后的结果按照userid进行排序。这个排序过程就是filesort。下面详细介绍这两种排序方法。3索引扫描排序执行过程分析在介绍索引扫描排序之前，我们先了解一下索引的用途。在SQL语句中，WHERE子句和ORDERBY子句都可以使用索引：WHERE子句使用索引避免全表扫描，ORDERBY子句使用索引避免filesort（使用“avoid”可能不合适。在某些场景下，全表扫描和文件排序可能并不比索引慢）来提高查询效率。索引虽然可以提高查询效率，但是在单条SQL中，一个表查询一次只能使用一个索引（注意：排除索引合并的可能），也就是说，当WHERE子句和ORDERBYclausearecombined当使用的索引不一致时，MySQL只能使用其中一个索引（B+树）。也就是说，在一个同时带有WHERE和ORDERBY的SQL中，使用索引有三种可能的场景：只用在WHERE子句中过滤掉符合条件的数据，只用在ORDERBY子句中返回排序的结果。WHERE也用在ORDERBY中，过滤出符合条件的数据，返回排序后的结果。比如我们创建一个order_detail表，记录每条充值记录的userid（用户id），money（充值金额），create_time（充值时间），主键是自增id：CREATETABLE`order_detail`(`id`int(11)NOTNULLAUTO_INCREMENT,`userid`int(11)NOTNULL,`money`floatNOTNULL,`create_time`timestampNOTNULLDEFAULTCURRENT_TIMESTAMP,PRIMARYKEY(`id`),KEY`userid`(`userid`),KEY`create_time`(`create_time`))ENGINE=InnoDBDEFAULTCHARSET=utf8写一个脚本插入100w行数据（InnoDB不要使用COUNT(*)来检查总行数，它会扫描整个表，这里只是为了演示）：SELECTCOUNT(*)FROMorder_detail;+----------+|计数(*)|+----------+|1000000|+--------+SELECT*FROMorder_detailLIMIT5;+----+--------+--------+----------------------+|编号|用户名|钱|创建时间|+----+--------+-------+--------------------+|1|104832|3109|2013-01-0107:40:38||2|138455|6123|2013-01-0107:40:42||3|109967|7925|2013-01-0107:40:46||4|166686|4307|2013-01-0107:40:55||5|119837|1912年|2013-01-0107:40:58|+----+--------+------+--------------------+现在我们要取出userid=104832的所有充值记录，按照充值时间排序create_time返回场景1索引仅用于WHERE子句。编写以下SQL并对其进行解释：EXPLAINSELECT*FROMorder_detailWHEREuserid=104832ORDERBYcreate_time;+------+-------------+--------------+--------+----------------+--------+---------+-------+------+---------------------------+|id|select_type|table|type|possible_keys|key|key_len|ref|rows|Extra|+------+------------+-------------+------+----------------+--------+---------+-------+------+----------------------------+|1|简单|订单详情|参考|用户名|用户名|4|常量|8|在哪里使用；使用文件排序|+------+------------+------------+------+------------+--------+----------+--------+------+----------------------------+key列值为userid。可以看出，这条SQL会使用userid索引作为WHERE子句的条件过滤，但是ORDERBY子句不能使用索引，只能通过filesort进行排序。这是上面的第一个场景。整个执行过程大致如下：首先通过userid索引找到所有满足WHERE条件的主键id（注：从b+树的根节点到叶子节点，时间复杂度为O(logN))然后根据这些主键id去主键索引（聚簇索引）中找到这些行的数据，生成临时表放入排序缓冲区（时间复杂度为O(M*logN)，M为临时表缓冲区临时表缓冲区的行数）对临时表缓冲区中的数据进行排序（时间复杂度O(M*logM)，M为临时表缓冲区的行数）由于取值本例中的M可以粗略的参考rows列值为8，这个值很小，所以整个执行过程只需要0.00秒场景2索引只用在ORDERBY子句中接下来就是上面的第二种场景，索引只用在ORDERBY子句中，也就是索引扫描排序：Wecancontinue使用上面的SQL通过FORCEINDEX子句强制Optimizer使用ORDERBY子句的索引create_time:EXPLAINSELECT*FROMorder_detailFORCEINDEX(create_time)WHEREuserid=104832ORDERBYcreate_time;+-----+------------+------------+--------+--------------+------------+--------+-----+--------+-------------+|id|select_type|table|type|possible_keys|key|key_len|ref|rows|Extra|+-----+-------------+--------------+--------+------------+------------+--------+------+--------+------------+|1|简单|订单详情|索引|空|创建时间|4|空|998056|e|+------+------------+------------+--------+------------+------------+--------+-----+-------+------------+可以看到Extra字段中的Usingfilesort没有了，但是扫描的行中有998056行左右（准确的值应该是1000000行，InnoDB这一列只是一个估计）这是因为在ORDERBY子句中使用索引时，会直接遍历该索引的叶子节点链表，而不是像B+树那样从根节点往下查找在第一种情况下。执行过程如下：从create_time索引的第一个叶子节点开始，根据每个叶子节点记录的主键id依次扫描所有叶子节点到主键索引（聚簇索引））找到真正的行数据，并判断行数据是否满足WHERE子句的userid条件，则整个获取和返回的时间复杂度为O(M*logN)，M为主键id总数，N为numberofclusteredindexleafnodes(numberofdatapages)本例中M的值为1000000，所以整个执行过程比第一种场景耗时更多，在同一台机器上耗时1.34秒。上面两个例子只是说明了另一个道理：在某些场景下使用filesort比不使用filesort效率更高。场景3索引同时用于WHERE和ORDERBY第三种情况出现在WHERE子句和ORDERBY子句可以使用同一个索引（例如：WHEREuserid>xxxORDERBYuserid），这样可以保存第一个中的第二种情况，回表查询操作完成。因此，如果可能的话，索引的设计应该尽可能满足这两个任务，这样才是最好的。----《高性能MySQL》4文件排序（filesort）其实filesort的一些内容上面已经介绍过了。filesort这个名字很容易混淆，让人误以为它会：把一个非常大的表放到磁盘中，然后对它进行排序。事实上，情况并非如此。filesort只是排序。会不会放到磁盘上要看情况（filesort并不总是坏的，也不是说一个文件就保存在磁盘上，如果数据量小，就在内存中进行。）。下面是《高性能MySQL》中filesort的介绍：如果待排序的数据量小于“排序缓冲区”，MySQL使用内存进行“快速排序”操作。如果内存不够排序，那么MySQL会先把数据分成块，用“快速排序”对每个独立的块进行排序，然后把每个块的排序结果放到磁盘上，然后对每个排序好的块进行排序”归并排序”，最后返回排序后的结果。所以filesort是否会使用磁盘取决于它操作的数据量。总结一下，filesort按排序方式分为两种：1、当数据量较小时，可以在内存中快速排序；合并大量数据时，会涉及到磁盘io，效率会比较低。根据查询回表的次数，filesort可以分为两种方式：1.回表读取数据两次（two-pass）：两次传输排序2.回表读取数据一次（单次）-pass):single第二次传输排序，两次传输排序，两次传输排序，两次回表操作：第一次回表用于过滤掉WHERE子句中满足条件的rowid和ORDERBY列值对应rowid；第二次回表发生在ORDERBY子句对指定列进行排序后，通过rowid回表找出SELECT子句需要的字段信息。比如我们需要从充值记录表中筛选出2018年8月11日-12日所有userid>140000用户的订单明细，按照金额从大到小排序（以下只是filesort的例子），不是一个好的实现）：EXPLAINSELECT*FROMorder_detailWHEREcreate_time>='2018-08-1100:00:00'andcreate_time<'2018-08-1200:00:00'anduserid>140000orderby金钱描述；+------+------------+------------+--------+-------------------+------------+--------+------+------+----------------------------+|编号|选择类型|表|类型|可能的键|钥匙|密钥长度|参考|行|额外|+------+------------+------------+--------+------------------+------------+--------+-------+------+----------------------------+|1|简单|订单详情|范围|用户ID，创建时间|创建时间|4|空|1|在哪里使用；使用文件排序|+------+------------+---------------+--------+----------------+------------+---------+------+------+--------------------------------+下面尝试分析一下这条SQL的执行过程：使用create_time索引满足WHERE子句create_time>='2018-08-1100:00:00'andcreate_time<'2018-08-1200:00:00'rowid返回表（第一次），返回表后可以得到rowid对应的userid。如果userid满足userid>140000的条件，则将该行的rowid和money（ORDERBY的列）放入排序缓冲区中，如果排序缓冲区能容纳排序缓冲区中所有的rowid和money对，则直接排序排序缓冲区（内存）。如果排序缓冲区不能容纳所有的rowid和money对，那么这个块会被快速排序，这个块会被存储在一个临时文件（磁盘）中，然后这个块会被合并排序。遍历排序后的结果，对排序后的每个rowid返回表（第二次返回表），取出SELECT子句需要的所有字段。熟悉计算机系统的人都可以看出，第二次回表的效率要比第一次低很多，因为第一次回表几乎是顺序I/O；并且由于rowid是按照money排序的，所以第二次回表会按照rowid随机顺序读取行记录。这些行记录在磁盘中的存储是分散的。每次从磁盘读取一行，可能会有一个寻址延时（磁臂移动到指定磁道）+旋转时间Delay（磁盘旋转到指定扇区），这就是随机I/O。因此，为了避免第二次回表的随机I/O，MySQL在4.1之后做了一些改进：第一次回表时，将本次查询用到的列全部取出，以供后续使用.我们称之为一次性排序。单传输排序（MySQL4.1之后引入）还是上面的SQL。我们看一下单传输排序的执行过程：使用create_time索引满足WHERE子句create_time>='2018-08-1100:00:00'andcreate_time<'2018-08-1200:00:00'回表（第一次回表），回表后可以得到变化后的rowid对应的userid，如果userid满足userid>140000条件，所有列（包括ORDERBY列）作为数据元组取出放入排序缓冲区。如果排序缓冲区可以容纳所有元组，则直接在排序缓冲区（内存）中进行快速排序。如果排序缓冲区不能容纳所有的元组，则将其分成块并快速排序，并将块存储在临时文件（磁盘）中，然后将块合并并排序。排序后遍历每个元组，从元组中提取SELECT子句需要的所有字段。single-pass排序的缺点是所有涉及的列都会被放入排序缓冲区，而排序缓冲区一次可以容纳的元组较少，增加了归并排序的概率。列数据量越大，需要的合并路径就越多，这会增加额外的I/O开销。因此，当列数据量过大时，单转移排序的效率可能不如二次转移排序。当然，列数据量过大的情况并不是很常见，所以MySQL的filesort会尝试使用单次传输排序，但是为了防止上述情况的发生，MySQL做了如下限制：allrequiredcolumns或ORDERBY列只要是BLOB或TEXT类型，使用两次传输进行排序。如果所有需要的列和ORDERBY列的总大小超过max_length_for_sort_data字节，则使用两次传输进行排序。我们的开发者也应该尝试让filesort使用单传输排序，但是EXPLAIN不会告诉我们这个信息，所以我们只能肉眼查看每列的大小，看看上面的两个限制会不会触发两个的发生转移排序。5补充说明第3节提到，既然filesort的效率不一定比indexscan排序低，为什么很多人要避免filesort呢？Googleusingfilesort，几乎都是和“如何避免filesort”相关的。：这是因为通常ORDERBY子句会配合LIMIT子句只获取部分行。仅仅为了取出top1行而对所有行进行排序显然不是一种有效的方法。在这种场景下，顺序索引扫描排序可能比filesort有更好的性能（当然也有例外）。如果还必须读取不在索引中的列，优化器是否实际这样做取决于读取索引是否比表扫描更有效。官方文档告诉我们优化器会帮助我们选择一个高效的ORDERBY方法。但是不能完全依赖优化器的判断。这时候，合理的建立一个索引，引导它使用指定的索引，可能是更好的选择。6参考资料MySQL8.0参考手册::8.2.1.14ORDERBY优化《高性能MySQL》SergeyPetrunia的博客?MySQL如何执行ORDERBYMySQL文件排序算法-ValinvMySQL技术内幕：InnoDB存储引擎（第2版）B+树可视化B+树(pdf)MySQL::MySQL8.0参考手册::8.8.2EXPLAIN输出格式Clustered和Nonclusteredindex到底是什么意思？-堆栈溢出
