$shibayu36->blog;

クラスター株式会社のソフトウェアエンジニアです。エンジニアリングや読書などについて書いています。

MySQLのfilesortは何ソートで行われているのか

　最近、CourseraのArgorithms, Part1という講義を受けている。そこでソートの講義を受けて、そういえばMySQLのORDER BYでfilesortになったときってどのソートが使われているのだろうと気になってきたので調べてみた。

　調べてみると非常に難解で、結局いまいち分からなかったが、今の段階の調べた内容をひとまず書いておく。MySQLのコードを読んだのも初めてで、しかもちゃんと読み解くことができなかったので、情報が間違っている可能性も非常に高い。間違ってたら指摘してもらえるとうれしいです。

調査結果

最初に調査結果を書いておく。たぶんこれは非常に単純化したもので、詳しく見るともっといろいろチューニングされてそう。

  • sort_buffer_size以内のメモリ量でソートが可能な場合、メモリ内でのみソートされる
  • ソートにsort_buffer_size以上のメモリが必要な場合、sort_buffer_sizeでメモリが足りる単位でメモリ内ソートが行われ、それぞれの結果を一時ファイルに書き出す。最後に一時ファイルからマージソートする
  • メモリ内のソートには、クイックソートか、Priority Queueを使ったTop-kソートが用いられる
  • ソートしなければならない行数が、最終的に必要な行数の3倍を超える時、Priority Queueを使ってソートされる。そうでなければクイックソートが使われる

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を使ったほうが良い

という風に見えた。

　このあたりのコード、かなり難しくて、本当に今回調べた結果が正しいのか分からない...

参考

まとめ

　アルゴリズムでソートの勉強をしていて、ふとMySQLのfilesortはどうやっているんだろうと気になったので、軽く調査をしてみた。MySQLのコード初めて読んだのだけど、非常に難しくて正しく読み解くことが出来たか怪しい。間違っている可能性も大いにあるので、何かおかしいことがあれば指摘してもらえるとうれしいです。

Emacsでvirtualenvに入れたライブラリも考慮したPythonの補完環境を作る

tech python

　新言語を使うときは、その言語の補完ができるかどうかで学習効率が変わってくるので、ひとまずPythonの補完環境を作った。基本Pythonではvirtualenvを使うのが一般的なようなので、環境ごとに入れたライブラリも考慮して補完できるようにした。

　色々調べたところ、次の三つを使うのが良さそうだった。

  • python-mode
  • jedi
  • auto-virtualenvwrapper

今回の設定で以下のように補完が出来るようになった。

f:id:shiba_yu36:20170402145819g:plain

python-mode

　とりあえず編集モードを入れる。M-x package-install RET python-mode RETしたあと、以下の設定を入れる。

(require 'python-mode)
(setq auto-mode-alist (cons '("\\.py\\'" . python-mode) auto-mode-alist))

jedi

　Pythonの補完なら、Jedi というのが良さそうに見えた。Emacsでの入れ方は http://tkf.github.io/emacs-jedi/latest/ に書かれていたので、このページに従ってインストールした。

　まずvirtualenvを自分がメインで使っているPython環境に入れる。

$ pip install virtualenv

　Emacsにjedi.elを入れる。

M-x package-install RET jedi RET

　以下の設定を追加する。

(require 'jedi)
(add-hook 'python-mode-hook 'jedi:setup)
(setq jedi:complete-on-dot t)

　最後にM-x jedi:install-serverして完了。

auto-virtualenvwrapper

　以上でPythonの補完が出来るようになった。しかし今のままだとグローバルなPython環境のみ見て補完してくれるだけだった。Pythonではプロジェクト単位でvirtualenvを用いるのが一般的なようなので、virtualenvの環境にインストールしたライブラリも見て補完できるようにしておきたい。

　それを実現するには virtualenvwrapper.el というのを使えば良いみたい。さらに auto-virtualenvwrapper.el というのを使うと、プロジェクトのファイルを開いた時に自動でvirtualenvの環境を切り替えてくれるようだった。

　まずはvirtualenvwrapper.elとauto-virtualenvwrapper.elをインストール。

M-x package-install RET virtualenvwrapper RET
M-x package-install RET auto-virtualenvwrapper RET

　以下の設定を追加すると、自動でvirtualenvの環境を切り替えてくれるようになる。

(require 'virtualenvwrapper)
(require 'auto-virtualenvwrapper)
(add-hook 'python-mode-hook #'auto-virtualenvwrapper-activate)

まとめ

　今回の設定で、virtualenvにいれたライブラリも考慮したPythonの補完環境を作れた。ここにたどり着くまでに結構時間がかかってしまったけど、補完がうまくいくようになって良かった。

zsh-autoenvを使って、virtualenvの自動activate/deactivateを実現する

tech python

　pyenv + venvでPython3環境を構築する - $shibayu36->blog; の記事で、特定のPythonプロジェクト用のvirtualenv環境を導入することが出来ました。しかし、このプロジェクトに入るたびにsource venv/bin/activateし、逆に抜ける時にdeactivateするのは

  • 面倒
  • どう考えても実行を忘れる

という問題があります。

　そこでzsh-autoenvというzshプラグインを使って、自動でactivateとdeactivateを出来るようにしたのでメモしておきます。

zplugを導入する

今回の本題から外れますが、zshのプラグインの管理ツールをこれまで入れてこなかったので、この機会にzplugを導入しました。

$ curl -sL --proto-redir -all,https https://zplug.sh/installer | zsh

でインストールし、下記設定をするだけの簡単導入でした。

# ---------------- setting for zplug --------------------------
source ~/.zplug/init.zsh

# zsh-autoenvのインストール
zplug "Tarrasch/zsh-autoenv"

# Install plugins if there are plugins that have not been installed
if ! zplug check --verbose; then
    printf "Install? [y/N]: "
    if read -q; then
        echo; zplug install
    fi
fi

# プラグインを読み込み、コマンドにパスを通す
zplug load --verbose

zsh-autoenvを使って自動でactivateとdeactivateを出来るように

　zsh-autoenv とは、

  • ディレクトリに.autoenv.zshを置いておくと、そのディレクトリ以下に入った時に自動でそのファイルを実行してくれる
  • ディレクトリに.autoenv_leave.zshを置いておくと、そのディレクトリから抜ける時に自動でそのファイルを実行してくれる

というものです。これを使えば

が実現できますね。

インストール

　先程zplugを導入したので、.zshrcに以下を追加するだけです。

zplug "Tarrasch/zsh-autoenv"

venv環境を作る

　以下のコマンドでvenv環境を作ります。

$ mkdir python-playground
$ cd python-playground
$ python -m venv venv

これでpython-playground/venvディレクトリ下にpythonの環境が作られました。

zsh-autoenvの設定を行う

　python-playgroundディレクトリにて以下のコマンドを実行し、.autoenv.zshと.autoenv_leave.zshを用意します。

$ echo 'source venv/bin/activate' > .autoenv.zsh
$ echo 'deactivate' > .autoenv_leave.zsh

　これでディレクトリに入ったらactivateし、ディレクトリから出たらdeactivateされるはずです。

確認する

　ではこのディレクトリに入ってみます。

$ cd python-playground
Attempting to load unauthorized env file!
-rw-r--r--  1 shibayu36  staff  25 Apr  1 21:20 /Users/shibayu36/development/src/github.com/shibayu36/python-playground/.autoenv.zsh

**********************************************

source venv/bin/activate

**********************************************

Would you like to authorize it? (type 'yes') yes
$ which python
/Users/shibayu36/development/src/github.com/shibayu36/python-playground/venv/bin/python

　初回はファイルを実行してよいか聞かれるのでyesと答えます。which pythonすると、ディレクトリ配下のpythonを示すようになっているので、cdでディレクトリに入っただけでvirtualenvのactivateがされるようになりました。


　逆にディレクトリを出てみます。

$ cd ..
Attempting to load unauthorized env file!
-rw-r--r--  1 shibayu36  staff  11 Apr  1 21:20 /Users/shibayu36/development/src/github.com/shibayu36/python-playground/.autoenv_leave.zsh

**********************************************

deactivate

**********************************************

Would you like to authorize it? (type 'yes') yes
$ which python
/Users/shibayu36/.anyenv/envs/pyenv/shims/python

　こちらも初回は確認が出るのでyesと答えます。そうするとディレクトリを出るだけでpyenvのpythonを指し示すようになり、自動でdeactivateされるようになりました。

まとめ

　今回はzsh-autoenvを使って、ディレクトリに入った時に自動でvirtualenvをactivateし、ディレクトリから出た時に自動でdeactivateするということをしてみました。zsh-autoenvは他にもいろいろと使えそうで良いですね。