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;
    
  • ASCDESC を混在させます。

    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 カラム abc、および d があり、オプティマイザはこのクエリーに filesort を使用するとします。

SELECT * FROM t1 ORDER BY a, b;

クエリーは ab でソートしますが、すべてのカラムを返すため、クエリーによって参照されているカラムは abc、および 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)

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

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

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 クエリーの最適化」を参照してください。


User Comments
  Posted by Henrik Grubbström on March 24, 2006
To be certain that this optimization is done you often need to force the correct index to be used with FORCE INDEX.

Another problem is that the optimization is lost when you have an OR on a prefix of the index:

SELECT * FROM t1 FORCE INDEX (key1_key2_key3)
WHERE key1=1 OR key1=2 ORDER BY key2,key3 LIMIT 5, 5;

This can be worked around by using UNION:

(SELECT * FROM t1 FORCE INDEX (key1_key2_key3)
WHERE key1=1 ORDER BY key2,key3 LIMIT 10)
UNION
(SELECT * FROM t1 FORCE INDEX (key1_key2_key3)
WHERE key1=2 ORDER BY key2,key3 LIMIT 10)
ORDER BY key2,key3 LIMIT 5, 5

This rewrite can make the query go ~20000 times faster on a table with ~2M rows.
  Posted by Milen Kostadinov on August 29, 2006
===========================================================
Posted by Ravenous Bugblatter Beast on August 15 2006

If you are selecting a wide result set and using ORDER BY RAND() with a LIMIT, you can often speed things up by changing a query of the form:

SELECT id, col1, col2, ... , colN FROM tab WHERE conditions ORDER BY RAND() LIMIT m

To a query of the form:

SELECT id, col1, col2, ... , colN FROM tab WHERE id IN (SELECT id FROM tab WHERE conditions ORDER BY RAND() LIMIT m)

Although the second query has to perform an additional select, it only has to sort a result set containing the single id column, rather than the full result set you are returning from the query.
===========================================================

it's true, but if we have a big database with 1000ths of table rows and we must to join them ...... so oooops ;)
Lately I saw the following link http://jan.kneschke.de/projects/mysql/order-by-rand/ .....you can read here how to get more speed from your executing query in some cases. First read the explanation and see bottom of the page:

============================================================
Performance

Now let's see what happends to our performance. We have 3 different queries for solving our problems.

* Q1. ORDER BY RAND()
* Q2. RAND() * MAX(ID)
* Q3. RAND() * MAX(ID) + ORDER BY ID

Q1 is expected to cost N * log2(N), Q2 and Q3 are nearly constant.

The get real values we filled the table with N rows ( one thousand to one million) and executed each query 1000 times.
----------------------------------------------------------
Rows ||100 ||1.000 ||10.000 ||100.000 ||1.000.000
----------------------------------------------------------
Q1||0:00.718s||0:02.092s||0:18.684s||2:59.081s||58:20.000s
Q2||0:00.519s||0:00.607s||0:00.614s||0:00.628s||0:00.637s
Q3||0:00.570s||0:00.607s||0:00.614s|0:00.628s ||0:00.637s
----------------------------------------------------------

As you can see the plain ORDER BY RAND() is already behind the optimized query at only 100 rows in the table.
============================================================
  Posted by Hugo Azevedo on November 12, 2006
All this is much faster than an ORDER BY RAND(), the problem is, it does not do the same.

Imagine you have a table with two columns (id, name) of thousands of names of people.

If you want to produce a result of only one record, then this is by far the fastest way to do it. You select a random ID from the table, and query it directly.

The problem is, if you want to retrieve two random records from the table.

ORDER BY RAND() will give you, for example, ID 390 and ID 4957 in a result, but the sugested way, will calculate a random index (ex. 390) and return two records based on that index, ID 390 and ID 391...
This means, that the order of the result is not random, only the first "fetched" ID. If you query for more than two records, it will give you ID 390, 391, 392, 393...

In other words, this does not produce an actual random selected result on more than one record.
  Posted by Allan Bogh on February 21, 2007
When performing an ORDER BY col1 ASC - where col1 is an ENUM data type - the ORDER BY clause will not order by the natural language order, but the order of the values in the definition of the ENUM field.

To order by an ENUM field make sure the ENUM values are in alphabetical order or reverse-alphabetical order and then perform the ORDER BY clause.
  Posted by Dominique Thiebaut on May 16, 2007
If you need to "hard" sort a table, i.e. you want the table to be sorted in some predefined order, so that your query doesn't have to do it, use the following syntax:

alter table `yourtablename` order by `yourfieldname` desc;

In this case, when you execute:

select * from `yourtablename` limit 1;

you get the record for which yourfieldname is the largest.
  Posted by Markus Zeller on May 6, 2009
* Q2. RAND() * MAX(ID)
* Q3. RAND() * MAX(ID) + ORDER BY ID

You should NOT use these examples, because it could return invalid data:

With that you receive the highest stored index. Then a random number between 0 and MAX(id) is returned. 0 is a unwanted result. Imagine ID=3 is returned and this row has been deleted. Then this is a unwanted result, too.

If you need only 1 row in case of quotes or similar things then you ever should use the LIMIT 1 at the end of the query.
  Posted by Vladimir G. on February 26, 2012
About the problem with optimization lost when you have an OR in WHERE:

SELECT * FROM t1 FORCE INDEX (key1_key2_key3)
WHERE key1=1 OR key1=2 ORDER BY key2,key3 LIMIT 5, 5;

I found that IGNORE INDEX (key1) and use key3 instead works perfectly sometimes so you don't need to use UNION:

SELECT * FROM t1 IGNORE INDEX (key1)
WHERE key1=1 OR key1=2 ORDER BY key3 LIMIT 5, 5;

And it is interesting that the more elements I have - the faster it works, i.e. (key1=1 OR key1=2 OR key1=3 OR key1=4) works much faster on my table (>100 000 rows) than (key1=1 OR key1=2) .. (MySQL 5.0.77)
  Posted by Luc Vidal on October 25, 2012
With an InnoDB table you can do a query like this :

SELECT * FROM table WHERE col=<constant> ORDER BY id

where "id" is the primary key, and "col" is indexed.
MySQL will be able to use the index on "col" to sort. No need to create a composite index on (col, id).

I believe this is because InnoDB tables are stored with a clustered index (the primary key).

It doesn't work on MyISAM table however.
Always check with an "explain" if the optimisation is used (the Extra column from the explain must not contain "using filesort")
Sign Up Login You must be logged in to post a comment.