深入淺出 MySQL 優(yōu)先隊(duì)列
本文轉(zhuǎn)載自微信公眾號(hào)「Java課代表」，作者Java課代表 。轉(zhuǎn)載本文請(qǐng)聯(lián)系Java課代表公眾號(hào)。
本文適用于 MySQL 5.6 及以上版本
0.先拋問題
假設(shè)字段category無索引且有重復(fù)值，order by category 和limit組合使用的結(jié)果會(huì)和預(yù)期不符。
問題復(fù)現(xiàn)：
表結(jié)構(gòu)(就是兩個(gè)字段)
- 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;
對(duì)所有數(shù)據(jù)按category字段排序：select * from ratings order by category;
| id | category |
|---|---|
| 1 | 1 |
| 5 | 1 |
| 10 | 1 |
| 3 | 2 |
| 4 | 2 |
| 6 | 2 |
| 9 | 2 |
| 2 | 3 |
| 7 | 3 |
| 8 | 3 |
當(dāng)我們想分頁展示前5條時(shí)使用select * from ratings order by category limit 5;
期望得到的ID順序是1 5 10 3 4。
但實(shí)際結(jié)果如下：
| id | category |
|---|---|
| 1 | 1 |
| 10 | 1 |
| 5 | 1 |
| 3 | 2 |
| 4 | 2 |
怎么肥似?MySQL 出 Bug 了?
可能有同學(xué)遇到過這個(gè)問題，百度或谷歌一下解決了，你有沒有想過，你查到的辦法是最優(yōu)解嗎?別人是怎么得出這個(gè)辦法的?MySQL 為什么會(huì)這樣做，跟版本有關(guān)嗎?
先拋結(jié)論：
- 最優(yōu)解是后面再加個(gè)列值唯一的排序字段，如：order by category,id
- MySQL 為什么這樣做?答案是為了快!(MySQL 5.6及其之后才有此優(yōu)化)
- 次優(yōu)解是對(duì)order by后面的category 加索引(為什么是次優(yōu)解?看完本文你將會(huì)有答案)
- 下面課代表將還原一下這 3 條結(jié)論的產(chǎn)出過程。
1. 最優(yōu)解
MySQL 文檔 8.2.1.19 LIMIT Query Optimization 中對(duì)此場(chǎng)景有如下描述：
- 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.
總結(jié)來說就是：
當(dāng) ORDER BY 列的字段值存在重復(fù)，那么這條 ORDER BY 語句返回的數(shù)據(jù)順序會(huì)因?yàn)長(zhǎng)IMIT的存在而變得不一樣
這是 MySQL 默認(rèn)對(duì)該場(chǎng)景做的優(yōu)化，如果你需要保證加不加 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 后面再多加一個(gè)排序字段(比如 ID 字段)。
以上描述最早出現(xiàn)在MySQL 5.6文檔中，從這個(gè)版本開始，引入了這個(gè)針對(duì)ORDER BY LIMIT的優(yōu)化。
好了， 針對(duì)文中的場(chǎng)景，我們只需要select * from ratings order by category,id;即可解決。
那么問題來了，MySQL 為什么要做這么一個(gè)看似是 Bug 的優(yōu)化?
2.MySQL 的 ORDER BY 邏輯
顧名思義，ORDER BY 就是排序。
執(zhí)行一下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 會(huì)有內(nèi)存排序和外部排序兩種：
- 如果待排序的數(shù)據(jù)量小于sort buffer size，排序就在內(nèi)存中完成(快速排序);
- 如果待排序的數(shù)據(jù)量大于sort buffer size，就使用臨時(shí)文件進(jìn)行外部排序(歸并排序);
很明顯，這兩種排序都是對(duì)所有結(jié)果全部排序，講道理，不管有沒有LIMIT，都是從排完序的結(jié)果中按順序取需要的條數(shù)，有沒有LIMIT是不會(huì)影響返回的結(jié)果順序的。
但是，MySQL 5.6 版本針對(duì) ORDER BY LIMIT做了個(gè)小優(yōu)化(排序字段無索引，且列值不唯一時(shí))：優(yōu)化器在遇到 ORDER BY LIMIT語句的時(shí)候，使用了priority queue。
filesort.cc 中有如下偽代碼描述該優(yōu)化：
- 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 中闡述了該優(yōu)化邏輯:
- 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 中記錄了優(yōu)化后的效果：10 to 20 times faster than a quicksort(感興趣的同學(xué)可以去閱讀原文)。
所以，就是為了快!
MySQL 認(rèn)為這種場(chǎng)景就是求 TOP N 的問題，使用 priority queue 就能解決。
3.priority queue(優(yōu)先級(jí)隊(duì)列)
priority queue 其實(shí)就是堆，Java 中有java.util.PriorityQueue類，其本質(zhì)就是 [堆] 這種數(shù)據(jù)結(jié)構(gòu)。
簡(jiǎn)單解釋一下什么是堆：
堆是一個(gè)完全二叉樹;
堆中每一個(gè)節(jié)點(diǎn)的值都必須大于等于(大頂堆)或小于等于(小頂堆)其子樹中每個(gè)節(jié)點(diǎn)的值。
如果 MySQL 使用歸并或快排，需要把所有數(shù)據(jù)都排好序，再取LIMIT 的前幾條，剩余已排序的數(shù)據(jù)就白白浪費(fèi)了。
而采用 priority queue 可以根據(jù) LIMIT的條數(shù)維護(hù)一個(gè)堆，只需要把所有數(shù)據(jù)在這個(gè)堆里過一遍就能得到結(jié)果。
使用如下語句可以驗(yàn)證 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 的執(zhí)行邏輯(以LIMIT 5為例)：
友情提示：圖中的小頂堆以 category 值的大小排序
取前五條數(shù)據(jù)構(gòu)成一個(gè)小頂堆：
取下一行數(shù)據(jù)(6,2),發(fā)現(xiàn) 2 小于當(dāng)前堆中最大的category 3，于是把(2,3)從堆中刪掉，把(6,2) 入堆：
重復(fù)步驟 2，直至符合查詢條件的數(shù)據(jù)都經(jīng)歷過比較入堆，最終堆中數(shù)據(jù)如圖：
以上就是通過 priority queue 找到 最小的 5 行 category 數(shù)據(jù)的執(zhí)行過程。
最后我們將其出堆即可得到結(jié)果，每次出堆最小元素后將最后一個(gè)元素放入堆頂，按照小頂堆重新堆化，過程如圖：
可以看到，這個(gè)結(jié)果和select * from ratings order by category limit 5;的輸出一致
4.加索引為什么是次優(yōu)解
顯然，按照ORDER BY 的邏輯，直接對(duì)排序字段加索引也可以省去內(nèi)存排序步驟，從而解決這個(gè)問題。
但索引也不是銀彈，多出來的category索引會(huì)增加表的維護(hù)成本，如果沒有明顯的業(yè)務(wù)需要，單純?yōu)榱死@過這個(gè)priority queue的優(yōu)化而加索引，課代表認(rèn)為有點(diǎn)得不償失。
尤其是當(dāng)表數(shù)據(jù)量非常大的時(shí)候，索引的體量會(huì)很可觀。而且，針對(duì)文中場(chǎng)景，category作為分類字段，重復(fù)率會(huì)比較高，即使有按分類查詢的業(yè)務(wù) SQL ，MySQL 也不一定會(huì)選取這條索引。
綜上，針對(duì)本場(chǎng)景，個(gè)人認(rèn)為order by category,id才是該問題的最優(yōu)解。
PS：會(huì)不會(huì)有人問：關(guān)我鳥事，我從沒寫過帶 LIMIT 的 SQL 啊!
難道你寫的 CRUD 功能都不帶分頁的嗎?PageHelper 源碼去了解一下?
5. 總結(jié)
本文案例是課代表上線過程中遭遇到的實(shí)際問題，咨詢了下周圍同學(xué)，有好幾個(gè)都遇到過此問題，網(wǎng)上文章大多淺入淺出，讀完有隔靴搔癢之感，無法解答心中疑惑。遂整理此文。
其中涉及 數(shù)據(jù)結(jié)構(gòu)，PageHelper，MySQL 文檔，相關(guān)參考資料羅列在文末，如果有時(shí)間能順著文章思路親自讀一遍參考文檔，相信會(huì)有更深的收獲。
6.參考資料：
《數(shù)據(jù)結(jié)構(gòu)與算法之美》---王爭(zhēng) 第 28,29 講
《MySQL實(shí)戰(zhàn)45講》---林曉斌 第 04、05、10、16、17 講
8.2.1.16 LIMIT Query Optimization---https://dev.mysql.com/doc/refman/5.6/en/limit-optimization.html
MySQL · 答疑解惑 · MySQL Sort 分頁---http://mysql.taobao.org/monthly/2015/06/04/
filesort.cc---https://dev.mysql.com/doc/dev/mysql-server/8.0.18/filesort_8cc.html
WL#1393: Optimizing filesort with small limit---https://dev.mysql.com/worklog/task/?id=1393
