pg_bigm (bi-gram インデックス)

1. pg_bigm とは

pg_bigm は PostgreSQL に文字列の中間一致検索に使える GIN 方式のインデックスを提供するオープンソースの拡張モジュールです。以下のような B-tree インデックスを適用できない問い合わせを高速化することができます。

SELECT id FROM documents WHERE content LIKE '%文字列%';

bigm とは bi-gram (バイグラム)の略です。文字列中の連続する 2 文字ごとにインデックス項目を作ることを意味しています。
なお、 PostgreSQL 本体には追加モジュールとして pg_trgm という連続する 3 文字ごとにインデックス項目を作る tri-gram (トリグラム)のモジュールが付属しています。ただし、 pg_trgm はマルチバイト文字列が扱えないという制限があります。また、マルチバイト対応させたとしても、 2 文字から成る単語の検索には能力を発揮できませんので日本語には適しません。

2. 使用方法

◆ インストール

pg_bigm は最近の PostgreSQL バージョンに幅広く対応していますが、具体的な対応バージョンについては、導入する pg_bigm バージョンのドキュメントを確認してください。pg_bigm 1.2 バージョンのドキュメントには PostrgeSQL 9.1.x から 10.x に対応していると記載されています。
pg_bigm は以下ページでソースコードと rpm パッケージが配布されています。 rpm パッケージは PostgreSQL RPM Building Projectの PostgreSQL rpm パッケージと組み合わせて使うことができます。

ソフトウェア配布ページ: https://ja.osdn.net/projects/pgbigm/releases/

ソースコードから Linux/UNIX 上の PostrgeSQL むけに標準的な手順でビルド・インストールできます。以下のコマンドは導入する PostgreSQL のコマンドにパスが通った状態で実行します。

$ tar zxf pg_bigm-1.2-20161011.tar.gz
$ cd pg_bigm-1.2-20161011
$ make USE_PGXS=1
$ su -c 'make USE_PGXS=1 install'

pg_bigm は Windows 版 PostgreSQL むけにもビルド可能です。ただし、 pg_bigm 開発元で動作確認しているプラットフォームには含まれていません。また、ビルドには Visual Studio などの Windows むけ開発環境が必要です。使用には少しハードルが高いといえます。PostgreSQL の商用版である PowerGres on WindowsPowerGres Plus Windows 版には pg_bigm モジュールも含まれていますので、これらを利用しても良いかもしれません。

pg_bigm を使用するためには、 postgresql.conf で shared_preload_libraries に pg_bigm を加えます。これは PostgreSQL 再起動で反映されます。

shared_preload_libraries = 'pg_bigm'

そのうえで、 pg_bigm を使用したいデータベース上で CREATE EXTENSION コマンドを実行します。

db1=# CREATE EXTENSION pg_bigm;
CREATE EXTENSION

◆ インデックス検索の例

以下のテーブルを作ってテストしてみます。

db1=# CREATE TABLE t_book
          (id serial primary key, file text, line int, para text);

ここに日本語訳が書き加えられた PostgreSQL マニュアルのソースファイルの全パラグラフを格納します。テーブルの総物理サイズは 15MB 、レコード数は 24134 件となりました。

これに対してキーワード検索を実行してみます。インデックスは使えませんので、シーケンシャルスキャンが行われます。全件を調べる動作ですので、どのようなキーワードを与えても同程度の応答時間となります。

db1=# SELECT id, file, line FROM t_book WHERE para LIKE '%高速%';
  id   |          file          | line
-------+------------------------+-------
   202 | array.sgml             |   925
   256 | backup.sgml            |   511
(中略)
 24119 | xtypes.sgml            |   178
(151 rows)

Time: 94.252 ms

続いて、パラグラフ内の文書を格納している para カラムに pg_bigm によるインデックスを作ってみます。動作環境とデータ規模に応じてそれなりに時間がかかります。本環境では 13.8 秒を要しました。

db1=# CREATE INDEX idx_bigm_book ON t_book
        USING gin (para gin_bigm_ops);
CREATE INDEX
Time: 13759.958 ms

インデックス作成後、もう一度同じ問い合わせを実行すると、所要時間が 94 ms から 4.5 ms に短縮されました。

db1=# SELECT id, file, line FROM t_book WHERE para LIKE '%高速%';
  id   |          file          | line
-------+------------------------+-------
   202 | array.sgml             |   925
   256 | backup.sgml            |   511
(中略)
 24119 | xtypes.sgml            |   178
(151 rows)

Time: 4.543 ms

explain コマンドで実行プランを確認すると、 Bitmap Index Scan にて作成したインデックスが使われていることがわかります。

db1=# explain
       SELECT id, file, line FROM t_book WHERE para LIKE '%高速%';
                                 QUERY PLAN
------------------------------------------------------------------
 Bitmap Heap Scan on t_book  (cost=16.02..23.84 rows=2 width=23)
   Recheck Cond: (para ~~ '%高速%'::text)
   ->  Bitmap Index Scan on idx_bigm_book  (cost=0.00..16.02 rows=2 width=0)
         Index Cond: (para ~~ '%高速%'::text)
(4 rows)

◆ その他の機能

pg_bigm は類似度検索にも使うことができます。そのための関数と演算子が提供されます。検索のサンプル用に t_book テーブルのファイル名のカラムだけ取り出したテーブルを作って、 pg_bigm によるインデックスを作ります。

db1=# CREATE TABLE t_file AS SELECT DISTINCT file FROM t_book;
db1=# CREATE INDEX idx_bigm_file ON t_file USING gin (file gin_bigm_ops);

設定パラメータ pg_bigm.similarity_limit にヒットする類似度( 0 から 1 の範囲)の閾値を指定します。そのうえで「文字列が類似しているか」という =% 演算子を使って検索すると、以下のように少し間違った文字列から検索することができます。 =% 演算子はインデックスが無くとも利用可能です。

db1=# SET pg_bigm.similarity_limit TO 0.6;
SET
db1=# SELECT file FROM t_file WHERE file =% 'pgtrigrm.sgml';
    file
-------------
 pgtrgm.sgml
(1 row)

なお、本機能は比較する文字列全体の類似度です。文章に対して検索キーワードのあいまい検索ができるわけではない点に注意してください。

◆ チューニング

pg_bigm を使った検索の速度が遅いときに、設定パラメータ pg_bigm.gin_key_limit を調整して解決できる場合があります。
pg_bigm による LIKE 中間一致検索は、まずインデックス検索で 2 文字ペアが該当するものを拾い出し、その後 Recheck で正確に条件に一致するものを絞り込みます。
pg_bigm.gin_key_limit はインデックス検索の段階で使う bi-gram (切り出した 2 文字)の個数を制限するパラメータです。SET文で指定可能です。デフォルトは 0 で、制限なく全ての bi-gram を使うという意味です。設定値を 10 とすると、検索文字列から最大 10 個だけの bi-gram を使ってインデックス検索をして、余分にヒットした結果を Recheck で絞り込むという動作になります。
検索文字列が長い場合には、本パラメータを指定して制限を加えた方が速くなる場合があります。以下に例を示します。

db1=# SELECT id, file, line FROM t_book WHERE para LIKE '%例えば、あるトランザクションがすべての支店の残高を集計する作業を行なっているとき、アリスの口座がある支店からの引き落としを勘定に入れるけれども、ボブの口座がある支店への振り込みを勘定に入れないというのは受け入れられませんし、その逆も駄目です。%';
 id |     file      | line
----+---------------+------
 95 | advanced.sgml |  298
(1 row)

Time: 9.985 ms

db1=# SET pg_bigm.gin_key_limit TO 5;

db1=# SELECT id, file, line FROM t_book WHERE para LIKE '%例えば、あるトランザクションがすべての支店の残高を集計する作業を行なっているとき、アリスの口座がある支店からの引き落としを勘定に入れるけれども、ボブの口座がある支店への振り込みを勘定に入れないというのは受け入れられませんし、その逆も駄目です。%';
 id |     file      | line
----+---------------+------
 95 | advanced.sgml |  298
(1 row)

Time: 3.100 ms

◆ 注意事項

pg_bigm にはいくつかの欠点と制限事項があります。
pg_bigm はアルファベットの大文字小文字の同一視に対応していません。つまり、 LIKE 検索には適用可能ですが、 ILIKE 検索には使えず、また、類似度検索でも大文字と小文字も違いは単なる文字の違いとして扱われます。
また、 pg_bigm のインデックス対象文字列にはサイズ上限があります。約 100MB を超える文字列には適用できません。

3. まとめ

pg_bigm は、 PostgreSQL 上のデータに対する日本語の全文検索機能を実装する最も容易な手段といえます。外部にファイル等を持たず PostgreSQL 上のデータだけで処理が完結しますので、ストリーミングレプリケーションやバックアップに際して、追加的な考慮事項がありません。
全文検索にあたって pg_bigm を導入して効果があるのは、それなりにデータ量が多い場合、あるいは、頻繁にアクセスがあって1回の検索あたりの処理量を減らすことに意義がある場合といえます。インデックスが加われば、 INSERT や UPDATE にはインデックス更新の処理が加わることになりますので、導入するかどうか慎重な判断が必要となります。
提供される関数は本文書記載のもの以外にもいくつかあります。また、 pg_bigm のバージョンによって制限や対応 PostgreSQL バージョンの違いがあります。使用を計画する際には以下 URL のサイトにある pg_bigm のマニュアルを確認してください。

pg_bigm の Webサイト
http://pgbigm.osdn.jp/index.html