Kouhei Sutou
kou****@clear*****
2015年 2月 17日 (火) 16:09:42 JST
森さん 須藤です。 先日森さんに教えてもらった転置索引で検索するときの性能向上案 を実装してみました。確認してもらえませんか？ https://github.com/groonga/groonga/pull/281 頻出トークン（「です」とか）とレアトークン（「転置」とか）を 一緒に検索するときに検索性能が向上するパッチです。 （森さん以外でも興味がある人は後述する「動作確認」や「性能検 証」を手伝ってくれるとうれしいです。） 頻出トークンとレアトークンがあるときは、先にレアトークンが存 在する文書IDを検索します。ここは変わりません。 レアトークンが存在する文書IDを見つけたら、頻出トークンの方の 対応する文書IDを探します。このとき、トークンに紐付いている文 書IDは文書ID順にソートされているので、レアトークンで見つかっ た文書IDが見つかるまでは途中の文書IDをすっ飛ばすことができま す。これを実現するのがこのパッチです。 Groongaの転置索引は * スキップリストで実装されていて変更が可能なn個の「バッファー」 と * 変更が不可能だけど空間効率がよいm個の「チャンク」 にわかれていて、検索するときは両方のデータをマージしています。 （と、理解しました。） 2個目以降のトークンの場合は、前のトークンで見つかった文書ID をii->minに設定して、バッファーもチャンクもガンガン次のバッ ファー・次のチャンクに進めるようにしました。 バッファーの場合はbuffer_rec->jumpがあればそれを使って一気に 飛んで、チャンクの場合は飛べるなら今のチャンクを最後まで読ま ずに次のチャンクに飛ぶようにしたつもりです。 ↑のパッチですが、デフォルトでは無効にしていて GRN_II_CURSOR_SET_MIN_ENABLE という環境変数をしていすると有効になるようにしています。 これは次の2つのことをしやすくするためです。 * 動作確認 * この性能改善を入れても以前と動作が変わらないべき * 性能検証 * この性能改善を入れたら性能が向上するべき * この性能改善が効かないケースでもオーバーヘッドが十分小さいべき 興味のある人はこの2つをやってもらえないでしょうか？ ちなみに、この性能改善は小さな転置索引では効果がありません。 1つのバッファーしか使わないからです。複数のバッファー・複数 のチャンクになるようなある程度のサイズの文書量が必要です。 手元でWikipediaのデータを使って簡単に確認した感じでは2倍くら い高速になりました。 次のようにすると確認できるので、動作確認・性能検証に協力して くれる人は参考にしてください。（prefixは適宜変更してください。） ビルド: % git clone --recursive https://github.com/groonga/groonga.git % cd groonga % ./configure --prefix=/tmp/local % make -j8 > /dev/null % make install > /dev/null データ投入（schema.grnとdata.grnは各自用意してください）: % /tmp/local/bin/groonga -n /tmp/db shutdown % /tmp/local/bin/groonga /tmp/db < schema.grn % /tmp/local/bin/groonga /tmp/db < data.grn 従来の挙動を確認: % /tmp/local/bin/groonga /tmp/db select --query ... 改善後の挙動を確認: % GRN_II_CURSOR_SET_MIN_ENABLE=1 /tmp/local/bin/groonga /tmp/db select --query ... 開発への協力、よろしくお願いします！ -- 須藤 功平 <kou****@clear*****> 株式会社クリアコード <http://www.clear-code.com/> Groongaベースの全文検索システムを総合サポート: http://groonga.org/ja/support/ パッチ採用 - プログラミングが楽しい人向けの採用プロセス: http://www.clear-code.com/recruitment/ コードリーダー育成支援 - 自然とリーダブルコードを書くチームへ: http://www.clear-code.com/services/code-reader/
