pg_bigmとpg_trgmのPostgreSQL全文検索インデックスの性能比較

以下の3パターンで、PostgreSQLの全文検索インデックスの性能を比較します。
* ① [pg_bigm](https://github.com/pgbigm/pg_bigm)を利用
* ② [pg_trgm](https://www.postgresql.jp/document/current/html/pgtrgm.html)を利用
* ③ pg_trgmを利用 ([KEEPONLYALNUMをコメントアウトして無効化](https://lets.postgresql.jp/documents/technical/text-processing/3))

性能検証の条件は以下のとおりです。
* PostgreSQLのバージョン: 17.5
    * pg_trgmは、同梱のものを(③では一部改造して)利用
* pg_bigmのバージョン: v1.2-20240606
* データセット: 約430万件の日本語Wikipediaタイトルデータ
* パラレルクエリ: 性能への影響を排除するため無効化
* データベースエンコーディング: UTF-8

## インデックス作成時間
| パターン | インデックス作成時間 | インデックスサイズ |
|:-:|-:|-:|
| ① pg_bigm | 63806.253 ms<br>(01:03.806) | 151 MB |
| ② pg_trgm | 12627.690 ms<br>(00:12.628) | 40 MB |
| ③ pg_trgm<br>(KEEPONLYALNUM無効化) | 69578.506 ms<br>(01:09.579) | 245 MB |

## 検索時間
### 日本語1文字「象」での全文検索
約430万件のデータから2,672件のヒット

| パターン | 検索時間 | SQL実行プラン |
|:-:|-:|:-:|
| ① pg_bigm | 7.177 ms | Bitmap Heap/Index Scan |
| ② pg_trgm | 910.071 ms | Seq Scan |
| ③ pg_trgm<br>(KEEPONLYALNUM無効化) | 914.425 m | Seq Scan |

pg_bigmでは、検索キーワードが1〜2文字でも全文検索にインデックスを利用できます。一方で、pg_trgmでは、インデックスが効かずにシーケンシャルスキャンが発生するため、pg_bigmに比べて検索時間は長くなります。

```sql:【参考】① pg_bigmでのSQL実行プラン
=# EXPLAIN ANALYZE SELECT * FROM wikipedia_title_bigm WHERE title LIKE '%象%';
                                                              QUERY PLAN                                                               
---------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on wikipedia_title_bigm  (cost=40.36..1597.36 rows=430 width=22) (actual time=3.566..6.530 rows=2672 loops=1)
   Recheck Cond: (title ~~ '%象%'::text)
   Heap Blocks: exact=1675
   ->  Bitmap Index Scan on wikipedia_title_idx_bigm  (cost=0.00..40.25 rows=430 width=0) (actual time=2.940..2.941 rows=2672 loops=1)
         Index Cond: (title ~~ '%象%'::text)
 Planning Time: 0.125 ms
 Execution Time: 6.752 ms
(7 rows)

Time: 7.177 ms
```
```sql:【参考】② pg_trgmでのSQL実行プラン
=# EXPLAIN ANALYZE SELECT * FROM wikipedia_title_trgm WHERE title LIKE '%象%';
                                                        QUERY PLAN                                                        
--------------------------------------------------------------------------------------------------------------------------
 Seq Scan on wikipedia_title_trgm  (cost=0.00..82349.01 rows=430 width=23) (actual time=2.500..909.394 rows=2672 loops=1)
   Filter: (title ~~ '%象%'::text)
   Rows Removed by Filter: 4292769
 Planning Time: 0.166 ms
 Execution Time: 909.586 ms
(5 rows)

Time: 910.071 ms
```

### 日本語2文字「東京」での全文検索
約430万件のデータから15,500件のヒット

| パターン | 検索時間 | SQL実行プラン |
|:-:|-:|:-:|
| ① pg_bigm | 21.166 ms | Bitmap Heap/Index Scan |
| ② pg_trgm | 932.904 ms | Seq Scan |
| ③ pg_trgm<br>(KEEPONLYALNUM無効化) | 933.857 ms | Seq Scan |

### 日本語3文字「技術者」での全文検索
約430万件のデータから481件のヒット

| パターン | 検索時間 | SQL実行プラン |
|:-:|-:|:-:|
| ① pg_bigm | 2.824 ms | Bitmap Heap/Index Scan |
| ② pg_trgm | 939.157 ms | Seq Scan |
| ③ pg_trgm<br>(KEEPONLYALNUM無効化) | 2.469 ms | Bitmap Heap/Index Scan |

検索キーワードが3文字以上だと、pg_trgm (KEEPONLYALNUM無効化) でも全文検索にインデックスを利用できるため、pg_bigmと同等以上の検索性能となります。

```sql:【参考】③ pg_trgm (KEEPONLYALNUM無効化) でのSQL実行プラン
=# EXPLAIN ANALYZE SELECT * FROM wikipedia_title_trgm WHERE title LIKE '%技術者%';
                                                              QUERY PLAN                                                              
--------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on wikipedia_title_trgm  (cost=27.87..1584.87 rows=430 width=23) (actual time=0.636..1.833 rows=481 loops=1)
   Recheck Cond: (title ~~ '%技術者%'::text)
   Heap Blocks: exact=371
   ->  Bitmap Index Scan on wikipedia_title_idx_trgm  (cost=0.00..27.76 rows=430 width=0) (actual time=0.429..0.429 rows=481 loops=1)
         Index Cond: (title ~~ '%技術者%'::text)
 Planning Time: 0.183 ms
 Execution Time: 1.920 ms
(7 rows)

Time: 2.469 ms
```

### 日本語4文字「ロケット」での全文検索
約430万件のデータから1,141件のヒット

| パターン | 検索時間 | SQL実行プラン |
|:-:|-:|:-:|
| ① pg_bigm | 7.265 ms | Bitmap Heap/Index Scan |
| ② pg_trgm | 1137.419 ms | Seq Scan |
| ③ pg_trgm<br>(KEEPONLYALNUM無効化) | 4.826 ms | Bitmap Heap/Index Scan |

### 日本語6文字「データベース」での全文検索
約430万件のデータから359件のヒット

| パターン | 検索時間 | SQL実行プラン |
|:-:|-:|:-:|
| ① pg_bigm | 5.932 ms | Bitmap Heap/Index Scan |
| ② pg_trgm | 1148.318 ms | Seq Scan |
| ③ pg_trgm<br>(KEEPONLYALNUM無効化) | 2.415 ms | Bitmap Heap/Index Scan |

### 英字2文字「DB」での全文検索
約430万件のデータから1,685件のヒット

| パターン | 検索時間 | SQL実行プラン |
|:-:|-:|:-:|
| ① pg_bigm | 3.659 ms | Bitmap Heap/Index Scan |
| ② pg_trgm | 890.535 ms | Seq Scan |
| ③ pg_trgm<br>(KEEPONLYALNUM無効化) | 890.209 ms | Seq Scan |

検索キーワードが1〜2文字だと英字(シングルバイト文字)の場合も、pg_trgmでは、インデックスが効かずにシーケンシャルスキャンが発生するため、pg_bigmに比べて検索時間は長くなります。

### 英字4文字「test」での全文検索
約430万件のデータから3,093件のヒット

| パターン | 検索時間 | SQL実行プラン |
|:-:|-:|:-:|
| ① pg_bigm | 25.327 ms | Bitmap Heap/Index Scan |
| ② pg_trgm | 11.824 ms | Bitmap Heap/Index Scan |
| ③ pg_trgm<br>(KEEPONLYALNUM無効化) | 12.062 ms | Bitmap Heap/Index Scan |

検索キーワードが3文字以上で英字(シングルバイト文字)の場合、pg_trgmでも (KEEPONLYALNUMが有効/無効のどちらでも) 全文検索にインデックスを利用できます。

さらに、この検索キーワードの場合、pg_trgmの方がインデックスでの絞り込みが効きやすく、pg_bigmより高性能になることがあります。以下のSQL実行プランからも、pg_trgmの方がインデックスでの絞り込みが効いて、アクセスするページ数が少なくっていることを確認できます。
* ① pg_bigmでは、インデックスから結果候補の4,307件を抽出して、Recheckで1,214件を破棄して、3,093件の検索結果を得ており、結果として1,396ページにアクセスしている
* ② pg_trgmでは、インデックスから結果候補の3,724件を抽出して、Recheckで631件を破棄して、3,093件の検索結果を得ており、結果として1,036ページにアクセスしている

```sql:【参考】① pg_bigmでのSQL実行プラン
EXPLAIN ANALYZE SELECT * FROM wikipedia_title_bigm WHERE title LIKE '%test%';
                                                               QUERY PLAN                                                                
-----------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on wikipedia_title_bigm  (cost=58.06..1615.07 rows=430 width=22) (actual time=21.118..24.614 rows=3093 loops=1)
   Recheck Cond: (title ~~ '%test%'::text)
   Rows Removed by Index Recheck: 1214
   Heap Blocks: exact=1396
   ->  Bitmap Index Scan on wikipedia_title_idx_bigm  (cost=0.00..57.96 rows=430 width=0) (actual time=20.685..20.685 rows=4307 loops=1)
         Index Cond: (title ~~ '%test%'::text)
 Planning Time: 0.167 ms
 Execution Time: 24.846 ms
(8 rows)

Time: 25.327 ms
```
```sql:【参考】② pg_trgmでのSQL実行プラン
=# EXPLAIN ANALYZE SELECT * FROM wikipedia_title_trgm WHERE title LIKE '%test%';
                                                              QUERY PLAN                                                               
---------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on wikipedia_title_trgm  (cost=32.30..1589.30 rows=430 width=23) (actual time=5.204..10.613 rows=3093 loops=1)
   Recheck Cond: (title ~~ '%test%'::text)
   Rows Removed by Index Recheck: 631
   Heap Blocks: exact=1036
   ->  Bitmap Index Scan on wikipedia_title_idx_trgm  (cost=0.00..32.19 rows=430 width=0) (actual time=4.724..4.726 rows=3724 loops=1)
         Index Cond: (title ~~ '%test%'::text)
 Planning Time: 0.168 ms
 Execution Time: 10.991 ms
(8 rows)

Time: 11.824 ms
```

### 英字10文字「PostgreSQL」での全文検索
約430万件のデータから4件のヒット

| パターン | 検索時間 | SQL実行プラン |
|:-:|-:|:-:|
| ① pg_bigm | 6.236 ms | Bitmap Heap/Index Scan |
| ② pg_trgm | 1.881 ms | Bitmap Heap/Index Scan |
| ③ pg_trgm<br>(KEEPONLYALNUM無効化) | 1.809 ms | Bitmap Heap/Index Scan |

## PostgreSQLバージョン18 では
以上の検証結果のとおり、pg_trgmでもKEEPONLYALNUMを無効化すれば、3文字以上の検索キーワードに対して全文検索でインデックスを利用できます。
ただし、これはPostgreSQLバージョン17までのpg_trgmに限った話です。[バージョン18ではKEEPONLYALNUMが削除された](https://github.com/postgres/postgres/commit/d3aad4ac57c5592ade77916404e6d8a989a1d6a1)ため、以降のバージョンではKEEPONLYALNUMを無効化するようなpg_trgmの改造はできません。このため、バージョン18以降では、pg_trgmの検索性能は基本的に「② pg_trgm」のパターンになることに注意が必要です。