高速全文検索

データベースに格納した文書から、特定の文字列を検索するのに LIKE 演算子を用いても、データ量がさほど大きくなければ瞬時に結果を返してくれるが、 ある程度の量になると許容できない待ち時間となる。 たとえば「大規模でないデータ処理ならフィルタコマンドで十分なのでは」 で示した実験のように、12万件1.5GBでの LIKE 利用検索約2秒、 のように1、2秒を超えるようだと複数人同時アクセスに耐えられないと想像できる。

ここでは SQLite3 標準の FTS(Full Text Search) モジュールを用いた高速全文検索可能なデータベースの構築法を簡単に示す。

なお、FTS モジュールの検索では MATCH 演算子を用いるが、MATCH では単語完全一致もしくは単語先頭一致のみの対応である。つまりたとえば

ということである。この「単語」という単位が日本語処理においては曲者で、 わかち書きのない日本語では文脈を読み取って単語ごとに分けなければならない。 このような処理を形態素解析といい、多くのツールが存在している。SQLite でも日本語に適した形態素解析器を組み込んで利用できる設計になっているが、 簡易的な解析器が標準で利用できるようになっているので ここではそれを利用した例を紹介し、高速全文検索システムを作る足掛かりを示す。

FTS

FTSは SQLite の標準配布ソースに入っている全文検索用のモジュールで、 SQLite 3.10.x の時点では FTS3、FTS4、FTS5 の3つのバージョンが用意されている。 FTS モジュールは性能改善が盛んに行なわれるため、できるだけ新しいバージョンの SQLite のソースアーカイブを入手して手許でビルドしたものを使うのがよいだろう。

FTSつき SQLite のビルド

SQLite の標準配布ソースには FTS モジュールも入っていて、 それを有効化したバイナリを作成すれば、すぐに全文検索を試すことができる。 OS標準に付属している sqlite3 コマンドや、 パッケージングシステムによってインストールされるものでは、 日本語全文検索を行なうのに十分な状態でないことが多い。 ここでは本稿執筆時点で最新の SQLite 3.10.2(2016-01-20) に ICU tokenizer を組み込んでビルドする例を示す。

ICU Project(International Components for Unicode)による libicu は C/C++、Java でUnicodeを取り扱うためのライブラリであり、 そのなかにUnicodeによる文字並びを最短語素に分解する機能がある。 SQLiteでは形態素解析器を外部のライブラリで行なわせることができ、 そのうち手軽に利用できるのが ICU tokenizer であり今回はこれを利用する。 なお、システムに libicu を導入できない場合のために、SQLite 標準添付の unicode61 tokenizer を使う例も示す。

libicu の導入

可能であればICUライブラリを事前に導入する。OS ごとの導入例をいくつか示す。

: Debian由来の Linux ディストリビューションの場合
sudo apt-get -y install libicu-dev
: Arch Linuxの場合
sudo pacman -S icu
: FreeBSD
sudo pkg install icu
: pkgsrc
cd /usr/pkgsrc/textproc/icu
sudo make install clean clean-depends

導入完了なら icu-config コマンドが利用できるようになっているはずである。

icu-config --ldflags
-L/usr/local/lib -licui18n -licuuc -licudata

icu-config コマンドからの出力例はFreeBSD pkg システムの場合であり、システムごとに異なるが、ライブラリのリンクに必要な リンカ(ld)用オプションが現れていれば問題ない。

SQLite3のソース取得とビルド

前書きに記したように SQLite のサイト http://www.sqlite.org/ の Download リンクから最新版のソースをたどりアーカイブを取り寄せ展開する。 下記の例は sqlite-autoconf-3100200.tar.gz (SQLite 3.10.2) の例である。

gzip -dc sqlite-autoconf-3100200.tar.gz|tar xpf -
cd sqlite-autoconf-3100200

FTS4とICUが有効になるように configure スクリプトを起動し、成功したら make する。

CFLAGS="-DSQLITE_ENABLE_FTS4 -DSQLITE_ENABLE_ICU" \
	LDFLAGS=`icu-config --ldflags` \
	./configure --prefix=/usr/local/sqlite3 && make

うまく行けば、FTS4+ICU の使える sqlite3 コマンドができ上がる。

./sqlite3
CREATE VIRTUAL TABLE foo USING fts4(bar, tokenize=icu ja_JP);

エラーメッセージが出なければ構築完了である。

もし ICU ライブラリがうまく入らない場合は、デフォルトの tokenizer の unicode61 を利用する。単語区切りの精度は落ちるが高速さの度合いは体感できる。

インストールする。

sudo make install

インストールした sqlite3 が優先的に起動されるよう環境変数 PATH に設定しておく。

PATH=/usr/local/sqlite3/bin:$PATH

FTSを利用するシェルスクリプトの先頭にも入れておく。

FTSの利用

ここでは例として、1章でも利用した全国郵便番号データを利用する。 1章で作成したデータベースに FTS 用のテーブルを CREATE VIRTUAL TABLE で作成する。

sqlite3 zip.sq3
.mode csv
-- fts4+ICU のテーブル作成
CREATE VIRTUAL TABLE zfts4icu using fts4(
  x0401, zip5, zip7, prefkana, citykana, townkana, pref,
  city, town, multi, koaza, chome, mcover, modify, modreason,
  random, tokenize=icu ja_JP);
-- さらに比較用に fts4+unicode61 で FTS 用テーブル作成
-- ICUライブラリがない場合はこちらだけでもよい
CREATE VIRTUAL TABLE zfts4u61 using fts4(
  x0401, zip5, zip7, prefkana, citykana, townkana, pref,
  city, town, multi, koaza, chome, mcover, modify, modreason,
  random, tokenize=unicode61);
-- zipテーブルにあるデータをすべて FTS テーブルに入れる
-- 検索インデックスを作りながらなので時間がかかる!
INSERT INTO zfts4icu SELECT * FROM zip;
INSERT INTO zfts4u61 SELECT * FROM zip;
.quit
: データベースファイルサイズは約8.8GB
ls -lh zip.sq3
-rw-r--r--  1 yuuji  staff  8.8G Feb 14 16:44 zip.sq3

1.5GBほどのランダム文字列を FTS テーブルに入れると非常に時間が(2.1GHz CPU で約3時間半)かかるので、手短に実験したい場合は最後のランダム文字列用のカラム random を除外してテーブル作成するとよい。

ここまでの作業で以下の3つのテーブルが揃った。

種別テーブル名件数
通常テーブルzip121241件
FTS4, ICU ja_JPzfts4icu〃
FTS4, unicode61zfts4u61〃

通常テーブルからの LIKE による検索と、FTS で利用できる MATCH による検索を比較してみる。MATCH では、単語先頭マッチしかサポートされていないため LIKE も先頭マッチのみを用いた。検索にかかる所要時間は sqlite3 ドットコマンドの .timer により計測し、DB ファイルがメモリにキャッシュされる前とあとの結果のもの2つを示した。

.timer on
SELECT pref, city, town FROM zip WHERE town LIKE '東泉%';
山形県|酒田市|東泉町
栃木県|矢板市|東泉
新潟県|南魚沼市|東泉田
大阪府|豊中市|東泉丘
福岡県|大牟田市|東泉町
福岡県|行橋市|東泉
1回目: Run Time: real 199.088 user 0.582354 sys 2.959307
2回目: Run Time: real 1.843 user 0.515334 sys 1.324779
SELECT pref, city, town FROM zfts4icu WHERE town MATCH '東泉*';
栃木県|矢板市|東泉
新潟県|南魚沼市|東泉田
大阪府|豊中市|東泉丘
福岡県|行橋市|東泉
1回目: Run Time: real 0.225 user 0.003671 sys 0.025219
2回目: Run Time: real 0.003 user 0.000567 sys 0.001418
SELECT pref, city, town FROM zfts4u61 WHERE town MATCH '東泉*';
山形県|酒田市|東泉町
栃木県|矢板市|東泉
新潟県|南魚沼市|東泉田
大阪府|豊中市|東泉丘
福岡県|大牟田市|東泉町
福岡県|行橋市|東泉
1回目: Run Time: real 0.182 user -0.000167 sys 0.022389
2回目: Run Time: real 0.001 user 0.000297 sys 0.001092

計測結果をまとめると以下のようになる。

テーブル1回目(total/user/sys) 2回目(total/user/sys)
通常 (LIKE)199.088s / 0.582s / 2.959s 1.843s / 0.515s / 1.325s
FTS4+ICU (MATCH)0.225s / 0.004s / 0.025s 0.003s / 0.001s / 0.001s
FTS4+unicode61 (MATCH)0.182s / 0.000s / 0.022s 0.001s / 0.000s / 0.001s

注目すべきは次の2点である。

  1. FTSテーブルは通常テーブルより100倍以上高速に結果を返す。
  2. ICUの先頭マッチ検索が返すものが他と異なっている。

気をつけなければならないのは後者で、FTS テーブル構築時の tokenizer が異なることによる。 「東泉*」というパターンで他が6件見付かっているのに tokenize=ICU で4件なのは、「東泉町」が「東+泉町」と単語分解されて入っているためで、 試しにその単語分割で検索すると見付かる。

SELECT pref, city, town FROM zfts4icu WHERE town MATCH '東 泉町';
山形県|酒田市|東泉町
福岡県|大牟田市|東泉町
SELECT pref, city, town FROM zfts4icu WHERE town MATCH '東 泉*';
山形県|酒田市|東泉町
福岡県|大牟田市|東泉町

逆に、tokenize=unicode61 では同種の文字並びが1単語とみなされるので、 漢字が並んでいるものはすべて1単語の扱いとなる。

このようにFTSでは、インデックス作成時の tokenize 指定 が検索キーワード指定に対する結果を左右するため、 利用者の期待どおりの検索機能を実装するには、 それにふさわしい形態素解析器を準備することが必要になる。

yuuji@koeki-u.ac.jp