オトコのソートテクニック2008

今日は仕事納めだったので、一年の締めくくりとしてMySQLにおけるソートの話でもしようと思う。

インデックスを利用しないクエリで最もよく見かけるもののひとつは、ORDER BYを用いたソート処理だろう。もし、ソート処理においてインデックスを用いることが出来れば、MySQLは結果を抽出してから結果行をソートするのではなく、インデックス順に行を取り出せば良いので高速にソート処理することが可能になる。特に、LIMIT句やWHERE句を用いて行の絞り込みを行う場合は効果が絶大である。しかし、ひとたびインデックスを利用できない状況に直面すると、たちまちテーブルスキャンが発生して性能が劣化してしまう。

例えば、100万行のレコードを格納したt1というテーブルがあるとする。そのテーブルに対して以下のようなクエリを実行した場合を考えよう。

mysql> SELECT col1, col2 ... colx FROM t1 WHERE ...略... ORDER BY col1 LIMIT 10;

このクエリでは、LIMIT 10が指定されているので、クライアントに返す結果行はたったの10行である。一見するととても軽そうな処理のように思えるが、もしこのクエリにおいてインデックスが利用できないとどうなるだろうか？答えは「テーブルの全件スキャンが発生して、100万行のレコードをソートした後で最初の10行だけをクライアントに返す」という状況に陥ってしまう。たった10行のために100万行のソート処理が発生するのである。問い合わせのたびに毎回100万行のレコードをソートしていたのでは、すぐにサーバの処理能力はパンクしてしまうだろう。

もしこのクエリでインデックスを利用できるとどうなるだろうか。答えは「インデックスの順番に10行だけ読み込んで結果をクライアントに返す」である。これならば秒間に何千もの問い合わせが来ても平気である。

100万行のソート処理と10行の抽出では、処理速度は雲泥の差である。今日は前者のような悲劇が起こさないためのテクニックを紹介しようと思う。

インデックスを用いてソート処理を行うには、ORDER BYで指定するキーとWHERE句で指定するキーを工夫しなければならない。ソート処理でインデックスを利用するもっとも明白な例は、ORDER BY句においてインデックスが張られたカラムを指定して、WHERE句を使用しないことである。（次のクエリを参照）ORDER BYとLIMITだけならば、インデックスの順序通りに行を取り出せば既にソートが完了している。

mysql> SELECT ...略... FROM t1 ORDER BY col1 LIMIT 10;

しかし、世の中はそんな単純ではない。むしろWHERE句のない問い合わせなどほとんど無いといって良いだろう。WHERE句を指定することのメリットは、検索結果の行数が全体に比べて少なくなることである。例えば、100万行のレコードのうち、WHEREで指定した条件に適合する行が100行しかないとしよう。100行のソート処理などたかが知れているので、WHERE句によって行数を十分に少なく絞り込むことが出来るのであればORDER BYにおいてインデックスを用いることなどは考慮しなくても良い。

ただしWHERE句で指定した条件に適合する行が100万行のうち10万行ならばどうだろうか。ソートする行数が10万行ともなると、ソート処理にかかるCPUパワー、メモリ、ディスクI/Oなどは無視出来なくなるので、インデックスの使用が必須になる。10万行をソートした結果、クライアントへ返す行が10行だけとなると勿体ない限りである。

WHERE句で指定するカラムとORDER BYで指定するカラムの両方にインデックスがついていればいいかというと、実はそうではない。次のようなインデックスがあっても、クエリではインデックスが用いられることはない。

mysql> ALTER TABLE t1 ADD INDEX (col1), ADD INDEX (col2);
mysql> SELECT ...略... FROM t1 WHERE col1 = 12345 ORDER BY col2 LIMIT 10;

WHERE句を指定した場合にインデックスを利用できる最も単純な例は、WHERE句とORDER BY句の両方で同じカラムを指定することである。例えば次のように。

mysql> SELECT ...略... FROM t1 WHERE col1 >= 12345 ORDER BY col1 LIMIT 10;

これならば万事OK。col1が12345より大きい行を、col1の順番に10行読み込むだけである。col1に対して以下のようなインデックスが設定されてあればよい。

mysql> ALTER TABLE t1 ADD INDEX (col1);

しかし世の中はさらに厄介で、WHERE句とORDER BY句で別々のカラムを指定しないといけない場合が多々あり、しかもWHERE句の条件に適合する行が100万行のうち10万行もあったりするのである。次のようなクエリである。

mysql> SELECT ...略... FROM t1 WHERE col2 = 'ABC' ORDER BY col1 LIMIT 10;

そのような場合には、複合インデックス（またはマルチカラムインデックス）の出番である。複合インデックスとは、読んで字のごとく、複数のカラムに対して指定するインデックスのことである。上記のクエリでは、テーブルに次のようなインデックスがあると、インデックスを用いたソート処理が可能になる。

mysql> ALTER TABLE t1 ADD INDEX (col2, col1);

複合インデックスを用いた場合に注意しないといけないのは、最も左端にあるインデックス（left-most index）をWHERE句の検索条件として指定しないと、ソート処理においてインデックスを利用できないという点である。例えば、上記のような複合インデックスがあっても、次のクエリはインデックスを用いたソート処理を行うことが出来ない。最も左端にあるインデックス（このテーブルの場合はcol2）が、検索条件として指定されていないからである。

mysql> SELECT ...略... FROM t1 ORDER BY col1 LIMIT 10;

これは意外に思うかも知れない。しかし、インデックス内のレコードは、col1の順番に並んでないのである。これは、文章で説明するよりも絵を見た方がわかり易いだろう。複合インデックスのツリーは、例えば次の図のように並んでいる。col2の下にあるcol1は順番に並んでいるが、col1全体で見ると順番はバラバラなのだ。col1の順番に行を並べようと思うと、結局全ての行に対してソート処理を行わなければならないことになる。

また、ORDER BYの条件とWHERE句の条件が逆でもインデックスは利用されない。例えば次のようなクエリである。

mysql> SELECT ...略... FROM t1 WHERE col1=12345 ORDER BY col2 LIMIT 10;

つまり、(WHERE句で指定されたカラム,ORDER BYで指定されたカラム)という複合インデックスが、インデックスを用いてソート処理を行うための必要条件なのである。

次のケースはORDER BY句で指定するカラムが複数ある場合である。ここまで読んだ人は直感的に分かるかも知れないが、ここでも複合インデックスが役に立つ。例えば、前述のような複合インデックス(col2,col1)がある場合、次のソート処理ではインデックスが使われる。

mysql> SELECT ...略... FROM t1 ORDER BY col2, col1 LIMIT 10;

しかし次のクエリではインデックスが使われない。

mysql> SELECT ...略... FROM t1 ORDER BY col1, col2 LIMIT 10;

なぜインデックスが使われないかというと、col1の順番で並んだインデックスが存在しないからだ。ORDER BYで複数のカラムを指定した場合には、カラムの順序通りに複合インデックスを定義する必要がある。

また、ORDER BYで複数のカラムを指定する場合の注意点として、ソートの昇順（ASC）と降順（DESC）を混在出来ないということだ。次のようなクエリでは、たとえ複合インデックスが正しいカラム順序で定義されていても、ソート処理にインデックスが使用されることはない。

mysql> SELECT ...略... FROM t1 ORDER BY col2 DESC, col1 ASC LIMIT 10;

もちろん、デフォルトのソート順序は昇順である。降順（DESC）を指定する場合には注意が必要で、DESCを指定する場合には全てのカラムに対してDESCを明記しなければいけない。そうでないと指定のないカラムは昇順でソートされてしまう。次の例ではcol1は降順だがcol2は昇順でソートされる。

mysql> SELECT ...略... FROM t1 ORDER BY col2, col1 DESC LIMIT 10;

このクエリでは、ソート処理にインデックスが使用されないだけでなく、結果も意図したものと異なるものになってしまうから最悪である。正しくは次のように記述しよう。

mysql> SELECT ...略... FROM t1 ORDER BY col2 DESC, col1 DESC LIMIT 10;

さらに、WHERE句において検索条件が指定されていて、なおかつORDER BYにおいて複数のカラムが指定されている場合がある。例えば次のような場合である。

mysql> SELECT ...略... FROM t1 WHERE col3 = 123 ORDER BY col2, col1 DESC LIMIT 10;

もちろんこの場合は、(col3, col2, col1)の順序で定義された複合インデックスが必要になる。

このように説明すると、「なんだ。クエリの検索とソートの条件に従って複合インデックスを定義すれば万事解決じゃないか。」と思うかも知れないが、物事はそれほど単純ではない。複合インデックスには一つ重大な欠点がある。それは、サイズが大きいということだ。インデックスは検索を高速化する代わりに、インデックス情報を格納するためのディスクスペースが必要になるし、テーブル更新時にインデックスツリーも更新しなければいけないので負荷が少しだけ増える。複合インデックスは単体のカラム上に作成されたインデックスよりも多くのディスクスペースと更新処理が必要になるので、複合インデックスを作成するカラムは慎重に選ばなければならないのである。

このような事情があるため、WHERE句およびORDER BY句で指定されたカラム全てにインデックスを作成することは不可能である。従って、どうしてもソート処理において上記の必要条件を満たすことの出来ないケースが発生する。

既に説明したが、たとえばWHERE句の条件で行を絞り込んだ結果が100行しかないような場合など、WHERE句によって行数を十分に少なく絞り込むことが出来るのであればORDER BYにおいてインデックスを用いることなどは考慮しなくても良い。では逆の場合はどうだろうか？WHERE句の条件で絞り込んだ結果、100万行のうち90万行が条件に該当してしまう場合などである。この場合、WHERE句の検索条件に対してインデックスを使うことのメリットは皆無である。例えば次のクエリを考える。col1にはインデックスが張られていないとする。

mysql> SELECT ...略... FROM t1 WHERE col1 = 123 ORDER BY col2 LIMIT 10;

この場合、col2にインデックスを追加して、col2の順序で行を抽出し、その後WHERE句の条件で行を絞り込むという技が存在する。それが、USE INDEXオプションである。まずはcol2にインデックスを作成する。

mysql> ALTER TABLE t1 ADD INDEX (col2);

そして、クエリにおいてUSE INDEXオプションを使用するのである。

mysql> SELECT ...略... FROM t1 USE INDEX (col2) WHERE col1 = 123 ORDER BY col2 LIMIT 10;

100万行のうち90万行がWHERE句の条件に適合してしまう場合、平均して11行程度読み込むとWHERE句の条件に適合した10行を探し出すことが可能である。従って、上記のクエリの条件が満たされるのである。多くの場合、USE INDEXを指定しなくても、オプティマイザが自動的に同等の実行計画を立ててくれる。しかし、予想外の全件スキャンを回避できるよう確実を期すためには、USE INDEXオプションの指定があるといいだろう。

これまでの例では、クエリの対象になるテーブルが一つだけであった。しかし、複数のテーブルを結合する場合や、クエリにサブクエリが含まれているような場合には、インデックスを利用して効率よくソート処理を行うためにさらにもう少しだけクエリのチューニングが必要になる。が、話の続きはまた別の機会にブログで紹介しようと思う。今日はここまで！

仕事もブログも切り上げ時が肝心である。