mysql 002｜order by的排序算法竟然是這樣的！

酷扯兒

《酷扯兒》官方帳號

前言

平常寫業務的時候，我們經常需要對一些業務數據進行排序，例如點贊排名，瀏覽量排名等等。雖然這個字段很常用了，可能出於對服務器是 MySQL 的原因，使我們會膽怯或不想去了解它背後的執行流程，純黑箱子使用。但是如果不了解其內部機制，又何談以優化使用？今天決定在這篇文章介紹一些

Order By

相關知識。

拋出本文問題

order by 的排序流程是什麼？

order by 的排序算法是什麼？

order by 的優化點在於什麼？

解答疑問

排序流程

關於排序過程，MySQL 會通過判斷

sort_buffer_size

來執行不同的排序流程。

其實是

MySQL

的一個系統參數，它可以控制

會在排序的時候分配的緩沖區大小，這個參數可以作用於

Global

或者

Session

級別。它的特點是允許動態變化，而且不針對特定的存儲引擎。每每當有新的線程的時候，都會分配相應參數值的排序緩沖區大小。

了解完了這個參數值，我們可以介紹兩種排序流程：

一次排序

二次排序

一次排序不是一個專業術語，按照我的理解來解讀，

排序流程需要一次讀取磁盤

。

可能你會感覺困惑，那麼來了解一下整個流程：

會初始化排序緩沖區，然後讀取目標

SQL

所有涉及到的字段(選擇列，篩選列，排序列) 。

如果篩選列是索引，則會根據索引進行查找數據；如果非索引就全局掃描

根據選擇列將所需的數據加進排序緩沖區

現在去尋找第二條數據，所以它會重複去走 2，3 步。直到所有符合篩選列的數據都被加載進緩沖區完。

目前進入了排序階段，根據排序列的要求，把排序緩沖區的數據加載進內存進行排序

返回客戶端

看完了一次排序，或許你對二次排序也有一定的明白了。是的，

二次排序流程需要對磁盤進行兩次讀取

那我們還是對這個流程梳理：

會初始化排序緩沖區，僅僅把

的目標表的主鍵ID以及排序列加載進去。

根據篩選列進行數據的篩選。如果篩選列是索引，則會根據索引進行查找數據；如果非索引就全局掃描

假設查找到了第一條數據，然後將這條數據的主鍵ID和排序列加載進內存。

現在去尋找第二條數據，所以它會重複去走 2，3 步，直到獲取了所有符合篩選列的數據。

目前進入了排序階段，根據排序列的要求，對排序緩沖區的數據進行排序並結果

拿到了排序後的結果，根據每一條數據的主鍵ID回到原表掃描，獲取到選擇列的信息。

返回給客戶端

比對

排序算法

剛剛在排序流程中我們可以知道，實際進行排序的操作是放在內存的。其實上面的流程的都是在內存進行排序。但是實際應用場景上，有可能是一次性需要排序的數據集超出了內存範圍；或者選擇列太多，，導致即使是少數據量也會內存爆滿。所以當

面對大數據量的情況下，會使用臨時文件進行輔助存儲已排序數據。

內存

內存當中主要使用的是比較常見的快速排序，基本思想是：

通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然後再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列

內存+物理文件

由於內存不足的問題，

會對數據集進行多次讀取，多次排序處理。假設目前內存已經滿了，

會對內存的數據集使用快速排序，然後將結果保存到一個臨時文件當中。然後

會將內存清掉，重新根據篩選列再次讀取數據。當內存再次爆滿，然後會繼續在內存進行排序，然後保存到臨時文件。當數據完全准備好了，那麼

會使用多路歸並排序對文件進行排序，原理跟

歸並排序中的二路歸並

比較類型，建議去了解一下。

優化點

提高

。該值應該足夠大，可以讓大數據集也能加載進去，這樣可以讓

減少在排序的過程中對排序數據進行切分，避免讀寫磁盤和合並文件。

根據系統情況調節

max_length_for_sort_data

，因為這個參數的大小會影響

選擇使用

還是

。當值比較小的時候，會使用

，相反使用

。（如果數值設的太高，會導致磁盤活動太高，CPU 活動太低）。

read_rnd_buffer_size

可以提高讀取的行數，減少的讀的時間。

盡量在

上使用索引滿足

order by

的，避免執行文件排序操作時涉及的額外排序。而且有些通過索引掃描比通過表掃描更加廉價。