INをEXISTSに書き換えると速くなるサンプルSQLを作るのは難しい
「INをEXISTSに書き換えると速くなる」という話が、DBMSやそのバージョンを限定せずにSQL一般の話として語られることがあるけど、実感としてそれはないだろうと。
そこでどういう場合に速くなるのか確認しようと思ったけどうまくいかなかったので、どういう場合に速くならないかを書いてみます。
速くならない(1) - 同一の実行計画になる
SQL Server 2005で以下のSQLを流すと、IN/EXISTSで同一の実行計画が出てきた。
IN
select count(*) from 受注 t
where 商品CD in
(select 商品CD from 商品)
EXISTS
select count(*) from 受注 t
where exists
(select * from 商品 where 商品CD=t.商品CD)
実行計画
|--Compute Scalar(DEFINE:([Expr1008]=CONVERT_IMPLICIT(int,[globalagg1010],0)))
|--Stream Aggregate(DEFINE:([globalagg1010]=SUM([partialagg1009])))
|--Parallelism(Gather Streams)
|--Hash Match(Inner Join, HASH:([t].[商品CD])=([商品].[商品CD]), RESIDUAL:([商品].[商品CD]=[受注].[商品CD] as [t].[商品CD]))
|--Bitmap(HASH:([t].[商品CD]), DEFINE:([Bitmap1011]))
| |--Hash Match(Aggregate, HASH:([t].[商品CD]), RESIDUAL:([受注].[商品CD] as [t].[商品CD] = [受注].[商品CD] as [t].[商品CD]) DEFINE:([partialagg1009]=COUNT(*)))
| |--Parallelism(Repartition Streams, Hash Partitioning, PARTITION COLUMNS:([t].[商品CD]))
| |--Clustered Index Scan(OBJECT:([受注].[受注_koten_cd_idx] AS [t]))
|--Parallelism(Repartition Streams, Hash Partitioning, PARTITION COLUMNS:([商品].[商品CD]), WHERE:(PROBE([Bitmap1011])=TRUE))
|--Index Scan(OBJECT:([商品].[商品_UNIQUE_IDX]))やってることはハッシュ結合による「セミジョイン」といわれるもので、
- マスタを全件読んで、結合カラムである商品コードでハッシュテーブルを作る
- トランザクションを1件ずつ読んでハッシュテーブルにぶつけ、マスタ側に対応する行があれば返す。なければ捨てる
というもの。INでもEXISTSでも当然同じ速さ。
速くならない(2) - INはセミジョインするのに、EXISTSは1件ずつサブクエリを実行してしまう
PostgreSQL 8.3.5 でやってみると、INとEXISTSで異なる実行計画が出てきた。
IN
bench=# explain analyze
bench-# select count(*)
bench-# from accounts a
bench-# where bid in
bench-# (select tid from tellers);
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=421259.89..421259.90 rows=1 width=0) (actual time=30531.857..30531.857 rows=1 loops=1)
-> Hash IN Join (cost=27.50..396259.76 rows=10000053 width=0) (actual time=8.434..23842.963 rows=10000000 loops=1)
Hash Cond: (a.bid = tellers.tid)
-> Seq Scan on accounts a (cost=0.00..258731.53 rows=10000053 width=4) (actual time=6.767..8577.783 rows=10000000 loops=1)
-> Hash (cost=15.00..15.00 rows=1000 width=4) (actual time=1.654..1.654 rows=1000 loops=1)
-> Seq Scan on tellers (cost=0.00..15.00 rows=1000 width=4) (actual time=0.009..0.790 rows=1000 loops=1)
Total runtime: 30531.923 ms
(7 rows)
EXISTS
bench=# explain analyze
bench-# select count(*)
bench-# from accounts a
bench-# where exists
bench-# (select * from tellers where tid=a.bid);
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=82948669.79..82948669.80 rows=1 width=0) (actual time=52020.969..52020.969 rows=1 loops=1)
-> Seq Scan on accounts a (cost=0.00..82936169.72 rows=5000026 width=0) (actual time=14.702..45362.230 rows=10000000 loops=1)
Filter: (subplan)
SubPlan
-> Index Scan using tellers_pkey on tellers (cost=0.00..8.27 rows=1 width=352) (actual time=0.003..0.003 rows=1 loops=10000000)
Index Cond: (tid = $0)
Total runtime: 52021.028 ms
(7 rows)INはSQL Serverと似た実行計画で、マスタとランザクションをそれぞれ1回ずつ全件読みしてハッシュ結合している。
EXISTSはトランザクションを全件読みしながら、対応するマスタのレコードをインデックス経由でランダムアクセスしている。
トランザクションが1000万件あるので、1000万回マスタのselectが発生している。
結果、EXISTSに書き換えることで実行時間が1.7倍になった*1。
まとめ
- テストしたSQLはハッシュ結合でセミジョインするのが一番速い。
- どう書けばハッシュ結合に誘導できるのかはDBMSによって違う。
- 恐らくEXISTSよりINの方が誘導しやすい。SQLの見た目と実行計画の手順が似ているから。
- EXISTSは相関サブクエリなので、オプティマイザによっては馬鹿正直に1件ずつランダムアクセスしようとする(PostgreSQL)。
- かつて「INをEXISTSに書き換えると速くなる」と言われたころは、セミジョインまたはハッシュ結合が実装されていなかった？
- 2008年時点で最新バージョンのDBMSでは、テストしたようなSQLで、INをEXISTSに書き換えても速くならないのでは。
課題
NULLがからむとまた別の結果になるかもしれない。
例えばNOT NULL制約のない列を結合カラムにして NOT IN から NOT EXISTS に書き換えると速くなったりしないか。
