Order Byを制して一覧表示を速くする

対象読者

• Webアプリケーションエンジニア
• SQLチューニングの基本を学習ずみ

使用環境

• MySQL ５.6

一覧表示の抱えるリスク

webアプリケーションにおけるデータの一覧表示処理は、SQLが遅くなる可能性の高い処理です。
時間が経つとともにデータが増え、複数のテーブル結合で走査件数が多くなりやすいことに加え、大抵の場合、ソート機能を備えているからです。
このソート処理は、走査件数が多くなるほどにコストが非常に高まってくる問題児です。
この記事ではそんなソート処理への対策について、自分自身の理解を深めるためにも内容をまとめてみたいと思います。

大規模のデータの全件を処理するとコストが高いので、ページングなどでLIMIT句をつけると良いと考えても、LIMIT句が適用されるのはSQL評価順序の最後なので、その前に処理時間のかかる箇所があると改善されません。
遅い箇所を調べていくのですが、SQLがORDER BYしているならば、まずはORDER BY句の列にインデックスが定義され、それが使えているかどうかをチェックするのが良いと思います。

インデックスとソートの関係について

インデックスは並び替えられた状態でデータを持っているため、Order By句に指定した列のインデックスからデータをフェッチできている場合は、その時点でソートは完了します。
しかし、そうでない場合は、毎回メモリ内でソート（クイックソート）を行うので、データ量が多くなったとき、大変遅くなってしまいます。
そのため、ソート列にインデックスを定義することと、それが使用されるようにすることが対処の要点になります。

悪玉ソート処理の確認

explainステートメントを発行したとき、key欄に並び替え列のインデックスの表示がなく、Extra欄に「filesort」表示があるなら、インデックスが使用されずにDBサーバのメモリ内でソートされています。これは年老いてから（レコードが増えてから）の癌となるソートです。
データ量の多くなった時にshow profileステートメントで、「Creating sort index」の項を確認すれば、相当な時間がかかっていることが確認できると思います。
※データ量が少ないときはインデックスが使われないので「filesort」表示されますが、これは問題ありません。

複合インデックスが必要でないか

並び替え列にインデックスが使われていなければ、まずWHERE句等でテーブルに対して先に別のインデックスが使われていないかを確認します。MySQLの場合、1テーブル1インデックスしか使うことができないためです。
先に別のインデックスが使われてしまっている場合、複合インデックスを追加できるかどうか検討しましょう。WHERE句はORDER BY句より先に評価されるので、WHERE句の列, ORDER BY句の列の順番で定義します。

複合インデックスで並び替える

SELECT * FROM t1 LEFT JOIN t2 ON t1.t2_id = t2.id
WHERE t1.type = 1
ORDER BY t1.日付 DESC
/* 
 t1.type単体のインデックスが存在する場合、t1.日付のインデックスはNG
 t1.type, t2.日付の複合インデックスならOK 
*/

ORDER BYは駆動表の列で指定されているか

他に使われるインデックスがない状態でORDER BY句のインデックスが使われていなければ、その並び替え列が駆動表の列で行われているかどうかを確認します。駆動表は、LEFT JOINであれば先に指定したテーブルです。
結合しているクエリで並び替え列を、駆動表の列でなく、内部表の列で指定すると、インデックスを定義していても並び替えに使われず、explainのExtra欄に「filesort, using temporary」と表示されてしまいます。

JOIN先のテーブル（内部表）で並び替えはNG

SELECT * FROM t1 LEFT JOIN t2 ON t1.t2_id = t2.id
ORDER BY t2.日付 DESC

JOINは駆動表が親ループの集合となるので、並び替えされたインデックスフェッチで親ループの集合が作成できると、並び替えの必要がなくなりますが、内部表のインデックスフェッチでは、そこで並び替えは完了できません。結合が終わってから改めて並び替え（一時テーブルを作成してクイックソート）する必要があります。
以下の疑似コードで説明します。

ネステッドループ結合の疑似コード

/*
  駆動表の作成にORDER BY句のインデックスを参照できると、そこで並び替え完了
*/
t1 = indexFetch(t1, "日付")
for each row1 in t1.filter(it => { return it.col == joinKey } {
  /*
    内部表の作成でORDER BY句のインデックスを参照しても、全体の並び替えはできない
    t2 = indexFetch(t2, "日付")
  */
  for each row2 in t2.filter(it => { return it.col == joinKey } {
    sendClient(row1, row2)
  }
}

SQLでの評価順では、ORDER BY句はJOIN句よりも後ですが、ORDER BY句の定義であってもそのインデックスが使える場合はインデックスフェッチにより、「先に並び替え」が実行されるというのがポイントかと思います。
全件の処理ではなく、インデックスの他に結合条件・検索条件でフェッチできる状況では、
インデックス → 結合 → 検索
の順番で絞り込み処理がされるので、後続の負担が減らせるよう早い段階での絞り込みができれば、より効果的となります。
全体のフェッチにかかった時間は、show profileを実行し、「Sending data」の表示で確認することができます。

ちなみに、外部結合ではなく内部結合では、駆動表がオプティマイザの判断次第になるため、駆動表を固定するために、INNER JOINの代わりにSTRAIGHT_JOINを使った方が良いです。

内部結合でもSTRAIGHT_JOINなら、t1は駆動表になることが保証される

SELECT * FROM t1 STRAIGHT_JOIN t2 ON t1.t2_id = t2.id
ORDER BY t1.日付 DESC

ORDER BYのみのインデックスでLIMITを効かせる

さきほどの項で、駆動表でORDER BYインデックスを貼り、それが使われる時は最初に評価されることが分かりました。
これにより、LIMITを効かせることができます。並び替えしてるに関わらず、結果は爆速です。

select * from t1
order by 日付
limit 100;

しかし、ことは簡単にはいかず、ほとんどのユースケースでは、絞り込みの条件を追加すると思います。
その場合に注意が必要です。

select * from t1
where ... /* 追加の条件。テーブル内で一致する列値が少ない場合は注意が必要 */
order by 日付
limit 100;

この方法では、最初にインデックス内で日付の並び替えを行ってから、条件に合う行を100行見つけた時点で処理を終了しています。
（通常のOrder Byで最後に並び替えた場合と比較した時、同じ日付間での並び順が異なる場合があります。）

上記の日付以外に追加する条件が、一致する列値がテーブル内に少ない（カーディナリティが高い）ものである場合は、日付にインデックスがあることで、余計に時間がかかったりします。
全体を先に並び替えた後、一致する100件を見つけるのに時間がかかる感じです。

MySQLでは原則1テーブル1インデックスしか効かないので（インデックスマージが適用される場合もありますが）、追加の条件に一致する列値が少ない場合はOrder Byをあきらめ、インデックスはWHERE句に貼った方が良いと思います。
または、[日付, カーディナリティの高い条件列]で複合インデックスを貼れば、インデックス内にデータを持つので、その条件の検索では速くすることができます。

GROUP BYのソートに注意しているか

GROUP BYによっても、暗黙的にソートが発生します。通常、GROUP BYのキーでインデックスフェッチしたいところですが、もしインデックスを作成していない、作成していても使えない等の理由でこれが無理な場合は、ORDER BY NULL指定をすることで、GROUP BYによる暗黙ソートを止めることできます。(MySQL8.0ではこの暗黙ソートが無くなるとのことです）
また、GROUP BYで必要な並び替えが終わっている場合は、不要なORDER BYをしていないかどうかも確認しましょう。

SELECT * FROM t1 LEFT JOIN
(
 /* 日付キーにインデックス作成できない時、暗黙の並び替えを防いでおく */
 SELECT * FROM t2 GROUP BY 日付 ORDER BY NULL
) as grouping_t2
ON sorted_t2.id = t2.id

今回は件数の多いデータを処理するために、まずソート処理の問題解決を図ることが効果的であることを書きました。
ちょうどSQLチューニングネタで記事を書きたいと思っていたところに、こちらの素晴らしい記事に触発されました。。
ソート以外にも書くつもりでしたが、まとまらなかったので、一旦打ち切ることにします。
また機会があれば書いてみたいと思います。

参考文献

http://nippondanji.blogspot.com/2009/03/using-filesort.html
https://www.slideshare.net/yoku0825/whereorder-by