MySQL JOINアルゴリズム詳解
- 0. はじめに
- 1. 用語の説明
- 2. JOINをEXPLAINで分析
- 3. JOINアルゴリズムについて
- ところでMySQLのJOINって遅いよねっていう話をネット上でちらほら見かけるけどどうなの？
- チューニングのポイントをいくつか参考URLで
0. はじめに
この記事で分かること
- JOIN周りの実装から理解し、EXPLAINで具体的な処理が見えるようになる
- JOIN周りのコスト効率が把握できるようになる
- JOIN周りのチューニングができるようになる
想定する実行環境
- MySQL 5.7
- Amazon Aurora MySQL 5.7 Compatibility
- ただし『ハッシュ結合』については取り上げません。また別の機会で説明したいと思います。
注意事項
- タイトルの通りJOINに関係のある話に絞っています
- この記事では公式ドキュメントのsampleデータベースを使用しています https://dev.mysql.com/doc/index-other.html
1. 用語の説明
実行計画に関連する用語
| 用語 | 説明 | 参考URL |
|---|---|---|
| コスト | 処理コスト。小さければ小さいほど良い | |
| EXPLAIN rows | アクセスタイプ(typeフィールド)によってどれだけの行が取得されるかを示す。駆動表についてはクエリ全体によってアクセスされる行数内部表については1行のJOIN毎に平均で何行のアクセスが発生するか | |
| EXPLAIN filtered | 行データが取得されてからさらにWHERE句の検索条件が適用されたときに、どれだけの行が残るかを示す。 | |
| EXPLAIN extra Using index | インデックスにしかアクセスしないことを表すもの | |
| セカンダリインデックス | インデックスツリーのリーフノードにPKが含まれているインデックスのこと | Mikiya Okuno. "知って得するInnoDBセカンダリインデックス活用術！" |
| カバリングインデックス | セカンダリインデックスへアクセスするだけでクエリが解決できる実行計画。とても効率が良い |
JOINに関連する用語
| 用語 | 説明 | 参考URL |
|---|---|---|
| DrivingTable (駆動表) または外部表 | JOINにおいて最初にアクセスされるテーブル。実行計画によって決められるもので必ずしもFrom句のテーブルではない | |
| Inner Table (内部表) | JOINにおいて結合される方のテーブル |
2. JOINをEXPLAINで分析
JOINを含む実行計画の読み方
下にSQLとそのEXPLAINを貼りました。EXPLAINについてJOINに関係あるところだけ見ていきます。
- JOINの場合は上から順番にアクセスが行われている
- idフィールドはそのクエリの実行単位を識別するもの。すべて1だが、MySQLはJOINを一つの単位として実行している。後述のNLJアルゴリズムと関係があります
- 2行目のtypeがeq_refなのでレコードのJOIN毎に1件だけ取得されている
JOIN world.country ON city.countrycode = country.code AND city.id = country.capital行だが、EXPLAINの２行目のkeyフィールドを見るとPRIMARYとあるので、city.id = country.capitalがcityのJOINに使われている- ON句の
city.countrycode = country.codeはWHERE句扱いとなり、cityテーブルの絞り込みに使われている。2行目のExtraにあるUsing whereと対応(この表からはどんなWhere条件が当たっているかまで分からないがJSON形式で見ると書いてある)
SELECT city.name, country.code, countrylanguage.language FROM world.city JOIN world.country ON city.countrycode = country.code AND city.id = country.capital JOIN world.countrylanguage ON countrylanguage.countrycode = city.countrycode;
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | extra |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | SIMPLE | country | NULL | ALL | PRIMARY | NULL | 239 | NULL | 239 | 100 | Using where |
| 1 | SIMPLE | city | NULL | eq_ref | PRIMARY,CountryCode | PRIMARY | 4 | world.country.Capital | 1 | 5 | Using where |
| 1 | SIMPLE | country_language | NULL | ref | PRIMARY,CountryCode | CountryCode | 12 | world.country.Code | 4 | 100 | Using index |
補足. EXPLAINを読むためのテーブル情報
- cityテーブル
- PK: id
- INDEXあり: countrycode
- countryテーブル
- PK: id
- INDEXあり: code
- country_languageテーブル
- PK: (countrycode, language)の複合キー
- INDEXあり: countrycode
EXPLAINはJSON形式の方が情報が多いのでオススメ
MySQL 5.7ではEXPLAINを使うのをやめ、代わりにEXPLAIN FORMAT=JSONを使うのである。
Morgan Tocker. "Optimizer TraceとMySQL 5.7におけるEXPLAIN FORMAT=JSON". Yakstから引用
- 例えば、適用できるWhere句がある場合Extraフィールドに「Using where」と表示されるが、optimizerが勝手にWhere句を生成することがあり、SQLと見比べても、なんでここに「Using where」があるのか、いったい何が適用されているのか分からないことがある。JSON形式で出力すると『attached_condition』という項目があり、具体的に適用されているWhere句を教えてくれる
- MySQLWorkbenchにVisual ExplainというJSON形式を図にしてくれる機能があるので、複雑なSQLなど見るときはまずこれで全体を把握してから細部を調べていくとよいと思います
3. JOINアルゴリズムについて
基本的にMySQLのJOINアルゴリズムは下記の1つしかなく、
- Nested Loop Join (NLJ)
このNLJを一定の条件下でより効率的に働くようにチューニングされたアルゴリズムがあと2つあります。
アルゴリズムの説明に入る前に
駆動表と内部表の定義を押さえておく
JOINの説明で必ず出てくる用語ですが、ここがあやふやだとJOINの説明が全く頭に入ってこないのでしっかり復習します。
駆動表とは、JOINにおいて最初にアクセスされるテーブルです。上の例ではEXPLAINの最初の行にあるcountryが該当します。決してFROM句で指定したテーブルとは限りません。後述のNLJアルゴリズムの説明で出てきますが、駆動表は桁数が少ないほうが効率が良いので、そういった材料を考慮してオプティマイザが決定します。
内部表とは、結合されるほうのテーブルのことです。上の例では、cityとcountry_languageが該当します。
Nested Loop Joinとは
下記URLの説明が詳しいです。
MySQL公式. "8.2.1.10 Nested Loop 結合アルゴリズム"
Nested Loop 結合アルゴリズム
疑似コードを見るとかなり単純な処理ですね。
for each row in t1 matching range {
for each row in t2 matching reference key {
for each row in t3 {
if row satisfies join conditions,
send to client
}
}
}
要点だけ列挙
- ただのネストされたループなのでEXPLAINではidフィールドがすべて1、つまり同一の実行単位として認識されている
- 駆動表の取得桁数が少なければ少ないほうがコスト効率が良い。つまり駆動表の件数が多いとよろしくない
- 外部表(駆動表)、内部表というのは外側のforeach、内側のforeachという意味なのかもですね
どのようなケースで使用されるか
- 残りの二つが特定条件下で有利なNLJのチューニング版なので、基本的にこれが採用される。
メリット
- 処理がシンプル
デメリット
- 駆動表の件数が多いと効率が悪い
- 内部表へのアクセスは何度も行われるためインデックスが使えないと効率が悪い
Block Nested Loopとは
下記URLの説明が詳しいです。
MySQL公式. "8.2.1.10 Nested Loop 結合アルゴリズム"
Block Nested Loop 結合アルゴリズム
for each row in t1 matching range {
for each row in t2 matching reference key {
store used columns from t1, t2 in join buffer
if buffer is full {
for each row in t3 {
for each t1, t2 combination in join buffer {
if row satisfies join conditions,
send to client
}
}
empty buffer
}
}
}
if buffer is not empty {
for each row in t3 {
for each t1, t2 combination in join buffer {
if row satisfies join conditions,
send to client
}
}
}
上記の疑似コードを見ながら簡単に仕組みを説明すると、
- 駆動表からアクセスタイプにしたがって行を取得します(疑似コードだとt1, t2をまずNLJで取得しているようです)
- 取得した行をjoin bufferというメモリ領域に詰めます(メインメモリは有限なのでここでは100件詰められるものと仮定します)
- t3をforeachしてbuffer内の行と突き合わせてJOINしていきます
- (100件詰められると仮定したので)NLJと比べるとt3からの取得回数が1/100になります
どのようなケースで使用されるか
INDEXを使ってJOINができない場合にオプティマイザによって選択されるようです。内部表の取得でディスクアクセスを減らすことが目的
メリット
- ディスクアクセスをできるだけ減らすことで全体のコスト効率をよくする
デメリット
- 内部表がすでにメモリ領域(inndb buffer pool)に上がっている場合は効果が薄い
- バッファに貯めて内部表と比較を繰り返すのでCPUに相応の負荷がかかる
Batched Key Access Joinとは
下記URLの説明が詳しいです。
MySQL公式. "8.2.1.14 Block Nested Loop 結合と Batched Key Access 結合"
簡単に説明すると、MRR(Multi Range Read)というランダムアクセスをシーケンシャルアクセスに整える機構を使ってディスクアクセスするBNJです。
つまり、
Block Nested Loop with MRR
です。
メリット
- ランダムアクセスで読み取り速度が落ちるHDDで効果は抜群だ
デメリット
- 今の時代ほとんどSSDだと思うので効果のほどは❓❓
- MRR自体レコードとアドレスのキャッシュを持っておく必要があるし、効果の薄そうなSSDでこれをやると逆にコスト増になりそう。オプティマイザはハードの種類まで判定しないだろうし、どうやってこれが最適解だと判定されるかまで調査及ばす
ところでMySQLのJOINって遅いよねっていう話をネット上でちらほら見かけるけどどうなの？
ここまでの振り返りとして重くなりそうなケースを考えてみる。
駆動表がFull Scanだと場合によっては重そう
NLJのアルゴリズム上、駆動表の件数が多いと不利なのは見てきた通り。駆動表の件数にもよるが、物理削除などせずどんどん貯まっていく一方の性質のテーブルだと、徐々に重くなっていきそう。
内部表へのアクセスに使えるインデックスがないと重そう
ここにインデックスがないとBNLあるいはBKAがオプティマイザによって検討・採用されると思うが、クエリ改善的な意味ではそもそもインデックス追加を検討したいところ。あくまでBNL、BKAは狙って使うものではなくてNLJが遅い場合の対症療法でしかないと思った。
本当にJOINが遅いのか？
JOIN自体はむしろ、フルスキャンを避けて効果的なインデックスを貼るというSQLチューニングの定石でなんとかなりそうな気がした。
- MySQLはJOINが遅い、非正規化すれば速くなる
- ⼤概遅いのはJOINそのものでなく、ORDER BY狙いのキー や GROUP BY狙いのキーが上⼿く使えてないこと（あるいは、ちゃんと波及させられていないこと）
- NLJの仕組みがわかれば非正規化しなくても⾼速化できるよ
- See also WHERE狙いのキー、ORDER BY狙いのキー
yoku0825. "MySQLアンチパターン". SlideShare から引用
なるほど❓
- youku0825. "Where狙いのキー、order by狙いのキー". SlideShare
- to be continued...
チューニングのポイントをいくつか参考URLで
ちなみにこの記事は分析方法と実装(アルゴリズム)しか扱ってません。そこまで理解できればチューニングの方法はネット上にたくさん転がってます。
FreeBSD pkg installのダウンロードの調子が悪かったので対処した
ここ一週間ほどpkg installを実行するとパッケージのダウンロードが途中で止まりTimeoutすることでインストール失敗する現象が何度も発生しました。
下記がその出力です。下の方にOperation timed outと表示されてインストールが失敗します。
% sudo pkg -d install -y git
DBG(1)[3040]> pkg initialized
Updating FreeBSD repository catalogue...
DBG(1)[3040]> PkgRepo: verifying update for FreeBSD
DBG(1)[3040]> Pkgrepo, begin update of '/var/db/pkg/repo-FreeBSD.sqlite'
DBG(1)[3040]> Fetch: fetching from: http://pkgmir.geo.FreeBSD.org/FreeBSD:12:amd64/quarterly/meta.txz with opts "i"
DBG(1)[3040]> Fetch: fetching from: http://pkgmir.geo.FreeBSD.org/FreeBSD:12:amd64/quarterly/packagesite.txz with opts "i"
FreeBSD repository is up to date.
All repositories are up to date.
DBG(1)[3040]> want to get an advisory lock on a database
The following 17 package(s) will be affected (of 0 checked):
New packages to be INSTALLED:
git: 2.23.0
p5-CGI: 4.44
p5-HTML-Parser: 3.72
p5-HTML-Tagset: 3.20_1
p5-IO-Socket-SSL: 2.066
p5-Mozilla-CA: 20180117
p5-Net-SSLeay: 1.85
p5-IO-Socket-INET6: 2.72_1
p5-Socket6: 0.29
p5-Authen-SASL: 2.16_1
p5-GSSAPI: 0.28_1
p5-Digest-HMAC: 1.03_1
python36: 3.6.9_1
readline: 8.0.0
libffi: 3.2.1_3
p5-Error: 0.17028
cvsps: 2.1_2
Number of packages to be installed: 17
The process will require 142 MiB more space.
22 MiB to be downloaded.
DBG(1)[3040]> Fetch: fetching from: http://pkgmir.geo.FreeBSD.org/FreeBSD:12:amd64/quarterly/All/git-2.23.0.txz with opts "i"
[1/17] Fetching git-2.23.0.txz: 100% 5 MiB 167.3kB/s 00:32
pkg: http://pkg.FreeBSD.org/FreeBSD:12:amd64/quarterly/All/git-2.23.0.txz: Operation timed out
DBG(1)[3040]> release an advisory lock on a database
%
全くダウンロードできないわけではないのでpkg installを繰り返すとインストールを完了させることは可能ですが、依存関係の多いパッケージをインストールする場合は面倒です。下記はgitのインストールを実行していますが、調査の過程でこれに限らずxorgやmysql57-serverなどでも同様の現象が発生したことを確認しました。
最初はネットワーク設定が悪いのかなと思いましたが、curl, portsnapコマンドは正常に動きますし、port collectionからmakeコマンド経由でインストールするとうまくいくんですよね。。
ということで、pkg周りの何かがうまくいってなさそうなので、とりあえずTimeoutするまでの時間を延ばすことに
pkg設定ファイル(/usr/local/etc/pkg.conf)を開いて FETCH_TIMEOUTの値をデフォルトの30から600に変更
FETCH_TIMEOUT = 600; # コメントアウトを外すことを忘れずに
もう一度トライするとメッセージがConnection reset by peerに変わりました。サーバー側からコネクションが切られたようです。今度は向こう側でTimeoutしたのかな？
% sudo pkg -d install -y git DBG(1)[14180]> pkg initialized Updating FreeBSD repository catalogue... ...(省略) DBG(1)[14180]> Fetch: fetching from: http://pkgmir.geo.freebsd.org/FreeBSD:12:amd64/quarterly/All/p5-HTML-Tagset-3.20_1.txz with opts "i" [4/19] Fetching p5-HTML-Tagset-3.20_1.txz: 100% 12 KiB 12.0kB/s 00:01 DBG(1)[14180]> Fetch: fetching from: http://pkgmir.geo.freebsd.org/FreeBSD:12:amd64/quarterly/All/expat-2.2.8.txz with opts "i" [5/19] Fetching expat-2.2.8.txz: 100% 119 KiB 0.4kB/s 05:00 pkg: http://pkg.FreeBSD.org/FreeBSD:12:amd64/quarterly/All/expat-2.2.8.txz: Connection reset by peer DBG(1)[14180]> release an advisory lock on a database %
pkg用のリモートリポジトリの設定ファイル/etc/pkg/FreeBSD.confに記載のあるurl: "pkg+http://pkg.FreeBSD.org/${ABI}/quarterly"のpkg.FreeBSD.orgにブラウザからアクセスしてみると
This is pkg0.kwc.freebsd.org - a Japan regional mirror for pkg(8). It is generously hosted by KDDI Web Communications Inc in Tokyo, Japan. We use MaxMind GeoLite based geo-dns to choose a close mirror for you. IMPORTANT: We do NOT guarantee uptime of any particular mirror. We provide SRV fallbacks for redundancy.
日本にあるpkg向けミラーに繋がったみたいです。このサーバが何かおかしいのかもしれないとアタリをつけてページ下部に他のミラーのurlがあったので
Other mirrors:
pkg0.bme.freebsd.org
pkg0.cyb.freebsd.org
pkg0.isc.freebsd.org
pkg0.jinx.freebsd.org
pkg0.nyi.freebsd.org
pkg0.twn.freebsd.org
pingを打って一番近そうだったpkg0.twn.freebsd.orgに直接アクセスするように設定ファイルを編集したいと思います。
mkdir -p /usr/local/etc/pkg/repos
echo 'FreeBSD: { url: "pkg+http://pkg0.twn.FreeBSD.org/${ABI}/quarterly" }' > /usr/local/etc/pkg/repos/FreeBSD.conf
設定変更したのでトライ
% sudo pkg -d install -y git
DBG(1)[3484]> pkg initialized
Updating FreeBSD repository catalogue...
DBG(1)[3484]> PkgRepo: verifying update for FreeBSD
DBG(1)[3484]> Pkgrepo, begin update of '/var/db/pkg/repo-FreeBSD.sqlite'
DBG(1)[3484]> Fetch: fetching from: http://pkg0.twn.FreeBSD.org/FreeBSD:12:amd64/quarterly/meta.txz with opts "i"
DBG(1)[3484]> Fetch: fetching from: http://pkg0.twn.FreeBSD.org/FreeBSD:12:amd64/quarterly/packagesite.txz with opts "i"
FreeBSD repository is up to date.
All repositories are up to date.
DBG(1)[3484]> want to get an advisory lock on a database
The following 19 package(s) will be affected (of 0 checked):
New packages to be INSTALLED:
git: 2.23.0
p5-CGI: 4.44
p5-HTML-Parser: 3.72
p5-HTML-Tagset: 3.20_1
expat: 2.2.8
p5-IO-Socket-SSL: 2.066
p5-Mozilla-CA: 20180117
p5-Net-SSLeay: 1.85
p5-IO-Socket-INET6: 2.72_1
p5-Socket6: 0.29
p5-Authen-SASL: 2.16_1
p5-GSSAPI: 0.28_1
p5-Digest-HMAC: 1.03_1
python36: 3.6.9_1
readline: 8.0.0
libffi: 3.2.1_3
p5-Error: 0.17028
pcre: 8.43_2
cvsps: 2.1_2
Number of packages to be installed: 19
The process will require 150 MiB more space.
23 MiB to be downloaded.
DBG(1)[3484]> Fetch: fetching from: http://pkg0.twn.FreeBSD.org/FreeBSD:12:amd64/quarterly/All/git-2.23.0.txz with opts "i"
[1/19] Fetching git-2.23.0.txz: 100% 5 MiB 1.1MB/s 00:05
...(省略)
DBG(1)[3484]> Fetch: fetching from: http://pkg0.twn.FreeBSD.org/FreeBSD:12:amd64/quarterly/All/cvsps-2.1_2.txz with opts "i"
[19/19] Fetching cvsps-2.1_2.txz: 100% 44 KiB 44.6kB/s 00:01
Checking integrity...DBG(1)[3484]> Binary> loading /var/cache/pkg/git-2.23.0-b10e56920a.txz
...(省略)
DBG(1)[3484]> Binary> loading /var/cache/pkg/cvsps-2.1_2-0d3f2f1c58.txz
DBG(1)[3484]> check integrity for 19 items added
done (0 conflicting)
DBG(1)[3484]> want to upgrade advisory to exclusive lock
[1/19] Installing p5-HTML-Tagset-3.20_1...
[1/19] Extracting p5-HTML-Tagset-3.20_1: 100%
...(省略)
[18/19] Installing cvsps-2.1_2...
[18/19] Extracting cvsps-2.1_2: 100%
DBG(1)[3484]> release an advisory lock on a database
%
うまくインストールできました。
まとめ: pkgのリモートリポジトリの日本向けミラーの調子が良くなかったのかなと思いました。この症状が発生するまでは問題なく利用できていたため一時的なものと思われるので、うまくダウンロードできるようになったら変更した設定ファイルを元に戻したいと思います。
