現在位置: ホーム / OSSブログ / 1グラム(Unigram)の全文検索

1グラム(Unigram)の全文検索

今回は 1 グラムの全文検索を利用できるようにします。

■ 1 グラム(Unigram) の全文検索

1 グラムの全文検索は文字列を一文字単位で分割しインデックスします。PostgreSQL の場合、デフォルトで備わっている機能で利用できます。文字列を一文字単位で分割し、GIN でインデックスし、検索するだけです。以下に手順を示します。

テスト用テーブルを作成

# CREATE TABLE test2 (id SERIAL, txt TEXT);

保存用の関数を作成

CREATE OR REPLACE FUNCTION unigram(text) RETURNS tsvector AS $$
SELECT to_tsvector('simple', array_to_string(regexp_split_to_array($1, E'\\s*'),' '));
$$ IMMUTABLE LANGUAGE SQL;

textsearch_ja で単語単位に区切って tsvector を作成します。ここでは 1 グラムの全文検索を行いたいので正規表現で一文字単位に分割しています。PostgreSQL は関数インデックスをサポートしているので、この関数をインデックスします。

クエリ用の関数を作成

CREATE OR REPLACE FUNCTION uniquery(text) RETURNS tsquery AS $$
SELECT to_tsquery(array_to_string(regexp_split_to_array($1, E'\\s*'),'&'));
$$ LANGUAGE SQL;

tsquery は検索する単語を "&" で区切って渡します。1 グラムの全文検索なので一文字で分割し "&" で区切ります。

検索用のインデックスを作成

CREATE INDEX unigram_index ON test2 USING GIN(unigram(txt));

GIN を使い unigram 関数で txt コラムをインデックスしています。

以上で全文検索を利用できるようになります。単語ベースの textsearch と異なり任意の文字列の検索が可能になりました。SQL の LIKE クエリは前方一致検索以外は苦手ですが、この方法ではより効率的に中間一致の検索ができるようになります。

■■ 全文検索の動作確認

簡単なテストデータを挿入して試してみます。

INSERT INTO test2 (txt) VALUES ('PostgreSQLは日本語に対応している。');
INSERT INTO test2 (txt) VALUES ('PostgreSQLは日本語に対応している。');

このデータから "日本語" を検索するにはテキスト検索演算子の @@ を利用します。

演算子説明
@@ tsvectorがtsqueryに一致するか? to_tsvector('fat cats ate rats') @@ to_tsquery('cat & rat')

@@ 演算子を利用して

SELECT * FROM test2 WHERE unigram(txt) @@ uniquery('日本語') ;

とすれば良いように思えますが、この検索方法では '日','本','語' を含むレコードも検索してしまいます。'日曜日は本を読み感想を語る' という文章にもマッチしてしまいます。試しにこのデータも挿入してクエリを実行してみます。

INSERT INTO test2 (txt) VALUES ('日曜日は本を読み感想を語る');

クエリを実行すると、不必要なレコードまで検索されていることが分かります。

 SELECT * FROM test2 WHERE uniquery('日本語') @@ unigram(txt);
┌────┬────────────────────────────────────┐
│ id │                txt                 │
├────┼────────────────────────────────────┤
│  1 │ PostgreSQLは日本語に対応している。 │
│  2 │ PostgreSQLは日本語に対応している。 │
│  3 │ 日曜日は本を読み感想を語る         │
└────┴────────────────────────────────────┘
(3 行)

時間: 0.379 ms

これを防ぐには LIKE で検索するデータを制限します。

SELECT * FROM test2 WHERE uniquery('日本語') @@ unigram(txt) AND txt LIKE '%日本語%';
┌────┬────────────────────────────────────┐
│ id │                txt                 │
├────┼────────────────────────────────────┤
│  1 │ PostgreSQLは日本語に対応している。 │
│  2 │ PostgreSQLは日本語に対応している。 │
└────┴────────────────────────────────────┘
(2 行)

時間: 0.380 ms

必要なデータのみが検索されていることがわかります。実際に望み通りの検索方法になっているか、EXPLAIN ANALYZE で確認してみます。

LIKE を追加する前のクエリプラン

EXPLAIN ANALYZE SELECT * FROM test2 WHERE uniquery('日本語') @@ unigram(txt);

┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────
│                                                      QUERY PLAN                                             
├─────────────────────────────────────────────────────────────────────────────────────────────────────────────
│ Bitmap Heap Scan on test2  (cost=20.26..24.52 rows=1 width=36) (actual time=0.018..0.018 rows=3 loops=1)    
│   Recheck Cond: (to_tsquery(array_to_string('{日,本,語}'::text[], '&'::text)) @@ unigram(txt))              
│   ->  Bitmap Index Scan on unigram_index  (cost=0.00..20.26 rows=1 width=0) (actual time=0.016..0.016 rows=3
│         Index Cond: (to_tsquery(array_to_string('{日,本,語}'::text[], '&'::text)) @@ unigram(txt))          
│ Total runtime: 0.034 ms                                                                                     
└─────────────────────────────────────────────────────────────────────────────────────────────────────────────
(5 行)

LIKE を追加後のクエリプラン

 EXPLAIN ANALYZE SELECT * FROM test2 WHERE uniquery('日本語') @@ unigram(txt) AND txt LIKE '%日本語%';

┌─────────────────────────────────────────────────────────────────────────────────────────────────────────────
│                                                      QUERY PLAN                                             
├─────────────────────────────────────────────────────────────────────────────────────────────────────────────
│ Bitmap Heap Scan on test2  (cost=20.26..24.53 rows=1 width=36) (actual time=0.020..0.021 rows=2 loops=1)    
│   Recheck Cond: (to_tsquery(array_to_string('{日,本,語}'::text[], '&'::text)) @@ unigram(txt))              
│   Filter: (txt ~~ '%日本語%'::text)                                                                         
│   Rows Removed by Filter: 1                                                                                 
│   ->  Bitmap Index Scan on unigram_index  (cost=0.00..20.26 rows=1 width=0) (actual time=0.015..0.015 rows=3
│         Index Cond: (to_tsquery(array_to_string('{日,本,語}'::text[], '&'::text)) @@ unigram(txt))          
│ Total runtime: 0.039 ms                                                                                     
└─────────────────────────────────────────────────────────────────────────────────────────────────────────────
(7 行)

想定通り、全文検索インデックスが利用されている事がわかります。

PostgreSQL の全文検索はランク付けもサポートしているので、ランクを利用し、できるだけ検索文字がまとまっている結果を抽出することが可能です。全ての中間一致レコードを検索する必要がない場合は、ランクを利用した最適化を考えても良いでしょう。

■■ 簡単なベンチマーク

実際どの程度速くなっているのか、青空文庫の「我輩は猫である」のテキストデータを 1000 回挿入(約 230 万行)したテーブルで検索を行ってみました。

(テキストは加工せず、1 行を 1 レコードとして挿入しました。この為、1つのレコードの大きさには大きな偏りがあります。)

EXPLAIN ANALYZE SELECT * FROM test2 WHERE txt LIKE '%日本語%';
時間: 3201.016 ms
EXPLAIN ANALYZE SELECT * FROM test2 WHERE uniquery('日本語') @@ unigram(txt) AND txt LIKE '%日本語%';
時間: 485.152 ms

およそ 6 倍高速であることがわかりました。任意テキストの検索を行う必要がある場合、LIKE 検索より充分に速い事がわかります。

■■ インデックスサイズ

1 グラムの全文検索インデックスは単語ベースの全文検索インデックスよりも大きなインデックスになります。大きなテキストデータベースになればなるほどインデックスの大きさは問題になります。先ほどのベンチマークに使ったインデックスのサイズは以下の通りでした。

SELECT c2.relname, c2.relpages
FROM pg_class c, pg_class c2, pg_index i
WHERE c.relname = 'test2' AND
      c.oid = i.indrelid AND
      c2.oid = i.indexrelid
ORDER BY c2.relname;
┌───────────────┬──────────┐
│    relname    │ relpages │
├───────────────┼──────────┤
│ unigram_index │   101736 │
└───────────────┴──────────┘
(1 行)

時間: 6.238 ms

1 ページが 8KB なので約 800MB のインデックスサイズになっています。

テーブルサイズは以下の通りです。

SELECT relname, relpages
FROM pg_class WHERE relname = 'test2';
┌─────────┬──────────┐
│ relname │ relpages │
├─────────┼──────────┤
│ test2   │    88538 │
└─────────┴──────────┘
(1 行)

時間: 0.295 ms

テキストデータのおよそ 6 倍のインデックスサイズになった事がわかります。PostgreSQL のテキストコラムは Toast と呼ばれる仕組みで圧縮されます。

PostgreSQL 9.4 では GIN インデックスが改良され、インデックスサイズは約 1/3 になるとされています。テキストデータ 732KB を 1000 回挿入したデータ、約 714MB のデータに対して PostgreSQL 9.4 では 250MB 程度、データサイズおよそ倍程度のインデックスサイズになると予想できます。

比較的小さなテキストデータをより高速に検索するには充分ですが、大きなテキストデータをインデックスする場合にはインデックスの大きさが問題になることが分かります。GIN インデックスの更新は比較的遅い事にも注意が必要です。

■■ PostgreSQL 9.4のGINインデックス

実際に PostgreSQL 9.3 と同じテーブルに同じデータを挿入してみました。当然ですが、テーブルサイズは同じになります。

FROM pg_class WHERE relname = 'test2';
┌─────────┬──────────┐
│ relname │ relpages │
├─────────┼──────────┤
│ test2   │    88538 │
└─────────┴──────────┘
(1 行)

時間: 0.286 ms

PostgreSQL 9.4 では GIN のインデックスサイズとインデックスへの挿入が高速化されています。検索速度は同じであるとされています。

実際に検索してみると、同等の postgresql.conf で LIKE、テキスト検索どちらも多少速くなっていますが、大きな違いはありませんでした。全体的に高速化されているのはバージョンアップによる PostgreSQL 全体の高速化だと思われます。

EXPLAIN ANALYZE SELECT * FROM test2 WHERE txt LIKE '%日本語%';
時間: 2976.471 ms
EXPLAIN ANALYZE SELECT * FROM test2 WHERE uniquery('日本語') @@ unigram(txt) AND txt LIKE '%日本語%';
時間: 452.720 ms

特筆すべきはインデックスサイズでした。インデックスサイズは PostgreSQL 9.3 の 25% 程度まで減少しています。ここまで激減した理由はインデックスしたデータの特徴が新しい GIN インデックスに向いている為だと思われます。一般には PostgreSQL 9.4 のリリースノートなどに記載されている通り 1/3 程度になると思っておくと良いでしょう。

SELECT c2.relname, c2.relpages
FROM pg_class c, pg_class c2, pg_index i
WHERE c.relname = 'test2' AND
      c.oid = i.indrelid AND
      c2.oid = i.indexrelid
┌───────────────┬──────────┐
│    relname    │ relpages │
├───────────────┼──────────┤
│ unigram_index │    25993 │
└───────────────┴──────────┘
(1 行)

時間: 65.509 ms

PostgreSQL 9.3 では 101736 ページ (およそ 800MB) 利用しましたが、25993 ページ (およそ 200MB) しか利用していません。この程度の大きさであればあまり気にせず使う事ができると思います。

■ まとめ

1 グラムの全文検索インデックスは単語ベースの全文検索と異なり、任意の文字列を検索できる利点があります。PostgreSQL の場合、追加の拡張を利用しなくても 1 グラムの全文検索が利用できることは大きなメリットです。PostgreSQL 9.4 からは GIN がより小さく、更新も高速化されるので利用できる場面は広がると思います。特に環境を指定しづらいオープンソース製品などでは便利に利用できると思います。

今回利用したテストデータで GIN インデックスサイズが 5% 程度まで激減することは予想外でした。インデックスサイズがインデックス対象のデータサイズよりも小さくなってしまった事も予想外でした。実際にテストしてみる事の重要性を改めて実感しました。PostgreSQL の GIN インデックスを利用しているユーザーは 9.4 へのアップグレードで大きな利益を得ると思います。