MySQL使用order by + limit语句有重复数据的坑

2019年9月25日11:25:41 发表评论 46 views

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

1. 问题重现

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

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

MySQL使用order by + limit语句有重复数据的坑

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

MySQL使用order by + limit语句有重复数据的坑

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

MySQL使用order by + limit语句有重复数据的坑

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语句来看一下,结果如下:

MySQL使用order by + limit语句有重复数据的坑

只能看到使用了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使用了优先级队列,而优先级队列的原理就是二叉堆。

下面我们验证一下,真实的查询中是否使用了优先级队列。怎么看呢?官方文档也给出了方法:

MySQL使用order by + limit语句有重复数据的坑

Optimizer Tracer非常强大,但没有默认开启:

SHOW VARIABLES LIKE '%trace%';

我们手动开启:

SET optimizer_trace = "enabled=on";

接着进行查询。查询执行完后,查看tracer:

SELECT * FROM information_schema.optimizer_trace;

Optimizer Tracer使用一个Blob字段存放优化记录,格式为json。可以看到,确实使用了优先级队列。

MySQL使用order by + limit语句有重复数据的坑

6. 后记

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

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: