松本です。

正月休みを利用して、Rastを色々といじってみました。
その結果、150万件の登録を１時間弱で行う事ができるように
なりましたので、お知らせしたいと思います。

■すぐに試したい人へ
添付のパッチをリビジョン62に当てて下さい。
各データベースは従来バージョンと互換性がありません。データベースは新しく
作って下さい。また構造体のサイズや内容も一部変わっていますので、関連プロ
ジェクトはすべてリコンパイルして下さい。

プログラムではdb_register()の実行前後で、以下の関数をコールして下さい。

// 大量登録の準備を行う
db->db_begin_bulk_registration(db);

// ここで大量登録を行う
while(なんたら)
 db->db_register(...);

// 大量登録を終了し、データベースを更新
db->db_commit_bulk_registration(db);


■出来る事
P3 800MHz RAM 256Mのマシンで、文書ひとつ当たり平均154文字のeuc-jpテキスト
を、１時間弱で150万件登録できるようになります。リビジョン58を同等程度のRAM
使用量で実行した場合(options->sync_threshold_chars = 3000000)と比較し、約
35倍速い事になります。またデフォルトのバッファサイズを用いた時
(options->sync_threshold_chars = 100000)と比較し、約320倍速くなります。
計算量オーダーはO(N * log(N))です。O(N)にはなりませんでしたが、理論的には
300万件で130分程度、600万件で270分程度ではないかと思います。ただし、極めて
多くのプロパティを登録した場合等は、BerkeleyDBの性能に依存してくる可能性が
あります。

また、rast-ja No.49のパッチも適用済になっていて、検索も約70倍速くなりま
す。前回のパッチでは削除済データを認識できない、スコアを正しく生成できな
いという問題がありましたが、以下の方法で回避しました。

・正しくソートできない
転置インデックス内に文書長の情報を埋め込む事により、プロパティ情報を読み
込む事なく、文書長を取得するようにしました。

・削除データを認識できない
削除マークを別途データベース化する事により対応しました。削除マークデータ
ベースはとても単純な構造です。１レコード４バイトで、ひたすら削除マーク済
のdoc_idを記録していきます。データベースをオプティマイズすると、削除マー
クデータベースは空になる予定ですが、現在オプティマイズそのものが未完成の
ため、実装されていません。

■出来なくなった事、悪くなった点
プロパティでソートする事ができません。プロパティでソートしても高速性を維
持する事は可能だと思いますが、現在実装されていません。せめて完成するまで
はプロパティソートは従来と同様の方法で出来るようにしたいと思ってはいるの
ですが、これも実装されていません。ですのでこのパッチを当てると、プロパテ
ィでソートする事が一切できなくなります。

また、現在オプティマイズが実装されていません。削除データベースの運用や、
後述する登録専用データベースの運用等でオプティマイズは必須要件とも言える
のですが、今の所出来ていません。もちろん、作っていきたいと思っています。

その他については、従来のRastで出来た事は、すべて出来ると思います。ただ
し、db_begin_bulk_registration()とdb_commit_bulk_registration()はローカル
DBにのみ実装してありますので、それ以外のデータベースでは利用できません。
またRubyのバインディングはいじっていませんので、現状では高速登録はＣ言語
からのみの利用という事になります。

■どのように使うのか？
db_register()の実行の前後で、以下の関数をコールして下さい。

// 大量登録の準備を行う
db->db_begin_bulk_registration(db);

// ここで大量登録を行う
while(なんたら)
{
 ...
 db->db_register(...);
 ...
}

// 大量登録を終了し、転置インデックスを更新
db->db_commit_bulk_registration(db);

と言うわけで、大量登録したい時は明示的にトランザクションを宣言します。コ
ミットするまでは、登録中のデータは検索に反映されません。
トランザクションを中止するdb_rollback_bulk_registration()という関数が構造
体の中には用意されていますが、現在実装されていません。
たまたまトランザクションぽい感じになったのでトランザクションと呼んでみま
したが、ACID特性は期待しないで下さい。:-) ただし、一応それらしい動作をす
る準備をやってます。もう少し工夫すれば更新が検索をブロックしなくて済むよ
うになると思いますし、更新が更新をブロックしない構造も不可能では無いと思
います。

なお、大量登録以外の登録は、従来通りdb_register()単体で実行して下さい。登
録用のデータベースは検索用のデータベースとは別に用意してありますので、登録
文書数がかなり大きくなっても、db_register()の実行時間はあまり長くなりませ
ん。検索時には登録用データベースの内容も検索しますので、登録直後から検索結
果に反映されます。
ただし、この状態を放っておくと、次第にdb_register()の実行時間が長くなって
しまいます。オプティマイズを実行する事により、登録時間はまた短くなります。
オプティマイズは従来通り、rast_local_db_optimize()で実行する予定ですが、
現在実装されていません。

どのぐらい登録したらオプティマイズするべきか、また、どのぐらいの文章を登録
するならdb_begin_bulk_registration() を利用するべきかについては、今の所、
データが揃っていません（なにせオプティマイズが完成していませんので……）。
ただし、空のデータベースに登録する時には、db_begin_bulk_registration() を
利用した方が通常はよいと思います。
現実的な運用としては、最初の１回はdb_begin_bulk_registration()を利用し、そ
の後随時登録されるデータはdb_register()単体で利用する。そして日に１回、あ
るいは週に１回等の割合でオプティマイズを実行するというような方法が良いと思
います。

■何をやっているのか
詳しく話せば長くなると思います。
簡単に申し上げると、Rastの登録時間をO(N**2)であると仮定したとしても、微小
部分においてはO(N)である事を利用しました。つまり、全登録内容を微小部分に
分割し、適時マージするという方法を取っています。ここで言うマージは、ファ
イルの物理的なマージであり、Rastが従来より持っている複数データベースの結
合検索とは異なります。マージそのものはO(N**2)ですが、登録方法を工夫しまし
て、理論的にはO(N * log(N))で動作します。実測値においても理論値に近い値が
出ています。

また、text.ngmを作らない事も高速化の要因になっています。
ただし検索にはtext.ngmが必要ですので、db_commit_bulk_registration()のタイ
ミングで作成します。text.ngmを作成するために必要な情報は、text.posの中に
予め埋め込んでおきます。

以下のURLのエクセルファイルは、新しい登録方法による各種資料です。

http://shop.spline.tv/rast.xls

資料内で「フラクタル法」と呼んでいる方法を、バルク登録の実装に利用していま
す。また、単体でdb_register()を実行した時には、「シーケンシャル法」と呼ん
でいる登録方式を利用しています。添付資料はまとまっていない部分も多いのです
が、もし興味を持たれた方がいらっしゃいましたらご質問下さい。

よろしくお願いします。

追伸１：
以前rast-ja No49 において、text.ngmでBDBの利用をやめ、2.5GBの単純なバケツ
にマッピングしてみたら速くなるかも知れないと言いましたが、その実装はやめ
ました。と言うより、その実装で速くする事はできないだろう事が分かってきて
しまいました。

追伸２：
Rastのソースは綺麗ですね :-) なるべくコーディングスタイルを似せたつもりな
んですが、汚してしまったかも知れません。また、BDBやapr等、あまり使った事が
無かったのでとても参考になりました。


-- 
archive-> http://qwik.netlab.jp/rast-ja/18.html 
ML-> rast-ja@q...