この記事はラクス Advent Calendar 2018の24日目です。
今年、仕事で取り組んだ中間一致検索機能の性能改善について書きたいと思います。
前提条件
- かなり大量レコードを扱う中間一致検索処理の性能を改善したい
- 工数と納期の都合によりElasticSearchのようにシステム構成が変わるような大掛かりな変更はできない
- 同じ理由でデータベース本体のバージョンも避けたい（現状、PostgreSQL9.4を使用）
- yumでインストール出来て、カスタマイズが不要なものが好ましい
- 担当しているシステムの特性上、形態素解析は不向きなのでN-gramが前提
という制約のなか検討を行いました。
現状の実装
GINインデックス + tsvector/tsquery というPostgreSQLの標準機能を組み合わせてuni-gramなインデックスを実装をしていました。
かなりのレコード数までは高速に検索できるのですが、レコード数の多い環境では性能が厳しくなってきました。
「Let's postgres」の記事「テキスト検索の方法とインデックス」の「単語単位の検索」の項で紹介されているやり方に近いです。（昔、ズバリこの実装方法が紹介されているサイトがあったのですが現在はリンク切れになってました）現状の実装
CREATE OR REPLACE FUNCTION to_unigram(text) RETURNS tsvector as $$
SELECT TO_TSVECTOR('simple', ARRAY_TO_STRING(REGEXP_SPLIT_TO_ARRAY($1, E'\\s*'), ' '));
$$ IMMUTABLE LANGUAGE SQL;
CREATE OR REPLACE FUNCTION to_unigram_query(text) RETURNS tsquery as $$
SELECT TO_TSQUERY(ARRAY_TO_STRING(REGEXP_SPLIT_TO_ARRAY($1, E'\\s*'),'&'));
$$ LANGUAGE SQL;
postgres=# select to_unigram('メリークリスマス');
to_unigram
-----------------------------------------------
'ク':4 'ス':6,8 'マ':7 'メ':1 'リ':2,5 'ー':3
postgres=# select to_unigram_query('メリークリスマス');
to_unigram_query
-------------------------------------------------------
'メ' & 'リ' & 'ー' & 'ク' & 'リ' & 'ス' & 'マ' & 'ス'
-- Ginインデックスを生成
CREATE INDEX unigram_index ON zip USING gin (to_unigram(city));
-- 検索SQL
select * from zip
where to_unigram(city) @@ to_unigram_query('新宿')
and city like '%新宿%'; -- "新"、"宿" が含まれているだけでヒットしてしまうので「新宿」で絞り込む必要がある
実装方法の検討
インデックスを何に置き替えるか検討を行いました。
pg_trgm
PostgreSQLの標準(contrib）であることと、検索の高速性は良さそうでしたが、
基本的に日本語対応されていない1のと、検索ワードが2文字以下だとインデックスが使われないので見送りました
PGroonga
高機能で要件を満たせそうだったのですが、WALベースのストリーミングレプリケーションに対応するにはPostgreSQL9.6以上に上げる必要があるため今回は見送りました2
インデックス作成時間は後述するpg_bigmよりも高速なようなのでPostgreSQLをバージョンアップした後なら候補になるかと思います。
pg_bigm
最終的にpg_bigmを採用しました。良かった点は以下の通りです。
- 普通のLIKEで書けるので初見に優しく学習コストが必要ない
- 後で他の実装に乗り換えるとしてもインデックスを破棄するだけなのでコストが高くない
- ストリーミングレプリケーションが使える
- rpmパッケージが用意されているので、yumでインストールできる
- 最新への追随性も問題なし（既にPostgreSQL11対応を謳っている）
まとめると以下のとおりです。本文に書いてませんがインデックス項目の容量制限も気にして調べてました。
| インデックス作成方法 | インデックスの種類 | 検索演算子 | 日本語 | 容量の制限 | |
|---|---|---|---|---|---|
| 現状 | 1-gram | GIN | @@ |
○ | 1MB(tsvectorの限界) |
| pg_trgm | 3-gram | GIN/Gist |
LIKE(~~)、ILIKE(~~*)、~、~*
|
×1 | 約228MB |
| pg_bigm | 2-gram | GIN | LIKE |
○ | 約102MB |
| PGroonga | 可変N-gram | pgroonga |
&@、 &@~、LIKE、ILIKE
|
○ | なし(text型の限界まで) |
性能比較
定番の郵便番号CSV（124,231件）を使って性能比較を行いました。
ただ、12万件程度では差が出にくいので同じデータを繰り返し登録して2000万件までデータを増やして検証しました。
DDL
- DDL
create table zip (
id serial primary key,
gov_code char(5),
zip_code_old char(5),
zip_code char(7),
pref_kana text,
city_kana text,
town_kana text,
pref text,
city text,
town text,
flg_n1 boolean,
flg_kaza boolean,
flg_chome boolean,
flg_1n boolean,
upd_stat smallint,
upd_reason smallint
);
インデックス生成時間
create index idx_unigram on zip using gin (to_unigram(city));
create index idx_bigram on zip using gin (city gin_bigm_ops);
CREATE INDEXに掛る時間を比較すると pg_bigm が圧勝でした。
検索の性能改善が目的でしたが副次的に更新処理も速くなりそうです（常にindexを作り直す訳じゃないので、そこまで変わらないかもしれませんが）
インデックスのサイズ
逆にインデックスサイズはpg_bigmを使った方がおよそ1.5倍大きくなりました。（データによって傾向が異なると思いますので参考まで）
検索の性能比較
それぞれ、いろいろなキーワードで検索して平均値を出してみましたが。pg_bigmの方が大分速いという結果になりました。
select * from zip where to_unigram(city) @@ to_unigram_query('新宿') and city like '%新宿%';
select * from zip where city like '%新宿%';
シンプルなSQLで検証したためどちらも速いですが、実際のアプリケーションでは業務要件を満たすため複数キーワードでのAND検索や複数のカラムの検索をかける必要があり、両者の差はもっと大きく開きました。
ちなみに、インデックスを使わない検索でも大体3秒程度でしたので、要件によっては容量も喰いますしインデックスなしもアリと思えたのは自分の中では発見でした。
さいごに
前提条件を満たし、大きな手間をかけずに中間一致検索の性能を大きく改善することができました。
pg_bigmは導入障障壁が低い割に、効果は大きい良いライブラリだと思います。
同じような前提条件で検討している人の参考にでもなれば幸いです。
<参考にさせて頂いたサイト>
https://blog.longkey1.net/2013/05/08/about-japanese-textsearch-on-postgresql9/
http://shanon-tech.blogspot.com/2012/12/postgresql.html
https://blog.honjala.net/entry/2016/11/19/021057
http://d.hatena.ne.jp/nuko_yokohama/20130406/1365255398
https://qiita.com/fujii_masao/items/87f1d94ff4d350a718aa
https://www.clear-code.com/blog/2015/5/25.html
https://pgroonga.github.io/ja/reference/pgroonga-versus-pg-bigm.html
https://www.sraoss.co.jp/technology/postgresql/3rdparty/pg_bigm.php
https://www.slideshare.net/hadoopxnttdata/postgresqlpgbigm-mysqlpostgresql
https://www.slideshare.net/hadoopxnttdata/pgtrgm
https://www.slideshare.net/masahikosawada98/pgbigm-66639588?next_slideshow=1