Using filesort

去年ソートに関する記事を書いたが、今日はその続きである。

MySQLでEXPLAIN SELECT...を実行するとExtraフィールドでよく見かける「Using filesort」という文字列。Filesortって一体なんだろう？と思ったことはないだろうか。単刀直入に言ってFilesortの正体はクイックソートである。

クエリにORDER BYが含まれる場合、MySQLはある程度の大きさまでは全てメモリ内でクイックソートを処理する。ある程度の大きさとはsort_buffer_sizeであり、これはセッションごとに変更可能である。ソートに必要なメモリがsort_buffer_sizeより大きくなると、テンポラリファイル（テンポラリテーブルではない）が作成され、メモリとファイルを併用してクイックソートが実行される。

Filesortは全てのソート処理において実行されるわけではない。前回の記事ではソート処理でインデックスを利用できる場合について紹介したが、つまりインデックス順で行をフェッチすることが出来ればFilesortは必要ないわけである。そのような場合にはExtraフィールドにUsing filesortは現れないので、ソートではインデックスが利用されるようにクエリおよびテーブルをチューニングしよう。

テーブルが一つの場合、つまりJOINを利用しない場合のソートについては前回の記事でだいたいの場合を網羅しているのだが、JOINを利用する場合にはまた別のチューニングテクニックが必要になる。Filesortは複数のテーブルを一度にソートする事は出来ない。従って複数のテーブルをJOINする場合には、ソートを行うタイミングには2つの場合が考えられる。JOINの最初のテーブルをソートしてからJOINするか、もしくはJOINをした結果をソートするかである。前者の場合はさらにソート処理をFilesortを用いるかインデックスを利用するかという2通りに分けられるので、計3通りの手法がMySQLには実装されている。（JOINした結果にはインデックスがないので、JOINした結果に対してソートするときは常にFilesortである。）

このことについて、MySQLのオプティマイザの開発者であるセルゲイさんが自身のブログでわかり易く解説してくれているので、彼の画像を引用して解説したいと思う。引用を快諾してくれたセルゲイさんありがとう :)

まずは最初のテーブルをインデックスを用いてソートして、それからJOINするパターン。


次は最初のテーブルをFilesortしてからJOINするパターン。


そして全てのテーブルをJOINしてからFilesortをするパターンである。


単純明快！図を見ればどのようにソートが行われているかが一目瞭然である。なので下手な解説はしないでおこう。詳細が気になる人はセルゲイさんのブログを見て欲しい。（英語だけど）どの実行計画になっているかはEXPLAINのExtraフィールドを見れば分かる。

• 最初のテーブルをインデックスを用いてソートして、それからJOINするパターン・・・Using filesortの表示がない。
• 最初のテーブルをFilesortしてからJOINするパターン・・・EXPLAINの最初の行にUsing filesortの表示。
• 全てのテーブルをJOINしてからFilesortをするパターン・・・EXPLAINの最初の行にUsing temporary; Using filesortの表示。
  

もちろん後になればなるほど処理が重くなるので、出来るだけそのようなクエリはさけて1番目や2番目の実行計画になるようにすると良いわけである。1番目や2番目の実行計画になるようにするには、次のような点に注意しなければいけない。

最も大切なことはWHERE句における検索条件とソートする対象のカラムを一つのテーブルに集中させることである。例えば以下のようなクエリならばUsing temporary; Using filesortを避けられる。

SELECT ... FROM tbl1,tbl2,tbl3
WHERE tbl1.col1 = 100
AND tbl1.col3 = tbl2.col1 AND tbl2.col2 = tbl3.col1
ORDER BY tbl1.col2;

この場合、もし(col1,col2)というインデックスがあればインデックス順に行をフェッチできるし、そのようなインデックスがない場合にはFilesortでソートが実行される。

次のようなクエリはUsing temporary; Using filesortになってしまうのでNGだ。

SELECT ... FROM tbl1,tbl2,tbl3
WHERE tbl1.col1 = 100
AND tbl1.col3 = tbl2.col1 AND tbl2.col2 = tbl3.col1
ORDER BY tbl2.col1;

※WHERE句ではtbl1.col1を指定しているが、ORDER BYではtbl2.col1という別のテーブルのカラムを指定している。これではJOINを行ってから最終的にソートするしかないわけである。

WHERE句で多数のテーブルにおいて検索条件を指定していると、必ずしもORDER BYで指定したテーブルからJOINされない場合がある。そのような場合には、STRAIGHT_JOINチューニングヒントを使ってJOINの順序を固定するといいだろう。

SELECT STRAIGHT_JOIN... FROM tbl1,tbl2,tbl3
WHERE tbl1.col1 = 100
AND tbl2.col1 = 100 AND tbl2.col3 = 200
AND tbl3.col2 IN (1,2,3)
AND tbl1.col3 = tbl2.col1 AND tbl2.col2 = tbl3.col1
ORDER BY tbl1.col2;

複数のテーブルをJOINする際にもう一つ気をつけなければならないのはLIMIT句である。JOINでは最終的な行数がどれだけになるかということは、一番目のテーブルから行をフェッチした段階では分からない。例えばtbl1でフェッチした行に対してtbl2またはtbl3に該当する行がない場合に行数が減る場合もある（INNER JOINのみ）し、tbl2またはtbl3で複数の行がマッチした場合には行数が増える場合があるからである。従って、いずれのパターンにおいてもLIMIT句が適用されるのはJOINとソートが完了した後なのである。

LIMIT句が最後に適用されるということで問題になるのは、LIMITする前の結果セットが巨大な場合である。LIMIT 100が指定されているクエリにおいて、JOINした結果が全部で1万行になってしまったとしよう。最終的には先頭の100行しかクライアントへ返されることはないので、残りの9900行は無駄になってしまう。この様な無駄を作らないためには、JOINした結果が大きくならないようなクエリを書くしかない。出来ることなら、複数のテーブルをJOINするときにはLIMITで行数を絞ろうと考えないのがいい。

JOINの種類がLEFT JOINまたはRIGHT JOINの場合で、

• 最初のテーブルにしか検索条件がない
• 最初のテーブルをフェッチした段階で結果行が多くなってしまう

というような場合には、サブクエリの内部でLIMITを用いるという対策が可能である。

SELECT ... FROM
(SELECT * from tbl1 WHERE ...検索条件... ORDER BY col1 LIMIT 100) AS tbl1
LEFT JOIN tbl2 ON tbl1.col3 = tbl2.col1 LEFT JOIN tbl3 ON tbl1.col3 = tbl3.col1
ORDER BY tbl1.col1 LIMIT 100;

サブクエリの中とクエリ全体で同じソート条件を指定しているのがミソである。ソート処理が2回行われることになるが、1万行をJOINしてから全体をソートするより、先に行を絞り込んでおけば無用なJOINを避けられるのでかなり効果的である。（2度目のソートは1万行よりずっと少ない場合が多いだろう。）

上記以外の場合、例えばtbl2やtbl3でWHERE句による絞り込みが行われているような場合にはこの方法は使えない。また、tbl1を先に100行に絞り込んだとしても、tbl2やtbl3で行数が大幅に増えてしまうような場合にもこの方法はあまり有効ではない。（tbl2やtbl3を主キーやユニークキーでJOINするならOKである。）また、INNER JOINの場合もtbl2やtbl3に該当する行が存在しない場合があるのでサブクエリでの対策は難しい。しかしtbl2やtbl3に50%程度の確率で該当する行が存在するような場合、サブクエリ内のLIMITを少し多め（500など）に設定してやることで近似的な結果を得ることが可能である。（近似的とは、本来JOINした結果が100行以上あるような場合でもサブクエリ内でLIMIT 500を指定したため、tbl2やtbl3においてマッチする行が少ない場合には結果が100行未満になってしまうことがあるということである。）アプリケーション次第であるが、結果の正確さよりも性能を重視する場合にはこのような最適化も検討するといいだろう。

まとめ。

以上の話をまとめると次のようになる。

• Filesortとはクイックソートのことである。
• JOINにおいてORDER BYが指定されているとき、ソートが行われるタイミングは3種類ある。
• Using filesortがEXPLAINに出ていないときはインデックスを用いてソートが行われている。（最も高速。）
• Using filesortだけがEXPLAINの最初の行に出ている時は、先にソートしてからJOINが実行されている。
• Using temporary; Using filesortがEXPLAINの最初の行に出ている時は、先にJOINしてからソートされている。（最も遅い。）
• WHERE句による検索条件とORDER BYにおけるソート条件は、一つのテーブルに集中させる。
• JOINにおいてソート処理する場合には、LIMIT句が適用されるのはJOINとソートが完了した後である。
• LEFT/RIGHT JOINの場合には、LIMIT句の問題はサブクエリである程度対策が可能である。