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

きっかけ

みんな大好きRebuild.fmの#232でPostgreSQLの話題があった。

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

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

テーブル定義

PostgreでRebuild内検索してみると

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

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

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

クエリ

Rebuildによると

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

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

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

こうですかね。

高速化の方針

日本語で全文検索させるのでpg_trgmなインデックスを作成する。リンク先によると

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を利用する。またIndexes on Expressionsで利用できるFunctionはimmutableである必要があるが、array_to_stringはimmutableではない点に注意する必要がある。

これらを考慮すると、

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を利用する必要がある。そこでクエリは

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

とする必要がある。

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

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

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

GINインデックス

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してからもう一度試してみる。

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インデックス

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インデックスを使うことにする。

日本語での動作

日本語テキストは青空文庫の作家別作品一覧を使う。データのインポートは省略する。データ件数は下の通り。

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

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

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文字の場合

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文字の場合

これは難しいかな？

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使っていないのであれば役立ててほしい。