此文已由作者葛志诚授权网易云社区发布。

欢迎访问网易云社区，了解更多网易技术产品运营经验。

此前做热门信息排序时，细心负责的QA发现这样一个问题——排序分页结果中有重复数据。百思不得其解，仔细检查了代码，没有发现任何问题，但这种现象就是会出现。通过对这种现象进行分析以及查阅资料，终于找到了弄清了事情的原委。这是一个比较常见的通用问题，项目此前所有的排序查询语句都有涉及，我们一并进行了修改。

1. 问题重现

这里，我使用RDS进行问题重现。经过测试，DDB也出现同样现象。

首先，执行一次带order by的查询，limit 40。结果为排序前40条数据，不用细看。

然后，执行同样带order by的查询，limit20。结果为排序前20条数据，和limit 40查询结果中的前20项进行比对，发现不一致。留意下红框中的几个数据项。

最后，执行同样带order by的查询，limit 20,20。结果为排序第21-40条数据，注意红框中的数据项，竟然和前20条数据有重复！

2. 问题分析

分析上面的数据，不难看出，出现重复的数据项有一个特点，他们的排序值相同。例如，上面的数据项中，id为16923、16925、16872对应的排序值都为1。也就是说，带limit的order by查询只保证排序值不同的结果集之前绝对有序，排序值相同的结果不保证顺序。推测MySQL对order by limit进行了优化。limit n [, m]不需返回全部数据，只需返回前n项或前n + m项。对于这种问题，如果让我们自己处理，会如何做？回顾一下排序演算法，适用于大数据取前n的演算法也只有堆排序了。mysql会不会也使用了类似的优化方法呢？

3. 问题调研

MySQL5.7文档中有一节——8.2.1.16 LIMIT Query Optimization，里面有这样一句话：

If an index is not used for ORDER BY but a LIMIT clause is also present, the optimizer may be able to avoid using a merge file and sort the rows in memory using an in-memory filesort operation. For details, see The In-Memory filesort Algorithm.

在ORDER BY + LIMIT的查询语句中，如果ORDER BY不能使用索引的话，优化器可能会使用in-memory sort操作。详情请参考The In-Memory filesort Algorithm。

紧接著下面给出了个例子。这个例子和我们遇到的现象一模一样。此外，还给出了解决方案——在order by中指定一个二级排序栏位，这个栏位绝对有序，这样就保证了整个排序结果的有序性。

4. 解决方案

就像上面所说的，在order by指定的排序栏位后加一个二级排序栏位，保证有序。这样问题就解决了，此处不再贴结果了，占用篇幅。感兴趣的读者可以自行验证一下。

5. 深入学习

使用上述解决方案，问题就解决了，很高兴。但你或许仍然心存疑问，MySQL针对此语句到底进行了怎样的优化，到底是否使用了堆排序演算法？我们使用explain语句来看一下，结果如下：

只能看到使用了filesort，但具体使用了怎样的排序演算法，从explain的结果看不出来。

继续查资料，阅读上面提到的The In-Memory filesort Algorithm官方doc，可以知道MySQL的filesort有3种优化演算法，分别是：

  • 基本filesort
  • 改进filesort
  • In memory filesort

三种演算法在该页面中有介绍，推荐花10分钟阅读。也可以阅读这篇博客MySQL排序内部原理探秘。

官方doc指出：The sort buffer has a size of sort_buffer_size. If the sort elements for N rows are small enough to fit in the sort buffer (M+N rows if M was specified), the server can avoid using a merge file and performs an in-memory sort by treating the sort buffer as a priority queue. 也就是说，In memory filesort使用了优先顺序队列，而优先顺序队列的原理就是二叉堆。

下面我们验证一下，真实的查询中是否使用了优先顺序队列。怎么看呢？官方文档也给出了方法：

Optimizer Tracer非常强大，但没有默认开启：

SHOW VARIABLES LIKE %trace%;

我们手动开启：

SET optimizer_trace = "enabled=on";

接著进行查询。查询执行完后，查看tracer：

SELECT * FROM information_schema.optimizer_trace;

Optimizer Tracer使用一个Blob栏位存放优化记录，格式为json。可以看到，确实使用了优先顺序队列。

6. 后记

解决一个问题很容易，但发现问题和搞清楚问题的本质就要耗费一些精力。首先，感谢QA同学的无私协助，为我们找BUG。其次，开发效率和深入探究问题这二者在时间上是冲突的，需要我们权衡。这个问题是某个晚上QA报给我们的，在测试环境中出现，当晚我们就想到了添加绝对排序列的解决方案，第二天我们就进行了解决。但时隔2周，才整理了这篇文章。希望能对大家有所帮助。

免费体验云安全(易盾)内容安全、验证码等服务

更多网易技术、产品、运营经验分享请点击。


推荐阅读：
相关文章