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

検索システム勉強会資料

日時
2005年3月26日
場所
文京グリーンコート産総研オフィス

開発の目的

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

転置インデックス

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

設計方針(1/2)

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

設計方針(2/2)

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

n-gramインデックス vs 単語インデックス

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

適合率←→再現率: おさらい

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

適合率←→再現率: どーする?

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

sennaのアプローチ

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

実装

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

シンボル表

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

可変長レコード表

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

インデックスの構成

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