此文已由作者葛志誠授權網易雲社區發布。

歡迎訪問網易雲社區，了解更多網易技術產品運營經驗。

此前做熱門信息排序時，細心負責的QA發現這樣一個問題——排序分頁結果中有重複數據。百思不得其解，仔細檢查了代碼，沒有發現任何問題，但這種現象就是會出現。通過對這種現象進行分析以及查閱資料，終於找到了弄清了事情的原委。這是一個比較常見的通用問題，項目此前所有的排序查詢語句都有涉及，我們一併進行了修改。

1. 問題重現

這裡，我使用RDS進行問題重現。經過測試，DDB也出現同樣現象。

首先，執行一次帶order by的查詢，limit 40。結果為排序前40條數據，不用細看。

然後，執行同樣帶order by的查詢，limit20。結果為排序前20條數據，和limit 40查詢結果中的前20項進行比對，發現不一致。留意下紅框中的幾個數據項。

最後，執行同樣帶order by的查詢，limit 20,20。結果為排序第21-40條數據，注意紅框中的數據項，竟然和前20條數據有重複！

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語句來看一下，結果如下：

只能看到使用了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使用了優先順序隊列，而優先順序隊列的原理就是二叉堆。

下面我們驗證一下，真實的查詢中是否使用了優先順序隊列。怎麼看呢？官方文檔也給出了方法：

Optimizer Tracer非常強大，但沒有默認開啟：

SHOW VARIABLES LIKE %trace%;

我們手動開啟：

SET optimizer_trace = "enabled=on";

接著進行查詢。查詢執行完後，查看tracer：

SELECT * FROM information_schema.optimizer_trace;

Optimizer Tracer使用一個Blob欄位存放優化記錄，格式為json。可以看到，確實使用了優先順序隊列。

6. 後記

解決一個問題很容易，但發現問題和搞清楚問題的本質就要耗費一些精力。首先，感謝QA同學的無私協助，為我們找BUG。其次，開發效率和深入探究問題這二者在時間上是衝突的，需要我們權衡。這個問題是某個晚上QA報給我們的，在測試環境中出現，當晚我們就想到了添加絕對排序列的解決方案，第二天我們就進行了解決。但時隔2周，才整理了這篇文章。希望能對大家有所幫助。

免費體驗雲安全(易盾)內容安全、驗證碼等服務

更多網易技術、產品、運營經驗分享請點擊。


推薦閱讀：
相关文章