🐘

慣れた人間は空のテーブルを相手にEXPLAINの結果を予測できるのか

2021/06/30に公開

1件

「は〜、今日も仕事つかれたなー」と思いながらTwitterを眺めていたらこんなツイートが流れてきました。

空のテーブルを相手にEXPLAINの結果を予測できるか

答えからいうと、「できる」になります。
それも、まーまー大きく外さない精度で予測できるかな、というのが自分の感覚です。

ですが、この感覚が理解できないという人もいるかと思うので、どのような思考順で予測をしているのかを解説してみたいと思います。

サンプルのデータ構造とSQL

ひとまずめちゃくちゃ単純なデータ構造で考えてみます。

このようなテーブルに対し、以下のSQLを投げるとします。

SELECT
  e.id,
  e.name,
  e.department_id,
  d.name
FROM
  employee e
INNER JOIN
  department d
ON
  e.department_id = d.id
WHERE
  d.id = 10;

予測したEXPLAIN

この場合、オプティマイザの気持ちがわかる人間は以下のようなEXPLAINの結果をイメージすると思います。（便宜上MySQLのEXPLAINのフォーマットで記載しますが、他のDBでも大体こんな感じかと）

+----+-------------+-------+-------+---------------+------------+---------+-------+------+-------+
| id | select_type | table | type  | possible_keys | key        | key_len | ref   | rows | Extra |
+----+-------------+-------+-------+---------------+------------+---------+-------+------+-------+
|  1 | SIMPLE      | d     | const | PRIMARY       | PRIMARY    | 4       | const |    1 | NULL  |
|  1 | SIMPLE      | e     | ref   | dept_id_fk    | dept_id_fk | 4       | const |    2 | NULL  |
+----+-------------+-------+-------+---------------+------------+---------+-------+------+-------+

イメージするときのポイントはだいたい次の2つになるかと思います。

駆動表がどちらになるか
内部表へのアクセスにINDEXが使えるか

そして、今回のケースだと

駆動表がどちらになるか　→ department
内部表へのアクセスにINDEXが使えるか → 使える
ということになり、上のようなEXPLAINをイメージすることになります。

このあたりについて、もうちょい細かく見ていきます。

駆動表と内部表の判定

いったんネステッドループを前提として考えますが、ネステッドループの場合は駆動表と内部表というのがありますね。
結合する2表のうち、先にフェッチされる方が駆動表。
駆動表の行と結合される、後からフェッチされる表が内部表です。

2つの表を結合するSQLを受け取ったオプティマイザは、処理コストが小さくなる順番で結合したいと考えています。（考えているわけじゃなく決まったアルゴリズムで計算するわけですが、擬人化した方が親しみやすいかなと）

処理コストには色々な要素が絡みますが、データのフェッチ回数で言えば「行数の少ない表」を駆動表にした方が少なくできます。
まずこの部分がわかりにくい人もいるかもしれないので補足をします。

話を単純にするために、employeeとdepartentにはINDEXがない状態で、全件を結合して取り出すとします。
そして以下のようなデータが入っている状態で、departmentを駆動表にしてネステッドループをした場合の処理内容はこうなります。
（全件取得するならネステッドループじゃなくてソートマージ結合とかハッシュ結合じゃないの？と言いたくなったORACLE技術者の方はいったん黙っててください。おっしゃる通りですが、今は行のフェッチの回数の話なので。）

department → employee の順で結合する場合

departmentの1行目をフェッチ（department.id = 10）
- employeeの1行目をフェッチ（employee.department_id = 10）してdepaertmentの行と結合してクライアントへ返す
- 2行目をフェッチ（employee.department_id = 20）して、結合できないので捨てる
- 3行目をフェッチ（employee.department_id = 30）して、結合できないので捨てる
- 4行目をフェッチ（employee.department_id = 10）して、depaertmentの行と結合してクライアントへ返す
- …
- 10行目をフェッチ（employee.department_id = 10）して、depaertmentの行と結合してクライアントへ返す
1へ戻ってdepartmentの2行目をフェッチ

つまり、departmentから1件フェッチするたびに、employeeの10件をチェックするので、
1件[department] + 10[employee] = 11件
を処理しており、今回のサンプルデータではdepartmentに3行あるので

(1件[department] + 10件[employee]) * 3件 = 33件

が処理される行数になる。

employee → department の順で結合する場合

では今度は逆に、employeeを駆動表にした場合にしてみる。

employeeの1行目をフェッチ（employee.department_id = 10）
- departmentの1行目をフェッチ（department.id = 10）してemployeeの行と結合してクライアントへ返す
- 2行目をフェッチ（department.id = 20）して、結合できないので捨てる
- 3行目をフェッチ（department.id = 30）して、結合できないので捨てる
1へ戻ってdepartmentの2行目以降を繰り返す（10件分）

ということで、employeeから1件フェッチするたびに、departmentの3件をチェックするので
1件[employee] + 3件[department] = 4件
を処理する。
これを10件分くりかえすので

(1件[employee] + 3件[department]) * 10件 = 44件

となる。

件数の少ないdepartmentが駆動表の場合は33件分の処理があり、
件数の多いemployeeが駆動表の場合は44件分の処理があるということで、ネステッドループは件数が少ない方から処理した方がコストが小さいということになります。

はい、ちょっと無理やりなところもありましたが、「件数が少ない方を駆動表にした方がコストが小さい」っぽい、という雰囲気は伝わったでしょうか。

サンプルのテーブルで駆動表・内部表を予測

ではその前提で改めて冒頭のテーブルとSQLを見てみます。

SELECT
  e.id,
  e.name,
  e.department_id,
  d.name
FROM
  employee e
INNER JOIN
  department d
ON
  e.department_id = d.id
WHERE
  d.id = 10;

件数の少ない方が駆動表になります。
とはいえ、今回の命題は「空のテーブルを見て」判断できるかどうかですよね。
サンプルデータ無しで、ER図とSQLだけを見て判断します。
注目したいのはWHERE句ですね。

d.id = 10

とありますので、departmentからidが10の行だけに絞り込みます。
そしてdepartment.id はPRIMARY KEYになっていますからUNIQUE INDEXがありますね。
つまり、departmentからidが10の行を取り出すには、（INDEXのスキャンは必要ですが）ピンポイントで1行だけを取り出せるイメージになります。
それに対し、employeeに対する絞り込み条件はありません。

ON
  e.department_id = d.id
WHERE
  d.id = 10

仮に、結合条件を加味して、 employeeからdepartment_idが10の行だけを取得すると評価できたとしても、employee.department_idはPRIMARY KEYでもUNIQUEでもありませんので、複数件がヒットする可能性があります。

したがって、departmentの方が少ない件数になるであろうと予測できる、ということは駆動表はdepartmentになると予測できることになります。

はい、まずここまでが駆動表と内部表の判断でした。

余談
処理される件数から駆動表を判別しましょう、みたいに書いてきましたが、おそらくもっと感覚的に判別している人も多いかと思います。
それは
「1対多のリレーションシップがあるなら、1側が駆動表」
という考え方です。
格納されているデータやSQLによっても変わることが多いので、精度でいうと若干下がるのですが、以外とこの判別方法でもそこそこ雰囲気は掴めます。
なので、SQLチューニングをするような場面でなければ、大まかにこの捉え方をしている人もいるかなーと思います。

内部表のアクセスにINDEXが使えるか

これは駆動表と内部表の判別ができてしまえば機械的に判断できますね。

駆動表がdepartmentなわけですから、employeeへのアクセスは

ON
  e.department_id = d.id
WHERE
  d.id = 10

この部分が評価されますね。
d.id = 10 でフェッチされた行から e.department_id = d.id でemployeeの行を探すので、つまり employee.department_id = 10 でスキャンすることになります。
であれば、 department_idにINDEXがあるかどうかだけ確認すればOKです。

ちなみに、今回はMySQLでサンプルを作っていますので、FOREIGN KEYを設定したタイミングで暗黙的にINDEXが作成されており、「使える」ということになります。

予測するEXPLAIN

はい、ではここまでの内容から、改めてEXPLAIN（というか処理順）を書き出して見ます。

department.idのINDEXをつかって、 id = 10 の行アドレスを取得（1件分）
行アドレスを元に、departmentから1行を取得する（1件）
employee.department_idのINDEXを使って、 department_id = 10 の行アドレスを取得する（複数件分）
行アドレスを元に、employeeからn件目を取得し、結合した結果を返す（これを行アドレスの件数分繰り返す）

こんなイメージですね。
これをEXPLAINの形で表現すると

+----+-------------+-------+-------+---------------+------------+---------+-------+------+-------+
| id | select_type | table | type  | possible_keys | key        | key_len | ref   | rows | Extra |
+----+-------------+-------+-------+---------------+------------+---------+-------+------+-------+
|  1 | SIMPLE      | d     | const | PRIMARY       | PRIMARY    | 4       | const |    1 | NULL  |
|  1 | SIMPLE      | e     | ref   | dept_id_fk    | dept_id_fk | 4       | const |    2 | NULL  |
+----+-------------+-------+-------+---------------+------------+---------+-------+------+-------+

こんな感じになるわけです。

結論

「慣れた人間は空のテーブルを相手にEXPLAINの結果を予測できるのか」

答えはYesです。
むしろ、慣れていなくてもある程度理屈で予測することができると言ってもいいですね。

そして、これは結合するテーブルが3つでも4つでも基本的には同じ考え方で予測ができます。
とにかく、結合したいテーブル達の中で、駆動表になるのはどれかを判別します。
ようするに少ない行数に絞り込みができる表を探します。
あとはそこから順番に辿っていけばOKです。

スタースキーマとかの場合はどうなるの？

ね！
ですよね！（何が）

これについては空のテーブルで予測できる人がいたら、むしろどこをポイントとして見ているのか教えてもらいたいです。

最後に

今回自分の中のイメージをざざざっと書き出したので、データベース・モヒカン達が大挙して間違いや曖昧な表現を正してくれると期待しています。
そのついでに、他の手段で予測しているよというのも教えて頂けたらありがたいです。
特にMySQLなどOSSな製品については、ソースのここでこんな判断してるよ！とか詳しく解説してくれる人がいたら本当にありがたい。
ふわっとイメージでしか理解できていないので、たくさんの修正、指摘を待ってます！

Discussion

TomoProg 2023/05/27に更新

読ませていただきました。
駆動表には行数が少ない方を選択した方がよいというのをよく聞いていましたが、「駆動表と内部表の判定
」のところを読んで理解が深まったと思います。
駆動表の選択も結局DB側が考えてくれるのであれば、開発者側はあまり意識しなくてもいいのかな？と思いながら読んでいました。

あと、計算が間違っているのではないかと思うところがあったため、こちらに記載させていただきます。

employee側を駆動表にした場合のフェッチ件数の計算のところです。
(1件[employee] + 3件[department]) * 10件 = 44件
と書かれていますが、40件だと思われます。