最近、CourseraのArgorithms, Part1という講義を受けている。そこでソートの講義を受けて、そういえばMySQLのORDER BYでfilesortになったときってどのソートが使われているのだろうと気になってきたので調べてみた。
調べてみると非常に難解で、結局いまいち分からなかったが、今の段階の調べた内容をひとまず書いておく。MySQLのコードを読んだのも初めてで、しかもちゃんと読み解くことができなかったので、情報が間違っている可能性も非常に高い。間違ってたら指摘してもらえるとうれしいです。
調査結果
最初に調査結果を書いておく。たぶんこれは非常に単純化したもので、詳しく見るともっといろいろチューニングされてそう。
filesortは基本的にクイックソートとマージソートの組み合わせ
MySQL :: MySQL 5.6 リファレンスマニュアル :: 8.2.1.15 ORDER BY の最適化 を見てみると、filesortのアルゴリズムが書かれていた。これによると、filesortのアルゴリズムには、﹁元のアルゴリズム﹂と﹁変更されたアルゴリズム﹂の二つがあるらしい。﹁変更されたアルゴリズム﹂は﹁行を2回読み取ることを回避する最適化が行われたもの﹂らしいので、今回は考えないことにして、﹁元のアルゴリズム﹂の内容を見てみる。
﹁元のアルゴリズム﹂は次のステップで進むらしい。
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 ソースファイルにあります。
単純に書くと
●sort_buffer_sizeに収まりソートできるなら、quicksortが実行され、結果として返される
●収まらないなら、分割してquicksortした結果を一時ファイルに書き出しておき、最後にマージソートしていく
というイメージだろうか。
メモリ上でソートするなら、クイックソートは計算時間も速く、かつ無駄な空間も使わないので効率的である。また一旦ファイルに書き出したソート済配列を結合するなら、シーケンシャルに先頭から見ていけばソートが完了するマージソートの手法が効率的である。これからクイックソート+マージソートの組み合わせになるのは自然だなと感じた。
メモリ内のソートはクイックソートでなく、Priority Queueを使ったソートが使われる時もある(?)
以上の知識を持って、filesortのコード を読んでみると、なぜかPriority Queue sortという文字列が出てきて混乱している。https://github.com/mysql/mysql-server/blob/567bb732bc0e2de38f10c1793dcc0a0c6f877742/sql/filesort.cc#L1313 あたり。
Priority Queueを使うと、n個の中から上位k個を取り出すTop-k sortという手法が使われることになり、この時間計算量はO(n * log(k))となる。クイックソートの時間計算量はO(n * log(n))なので、nが大きくkが小さい時、つまりたくさんの候補の中から取り出したい数が少ないときは、クイックソートよりPriority Queueを使ったほうが速いように見える。
この辺りの前提から考えると、WHERE句でそこまで絞り込まれない時(nが大きい時)に、LIMIT句が指定されて取り出したい個数が少ない時(kが小さい時)に、クイックソートの代わりにPriority Queueを使うイメージだろうか。
軽くコードを見てみると
●計測してみるとクイックソートよりPriority Queueのソートのほうが3倍ほど遅いことが分かっている
●なので、LIMITで指定した数に対して、候補となる件数が3倍以上になるなら、クイックソートよりPriority Queueを使ったほうが良い
という風に見えた。
このあたりのコード、かなり難しくて、本当に今回調べた結果が正しいのか分からない...
