とある実装でSQLのOR条件を多用する機会があり、そのパフォーマンスが著しく低く悩まされたので調査・改善した話。
1. 例に取るテーブルとインデックス
| テーブル | カラム(型) | インデックス・外部キー |
|---|---|---|
| table_1 | table_2_id(bigint) | "table_1_table_2_id_idx" btree (table_2_id)\n"table_1_table_2_id_fkey" FOREIGN KEY (table_2_id) REFERENCES table_2(id) |
| email(text) | "table_1_email_idx" btree (email) | |
| table_2 | id(bigint) | "table_2_pkey" PRIMARY KEY, btree (id) |
| prefecture_id(bigint) | "table_2_prefecture_id_idx1" btree (prefecture_id)\n"table_2_prefecture_id_fkey" FOREIGN KEY (prefecture_id) REFERENCES prefecture_kind(id) |
table_1とtable_2は多：１の関係。
レコード数はtable_1が250万レコード以上、table_2が180万件以上。
2. まずAND条件のクエリ
EXPLAIN ANALYZE SELECT table_1.* FROM table_1 WHERE table_1.table_2_id = 1 and table_1.email = 'test@example.com' QUERY PLAN Index Scan using table_1_table_2_id_idx on table_1 (cost=0.43..11.78 rows=1 width=176) (actual time=0.012..0.013 rows=0 loops=1) Index Cond: (table_2_id = 1) Filter: (email = 'test@example.com'::text) Planning Time: 0.197 ms Execution Time: 0.040 ms
問題なく作成しているインデックスが効いている。
3. OR条件のクエリ
EXPLAIN ANALYZE SELECT table_1.* FROM table_1 WHERE table_1.table_2_id = 1 or table_1.email = 'test@example.com' QUERY PLAN Bitmap Heap Scan on table_1 (cost=9.74..446.00 rows=111 width=176) (actual time=0.042..0.043 rows=1 loops=1) Recheck Cond: ((table_2_id = 1) OR (email = 'test@example.com'::text)) Heap Blocks: exact=1 -> BitmapOr (cost=9.74..9.74 rows=111 width=0) (actual time=0.033..0.033 rows=0 loops=1) -> Bitmap Index Scan on table_1_table_2_id_idx (cost=0.00..4.44 rows=2 width=0) (actual time=0.019..0.019 rows=0 loops=1) Index Cond: (table_2_id = 1) -> Bitmap Index Scan on table_1_email_idx2 (cost=0.00..5.24 rows=108 width=0) (actual time=0.013..0.013 rows=1 loops=1) Index Cond: (email = 'test@example.com'::text) Planning Time: 0.155 ms Execution Time: 0.089 ms
明らかな違いが出る。bitmap index scanなるものが使用されている。
これは通常のindex scanと違い、bitmapをビルドする必要があるためコストが上昇する。しかもRAMの使用量も増大。ちなみにbitmap index scanはOR条件以外にも、検索対象カラムのカーディナリが低い場合にも使用される。
コスト、実行時間から見てもパフォーマンスは低下している。
4. OR条件をJOINテーブルのカラムと組み合わせると悲惨
下記のようにtable_1とtable_2をJOINし、各テーブルのカラムを用いたOR条件にすると悪い意味でインパクトが大きい。
EXPLAIN ANALYZE SELECT table_1.* FROM table_1 JOIN table_2 on table_1.table_2_id = table_2.id WHERE table_1.table_2_id = 1 or table_1.email = 'test@example.com' or table_2.prefecture_id = 1 QUERY PLAN Gather (cost=501575.00..719474.05 rows=102828 width=176) (actual time=2828.582..4238.380 rows=99275 loops=1) Workers Planned: 2 Workers Launched: 2 -> Parallel Hash Join (cost=500575.00..708191.25 rows=42845 width=176) (actual time=2848.523..3986.268 rows=33092 loops=3) Hash Cond: (table_1.table_2_id = table_2.id) Join Filter: ((table_1.table_2_id = 1) OR (table_1.email = 'test@example.com'::text) OR (table_2.prefecture_id = 1)) Rows Removed by Join Filter: 812364 -> Parallel Seq Scan on table_1 (cost=0.00..149578.12 rows=1056812 width=176) (actual time=0.012..898.463 rows=845456 loops=3) -> Parallel Hash (cost=487547.78..487547.78 rows=749378 width=16) (actual time=712.106..712.107 rows=604545 loops=3) Buckets: 262144 Batches: 16 Memory Usage: 7392kB -> Parallel Seq Scan on table_2 (cost=0.00..487547.78 rows=749378 width=16) (actual time=0.007..529.110 rows=604545 loops=3) Planning Time: 0.761 ms Execution Time: 4243.017 ms
見た通りindex scanが使われず、seq scanになる。つまりフルスキャン。
JOINし複数のテーブルに関わるOR条件の場合、indexはテーブル単位で作成するもののため、複数テーブルがOR条件に入るとindexは使用できなくなることがほとんど。
また結合したテーブルをフィルタリング完了までずっと保持し続けないといけないので、さらにパフォーマンスを低下させる。
5. 解決方法の一つ
とはいえ実装上はOR条件の使用は避けられない。一つの対策としてunionの使用がある。
EXPLAIN ANALYZE SELECT table_1.* FROM table_1 WHERE table_1.table_2_id = 1 or table_1.email = 'test@example.com' UNION SELECT table_1.* FROM table_1 JOIN table_2 on table_1.table_2_id = table_2.id WHERE table_2.prefecture_id = 1 QUERY PLAN Unique (cost=463024.64..474336.16 rows=102832 width=980) (actual time=1446.646..1544.976 rows=99275 loops=1) -> Sort (cost=463024.64..463281.72 rows=102832 width=980) (actual time=1446.644..1467.116 rows=99275 loops=1) " Sort Key: table_1.id, table_1.table_2_id, table_1.last_name, table_1.first_name, table_1.name_kana, table_1.tel, table_1.mobile_tel, table_1.personal_tel, table_1.fax, table_1.email, table_1.zip_code, table_1.prefecture_id, table_1.city, table_1.address, table_1.building, table_1.date_of_birth, table_1.hobby, table_1.birthplace, table_1.graduated_school, table_1.contact_type_kind_id, table_1.department, table_1.post, table_1.km_flag, table_1.main_shareholder_flag, table_1.stock_share_ratio, table_1.note, table_1.antisocial_check_status_kind_id, table_1.antisocial_check_date, table_1.antisocial_check_user_id, table_1.antisocial_check_client_id, table_1.antisocial_check_result_url, table_1.deletion_flag, table_1.version, table_1.created_at, table_1.updated_at, table_1.referrer_code, table_1.retirement_flag, table_1.sf_contact_id, table_1.sf_lead_id, table_1.tel_hyphen_removed, table_1.normalized_first_name, table_1.normalized_last_name, table_1.normalized_address" Sort Method: external merge Disk: 20224kB -> Append (cost=9.74..365885.91 rows=102832 width=980) (actual time=0.036..1364.478 rows=99275 loops=1) -> Bitmap Heap Scan on table_1 (cost=9.74..446.00 rows=111 width=176) (actual time=0.035..0.038 rows=1 loops=1) Recheck Cond: ((table_2_id = 1) OR (email = 'test@example.com'::text)) Heap Blocks: exact=1 -> BitmapOr (cost=9.74..9.74 rows=111 width=0) (actual time=0.027..0.029 rows=0 loops=1) -> Bitmap Index Scan on table_1_table_2_id_idx (cost=0.00..4.44 rows=2 width=0) (actual time=0.011..0.011 rows=0 loops=1) Index Cond: (table_2_id = 1) -> Bitmap Index Scan on table_1_email_idx2 (cost=0.00..5.24 rows=108 width=0) (actual time=0.015..0.016 rows=1 loops=1) Index Cond: (email = 'test@example.com'::text) -> Gather (cost=202301.39..364925.75 rows=102721 width=176) (actual time=114.310..1353.560 rows=99274 loops=1) Workers Planned: 2 Workers Launched: 2 -> Parallel Hash Join (cost=201301.39..353653.65 rows=42800 width=176) (actual time=106.907..1187.671 rows=33091 loops=3) Hash Cond: (table_1_1.table_2_id = table_2.id) -> Parallel Seq Scan on table_1 table_1_1 (cost=0.00..149578.12 rows=1056812 width=176) (actual time=0.012..824.483 rows=845456 loops=3) -> Parallel Hash (cost=200922.01..200922.01 rows=30350 width=8) (actual time=106.255..106.256 rows=24881 loops=3) Buckets: 131072 Batches: 1 Memory Usage: 3968kB -> Parallel Bitmap Heap Scan on table_2 (cost=1368.93..200922.01 rows=30350 width=8) (actual time=17.456..98.594 rows=24881 loops=3) Recheck Cond: (prefecture_id = 1) Heap Blocks: exact=15772 -> Bitmap Index Scan on table_2_prefecture_id_idx1 (cost=0.00..1350.72 rows=72839 width=0) (actual time=12.813..12.813 rows=78960 loops=1) Index Cond: (prefecture_id = 1) Planning Time: 3.636 ms Execution Time: 1554.494 ms
OR条件には一つのテーブルカラムしか介在しないようにすることでindex scanを可能にする。複数クエリに分けてJOINをそれぞれで行うオーバーヘッドも、indexの恩恵で有り余るメリットが得られる。ネガティブ要素は可読性の悪化。
クエリ、ORM等の実装も既存をUNION書き換えるのは面倒。先を見越してパフォーマンスにセンシティブなところは、初めからUNIONで記述しても良いかもしれない。
6. ここで疑問点
「4. OR条件をJOINテーブルのカラムと組み合わせると悲惨」で
- また結合したテーブルをフィルタリング完了までずっと保持し続けないといけないので
と先述したがSQLの実行順序から見れば当然にも思う。
- FROM句
- JOIN句
- ON句
- WHERE句
- GROUP BY句
- HAVING句
- SELECT句
- ORDER BY句
- LIMIT句
つまりOR条件を使っていなくとも、JOINしてからWHEREで絞る順序は同じなのではないかと思い、下記を試した。
EXPLAIN ANALYZE SELECT table_1.* FROM table_1 JOIN table_2 on table_1.table_2_id = table_2.id WHERE table_1.table_2_id = 1 and table_1.email = 'test@example.com' and table_2.prefecture_id = 1 QUERY PLAN Nested Loop (cost=0.86..20.24 rows=1 width=176) (actual time=0.024..0.025 rows=0 loops=1) -> Index Scan using table_1_table_2_id_idx on table_1 (cost=0.43..11.78 rows=1 width=176) (actual time=0.023..0.023 rows=0 loops=1) Index Cond: (table_2_id = 1) Filter: (email = 'test@example.com'::text) -> Index Scan using table_2_pkey on table_2 (cost=0.43..8.45 rows=1 width=8) (never executed) Index Cond: (id = 1) Filter: (prefecture_id = 1) Planning Time: 0.838 ms Execution Time: 0.067 ms
「4. OR条件をJOINテーブルのカラムと組み合わせると悲惨」のクエリのOR条件をAND条件にした。
比較すると
- OR条件のみ
- JOIN(Parallel Hash Join)の後にON(Hash Cond)
- AND条件のみ
- JOIN(Nested Loop)の後にWHERE(index scan)
認識している実行順序と違う模様。
7. オプティマイザの仕業（良い意味で）
先述した実行順序はあくまで論理的なもので、実行されるときにはSQLオプティマイザにより物理理的実行順序が導き出される。
実データの統計情報やindexを加味し、文字通り最適なパフォーマンスを出せるよう調節してくれている。JOINでParallel Hash JoinやNested Loopを使い分けたのもオプティマイザ。
実データの統計情報を見ているというのが問題で、データ量の変化によりオプティマイザの動きが変わるので、パフォーマンス改善は一度行って終わりとはいかない。
