全文検索エンジンSennaの設計

検索システム勉強会資料

日時

2005年3月26日

場所

文京グリーンコート産総研オフィス

• OSSパーツでGoogleを構成可能とすること
• LAMPを補完するパーツを作りたい
• ストレージエンジンに全文検索機能を追加する
• DBMS, ファイルシステムに組み込んで使用することを想定

• なぜ転置インデックス?
• 大規模な文書に対して高い検索性能を実現
• 転置インデックス型全文検索システムの構成
• 文書ファイル (文書毎の情報を局所化して格納)
• 転置ファイル (単語毎の情報を局所化して格納)
• Sennaは転置ファイルのみ提供
• 文書ファイルは流用可能な部品が一杯ある
• 転置ファイルは全文検索に特化した特殊な構造

• 本質的なトレードオフ
• 万能なエンジンは存在しない。どこでバランスするか
• 更新速度←→検索速度
• 転置インデックスは検索速度重視。可能な範囲で更新も頑張る
• 適合率←→再現率
• ‥どっちも大事

• リソース消費
• 実メモリより大きな文書セットもカバー。disk I/O 考慮
• 同時実行制御
• リーダとライタ間のロックは性能阻害要因→回避したい
• ACID特性の実現は高コスト→未コミット読み取りは許容
• 汎用性
• 様々なストレージエンジンと組み合わせて動作可能

               n-gramインデックス   単語インデックス
   適合率             ×                 ○
   再現率             ○                 ×
 インデックスサイズ   大                 小
 検索速度(小規模)     ○                 △
 検索速度(大規模)     △                 ○
 更新速度(小規模)     ○                 △
 更新速度(大規模)     △                 ○

• 小中規模文書セットならn-gramインデックス
• 大規模文書セットなら単語インデックス

• 京都 → 東京都
• 民主党 → 自由民主党
• あびる優 → 今注目をあびる優れたOSは?

• n-gramインデックスと単語インデックス選択可能に
• インデックス作成時に指定
• 検索時に適合率/再現率の優先順位を変えられない
• 両方のインデックス作る
• さすがにデカすぎ

• インデックスは単語単位で作成。シンボル表を部分一致可能に
• 任意の文字列で洩れなく検索可能
• どこまで再現率を求めるかソフトに調節可能
• 部分一致する文字列の中で取捨選択
• 字種境界等のヒューリスティックで
• 「ソフト分かち書き」技術で
• クエリーによっては検索時の転置ファイルI/Oが局所化できない
• 大規模文書ではI/Oネックで検索性能低下
• 大規模文書なら大体適合率重視だからいいか‥

• インデックスを構成する部品は二種類
• シンボル表: 文字列とIDとを対応づけて管理
• 可変長レコード表: 文書IDと位置情報のリストを単語毎に格納

• PATRICIAで実装
• 空間効率はhash表と同程度
• 前方一致可能
• 検索/更新速度はhash表よりやや遅
• 単語毎の半無限文字列を登録
• 部分一致検索が可能になる
• 日本語の単語のみならシンボル表の増大は1.5倍程度

• 転置ファイルの実体
• キーと値のペアを管理
• キー:単語ID
• 値:文書IDと位置情報のリスト
• 1文書の更新に対して複数のレコードを更新する必要がある
• バッファはメモリ上に確保(mmapしてる)
• バッファ上では非圧縮。連結リストで高速に更新
• ディスクフラッシュ時に圧縮

• 外部文書IDと内部文書IDを対応づけるためのシンボル表
• 外部文書IDは文字列だったり数値だったりいろいろ
• 外部IDが数値でも一旦内部IDに変換→圧縮率担保
• 単語文字列と単語IDを対応づけるためのシンボル表
• 正規化してから登録
• 単語IDと内部文書IDのリストを管理する可変長レコード表