今回はFINDSPOTのプロパティ検索式の最適化についての話題をとりあげます。

アーカイブシステムという側面

FINDSPOTを利用した開発案件をこなしていくうちに、文書管理などのアーカイブシステム、あるいは全文検索が可能なXML用のデータベースとして利用されることが多いのに気がつきました。これはFINDSPOTが文書のプロパティ情報を全文検索と併せて検索できる機能を持っているのが理由として考えられます。作者としては、文書のプロパティ情報で検索することも可能程度に軽くとらえていたのですが、実はニーズとしてはプロパティ検索も全文検索と同等程度のウェイトがありました。全文検索をまったく行わない、プロパティ情報のみの検索ニーズさえ存在することがわかってきたのです。

また多くの場合、全文検索のみが使われることは希で、多くの場合何らかのプロパティ検索が条件として加わる傾向がはっきりしてきました。中でも、権限付きの検索を実現するためにプロパティ情報を使って表現するのは、いつのまにか常套手段となっていました。

プロパティ検索が多用されるとなると、どうしても性能が問題になります。開発当初は全文検索の性能をいかに出すかに腐心していたので、プロパティ情報の検索性能が求められるとはまったく予想外でした。プロパティ検索の性能が問題になるつど、性能改善のための機能改善をFINDSPOT本体にも施してきましたが、一方で検索式の書き方の善し悪しが大きく検索性能に影響することが明らかになりました。今回は、どのような検索式が性能が悪いのか、また検索式を最適化する方法について解説します。

権限検索の例

権限検索の例として、プロパティに次の権限を表現するフィールドを設けます。

group_num    グループ番号

public_flag  公開フラグ(0:非公開, 1:公開)

検索システムにログインしたユーザが10番のグループに所属していたとします。このユーザは自分の所属するグループ内の文書で、かつ公開された文書のみしか検索できないものとします。

「地磁気センサー」という文字列で検索を行う際には、GUIやCGIによって生成される検索式は、次のようにグループ番号のプロパティと、公開フラグのプロパティの条件検索を使って権限の制約を設けます。

"地磁気センサー" AND ( [ group_num = "10" ] AND [ public_flag = "1" ] )

ここでは、検索対象として検索エンジンのインデックスに登録された文書が100万件、グループ番号のプロパティ10の文書が15万件、非公開（公開フラグが0）の文書が4万件、公開（公開フラグが1）の文書が残りの96万件とします。また、"地磁気センサー"という文字列を含む文書は400個としましょう。

FINDSPOTの検索は次のようなステップで実行されます。まずは、AND, OR, 括弧などで区切られた個々の部分検索が実行されます。検索結果は次のようになります。

"地磁気センサー"	→ 400件のヒット結果集合
[ group_num = "10" ] 	→ 15万件のヒット結果集合
[ public_flag = "1" ]	→ 96万件のヒット結果集合

次に、各ヒット結果の集合を元に、AND, 括弧等の論理演算を行います。

まずは、次の箇所です。

[ group_num = "10" ] AND [ public_flag = "1" ]

ここは次のような集合演算になります。

15万件のヒット結果集合 AND 96万件のヒット結果集合

この集合演算には、15万件のヒット結果と、96万件のヒット結果を付き合わせ、ANDの結果を得る処理が必要になります。この処理数は、かけ算に相当するので、15万×96万で1440億回のANDの処理が必要になります。1つのデータに対するANDの処理は比較的軽い処理ですが、1440億回ともなるとさすがに非常に大きなCPUリソースが必要です。

また、この部分の演算結果を14万件とすると、"地磁気センサー"の検索結果とのAND処理は次のようになります。

400件のヒット結果集合 AND 14万件のヒット結果集合

ここでも400件のヒット結果と、14万件のヒット結果を付き合わせ、ANDの結果を得る集合演算が必要になります。この処理数もかけ算に相当するので、5600万回のANDの処理が必要です。先の1440億回と比べると少ない数ですが、それでも結構大きな処理になっています。

検索式の最適化

先の検索式は、大量のヒット結果同士の論理演算が伴い非効率的です。このような場合には検索対象の文書プロパティがどのように分布しているかに着目し、部分的なヒット結果集合ができるだけ小さくなる条件式を考えます。もちろん論理的には、元の検索式と同等の結果が得られなければなりません。

前述の検索式では次の部分の集合演算の処理が非常に大きなCPUリソースを必要としていました。

[ group_num = "10" ] AND [ public_flag = "1" ]

この部分検索式はグループ番号10番の利用者が検索可能な文書全ての集合を、グループ番号が10で、かつ公開されている文書という条件で求めています。

ここを、グループ番号が10で、非公開の文書を除くという条件に置き換えてみるとどうでしょうか。部分検索式は次のようになります。

[ group_num = "10" ] NOT [ public_flag = "0" ]

この検索の部分実行結果は次のようになります。

[ group_num = "10" ] 	→ 15万件のヒット結果集合
[ public_flag = "0" ]	→ 4万件のヒット結果集合

集合演算部分の処理は次のようになります。

15万件のヒット結果集合 NOT 4万件のヒット結果集合

この集合演算には、15万件のヒット結果と、4万件のヒット結果を付き合わせ、NOTの結果を得る処理が必要です。この処理数もかけ算に相当するので、15万×4万で60億回のNOTの処理が必要です。1つのデータに対するANDの処理とNOTの処理はだいたい同等の処理と考えて良いので、このように検索式を最適化することで、1440億回分の処理が必要だったところを1／24の60億回分の処理に削減できました。

最適化済みの検索式は次のようになります。

"地磁気センサー" AND ( [ group_num = "10" ] NOT [ public_flag = "0" ] )

次回は、引き続きプロパティ検索の最適化について扱う予定です。