Rebuild Transcript Searchの高速化を提案する

### きっかけ

みんな大好き[Rebuild.fm](https://rebuild.fm)の[#232](https://rebuild.fm/232)でPostgreSQLの話題があった。

- 過去回の文字起こしを検索できるようにした
- 検索はPostgreSQLでやってる
- インフラはHerokuで、データ件数の制限があり、Episode毎の翻訳を配列に入れてる
- いまのところ現実的な時間で検索できてる

少し高速に検索できる方法を提案してみようということで、調べてみた。

### テーブル定義

PostgreでRebuild内検索してみると

> 1エピソード1レコードにして。段落をその配列にしてあれにして入れる

なる記述が見つかった。テーブル定義はきっとこんな感じだろう。

```sql
create table episodes (
  id serial primary key,
  texts text[]
);
```

### クエリ

Rebuildによると

> 普通さ1万とか何百万もドキュメントがあると遅すぎてできないと思うんですけど

らしいです。`text[]`をlikeで中間一致してることを示唆してると予測。

```sql
select * from episodes
  where array_to_text(text[], E'\n') like '%rebuild%';
```

こうですかね。

### 高速化の方針

日本語で全文検索させるので[pg_trgm](https://www.postgresql.org/docs/current/pgtrgm.html)なインデックスを作成する。リンク先によると

>CREATE TABLE test_trgm (t text);
>CREATE INDEX trgm_idx ON test_trgm USING GIST (t gist_trgm_ops);

>or

>CREATE INDEX trgm_idx ON test_trgm USING GIN (t gin_trgm_ops);

でよい。インデックス対象カラムはtextである必要があるので[Indexes on Expressions](https://www.postgresql.org/docs/current/indexes-expressional.html)を利用する。またIndexes on Expressionsで利用できるFunctionはimmutableである必要があるが、`array_to_string`はimmutableではない点に注意する必要がある。

これらを考慮すると、

```sql
create extension pg_trgm;
create function concat_texts(text[]) returns text
  as E'select array_to_string($1, E\'\\n\')'
  language sql immutable;
create index idx_gin on episodes using gin(concat_texts(texts) gin_trgm_ops);
-- or
-- create index idx_gist on episodes using gist(concat_texts(texts) gist_trgm_ops);
```

で良いだろう。

### 動作確認

インデックスが実行計画で選択されるに作成した`concat_texts` Functionを利用する必要がある。そこでクエリは

```sql
select * from episodes where concat_texts(texts) like '%Rebuild%';
```

とする必要がある。

`explain`してインデックスが利用されているか、テキトウにレコードを追加して確認する。レコード追加は

```sql
insert into episodes (texts) values
  (array[md5(random()::text)]),
  (array[md5(random()::text)]),
  (array[md5(random()::text)]),
  ...;
```

を適度な長さにして実行した。

##### GINインデックス

```sql
app=# explain select * from episodes where concat_texts(texts) like '%bbb%';
                        QUERY PLAN
----------------------------------------------------------
 Seq Scan on episodes  (cost=0.00..44.79 rows=1 width=57)
   Filter: (concat_texts(texts) ~~ '%bbb%'::text)
(2 rows)
```

なぜかインデックス利用されないので、`drop index` -> `create index`してからもう一度試してみる。

```sql
app=# explain select * from episodes where concat_texts(texts) like '%bbb%';
                              QUERY PLAN
-----------------------------------------------------------------------
 Bitmap Heap Scan on episodes  (cost=12.05..15.89 rows=7 width=57)
   Recheck Cond: (concat_texts(texts) ~~ '%bbb%'::text)
   ->  Bitmap Index Scan on idx_gin  (cost=0.00..12.05 rows=7 width=0)
         Index Cond: (concat_texts(texts) ~~ '%bbb%'::text)s
```

動いた。けど、ちょっと気持ち悪い。`SET ENABLE_SEQSCAN TO OFF;`してからクエリ投げれば良いのだろうけど、イマイチ。

##### GiSTインデックス
```sql
app=# explain select * from episodes where concat_texts(texts) like '%bbb%';
                                QUERY PLAN
--------------------------------------------------------------------------
 Index Scan using idx_gist on episodes  (cost=0.14..8.16 rows=1 width=57)
   Index Cond: (concat_texts(texts) ~~ '%bbb%'::text)
(2 rows)
```

GINインデックスと違い、こっちは素直。

参考文献を思い出せないのだが、

- GINインデックスはGiSTインデックスに比べて1/2 - 1/3程度のサイズ
- GiSTインデックスはGINインデックスに比べて高速に更新出来る

特性があったはず。なので更新がそれほど多くはないRebuildにはGINインデックスが良いはず。しかし、挙動が若干おかしいので、GiSTインデックスを使うことにする。

### 日本語での動作

日本語テキストは[青空文庫の作家別作品一覧](https://www.aozora.gr.jp/index_pages/person_all.html)を使う。データのインポートは省略する。データ件数は下の通り。

```sql
app=# select count(*) from episodes;
 count
-------
 16259
(1 row)
```


実時間を計測したいので`explain analyze`で実行する。

```sql
app=# explain analyze select * from episodes where concat_texts(texts) like '%柳田国男%';
                                                      QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------
 Index Scan using idx_gist on episodes  (cost=0.28..12.31 rows=2 width=797) (actual time=6.234..50.926 rows=1 loops=1)
   Index Cond: (concat_texts(texts) ~~ '%柳田国男%'::text)
 Planning time: 3.320 ms
 Execution time: 51.248 ms
(4 rows)
```

うん。早そう。

でもtrigramなので、最低3文字必要な気がする。文字数を減らしてみるとどうかな？

##### 2文字の場合

```sql
app=# explain analyze select * from episodes where concat_texts(texts) like '%柳田%';
                                                        QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------
 Index Scan using idx_gist on episodes  (cost=0.28..12.31 rows=2 width=797) (actual time=38.496..150.426 rows=42 loops=1)
   Index Cond: (concat_texts(texts) ~~ '%柳田%'::text)
   Rows Removed by Index Recheck: 16217
 Planning time: 6.523 ms
 Execution time: 151.231 ms
(5 rows)
```
ちゃんとインデックス効いてる。うれしい。

##### 1文字の場合

これは難しいかな？

```sql
app=# explain analyze select * from episodes where concat_texts(texts) like '%柳%';
                                                        QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on episodes  (cost=505.37..1941.31 rows=657 width=797) (actual time=48.892..122.481 rows=299 loops=1)
   Recheck Cond: (concat_texts(texts) ~~ '%柳%'::text)
   Rows Removed by Index Recheck: 15960
   Heap Blocks: exact=1702
   ->  Bitmap Index Scan on idx_gist  (cost=0.00..505.20 rows=657 width=0) (actual time=48.314..48.317 rows=16259 loops=1)
         Index Cond: (concat_texts(texts) ~~ '%柳%'::text)
 Planning time: 3.051 ms
 Execution time: 124.024 ms
(8 rows)
```

おお、`Recheck Cond` してるのでちょっと重たそうだけど、ちゃんとインデックス使えてる！

### まとめ

技術的には

- Rebuildの検索を再現してみた
- 単純なLikeの中間一致な気がしたので高速化を提案した
- pg_trgmが日本語でも動作すること、1文字中間一致でもインデックスが使える

を確認した。

もしRebuildがpg_trgm使っていないのであれば役立ててほしい。