MySQL 8 の Antijoin
RikiyaOtaMySQL 8.0.17 から、NOT IN (subquery) や NOT EXISTS (subquery) などの形を antijoin に書き換えてサブクエリを無くすように最適化してくれるらしい。
RikiyaOta
Antijoin の関係代数はこちら。もうこれはメモだけ、読んでないです。
RikiyaOtaAntijoin の2つの戦略を評価。
- "First Match": 駆動表（でいいよね？）のレコードを1つ読み、結合先のテーブル内でマッチするレコードがないか検索する→これは subquery を使ったのと同じ。
- "Materialization": 駆動表に依存しない条件だけから抽出したレコードからなる temporary table を作る。この temp table にインデックスを作成し、インデックスを使って検索をかける。
RikiyaOta
このクエリを例に、2つより多いテーブルに関するクエリでの antijoin のメリットを説明している。
and not exists (
select
*
from
lineitem l3
where
l3.l_orderkey = l1.l_orderkey
and l3.l_suppkey <> l1.l_suppkey
and l3.l_receiptdate > l3.l_commitdate
)
この部分を antijoin に変えた場合、ON に当たる部分が l1, l3 にしか依存していないので、結合順序を optimizer が決める際に、l1 より後ろにありさえすればどこにしても論理的には等価なのがメリットっぽい。
もし他の join で大幅に l1 のレコードを削減できるのなら、後で antijoin を実行するみたいな戦略を取ることができる。
RikiyaOtaこれだけ見ると、antijoin を直接使わずに、とりあえず NOT IN (subquery) で書いておいて、optimizer にあとはよろしく。としておいた方が良さそうな気がする。
subquery のままの方がいいと判断してくれたらそうしてくれるわけだし。
RikiyaOtaMySQL は top query を最適化したのちに、subquery を最適化するらしい。最適化のフェーズが異なる。
何が問題か？ top query の最適化をする際に、サブクエリのコストや選択性を知らないので、ある種の仮定を置くなどして評価するらしく。例えば NOT EXISTS (subquery) は、コストが無くて、１００％の選択性（つまり常に NOT EXISTS が TRUE と評価される）と仮定するらしい。
もちろんこれは良くない。当然ながら、NOT EXISTS によって除外されるレコードもあるはずだから。
じゃあサブクエリを先に最適化すれば、、、となるとまた同じ問題になる。
他にも、サブクエリ自身が何回評価されるか？などを考慮した戦略も立てられない。
antijoin にすることでサブクエリがなくなり、一度に同じフェーズで最適化ができることが大きなメリット。
RikiyaOta
antijion とサブクエリでそれぞれ EXPLAIN ANALYZE の出力結果が貼ってある。
Nested loop anti-join と subquery のパターンがそれぞれ出ている。
ちなみに、Nested loop anti-join ということは、ここでは antijoin は "First Match" 戦略で実行されていることになる。temp table が作られた的なことは出力されていないので。
RikiyaOta-
NOT EXISTS,NOT INでサブクエリを使っていると antijoin に最適化してくれることがある。 - First Match or Materizalition 戦略も決めてくれる。
- 結合順序もいい感じにしてくれる。