MySQLにおけるfulltext index
以前書いた、「mysql+sennaにおいて、sennaのインデックスと他のインデックスを組み合わせてクエリーを実行」というのを一部実現しました。(やたら時間が開いてしまいました。。 )
sennaのrev75に
bindings/mysql/mysql-2ind.diff
という小さなパッチをつけています。
これは、MySQLで全文検索したときに、sennaの処理はサクッと終わっても
その後MySQLのロジック上、MYDファイルをえんえんとスキャンしてしまう
類のクエリーを高速化するためのものです。
- count(*)で件数を取得して、全ヒット数を表示したい
- limitでページャ対応したい
- 他のカラムでソートしたい(日付順とか)
- 他のカラムで絞り込みたい(特定のユーザのレコードだけ検索したい)
などなど、実用的なwebアプリで頻繁に使われると思われるクエリー
がこのパッチを使うと見違えるように速くなります。
詳しくは以下を参照してください。
http://lists.sourceforge.jp/mailman/archives/senna-dev/2006-January/000187.html
はてなキーワードを高速に付与
sennaのsen_symクラスは、common prefix searchが可能です。この機能を使って(今更なのですが)Dartsと同じ手法ではてなキーワードを高速に付与するプログラムを作ってみました。
以下のような特徴があります。
- 任意のタイミングで付与対象のキーワードをインデックスに追加/削除できる
- インデックスの作成/更新が高速
- キーワード付与が高速
http://d.hatena.ne.jp/images/keyword/keywordlistの内容でインデックスを生成し、
350KB程度の日本語テキスト(EUC)にキーワードを付与した場合の処理速度を比較してみました。
Dartsを使ったインデックス作成 % time ./mkdarts keywordlist.sort keywordlist.da 2.010u 0.060s 0:02.74 75.5% 0+0k 0+0io 235pf+0w sennaを使ったインデックス生成 % time ./hatenapo keywordlist.pat ins < keywordlist.sort 0.680u 0.030s 0:00.73 97.2% 0+0k 0+0io 2648pf+0w Dartsを使ったキーワード付与 % time ./hatenakeyword < sample.txt > /dev/null 1.120u 0.060s 0:01.18 100.0% 0+0k 0+0io 211pf+0w sennaを使ったキーワード付与 % time ./hatenapo keywordlist.pat sel < sample.txt > /dev/null 0.560u 0.010s 0:00.57 100.0% 0+0k 0+0io 2085pf+0w
sennaもなかなか高速なことがわかります。ただし、検索に失敗した場合hatenakeyword(Darts)では1byteずつシフトしているのに対してhatenapo(senna)では1文字ずつシフトしているので、その点hatenapoが有利になっています(検索回数が半分程度で済んでいる)。common prefix searchそのものはDartsの方が高速かもしれません。
MySQLにおけるfulltext index
「実践ハイパフォーマンスMySQL」によれば、MySQLでは1つのクエリーを実行するとき1つのテーブルにつき1つのインデックスしか使用できません。
match against条件によって全文検索を行う時は、殆どのケースでfulltext indexを使用することになります。
しかし、例えば主キー条件と組み合わせた場合は、主キーインデックスを使用し、全文検索はテーブルスキャンによって行おうとするようです。
この挙動をうまく使えば、mysql+sennaにおいて、sennaのインデックスと他のインデックスを組み合わせてクエリーを実行することができるかも知れません。
全文検索ではしばしば非常に大量の行がヒットしますから、これは大幅な性能改善につながる可能性があります。
‥‥などともくろみつつin boolean modeを実装中です。
unicode正規化
http://dev.razil.jp/svnweb/senna/checkout/trunk/util/unicode/README
検索に必要なので書きました。
unicodeと言えばicu(http://ibm.com/software/globalization/icu)が定番ですが、
微妙に要件に合わないのでicuの出力をターゲットとして同様の正規化を行うcのコードを吐くスクリプトを書きました。
文書中からパタンを抽出して置換する問題は巷で話題の
「はてなキーワードを高速に付与する」問題と同じです。
http://chasen.org/~taku/blog/archives/2005/09/post_812.html
今回書いたのはtrieを生成しますから、
実行速度では恐らくDARTSにひけをとらないと思いますが、
空間効率ではDARTSの方が優れているかも知れません。
NFKCは日本語の全文検索にはオーバースペックなのですが、
敢えて時間をかけて対応したのは、
http://labs.cybozu.co.jp/blog/akky/archives/2005/08/google_yahoo.html
こういう考え方に感銘を受けたせいもあります。