关于java:深入浅出-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;

当咱们想分页展现前 5 条时应用select * from ratings order by category limit 5;

冀望失去的 ID 程序是1 5 10 3 4。

但理论后果如下：

怎么肥似？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 中对此场景有如下形容：

If multiple rows have identical values in the ORDER BY columns, the server is free to return those rows in any order, and may do so differently depending on the overall execution plan. In other words, the sort order of those rows is nondeterministic with respect to the nonordered columns.
One factor that affects the execution plan is LIMIT, so an ORDER BY query with and without LIMIT may return rows in different orders.

总结来说就是：

当 ORDER BY 列的字段值存在反复，那么这条 ORDER BY 语句返回的数据程序会因为 LIMIT 的存在而变得不一样

这是 MySQL 默认对该场景做的优化，如果你须要保障加不加 LIMIT 程序都要统一，官网也给出了方法：

If it is important to ensure the same row order with and without LIMIT, include additional columns in the ORDER BY clause to make the order deterministic.

就是在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. 取前五条数据形成一个小顶堆：

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

1. 反复步骤 2，直至合乎查问条件的数据都经验过比拟入堆，最终堆中数据如图：

以上就是通过 priority queue 找到 最小的 5 行 category 数据的执行过程。

最初咱们将其出堆即可失去后果，每次出堆最小元素后将最初一个元素放入堆顶，依照小顶堆从新堆化，过程如图：

能够看到，这个后果和 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 干货????