SQLのNOT INはなぜ遅い？
このあいだ聞かれたときにすぐに答えられなかったから書いとく。あとから考えたら当たり前のことだったんだけどね。
結論から言えば、全レコードをシーケンシャルアクセスしなければならないから遅い。
以下、それについて具体的な話を展開するけど、最初に断っておくと私はSQLもRDBMSも詳しくないので間違ったことを書いているかもしれない。もし、致命的な間違いなどに気づいた方はコメントしてくれると助かる。
NOT INについて考える
NOT INが遅いのは、RDBMSの内部動作を考えれば当たり前で。
SELECT * FROM Employee WHERE id NOT IN(2, 3);
というSQLは、Employeeテーブルからidが2でも3でもでないレコードを取得しようとしているが、これを達成するためには最初から最後のレコードまでアクセスしてノットイコールの比較を行わないと抽出できない。例外なく最後のレコードまでね。
for (Employee record : employeeTable) { if (record.id != 2 && record.id != 3) { resultList.add(record); } }
INについて考える
じゃあINの場合はどうなのか？
SELECT * FROM Employee WHERE id IN(2, 3);
この場合は、Employeeテーブルからidが2あるいは3のレコードを取得しようとしている。
これも最初から最後のレコードまでアクセスする必要がありそうに感じる。実際、特定の条件下では最後までアクセスする必要もある。でも、以下の2つの条件においてはそうはならない。
- 対象カラムがユニークインデックス（主キーを含む）である場合
- 対象カラムがユニークである場合
1つ目は2つ目の条件を含んでいる。では、それぞれについてみていこう。
対象カラムがユニークインデックス
ユニークインデックスのカラムはポインタによりアクセスすることが可能である。それはJavaでいうところのHashMapみたいなもので、レコードをシーケンシャルにアクセスする必要がないことを意味する。
if (employeeTable.containsKey(2)) resultList.add(employeeTable.get(2)); if (employeeTable.containsKey(3)) resultList.add(employeeTable.get(3));
見ただけで速いような気がするし、実際HashMapの実装がまずくなければ高速に動作する。幸いなことに殆のRDBMSはこれを高速にやってのける（と思っているのだが）。
対象カラムがユニーク
単なるユニーク制約の場合はポインタによりアクセスすることは不可能である。では、結局最後のレコードまでシーケンシャルアクセスしなければならないのか。そんなことはない。レコードをシーケンシャルアクセスする必要があるのは当然だが、同一の値がないことが保証されているので、INに指定された値にマッチするレコードが全て見つかった時点で処理を完了できるのだ。
先の例で言えば、idが2と3のレコードが見つかった時点で、それ以降のレコードにはアクセスする必要がないことになる。なぜなら、それ以降idが2あるいは3のレコードは登場しないはずだから。
boolean isFoundId2 = false; boolean isFoundId3 = false; for (Employee record : employeeTable) { if (!isFoundId2 && record.id == 2) { resultList.add(record); isFoundId2 = true; } else if (!isFoundId3 && record.id == 3) { resultList.add(record); isFoundId3 = true; } if (isFound2 && isFound3) break; }
まとめ
NOT INはあんまり速くないです。でも、それは主キーやユニークのカラムを対象としたINに比べればというレベルの話で、最後のレコードまでシーケンシャルアクセスが必要な他のSQLと同程度の速度です。
