dependent subquery と left join

mysql subquery

今日はもう一つ。

以前書いた日記 "Not Exists" なクエリの最適化 のブックマークコメントで、id:bull2さんから「subquery 使った方がいいんじゃないか」という意見をいただいてました。

もともと MySQL 4.0 ばっかり使っていたので、あのエントリを書いた時点ではそもそも subquery を使うという発想が出てきてませんでした。で、 subquery を使った場合と得られる結果が本質的に同じならば、賢い MySQL さんが速いほうに勝手に書き換えてくれるはずなので、好きなほうを書けばいいことになります。すなわち書くのが簡単な subquery のほうが絶対いいですよね!

というか、そもそもあのエントリは「"NOT EXISTS" なんていうのを実行計画でちゃんと考えているんだすげー」って話であって、最適なクエリを書くにはどうすればいいかって話ではないんですけどね…。

explain してみた

ということで、explainしてみました。ちなみに

mysql> pager tr '+' '|' | cut -f3-5,7- -d'|'

してます。

もとのクエリ (left outer join)
mysql> explain SELECT t1.user_id FROM test AS t1 LEFT JOIN test AS t2
    -> ON t1.user_id = t2.user_id AND t1.item_id = 200 AND t2.item_id = 100
    -> WHERE t1.item_id = 200 AND t2.item_id IS NULL;
-------------|-------|--------|---------|---------|----------------------|------|--------------------------------------|
 select_type | table | type   | key     | key_len | ref                  | rows | Extra                                |
-------------|-------|--------|---------|---------|----------------------|------|--------------------------------------|
 SIMPLE      | t1    | index  | PRIMARY | 8       | NULL                 |    3 | Using where; Using index             | 
 SIMPLE      | t2    | eq_ref | PRIMARY | 8       | aho.t1.user_id,const |    1 | Using where; Using index; Not exists | 
-------------|-------|--------|---------|---------|----------------------|------|--------------------------------------|
subquery版

コメントでいただいたSQLとほぼ同じやつです。

mysql> explain SELECT t1.user_id FROM test AS t1
    -> WHERE t1.item_id = 200 AND NOT EXISTS
    -> (SELECT * FROM test AS t2 WHERE t1.user_id = t2.user_id AND t2.item_id = 100);
--------------------|-------|--------|---------|---------|----------------------|------|--------------------------|
 select_type        | table | type   | key     | key_len | ref                  | rows | Extra                    |
--------------------|-------|--------|---------|---------|----------------------|------|--------------------------|
 PRIMARY            | t1    | index  | PRIMARY | 8       | NULL                 |    3 | Using where; Using index | 
 DEPENDENT SUBQUERY | t2    | eq_ref | PRIMARY | 8       | aho.t1.user_id,const |    1 | Using index              | 
--------------------|-------|--------|---------|---------|----------------------|------|--------------------------|
2 rows in set (0.00 sec)

subqueryの場合はselect typeに "DEPENDENT SUBQUERY" とあります。これはなにかというと、

For "DEPENDENT SUBQUERY", the subquery is re-evaluated only once for each set of different values of the variables from its outer context.

http://dev.mysql.com/doc/refman/5.1/en/explain.html

ということで、subqueryの中のselectがt1.user_idの数だけ再評価されるそうです。まあ、えらく真っ当な…。

詳しく追ってはいないですが、少なくとも user_id の種類が多い (cardinalityが大きい) ときは subquery 版は遅くなりそうな気がしました。

何にしても、2つのクエリはMySQLにとっては等価なものとは思ってくれないようでした。(NOT NULLなカラムの有無とかもあるし。)

もうちょいsubquery

なんてことでsubquery慣れしてない自分はリファレンスマニュアルのsubqueryのところを読んでいたわけですが、ほぼそのままなことがリファレンスに書いてありました!

The queries:
SELECT * FROM t1 WHERE id NOT IN (SELECT id FROM t2);
SELECT * FROM t1 WHERE NOT EXISTS (SELECT id FROM t2 WHERE t1.id=t2.id);
Can be rewritten using IN():
SELECT table1.* FROM table1 LEFT JOIN table2 ON table1.id=table2.id
WHERE table2.id IS NULL;

http://dev.mysql.com/doc/refman/5.1/en/rewriting-subqueries.html

え、using "IN()": って??

まあこれはtypoだとして、上のページ周辺を読むに、まだMySQLのsubqueryは発展途上なのでjoinで頑張って書いた方がいい場面も多いようでした。えらい人情報によるとMySQL 5.2からはこのへんは良くなるとのこと。ちょっと楽しみです。