クエリの抽出結果を並び替える（ソート）にはORDER BY句を使用します。MySQLではこのソートは高コストな処理のため、ソートするカラムに対してインデックスを貼ることが定石です。たとえば、以下のように 作成された記事に対して最新順に10件の取得クエリがあったとします。

mysql> SELECT * FROM article ORDER BY created_at DESC LIMIT 10;

この場合は、created_atにインデックスを貼ることでソート処理を排除することができます。というのも、インデックスはすでにソート済のデータが格納されているので、先頭から順番に辿れば良いだけなのです。

さらに、MySQL 8.0とそれ以降からはDESCENDING INDEX機能が追加されたので、今回の場合はそちらを使用すると、より効果的に処理されます。また、インデックスを使用したソート処理はyoku0825さんの資料：Where狙いのキー、order by狙いのキーが大変参考になりますのでご確認ください。

このようにソート処理はインデックスを貼ることが一番の解決策ですが、MySQLではインデックスのないカラムのソート処理をいくつか最適化しています。

今回はソート最適化や動作について紹介したいと思います。

ソート処理の動作

MySQLは最初にORDER BY句の条件がインデックスで解決できるか確認します。インデックスでソートが解決されたかどうかはEXPLAINから確認することができます。Extra列にUsing filesortの記述がなければ、インデックスで解決しています。記述がある場合は後述のソート処理が実行されています。

このソート処理は2種類あり、MySQL 5.5とそれ以前で動作するソート方式（以後、従来の方式）とMySQL 5.6とそれ以降から追加されたソート方式（以後、新しい方式）です。MySQL 5.6とそれ以降は従来の方式と新しい方式を使い分けています。どちらの方式もsort_buffer_sizeシステム変数で指定された値のバッファ（以後、ソートバッファ）を使います。

従来の方式

テーブルから行を読み取り、ソートバッファのタプルとしてソートキーとrow IDを詰め、クイックソート処理を行います。バッファがいっぱいになった場合はテンポラリファイルに書き出します。テンポラリファイルとはマージソート処理を行い、ソートバッファをマージします。ソートが完了すると、ソートされた順序を維持しながらrow IDから対象の行を読み取ります。よって、ソート処理のための行読み取りと、ソート後の対象行読み取りの2回の行読み取りが発生します。

新しい方式

これはrow IDではなく、SELECTで指定されたカラムタプルをソートバッファに詰めます。ソートが完了までは従来の方式と同じです。ソートが完了すると、ソートされた順序で読み出します。従来の方式とは違い、直接必要なカラムを取得できるので、ソート処理のための行読み取りの1回の行読み取りで完了します。

選択方法

どちらの方式をオプティマイザーが選択するかはmax_length_for_sort_dataシステム変数の値により変わります。ソートバッファに詰めるソートキーおよびSELECTで指定されたカラムタプルの行の合計サイズがこの変数より小さい場合は、新しい方式を実行します。この変数の値を超えるサイズの場合は従来の方式が実行されます。

※）

しかし、注意としてmax_length_for_sort_dataについてのドキュメントを見てみると、これからリリースされるMySQL8.0.20からDeprecatedになるようです（2019/11/25現在⁠）⁠。

MySQL 8.0.20からはソート方式において、なにかしらの変更があると考えられます。筆者が試したところ、すでに現在の最新リリースMySQL 8.0.18ではmax_length_for_sort_dataシステム変数は無視され、常に新しい方式を選択するように動作しているように思います。

確認方法

どちらの方式選択されたか確認するには、optimizer_traceのfile_summaryからわかります。"sort_mode"というキーの値を確認します。"<sort_key, rowid>"は従来の方式です。"<sort_key, additional_fields>"は新しい方式です。

また、MySQL 5.7とそれ以降からは"<sort_key, packed_additional_fields>"と表示されることもあります。これも新しい方式で、varcharなどの文字列を含むタプルに対してコンパクトにまとめていることを意味します。

新しい方式が選択されると、ソートバッファのタプルサイズが大きくなるため、CPUアクティビティーよりもディスクアクティビティーが高くなる傾向があります。

    "filesort_summary": {
      "rows": 16777217,
      "examined_rows": 16777217,
      "number_of_tmp_files": 11268,
      "sort_buffer_size": 32760,
               "sort_mode": "<sort_key, rowid>"

ちなみに、テンポラリファイルのマージ処理を実施した回数は、Sort_merge_passesステータス変数または、"number_of_tmp_files"キーの値から確認できます。

    "filesort_summary": {
      "rows": 16777217,
      "examined_rows": 16777217,
      "number_of_tmp_files": 16385,
      "sort_buffer_size": 32768,
      "sort_mode": "<sort_key, additional_fields>"
    }

LIMIT句の最適化

MySQL 5.6とそれ以降からインデックスで解決できないソート処理はLIMIT句があれば最適化されることもあります（ORDER BY no_index_column LIMIT number⁠）⁠。

この最適化はLIMIT句で指定された件数分のカラムタプルがソートバッファに収まるかを実行前に計算します。収まる場合は、ソートバッファ内で優先キューとして扱うことで、メモリ内のみでソートが完結されます。テンポラリファイルなどディスクを使用した処理を行わないので、処理が高速化されます。ソートバッファに収まらない場合は、前述のどちらかのソート処理が実行されます。

最適化されたかどうかはoptimizer_traceのfile_summaryからわかります。"filesort_priority_queue_optimization"キーを確認します。"chosen"キーの値がtrueであれば最適化されています。

    "filesort_priority_queue_optimization": {
      "limit": 10,
      "rows_estimate": 263778088,
      "row_size": 14,
      "memory_available": 32768,
      "chosen": true
    },

    "filesort_priority_queue_optimization": {
      "limit": 10000,
      "rows_estimate": 263778088,
      "row_size": 24,
      "memory_available": 32768,
      "strip_additional_fields": {
        "row_size": 22,
        "chosen": false,
        "cause": "not_enough_space"
      }

"chosen"キーの値がfalseとなり、"cause"キーに最適化できなかった理由が確認できます。

まとめ

最適化された処理など紹介しましたが、インデックスでソート処理を解決させるのが一番効率が良いことを忘れないでください。optimizer_trace内容については、MySQL5.7や8.0で表示項目が異なるところも多いのでご注意ください。

今回紹介した内容は以下のドキュメントから確認できます。

• 8.2.1.16 ORDER BY Optimization
• 8.2.1.19 LIMIT Query Optimization