MySQL核心月報 2014.11-MariaDB· 性能優化·filesort with small LIMIT optimization

從mysql 5.6.2/mariadb 10.0.0版本開始，mysql/mariadb針對"order by ...limit n"語句實作了一種新的優化政策。當n足夠小的時候，優化器會采用一個容積為n的優先隊列來進行排序，而不是排序所有資料然後取出前n條。 這個新算法可以這麼描述：（假設是asc排序）

建立一個隻有n個元素的優先隊列（堆），根節點為堆中最大元素

根據其他條件，依次從表中取出一行資料

如果目前行的排序關鍵字小于堆頭，則把目前元素替換堆頭，重新shift保持堆的特性

再取一條資料重複2步驟，如果沒有下一條資料則執行5

依次取出堆中的元素（從大到小排序），逆序輸出（從小到大排序），即可得asc的排序結果

這樣的算法，時間複雜度為m*log(n)，m為索引過濾後的行數，n為limit的行數。而原始的全排序算法，時間複雜度為m*log(m)。隻要n遠小于m，這個算法就會很有效。

不過在mysql 5.6中，除了optimizer_trace，沒有好的方法來看到這個新的執行計劃到底起了多少作用。mariadb 10.013開始，提供一個系統狀态，可以檢視新執行計劃調用的次數：

此外，mariadb還将此資訊打入了slow log中。隻要指定 log_slow_verbosity=query_plan，就可以在slow log中看到這樣的記錄：

"priority_queue: yes" 就表示這個query利用了優先隊列的執行計劃(pt-query-digest 目前已經可以解析 priority_queue 這個列)。