MySQL優(yōu)先隊列是什么

本篇內(nèi)容介紹了“MySQL優(yōu)先隊列是什么”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

 0.先拋問題

假設字段category無索引且有重復值，order by category 和 limit 組合使用的結果會和預期不符。

問題復現(xiàn)：

表結構（就是兩個字段）

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;

對所有數(shù)據(jù)按category字段排序： select * from ratings order by category;

當我們想分頁展示前5條時使用select * from ratings order by category limit 5;

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

但實際結果如下：

怎么肥似？MySQL 出 Bug 了？

可能有同學遇到過這個問題，百度或谷歌一下解決了，你有沒有想過，你查到的辦法是最優(yōu)解嗎？別人是怎么得出這個辦法的？MySQL 為什么會這樣做，跟版本有關嗎？

先拋結論：

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術社區(qū)

2.  最優(yōu)解是后面再加個列值唯一的排序字段，如：order by category,id；

3.  MySQL 為什么這樣做？答案是為了快！（MySQL 5.6及其之后才有此優(yōu)化）

4.  次優(yōu)解是對order by后面的category 加索引（為什么是次優(yōu)解？看完本文你將會有答案）；

下面課代表將還原一下這 3 條結論的產(chǎn)出過程。

1. 最優(yōu)解

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 語句返回的數(shù)據(jù)順序會因為LIMIT的存在而變得不一樣

這是 MySQL 默認對該場景做的優(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 后面再多加一個排序字段（比如 ID 字段）。

以上描述最早出現(xiàn)在MySQL 5.6文檔中，從這個版本開始，引入了這個針對ORDER BY LIMIT 的優(yōu)化。

好了， 針對文中的場景，我們只需要select * from ratings order by category,id;即可解決。

那么問題來了，MySQL 為什么要做這么一個看似是 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 會有內(nèi)存排序和外部排序兩種：

•  如果待排序的數(shù)據(jù)量小于sort buffer size，排序就在內(nèi)存中完成(快速排序)；

•  如果待排序的數(shù)據(jù)量大于sort buffer size，就使用臨時文件進行外部排序(歸并排序);

很明顯，這兩種排序都是對所有結果全部排序，講道理，不管有沒有LIMIT，都是從排完序的結果中按順序取需要的條數(shù)，有沒有LIMIT是不會影響返回的結果順序的。

但是，MySQL 5.6 版本針對 ORDER BY LIMIT做了個小優(yōu)化（排序字段無索引，且列值不唯一時）：優(yōu)化器在遇到 ORDER BY LIMIT語句的時候，使用了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(感興趣的同學可以去閱讀原文)。

所以，就是為了快！

MySQL 認為這種場景就是求 TOP N 的問題，使用 priority queue 就能解決。

3.priority queue(優(yōu)先級隊列)

priority queue 其實就是堆，Java 中有java.util.PriorityQueue類，其本質就是 堆 這種數(shù)據(jù)結構。

簡單解釋一下什么是堆：

堆是一個完全二叉樹；

堆中每一個節(jié)點的值都必須大于等于（大頂堆）或小于等于（小頂堆）其子樹中每個節(jié)點的值。

如果 MySQL 使用歸并或快排，需要把所有數(shù)據(jù)都排好序，再取LIMIT 的前幾條，剩余已排序的數(shù)據(jù)就白白浪費了。

而采用 priority queue 可以根據(jù) LIMIT的條數(shù)維護一個堆，只需要把所有數(shù)據(jù)在這個堆里過一遍就能得到結果。

使用如下語句可以驗證 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 值的大小排序

  1.  取前五條數(shù)據(jù)構成一個小頂堆：

  1.  取下一行數(shù)據(jù)(6,2),發(fā)現(xiàn) 2 小于當前堆中最大的category 3，于是把(2,3)從堆中刪掉，把(6,2) 入堆：

  1.  重復步驟 2，直至符合查詢條件的數(shù)據(jù)都經(jīng)歷過比較入堆，最終堆中數(shù)據(jù)如圖：

以上就是通過 priority queue 找到 最小的 5 行 category 數(shù)據(jù)的執(zhí)行過程。

最后我們將其出堆即可得到結果，每次出堆最小元素后將最后一個元素放入堆頂，按照小頂堆重新堆化，過程如圖：

可以看到，這個結果和select * from ratings order by category limit 5;的輸出一致

4.加索引為什么是次優(yōu)解

顯然，按照ORDER BY 的邏輯，直接對排序字段加索引也可以省去內(nèi)存排序步驟，從而解決這個問題。

但索引也不是銀彈，多出來的category索引會增加表的維護成本，如果沒有明顯的業(yè)務需要，單純?yōu)榱死@過這個priority queue的優(yōu)化而加索引，課代表認為有點得不償失。

尤其是當表數(shù)據(jù)量非常大的時候，索引的體量會很可觀。而且，針對文中場景，category作為分類字段，重復率會比較高，即使有按分類查詢的業(yè)務 SQL ，MySQL 也不一定會選取這條索引。

綜上，針對本場景，個人認為order by category,id才是該問題的最優(yōu)解。

PS：會不會有人問：關我鳥事，我從沒寫過帶 LIMIT 的 SQL 啊！

難道你寫的 CRUD 功能都不帶分頁的嗎？PageHelper 源碼去了解一下？

“MySQL優(yōu)先隊列是什么”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關的知識可以關注億速云網(wǎng)站，小編將為大家輸出更多高質量的實用文章！