結合方式とインデックスの関係
ネスト化ループ結合/マージ結合/ハッシュ結合は、それぞれインデックスをどのように使うのか、を整理する。
マスタのｘｘコードとトランザクションの同名の列を等結合にするSQLについて、
- インデックスが片側(マスタ側のみ)
- インデックスが両側
- インデックスなし
の3条件で、各結合方式の実行速度を計測してみる。
テスト内容
PostgreSQL8.3.5で以下のSQLを実行する。
explain analyze select * from tellers t -- 1000件のマスタ inner join history h on h.tid=t.tid -- 1000万件のトランザクション
結合方式は以下の手順で制御する。
- ふつうに実行すると、プランナはハッシュ結合を選択する。
- set enable_hashjoin to off を実行すると、プランナはマージ結合を選択する。
- さらに set enable_mergejoin to off を実行すると、プランナはネスト化ループ結合を選択する。
結論
- ハッシュ結合はインデックスの有無に関係なく、安定的に高速で動作する。
- これはあらゆるSQL・DBMSに通用する話ではないと予想する
- もし'select count(*) from ...'だったらインデックスだけ見て結合処理できるので、インデックスがあるとハッシュ結合が高速になるRDBMSもあるだろう
- PostgreSQLは「インデックスだけ見てデータは見ない」ということができないらしいので*1上記の結論になった
- マージ結合は両側にインデックスがあるときに高速で動作する。
- 実DBでは「インデックスがマスタ側のみ」というケースが多いので、マージ結合はあまり選択されない
- ネスト化ループ結合にはインデックスが必要。
- 両側にインデックスがある場合、片側にインデックスがある時よりも速くなることがある。件数の少ないマスタを外部表にしてIndex Scanの回数を減らせるから(これ知っててもあまり役に立たないと思うが)
1. 片側(マスタ側)だけインデックスがある場合
これは普通によくある状態。プランナはハッシュ結合を選択する。
ハッシュ結合
31秒ぐらいで完了。
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
Hash Join (cost=27.50..330985.64 rows=10000006 width=399) (actual time=1.608..24852.165 rows=10000000 loops=1)
Hash Cond: (h.tid = t.tid)
-> Seq Scan on history h (cost=0.00..193458.06 rows=10000006 width=47) (actual time=0.010..7285.277 rows=10000000 loops=1)
-> Hash (cost=15.00..15.00 rows=1000 width=352) (actual time=1.586..1.586 rows=1000 loops=1)
-> Seq Scan on tellers t (cost=0.00..15.00 rows=1000 width=352) (actual time=0.007..0.720 rows=1000 loops=1)
Total runtime: 30923.980 ms
(6 rows)
マージ結合
インデックスがないトランザクションをソートする処理が重く、80秒近くかかる。
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------
Merge Join (cost=2586608.05..2736653.47 rows=10000006 width=399) (actual time=24793.299..72566.423 rows=10000000 loops=1)
Merge Cond: (t.tid = h.tid)
-> Index Scan using tellers_pkey on tellers t (cost=0.00..43.25 rows=1000 width=352) (actual time=0.023..1.467 rows=1000 loops=1)
-> Materialize (cost=2586607.63..2711607.71 rows=10000006 width=47) (actual time=24793.246..57446.134 rows=10000000 loops=1)
-> Sort (cost=2586607.63..2611607.65 rows=10000006 width=47) (actual time=24793.241..41378.094 rows=10000000 loops=1)
Sort Key: h.tid
Sort Method: external merge Disk: 576448kB
-> Seq Scan on history h (cost=0.00..193458.06 rows=10000006 width=47) (actual time=0.007..13119.637 rows=10000000 loops=1)
Total runtime: 78964.182 ms
(9 rows)
ネスト化ループ結合
80秒ぐらいかかる。外部表のトランザクションは1000万件あるから、1000万回のIndex Scanが発生している。
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.00..66995499.74 rows=10000006 width=399) (actual time=0.033..73155.158 rows=10000000 loops=1)
-> Seq Scan on history h (cost=0.00..193458.06 rows=10000006 width=47) (actual time=0.010..7444.253 rows=10000000 loops=1)
-> Index Scan using tellers_pkey on tellers t (cost=0.00..6.67 rows=1 width=352) (actual time=0.003..0.004 rows=1 loops=10000000)
Index Cond: (t.tid = h.tid)
Total runtime: 79494.501 ms
2. 両側にインデックスがある場合
トランザクションの結合カラムにインデックスを追加して、SQLを各結合方式で再実行してみる。
ハッシュ結合
基本的にハッシュ結合にはインデックスは関係ない。速さは変わらない。
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
Hash Join (cost=27.50..330985.50 rows=10000000 width=399) (actual time=1.616..25016.110 rows=10000000 loops=1)
Hash Cond: (h.tid = t.tid)
-> Seq Scan on history h (cost=0.00..193458.00 rows=10000000 width=47) (actual time=0.032..7252.089 rows=10000000 loops=1)
-> Hash (cost=15.00..15.00 rows=1000 width=352) (actual time=1.571..1.571 rows=1000 loops=1)
-> Seq Scan on tellers t (cost=0.00..15.00 rows=1000 width=352) (actual time=0.007..0.709 rows=1000 loops=1)
Total runtime: 31078.684 ms
(6 rows)
マージ結合
両側にインデックスがある場合、ソートが不要なので速い。
速さはハッシュ結合と同等。31秒。
QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------------------------------- Merge Join (cost=0.41..456291.88 rows=10000000 width=399) (actual time=3.505..24941.755 rows=10000000 loops=1) Merge Cond: (t.tid = h.tid) -> Index Scan using tellers_pkey on tellers t (cost=0.00..43.25 rows=1000 width=352) (actual time=3.432..4.556 rows=1000 loops=1) -> Index Scan using history_tid_idx on history h (cost=0.00..331246.13 rows=10000000 width=47) (actual time=0.050..9568.710 rows=10000000 loops=1) Total runtime: 31077.265 ms (5 rows)
ネスト化ループ結合
意外なことにこれが一番速い。30秒。
両側にインデックスがある場合、外部表を件数の少ないマスタにできる。
この結果 Index Scan の回数が1000万回から1000回になり、速くなった模様。
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.00..6970250.84 rows=10000000 width=399) (actual time=0.153..23995.164 rows=10000000 loops=1)
-> Seq Scan on tellers t (cost=0.00..15.00 rows=1000 width=352) (actual time=0.030..0.995 rows=1000 loops=1)
-> Index Scan using history_tid_idx on history h (cost=0.00..5720.24 rows=100000 width=47) (actual time=0.006..9.600 rows=10000 loops=1000)
Index Cond: (h.tid = t.tid)
Total runtime: 30116.411 ms
(5 rows)
3. インデックスがない場合
マスタ/トランザクションのインデックスを削除して、SQLを各結合方式で再実行する。
ハッシュ結合
実行計画も速さも変わらない。31秒。
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
Hash Join (cost=27.50..330985.50 rows=10000000 width=399) (actual time=1.657..25184.198 rows=10000000 loops=1)
Hash Cond: (h.tid = t.tid)
-> Seq Scan on history h (cost=0.00..193458.00 rows=10000000 width=47) (actual time=0.040..7314.014 rows=10000000 loops=1)
-> Hash (cost=15.00..15.00 rows=1000 width=352) (actual time=1.603..1.603 rows=1000 loops=1)
-> Seq Scan on tellers_no_keys t (cost=0.00..15.00 rows=1000 width=352) (actual time=0.007..0.728 rows=1000 loops=1)
Total runtime: 31312.917 ms
(6 rows)
マージ結合
1000万件のトランザクションをソートするコストが重い。80秒ぐらい。
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------
Merge Join (cost=2586671.71..2736676.66 rows=10000000 width=399) (actual time=21971.475..72353.744 rows=10000000 loops=1)
Merge Cond: (t.tid = h.tid)
-> Sort (cost=64.83..67.33 rows=1000 width=352) (actual time=1.420..2.094 rows=1000 loops=1)
Sort Key: t.tid
Sort Method: quicksort Memory: 56kB
-> Seq Scan on tellers_no_keys t (cost=0.00..15.00 rows=1000 width=352) (actual time=0.012..0.673 rows=1000 loops=1)
-> Materialize (cost=2586606.83..2711606.83 rows=10000000 width=47) (actual time=21970.029..56852.698 rows=10000000 loops=1)
-> Sort (cost=2586606.83..2611606.83 rows=10000000 width=47) (actual time=21970.025..40503.733 rows=10000000 loops=1)
Sort Key: h.tid
Sort Method: external merge Disk: 576448kB
-> Seq Scan on history h (cost=0.00..193458.00 rows=10000000 width=47) (actual time=0.033..9745.576 rows=10000000 loops=1)
Total runtime: 78873.202 ms
(12 rows)
ネスト化ループ結合
1000万件×1000件のネスト化ループ結合は、インデックスがなければ使いものにならない。
10分経っても終わらないので、実行計画だけ載せておく。
QUERY PLAN
-----------------------------------------------------------------------------------
Nested Loop (cost=16.00..225193474.00 rows=10000000 width=399)
Join Filter: (t.tid = h.tid)
-> Seq Scan on history h (cost=0.00..193458.00 rows=10000000 width=47)
-> Materialize (cost=16.00..26.00 rows=1000 width=352)
-> Seq Scan on tellers_no_keys t (cost=0.00..15.00 rows=1000 width=352)
(5 rows)
