本文转载自微信公众号《Java类代表》，作者Java类代表。转载本文请联系Java课代表公众号。本文适用于MySQL5.6及0版本以上，先问个问题。假设字段category没有索引且有重复值，那么使用orderbycategory和limit组合的结果将不符合预期。问题复现：表结构（即两个字段）CREATETABLE`ratings`(`id`int(11)NOTNULLAUTO_INCREMENT,`category`int(11)DEFAULTNULL,PRIMARYKEY(`id`))ENGINE=InnoDBAUTO_INCREMENT=11DEFAULTCHARSET=utf8mb4COLLATE=utf8mb4_general_ci;按类别字段对所有数据进行排序：select*fromratingsorderbycategory;idcategory115110132426292237383当我们想在页面中显示前5个项目时使用select*fromratingsorderbycategorylimit5;所需的ID顺序为151034。但是实际结果是这样的：idcategory11101513242到底有多胖？MySQL中有错误吗？可能有同学遇到过这个问题，百度或者谷歌解决了。你想过吗？看看解是不是找到了最优解？其他人是如何想出这个解决方案的？MySQL为什么要这样做？跟版本有关系吗？先总结一下：最优方案是增加一个列值唯一的排序字段，比如：orderbycategory,id为什么MySQL要这样做？答案是要快！（MySQL5.6以后有这个优化）次优方案是给orderby后面的类别加一个索引（为什么是次优方案？看完这篇文章你会有答案）下面课代表会还原这3个结论的输出过程。1.优化方案MySQL文档8.2.1.19LIMITQueryOptimization对这种场景的描述如下：如果多行在ORDERBY列中有相同的值，服务器可以自由地以任意顺序返回这些行，并且可能会根据不同的顺序返回这些行关于总体执行计划。换句话说，这些行的排序顺序相对于未排序的列是不确定的。影响执行计划的一个因素是LIMIT，因此带有和不带有LIMIT的ORDERBY查询可能会以不同的顺序返回行。总结：当ORDERBY列的字段值重复时，由于LIMIT的存在，ORDERBY语句返回的数据顺序会不同。这是MySQL对此场景的默认优化。如果你需要保证加不加LIMIT的顺序一定要一致，官方也给出了方法：如果重要的是保证有和没有LIMIT的行顺序一致，在ORDERBY中包含额外的列使顺序具有??确定性的子句。就是在ORDERBY之后再增加一个排序字段（比如ID字段）。上面的描述最早出现在MySQL5.6的文档中。从这个版本开始，引入了对ORDERBYLIMIT的优化。好了，对于文章中的场景，我们只需要select*fromratingsorderbycategory,id；解决它。那么问题来了，为什么MySQL会做这样一个看似bug的优化呢？2、MySQL的ORDERBY逻辑，顾名思义，ORDERBY就是排序。执行explainselect*fromratingsorderbycategorylimit5;**************************1.row***************************id:1select_type:SIMPLEtable:ratingspartitions:NULLtype:ALLpossible_keys:NULLkey:NULLkey_len:NULLref:NULLrows:10filtered:100.00Extra:Usingfilesort1rowinset,1warning(0.00秒)可以看到Extra:Usingfilesort表示需要排序。一般情况下，MySQL有内存排序和外部排序两种：如果待排序的数据量小于排序缓冲区大小，则在内存中进行排序（快速排序）；如果要排序的数据量大于排序缓冲区大小，则使用临时文件进行外部排序（合并排序）；显然，这两种都是各种结果。按理说，不管有没有LIMIT，都是从排序后的结果中按顺序取出需要的item个数。是否有LIMIT不会影响返回结果的顺序。不过MySQL5.6版本对ORDERBYLIMIT做了一个小小的优化（当排序字段没有索引且列值不唯一时）：当优化器遇到ORDERBYLIMIT语句时，会使用优先队列。以下伪代码描述了filesort.cc中的优化：dumpsortedsequenceto'tempfile';dumpMerge_chunkdescribingsequencelocationinto'chunk_file';}}if(keywaspacked)tellsortbuffertheactualnumberofbytesused;}}if(bufferhasssomeelements&&dumpedatleastonce)sort-dump-dumpasabove;elsedon'tsort,leavesortbuffertobesortedbycaller.并在优化了WL#1393优化排序#1393:该优化总论：许多web客户必须做“SELECT...ORDERBYnon_index_columnLIMITX”，当X*小于sort_buff_size时，我们可以使用以下算法来加速排序：-创建一个队列以保持“limit”键。og中记录了优化后的效果：比quicksort快10到20倍（有兴趣的同学可以看原文）所以，就是为了速度！MySQL认为这种场景就是求TOPN的问题，可以使用优先队列解决。3.优先队列（priorityqueue）优先队列其实就是一个堆。Java中有一个java.util.PriorityQueue类，它的本质就是数据结构【堆】。简单解释一下什么是堆：堆是一棵完全二叉树；堆中每个节点的值必须大于或等于（大顶堆）或小于或等于（小顶堆）其子树中每个节点的值。如果MySQL使用merge或者quicksort，需要对所有数据进行排序，然后取LIMIT的前几项，剩下的排序后的数据就浪费了。使用优先级队列可以根据LIMIT项的个数维护一个堆，只需要将堆中的所有数据都传一遍就可以得到结果。使用以下语句验证MySQL使用优先级队列：SEToptimizer_trace='enabled=on';select*fromratingsorderbycategorylimit5;SELECT*FROM`information_schema`.`OPTIMIZER_TRACE`\G;"filesort_priority_queue_optimization":{"limit":5,"chosen":true}，可以看到filesort_priority_queue_optimization.chosen=true下面用流程图还原一下优先级队列的执行逻辑（以LIMIT5为例）：友情提示：图中的小顶堆是排序好的通过类别值的大小取前5条数据形成小顶堆：取下一行数据(6,2)，发现2小于当前堆中最大的类别3，则删除(2,3)从堆中取出，并将(6,2)放入堆中：重复步骤2，直到满足查询条件的数据被比较好放入堆中，最终堆中的数据如图上图：上图是寻找类别dat最小的5行的执行过程a通过优先级队列。最后，我们可以通过从堆中取出来得到结果。每次最小元素出堆后，把最后一个元素放到堆顶，按照小顶堆重新堆。流程如图：可以看到，这个结果和select*fromratingsorderbycategorylimit5的输出相同；同理4.为什么索引是次优解显然，按照ORDERBY的逻辑，直接在排序字段上加索引也可以省去内存排序步骤，从而解决这个问题。但该指数并不是灵丹妙药。额外的类别索引会增加表的维护成本。如果没有明显的业务需求，仅仅为了绕过优先级队列的优化而增加一个索引是得不偿失的。特别是当表数据量非常大的时候，索引的体积会相当可观。而且文章中的场景，使用category作为分类字段，重复率会比较高。即使有按类查询的业务SQL，MySQL也不一定会选择这个索引。综上所述，对于这种场景，我个人认为orderbycategory,id是这个问题的最优解。PS：会不会有人问：关我什么事，我从来没有用LIMIT写过SQL！你不会用分页编写CRUD函数吗？查看PageHelper的源代码？5.小结本文案例为一堂课代表我在上网过程中遇到的实际问题，请教了身边的同学。他们中有几个人遇到过这个问题。网上的文章大多简单易懂。然后整理这篇文章。涉及数据结构、PageHelper、MySQL文档，相关参考资料列在文末。如果大家有时间顺着文章的思路阅读参考文档，相信会有更深层次的收获。6.参考资料：《数据结构与算法之美》---王征第28、29讲《MySQL实战45讲》---林晓斌第04、05、10、16、17讲8.2.1.16LIMIT查询优化---https://dev。mysql.com/doc/refman/5.6/en/limit-optimization.htmlMySQL·Q&A·MySQL排序分页---http://mysql.taobao.org/monthly/2015/06/04/filesort.cc---https://dev.mysql.com/doc/dev/mysql-server/8.0.18/filesort_8cc.htmlWL#1393：用小限制优化文件排序---https://dev.mysql.com/worklog/task/?id=1393
