深入浅出 MySQL 优先队列(你一定会踩到的order by limit 问题)

本文适用于 MySQL 5.6 及以上版本

0.先抛问题

假设字段category无索引且有重复值,order by category limit 组合使用的结果会和预期不符。

问题复现:

表结构(就是两个字段)

CREATE TABLE `ratings` (

`id` int(11) NOT NULL AUTO_INCREMENT,

`category` int(11) DEFAULT NULL,

PRIMARY KEY (`id`)

) ENGINE=InnoDB AUTO_INCREMENT=11 DEFAULT CHARSET=utf8mb4 COLLATE=utf8mb4_general_ci;

对所有数据按category字段排序: select * from ratings order by category;

idcategory
11
51
101
32
42
62
92
23
73
83

当我们想分页展示前5条时使用select * from ratings order by category limit 5;

期望得到的ID顺序是1 5 10 3 4

但实际结果如下:

idcategory
11
101
51
32
42

怎么肥似?MySQL 出 Bug 了?

可能有同学遇到过这个问题,百度或谷歌一下解决了,你有没有想过,你查到的办法是最优解吗?别人是怎么得出这个办法的?MySQL 为什么会这样做,跟版本有关吗?

先抛结论:

  1. 最优解是后面再加个列值唯一的排序字段,如:order by category,id
  2. MySQL 为什么这样做?答案是为了快!(MySQL 5.6及其之后才有此优化)
  3. 次优解是对order by后面的category 加索引(为什么是次优解?看完本文你将会有答案);

下面课代表将还原一下这 3 条结论的产出过程。

1. 最优解

MySQL 文档 8.2.1.19 LIMIT Query Optimization 中对此场景有如下描述:

总结来说就是:

这是 MySQL 默认对该场景做的优化,如果你需要保证加不加 LIMIT 顺序都要一致,官方也给出了办法:

就是在ORDER BY 后面再多加一个排序字段(比如 ID 字段)。

以上描述最早出现在MySQL 5.6文档中,从这个版本开始,引入了这个针对ORDER BY LIMIT 的优化。

好了, 针对文中的场景,我们只需要select * from ratings order by category,id;即可解决。

那么问题来了,MySQL 为什么要做这么一个看似是 Bug 的优化?

2.MySQL 的 ORDER BY 逻辑

顾名思义,ORDER BY 就是排序。

执行一下explain select * from ratings order by category limit 5;

*************************** 1. row ***************************

id: 1

select_type: SIMPLE

table: ratings

partitions: NULL

type: ALL

possible_keys: NULL

key: NULL

key_len: NULL

ref: NULL

rows: 10

filtered: 100.00

Extra: Using filesort

1 row in set, 1 warning (0.00 sec)

可以看到 Extra: Using filesort 表示需要排序。

正常情况下, MySQL 会有内存排序和外部排序两种:

  • 如果待排序的数据量小于sort buffer size,排序就在内存中完成(快速排序);
  • 如果待排序的数据量大于sort buffer size,就使用临时文件进行外部排序(归并排序);

很明显,这两种排序都是对所有结果全部排序,讲道理,不管有没有LIMIT,都是从排完序的结果中按顺序取需要的条数,有没有LIMIT是不会影响返回的结果顺序的。

但是,MySQL 5.6 版本针对 ORDER BY LIMIT做了个小优化(排序字段无索引,且列值不唯一时):优化器在遇到 ORDER BY LIMIT语句的时候,使用了priority queue。

filesort.cc 中有如下伪代码描述该优化:

while (get_next_sortkey())

{

if (using priority queue)

push sort key into queue

else

{

try to put sort key into buffer;

if (no free space in sort buffer)

{

do {

allocate new, larger buffer;

retry putting sort key into buffer;

} until (record fits or no space for new buffer)

if (no space for new buffer)

{

sort record pointers (all buffers);

dump sorted sequence to 'tempfile';

dump Merge_chunk describing sequence location into 'chunk_file';

}

}

if (key was packed)

tell sort buffer the actual number of bytes used;

}

}

if (buffer has some elements && dumped at least once)

sort-dump-dump as above;

else

don't sort, leave sort buffer to be sorted by caller.

并在 WL#1393: Optimizing filesort with small limit 中阐述了该优化逻辑:

Many web customers have to do

"SELECT ... ORDER BY non_index_column LIMIT X",

When X * is smaller than sort_buff_size we can use

the following algoritm to speed up the sort:

- Create a queue to hold 'limit' keys.

- Scan through the table and store the first (last if DESC) keys in the queue

- Return values from queue

This is much faster than the current algoritm that works as:

该 WorkLog 中记录了优化后的效果:10 to 20 times faster than a quicksort(感兴趣的同学可以去阅读原文)。

所以,就是为了快!

MySQL 认为这种场景就是求 TOP N 的问题,使用 priority queue 就能解决。

3.priority queue(优先级队列)

priority queue 其实就是堆,Java 中有java.util.PriorityQueue类,其本质就是 堆 这种数据结构。

简单解释一下什么是堆:

堆是一个完全二叉树;

堆中每一个节点的值都必须大于等于(大顶堆)或小于等于(小顶堆)其子树中每个节点的值。

如果 MySQL 使用归并或快排,需要把所有数据都排好序,再取LIMIT 的前几条,剩余已排序的数据就白白浪费了。

而采用 priority queue 可以根据 LIMIT的条数维护一个堆,只需要把所有数据在这个堆里过一遍就能得到结果。

使用如下语句可以验证 MySQL 使用了 priority queue:

SET optimizer_trace='enabled=on';

select * from ratings order by category limit 5;

SELECT * FROM `information_schema`.`OPTIMIZER_TRACE`\G;

 "filesort_priority_queue_optimization": {

"limit": 5,

"chosen": true

},

可以看到 filesort_priority_queue_optimization.chosen = true

下面用流程图还原一下 priority queue 的执行逻辑(以LIMIT 5为例):

友情提示:图中的小顶堆以 category 值的大小排序

  1. 取前五条数据构成一个小顶堆:

深入浅出 MySQL 优先队列(你一定会踩到的order by limit 问题)

  1. 取下一行数据(6,2),发现 2 小于当前堆中最大的category 3,于是把(2,3)从堆中删掉,把(6,2) 入堆:

深入浅出 MySQL 优先队列(你一定会踩到的order by limit 问题)

  1. 重复步骤 2,直至符合查询条件的数据都经历过比较入堆,最终堆中数据如图:

以上就是通过 priority queue 找到 最小的 5 行 category 数据的执行过程。
深入浅出 MySQL 优先队列(你一定会踩到的order by limit 问题)

最后我们将其出堆即可得到结果,每次出堆最小元素后将最后一个元素放入堆顶,按照小顶堆重新堆化,过程如图:
深入浅出 MySQL 优先队列(你一定会踩到的order by limit 问题)

可以看到,这个结果和select * from ratings order by category limit 5;的输出一致

4.加索引为什么是次优解

显然,按照ORDER BY 的逻辑,直接对排序字段加索引也可以省去内存排序步骤,从而解决这个问题。

但索引也不是银弹,多出来的category索引会增加表的维护成本,如果没有明显的业务需要,单纯为了绕过这个priority queue的优化而加索引,课代表认为有点得不偿失。

尤其是当表数据量非常大的时候,索引的体量会很可观。而且,针对文中场景,category作为分类字段,重复率会比较高,即使有按分类查询的业务 SQL ,MySQL 也不一定会选取这条索引。

综上,针对本场景,个人认为order by category,id才是该问题的最优解。

PS:会不会有人问:关我鸟事,我从没写过带 LIMIT 的 SQL 啊!

难道你写的 CRUD 功能都不带分页的吗?PageHelper 源码去了解一下?

5. 总结

本文案例是课代表上线过程中遭遇到的实际问题,咨询了下周围同学,有好几个都遇到过此问题,网上文章大多浅入浅出,读完有隔靴搔痒之感,无法解答心中疑惑。遂整理此文。

其中涉及 数据结构,PageHelper,MySQL 文档,相关参考资料罗列在文末,如果有时间能顺着文章思路亲自读一遍参考文档,相信会有更深的收获。

6.参考资料:

  1. 《数据结构与算法之美》---王争 第 28,29 讲
  2. 《MySQL实战45讲》---林晓斌 第 04、05、10、16、17 讲
  3. 8.2.1.16 LIMIT Query Optimization---https://dev.mysql.com/doc/ref...

  4. MySQL · 答疑解惑 · MySQL Sort 分页---http://mysql.taobao.org/month...

  5. filesort.cc---https://dev.mysql.com/doc/dev...

  6. WL#1393: Optimizing filesort with small limit---https://dev.mysql.com/worklog...


👇关注 Java课代表,获取最新 Java 干货👇
深入浅出 MySQL 优先队列(你一定会踩到的order by limit 问题)

以上是 深入浅出 MySQL 优先队列(你一定会踩到的order by limit 问题) 的全部内容, 来源链接: utcz.com/a/66271.html

回到顶部