8.2.1.15 ORDER BY の最適化

場合によって、MySQL は、インデックスを使用して、特別なソートを行わずに ORDER BY 句を満たすことができます。

インデックスのすべての未使用の部分とすべての特別な ORDER BY カラムが WHERE 句内で定数であるかぎり、ORDER BY がインデックスに完全に一致しない場合でもインデックスを使用できます。次のクエリーではインデックスを使用して ORDER BY 部分を解決します。

SELECT * FROM t1
  ORDER BY key_part1,key_part2,... ;

SELECT * FROM t1
  WHERE key_part1 = constant
  ORDER BY key_part2;

SELECT * FROM t1
  ORDER BY key_part1 DESC, key_part2 DESC;

SELECT * FROM t1
  WHERE key_part1 = 1
  ORDER BY key_part1 DESC, key_part2 DESC;

SELECT * FROM t1
  WHERE key_part1 > constant
  ORDER BY key_part1 ASC;

SELECT * FROM t1
  WHERE key_part1 < constant
  ORDER BY key_part1 DESC;

SELECT * FROM t1
  WHERE key_part1 = constant1 AND key_part2 > constant2
  ORDER BY key_part2;

場合によって、MySQL は WHERE 句に一致する行を見つけるためにインデックスを使用しても、ORDER BY を解決するために、インデックスを使用できないことがあります。これらの例には、次のようなものが含まれます。

• さまざまなキーに対して ORDER BY を使用します。

  SELECT * FROM t1 ORDER BY key1, key2;
  

• キーの連続しない部分に対して ORDER BY を使用します。

  SELECT * FROM t1 WHERE key2=constant ORDER BY key_part2;
  

• ASC と DESC を混在させます。

  SELECT * FROM t1 ORDER BY key_part1 DESC, key_part2 ASC;
  

• 行をフェッチするために使用されるキーが ORDER BY で使用されるキーと同じでありません。

  SELECT * FROM t1 WHERE key2=constant ORDER BY key1;
  

• キーカラム名以外の項を含む式で ORDER BY を使用します。

  SELECT * FROM t1 ORDER BY ABS(key);
  SELECT * FROM t1 ORDER BY -key;
  

• 多数のテーブルを結合しようとしており、ORDER BY 内のカラムがすべて、行の取得に使用される最初の非定数テーブルからのものとはかぎりません。(これは EXPLAIN 出力で、const 結合型を持たない最初のテーブルです。)

• ORDER BY 式と GROUP BY 式が異なります。

• ORDER BY 句に指定されたカラムのプリフィクスのみにインデックスを設定しています。この場合、インデックスを使用してソート順序を完全には解決できません。たとえば、CHAR(20) カラムがあり、その先頭の 10 バイトだけにインデックスを設定している場合、インデックスで、10 バイト目を越える値を区別できないため、filesort が必要になります。

• 使用されたテーブルインデックスの種類が、行を順番に格納しません。たとえば、これは、MEMORY テーブルの HASH インデックスに当てはまります。

インデックスをソートに使用できるかどうかは、カラムエイリアスの使用によって影響を受けることがあります。カラム t1.a にインデックスが設定されているとします。次のステートメントでは、選択リスト内のカラム名は a です。これは t1.a を指しているため、ORDER BY 内の a への参照にはインデックスを使用できます。

SELECT a FROM t1 ORDER BY a;

次のステートメントでも、選択リスト内のカラム名は a ですが、これはエイリアス名です。これは ABS(a) を指しているため、ORDER BY 内の a への参照にはインデックスを使用できません。

SELECT ABS(a) AS a FROM t1 ORDER BY a;

次のステートメントでは、ORDER BY は、選択リスト内のカラムの名前でない名前を参照しています。ただし、t1 には a というカラムがあるため、ORDER BY はそれを使用し、インデックスを使用できます。(当然ながら、結果のソート順序は、ABS(a) の順序とはまったく異なる可能性があります。)

SELECT ABS(a) AS b FROM t1 ORDER BY a;

デフォルトで、MySQL はすべての GROUP BY col1, col2, ... クエリーを、ORDER BY col1, col2, ... とクエリーに指定したかのように、ソートします。同じカラムリストを含む明示的な ORDER BY 句が含まれている場合、ソート処理は引き続き行われますが、速度の低下なく、MySQL が最適化によってそれを除去します。クエリーに GROUP BY が含まれているが、結果のソートのオーバーヘッドを避けたい場合は、ORDER BY NULL を指定することでソートを抑止できます。例:

INSERT INTO foo
SELECT a, COUNT(*) FROM bar GROUP BY a ORDER BY NULL;

注記

MySQL 5.6 における暗黙の GROUP BY ソートへの依存は、非推奨になっています。グループ化された結果の特定のソート順序を実現するには、明示的な ORDER BY 句を使用することをお勧めします。GROUP BY ソートは、たとえば、オプティマイザがもっとも効率的であると考えるどのような方法でも、グループ化を指示できるようにしたり、ソートオーバーヘッドを回避したりするためなどに、今後のリリースで変更される可能性のある MySQL 拡張機能です。

EXPLAIN SELECT ... ORDER BY を使用すると、MySQL がインデックスを使用してクエリーを解決できるかどうかを確認できます。Extra カラムに Using filesort と表示された場合、それはできません。「セクション8.8.1「EXPLAIN によるクエリーの最適化」」を参照してください。filesort は、MEMORY ストレージエンジンによって使用されるものと似た固定長の行ストレージフォーマットを使用します。VARCHAR などの可変長型は、固定長を使用して格納されます。

MySQL には、結果をソートして取得するために 2 つの filesort アルゴリズムがあります。元のメソッドは ORDER BY カラムだけを使用します。変更されたメソッドは ORDER BY カラムだけでなく、クエリーによって参照されるすべてのカラムを使用します。

どちらの filesort アルゴリズムを使用するかはオプティマイザが選択します。通常は変更されたアルゴリズムが使用されますが、BLOB カラムや TEXT カラムが含まれる場合を除きます。その場合には元のアルゴリズムが使用されます。どちらのアルゴリズムでも、ソートバッファーサイズは sort_buffer_size システム変数値です。

元の filesort アルゴリズムは次のように動作します。

1. キーに従って、またはテーブルスキャンによって、すべての行を読み取ります。WHERE 句に一致しない行をスキップします。

2. 行ごとに、ソートバッファーに値のペア (ソートキー値と行 ID) を格納します。

3. すべてのペアがソートバッファーに収まる場合は、一時ファイルが作成されません。そうでない場合は、ソートバッファーがいっぱいになると、メモリー内でそれに対して qsort (quicksort) が実行され、それが一時ファイルに書き込まれます。ソートされたブロックへのポインタを保存します。

4. すべての行が読み取られるまで、前の手順を繰り返します。

5. 別の一時ファイルで、最大 MERGEBUFF (7) 領域の 1 つのブロックへのマルチマージを実行します。最初のファイルのすべてのブロックが 2 番目のファイルに格納されるまで、この処理を繰り返します。

6. 残りが MERGEBUFF2 (15) ブロックより少なくなるまで、次を繰り返します。

7. 最後のマルチマージで、行 ID (値のペアの最後の部分) のみが結果ファイルに書き込まれます。

8. 結果ファイルで、行 ID を使用して、ソートされた順序で行を読み取ります。これを最適化するには、行 ID の大きなブロックを読み取り、それらをソートして、それらを使用して、ソートされた順序で行を行バッファーに読み込みます。行バッファーサイズは read_rnd_buffer_size システム変数値です。この手順のコードは sql/records.cc ソースファイルにあります。

このアプローチの問題の 1 つは、WHERE 句の評価時に 1 回と値のペアのソート後にもう 1 回と、2 回行を読み取ることです。さらに、1 回目は行が連続してアクセスされても (テーブルスキャンを実行する場合など)、2 回目はそれらがランダムにアクセスされます。(ソートキーは順序付けされますが、行の位置は順序付けされません。)

変更された filesort アルゴリズムには、行を 2 回読み取ることを回避する最適化が組み込まれています。それは、ソートキー値を記録しますが、行 ID の代わりに、クエリーで参照されているカラムを記録します。変更された filesort アルゴリズムは次のように動作します。

1. WHERE 句に一致する行を読み取ります。

2. 行ごとに、ソートキー値とクエリーで参照されるカラムから構成される値のタプルを記録します。

3. ソートバッファーがいっぱいになると、メモリー内でソートキー値によってタプルをソートし、それを一時ファイルに書き込みます。

4. 一時ファイルのマージソート後、ソートされた順序で行を取得しますが、2 回目はテーブルにアクセスするのではなく、ソートされたタプルから直接必要なカラムを読み取ります。

変更された filesort アルゴリズムを使用すると、タプルが元のメソッドで使用されるペアより長くなり、ソートバッファーに収まるそれらの数が少なくなります。その結果、追加の I/O によって、変更されたアプローチの方が速くなるのではなく、遅くなる可能性があります。速度の低下を防ぐため、オプティマイザはソートタプル内の追加のカラムの合計サイズが max_length_for_sort_data システム変数の値を超えない場合にのみ、変更されたアルゴリズムを使用します。(この変数の値を著しく高く設定すると、高いディスクアクティビティーと低い CPU アクティビティーの組み合わせが見られます。)

filesort が実行されると、EXPLAIN 出力で、Extra カラムに Using filesort が含まれます。さらに、オプティマイザトレース出力には filesort_summary ブロックが含まれます。例:

"filesort_summary": {
  "rows": 100,
  "examined_rows": 100,
  "number_of_tmp_files": 0,
  "sort_buffer_size": 25192,
  "sort_mode": "<sort_key, additional_fields>"
}

sort_mode 値は、使用されたアルゴリズムとソートバッファー内のタプルの内容に関する情報を提供します。

• <sort_key, rowid>: ソートバッファータプルには、ソートキー値と元のテーブル行の行 ID が含まれます。タプルはソートキー値でソートされ、行 ID は、テーブルからの行の読み取りに使用されます。

• <sort_key, additional_fields>: ソートバッファータプルには、ソートキー値とクエリーで参照されているカラムが含まれます。タプルはソートキー値でソートされ、カラム値は、タプルから直接読み取られます。

オプティマイザのトレースについては、「MySQL Internals: Tracing the Optimizer」を参照してください。

テーブル t1 に、4 つの VARCHAR カラム a、b、c、および d があり、オプティマイザはこのクエリーに filesort を使用するとします。

SELECT * FROM t1 ORDER BY a, b;

クエリーは a と b でソートしますが、すべてのカラムを返すため、クエリーによって参照されているカラムは a、b、c、および d です。オプティマイザがどの filesort アルゴリズムを選択するかによって、クエリーは次のように実行されます。

元のアルゴリズムの場合、ソートバッファータプルの内容は次のようになります。

(fixed size a value, fixed size b value,
row ID into t1)

オプティマイザは固定サイズ値でソートします。ソート後、オプティマイザは、順番にタプルを読み取り、各タプル内の行 ID を使用して、t1 から行を読み取り、選択リストカラム値を取得します。

変更されたアルゴリズムの場合、ソートバッファータプルの内容は次のようになります。

(fixed size a value, fixed size b value,
a value, b value, c value, d value)

オプティマイザは固定サイズ値でソートします。ソート後、オプティマイザは、順番にタプルを読み取り、a、b、c、および d の値を使用して、t1 を再度読み取ることなく、選択リストカラム値を取得します。

filesort が使用されない遅いクエリーでは、max_length_for_sort_data を filesort がトリガーされる適切な値まで小さくしてみてください。

ORDER BY 速度を向上するには、MySQL で、追加のソートフェーズではなく、インデックスを使用させることができるかどうかをチェックします。これが不可能な場合は、次の戦略を試すことができます。

• sort_buffer_size 変数値を増やします。

• read_rnd_buffer_size 変数値を増やします。

• カラムに格納された値を保持するために必要なだけの大きさでカラムを宣言することにより、行あたりに使用する RAM を減らします。たとえば、値が 16 文字を超えることがない場合は、CHAR(16) の方が CHAR(200) よりも適切です。

• tmpdir システム変数を変更して、大量の空き領域のある専用ファイルシステムを指すようにします。変数値には、ラウンドロビン方式で使用される複数のパスをリストできます。この機能を使用して、複数のディレクトリに負荷を分散できます。パスは UNIX ではコロン文字 (「:」)、Windows ではセミコロン文字 (「;」) で区切るようにしてください。パスには、同じディスク上の異なるパーティションではなく、異なる物理ディスクにあるファイルシステム内のディレクトリを指定してください。

ORDER BY にインデックスが使用されないが、LIMIT 句も存在する場合、オプティマイザはマージファイルの使用を避け、メモリー内で行をソートできます。詳細は、セクション8.2.1.19「LIMIT クエリーの最適化」を参照してください。