MySQLのオプティマイザが行うanti-joinって何？

はじめに

「相関サブクエリはパフォーマンスが悪いから基本的に使わない」と言われて以来、特に疑問など持たずになるべく相関サブクエリは使わないようにしていました。

ですが、最近AIに作ってもらったSQLを検証していたとき、「おいおい相関サブクエリあるじゃーん」と思いながらも実行計画を見てみると全くコストが重くないことに気づきました。

そこで知ったオプティマイザが行なっている最適化について、サブクエリにも触れながら調べたことを備忘録としてまとめます。

想定読者

• DBについて何となく知っている方
• サブクエリで悩んでいる方

オプティマイザ？何それ美味しいの？

そもそも、今回の話を調べるまでオプティマイザが何者か実はよくわかっていませんでした。

optimizeとは最適化するという意味です。

なのでoptimizerはそのまま最適化する人（人？）ということになります。

DBの文脈で当てはめて考えると、クエリを実行する際に効率的な実行計画を決めて実行してくれるのがオプティマイザです。

各テーブルをどう読むか（テーブルフルスキャンか？インデックス使うか？など）、どういう順番でテーブルをJOINするか、そもそも不要なJOINを消せないかなど、どうすれば効率よく実行できるかを考えて、最もコストのかからないものを選ぶ仕事が最適化です。

このオプティマイザが、実はサブクエリの最適化も行ってくれています。

サブクエリは悪？

サブクエリが悪かどうかを考える際に大事になってくるのは相関か非相関かという観点かと思います。

• 非相関サブクエリ

  SELECT * FROM users 
  WHERE company_id = (
      SELECT id
      FROM companies
      WHERE name = 'ダイレクト出版'
  )
  

  内側のサブクエリが1回だけ実行され、外側に依存しない

• 相関サブクエリ

  SELECT * FROM users u
  WHERE NOT EXISTS (
      SELECT 1 FROM purchases p WHERE p.user_id = u.id
  );
  

  外側の行に応じてその都度内側のサブクエリが実行される

上記の通り、相関サブクエリは外側のテーブルの行だけクエリが増えるため、時間がかかりパフォーマンスが悪くなりがちです。

こういった理解のもと、あまり深く考えずにずっと「相関サブクエリは悪」という認識に囚われていました。

でも実際に実行計画をみると、自分が書いたはずのサブクエリが消えていてコストも全くかかっていなかったんです。

anti-joinとは何なのか

anti-joinとは、左テーブルの行のうち、右テーブルに対応する行が存在しないものだけを返す結合です。

つまり、NOT EXISTS/NOT INが表す「存在しない」という条件を、サブクエリの繰り返し実行ではなく1回の結合操作として処理してくれるのです。

なお、NOT INはサブクエリ側にNULLが混じると結果が空になってしまいます。「存在しない」ことを表現するならNOT EXISTSの方が安全で最適化も効きやすいです。

例えばこんなクエリがあったとします。

SELECT * FROM products p
WHERE NOT EXISTS (
    SELECT 1 
    FROM purchases pu 
    WHERE pu.customer_id = 100
    AND pu.product_id = p.id
);

productsは商品テーブル、purchasesは顧客と商品の中間テーブルです。

特定の顧客が買っていない商品を取得したい時に、買っていない（＝中間テーブルに存在しない）商品を取得するために相関サブクエリを使っています。

これを実行(EXPLAIN FORMAT=TREE)すると、実行計画は次のようになります。

-> Nested loop antijoin  (cost=360 rows=3000)
    -> Table scan on products  (rows=300)
    -> Single-row index lookup on <subquery2> using <auto_distinct_key> ...
        -> Materialize with deduplication  (rows=10)
            -> Covering index lookup on purchases
               using uni:customer_id:product_id (customer_id=100)

一番最初の行に「antijoin」と記載されています。

相関サブクエリを書いたはずですが、オプティマイザによってanti-joinに変換されていることがわかります。

ポイントは「Materialize with deduplication」です。

まずpurchasesからcustomer_id=1のproduct_idを一度だけ取得し、
重複を取り除いた一時テーブルを作ります。

その後productsを走査しながら、その集合に存在するかどうかだけを判定します。

そのため、productsの行ごとにpurchasesを再検索する必要がなくコストが軽くなっています。

まとめ

悪しき相関サブクエリを書いたとしても、場合によってはオプティマイザがanti-joinに変換してくれてパフォーマンスを担保することができます。

それなら初めからJOINで書けよとなるかもしれません。

確かにその方がいい場合もありますが、「LEFT JOIN ... IS NULL」を書くと直感的でないため可読性が落ちることもあります。

せっかくオプティマイザが効率よく変換してくれるなら可読性重視で書くという選択肢も現実的だと思いました。

ただし、すべてのNOT EXISTSがanti-joinに変換されるわけではありません。

サブクエリの内容（GROUP BYや集約関数など）によってはそのまま相関サブクエリとして実行されることもあります。

さらに、変換されたとしても、どの実行戦略が選ばれてコストが軽くなるかは統計情報やデータの分布次第です。そのため、1つのEXPLAIN結果を見て「コストが低いからこのクエリは最適化された」と判断するのは早計です。

検証の際は本番に近しいサンプルデータを用意し、特徴の異なる値（購入が多い顧客／少ない顧客など）で複数のEXPLAINを取り、プランとコストを確認することが大切です。

参考