BloGroonga

2011-07-28

InnoDB純正の全文検索エンジンInnoDB FTS


つい先日、MySQL-5.6.3-labs版がリリースがされました。この中にはInnoDBで動作する全文検索エンジン"InnoDB FTS"が含まれています。これまでは、MySQLとInnoDBの組み合わせで全文検索を行うためにはサードパーティの製品(mroonga 等..)が必要でしたが、これでズバっと選択肢が広がることになります。しかもInnoDBの開発チームが自ら開発した"純正の"エンジンということですから、これは大きな期待が持てます。
いったいどのような製品に仕上がっているのか、ざっくり記事やソースを読んで得た感触を述べてみたいと思います。
written by daijiro.mori

どんなエンジンか?


エンジンの概要については、 Overview and Getting Started with InnoDB FTS という記事によくまとまっていますが、Solr/LuceneやNamazuなどと同じく、転置索引方式の検索エンジンとなっています。転置索引方式といえばMyISAMのFTS実装もそうなのですが、MyISAM FTSとInnoDB FTSの最も大きな違いは後者が完全転置索引を採用している点です。完全転置索引とは、全文検索インデックスの中に、該当するワードが埋まっている文書IDだけでなく、それが文書中に出現した位置情報もすべて記録するタイプの転置索引を指します。
完全転置索引は、索引のサイズが大きくなり、構築により多くの時間を要するというデメリットがありますが、フレーズ検索や近傍検索(proximity search)を正確かつ高速に実行できるというメリットがあります。日本語のような非分かち書き言語を扱う場合、これは非常に重要なポイントとなります。(ちなみに他のFLOSS全文検索エンジンでは、Solr/Lucene, Senna/groongaは完全転置索引を採用しており、Namazu, Hyper Estraier等は採用していません。Sphinxは位置情報は全て記録しているのですが、正確な語彙表を持たないため、検索結果はやや不正確になります。)
話を戻すと、InnoDB FTSは、トークナイザなどが適宜整備されれば日本語全文検索のソリューションとして、MyISAM FTSよりもずっと実用的なものになることが期待できるということです。

どんな設計か?


InnoDB純正の全文検索エンジンだけあって、転置索引の実体もまたInnoDBの表によって実装されています。転置索引を一つ定義すると、InnoDB内部ではいくつかの補助表が作られます。この中の一つが転置索引の実体に相当します。転置索引補助表は、word, first_doc_id, last_doc_id, doc_count, ilistという5つのカラムを持っています。wordカラムには検索対象をトークナイズして得られた各文字列が、ilistカラムにはその文字列に対応する転置索引のポスティング情報が格納されます。ilistカラムの値は以下のような情報をBER圧縮したバイト列になっています。
 
[
  [
    最初の文書ID,
    [
      文書内の最初の出現バイト位置,
      文書内の出現バイト位置の差分,
      ..,
      0
    ]
  ],
  [
    文書IDの差分,
    [
      文書内の最初の出現バイト位置,
      文書内の出現バイト位置の差分,
      ..,
      0
    ]
  ],
  ..
]

一つのwordに該当する転置索引のエントリは、転置索引補助表の複数のレコードに分割して格納され、それぞれのレコードに含まれる文書IDの範囲はfirst_doc_id, last_doc_idカラムの値によって知ることができます。

リアルタイム更新性能は?


ところでRDB上で動作する全文検索エンジンなのですから、当然リアルタイムに転置索引を更新したいという要件があるはずです。InnoDB FTSはInnoDB上に構築されているわけですから、その更新性能がそのまま享受できそうなものなのですが、転置索引に特有の事情がやや絡んでいます。どういうことかと言いますと。。
一つの文書をトークナイズすると複数の(場合によっては大量の)wordが得られます。つまり文書が1レコード追加されると、背後では大量の更新クエリに相当することになります。これらを転置索引補助表に逐次反映していると、索引が断片化してしまうし更新性能も低下してしまうのです。そこで、InnoDB FTSでは赤黒木で実装したメモリ内のキャッシュ(Index Cache)に一旦これらの情報を蓄積しておいて、Index Cacheがいっぱいになったらマージした上で転置索引補助表に反映するようにしています。
InnoDB FTSに限らず、全文検索インデックスの動的更新はどのエンジンにとっても難易度の高いテーマです。手前味噌なのですが、実はSenna/groongaでもInnoDB FTSと同様に、メモリ上のキャッシュと、圧縮転置索引という二段構えの構成を採用しています。(ですので個人的にはInnoDB FTSの設計は好感が持てますw)
もう一つ世の中でよく使われる定番方式として、 Introduction to Information Retrieval にも載っているLogarithmic Mergingというものがあります。要は索引を何世代も小分けに作っておいて、それがたまってきたらマージする、という処理を再帰的に繰り返すのです。Solr/Luceneはこの方式を採用しています。しかし、この方式のエンジンでリアルタイム検索をこなそうとすると、間欠的に性能が落ち込むことになるため、実用的にはやや使いづらいものになってしまいます。
話を戻すと、InnoDB FTSはリアルタイム検索エンジンのソリューションとしても実用性が高いものになるかも知れない、ということです。

日本語対応は?


現状ではまだCJKには対応していません。しかし、N-GRAMトークナイザをサポートしたい、と先ほどの記事にも書いてあるので、近い将来サポートされるかも知れません。他にも、並列処理性能を高めるために、転置索引補助表がwordの先頭バイトによっていくつかに分割されていて、それが思いっきりハードコーディングされていたりする等、CJK対応の際に修正が必要な点がいくつかありますが、いずれもそれほど大きな問題ではないように思います。

まとめ


リリースされたばかりのInnoDB FTSですが、日本語全文検索エンジンとして実用的な製品となることが期待できるだけでなく、リアルタイム検索にも適した設計となっています。ただ、転置索引の実体がInnoDBの表によって実装されているのは、長所であると同時に、短所にもつながるかもしれないような予感もしています。なんとなくですが。。