今回は前回に引き続いて、プロパティ検索式の最適化について取り扱います。

プロパティ最適化のポイント

ここで、検索式の最適化のプロセスを振り返ってみましょう。検索式の最適化のポイントは、次の3つです。

1. 検索対象の文書データのプロパティごとの分布を調べる。
2. 部分検索式の検索結果がどの程度のヒット結果集合になるかを考察する。
3. 部分検索式を求めるために、少ないヒット結果集合を使って表現できないかを考える。

検索対象の文書データのプロパティごとの分布を調べるのは、前回の例では、グループ番号10の文書が何件存在するか、公開、非公開の文書が何件かを特定する作業に相当します。公開文書が96万件に対して、非公開文書が4万件という偏りがあることが最適化の決め手になりました。

部分検索式の検索結果がどの程度のヒット結果集合になるかを考察するには、それぞれの部分検索式の実行結果であるヒット結果集合が何件程度になるかを特定する作業です。この作業の結果、著しくヒット結果集合が大きい場合には、このヒット結果集合を求める検索式や、ヒット結果集合を利用する検索式部分に検討の余地がないかを考えます。

部分検索式を求めるために、少ないヒット結果集合を使って表現できないかを考える作業は、前回の例では、AND [ public_flag = "1" ]の部分をNOT [ public_flag = "0" ]のように書き換えた作業に相当します。

では、検索対象の文書の母集団が次のようにグループ番号10の文書が全体の95％を占めるような分布をしている場合について、最適化が可能かどうかを見てみましょう。

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

の部分検索では次のような集合演算が見込まれます。

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

ここは、95万×4万で380億回のNOT演算が必要になります。この結果を94万件とすると、"地磁気センサー"の検索結果集合とのAND処理に、さらに400×94万=37億6千万回の処理が必要になります。合計すると約418億回の論理演算が必要になります。

グループ番号10の文書が多いという分布は、裏をかえせばグループ番号10以外が少ない(5%)ことになります。そこで、"地磁気センサー"の検索結果に対して、グループ番号10以外を除き、さらに非公開の文書を除くという方法で検索を行えば極めて少ない部分集合同士の論理演算で検索を済ませます。この場合の検索式は次のようになります。

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

それぞれの部分検索式のヒット結果集合の件数は次の通りです。

"地磁気センサー"  ← 400件のヒット結果集合
[ group_num < "10" > "10" ]  ← 5万件のヒット結果集合
[ public_flag = "0" ]  ← 4万件のヒット結果集合

論理演算部分の演算量は、("地磁気センサー" NOT [ group_num < "10" > "10" ])が400×5万＝2000万回、結果が350件だったとすると、非公開部分の処理は350×4万件＝1400万回となります。合計しても3400万回のNOT処理で済ますことができます。先の式が約418億回の論理演算だったのと比べると、1／1229に論理演算部分の処理を簡略化できたことになります。

検索エンジン側のプロパティ検索の最適化

プロパティ検索式の最適化は特定プロパティの分布を利用する手法です。したがってプロパティの値が均等に分布している場合には最適化の手がかりが得られないことになります。先の例では公開と非公開が50万件ずつの分布だった場合、グループ10の文書とそうでない文書が50万件ずつだった場合などが該当します。

FINDSPOTの内部は、当初、[ group_num = "10" ] AND [ public_flag = "1" ]のような検索式を、[ group_num = "10" ]と[ public_flag = "1" ]の部分検索式を別々にSQLの書誌データベース対して問い合わせを行っていました。必然的に部分検索式の実行結果をSQLの書誌データベースから取り出す処理が、論理演算と並んで大きなボトルネックとなっていました。ヒット結果の集合を減らす最適化は、この部分に対しても効果的なのですが、プロパティが比較的均等に分布しているケースではやはりお手上げ状態になっていました。

連続するプロパティ検索の一括処理

そこでFINDSPOTの内部処理を変更し、連続するプロパティ検索式は1つのSQLのselect文として処理するような内部構造の最適化を行いました。この改良により、連続するプロパティ検索式はSQLのデータベース内で1度に処理できるようになりました。

現在のFINDSPOTでは、SQLの書誌データベースから取り出す必要があるのは連続するプロパティ検索式の処理結果だけなので、複雑なプロパティ検索式も効率よく処理できるようになっています。

ただし最適化の対象となるのは、連続するプロパティ検索式についてなので、プロパティ検索式はできるだけ1ヵ所にまとめて連続して記述するのが、検索エンジン側のプロパティ検索最適化の効果を引き出すポイントです。

論理演算の最適化

もう1つFINDSPOTの内部処理で、プロパティ検索に関して最適化を行った点があります。それはヒット結果集合に対する論理演算の方法です。

FINDSPOTの1つの文書に対する検索結果は、これまでの連載でも説明したように、次のように4つの情報で構成されています。

1つの文書に対する検索結果

• 文書ID
• 文中での検索語の出現位置
• 文中での出現回数
• 検索結果のソート用のキー情報（複数）

なお、全文検索対象として指定されていないプロパティ（書誌データベースに保存されたプロパティ）に対するプロパティ検索の場合には、文中での検索語の出現位置と文中での出現回数はセットされません。

この4つの情報を1要素として、複数の検索結果を格納したものが「ヒット結果集合」です。ヒット結果集合に対するAND, OR, NOTなどの論理演算がどのように実現できるかを見ていきましょう。

まず、論理演算は検索結果の情報のうち、文書IDを対象に集合演算を行う点に着目してください。文書ID以外の検索結果情報は論理演算の場面では関係がないので、以下の説明では省略します。

たとえば、次のようなヒット結果集合のAとBが存在したとします。

「Ａ AND Ｂ」の集合演算は、ヒット結果集合Ａとヒット結果集合Ｂの両方に存在する文書IDを求める操作になります。ここでの「Ａ AND Ｂ」の答は共通に存在する文書IDということで「4, 6」になります。

このAND演算のアルゴリズムをPerlで表現してみましょう（FINDSPOTは実際にはC++で記述していますが、ここでは説明を簡単にするためPerlで解説します⁠）⁠。

my @a = ( 1, 4, 6, 12 );  ← ヒット結果集合Ａ
my @b = ( 2, 3, 4, 5, 6 );  ← ヒット結果集合Ｂ
my @ans;

foreach my $unit_a (@a)
{
  foreach my $unit_b (@b)
  {
    if ($unit_a == $unit_b)
    {
      push @ans, $unit_a; 
    }
  }
}

foreach my $x (@ans)
{
  print "$x\n";
}

リスト1内のif文の箇所は、集合Ａの要素の数と、集合Ｂの要素の数のかけ算の回数実行されます。つまり、この方法によると、集合Ａの要素の数をN、集合Ｂの要素の数をMとすると、O(MN)の計算量が必要になります。この例では、集合Ａの要素数が4, 集合Ｂの要素数が5なので、20回の比較となります。

一般に集合は順序を持っていませんが、FINDSPOTのヒット結果集合はリストの形をしているため順序があります。また、リストの要素は文書IDの順で並んでいるという特徴があります。この特徴を論理演算のアルゴリズムに生かして、次のように二分検索を使って合致集合Ｂの要素を求めることができます。

my @a = ( 1, 4, 6, 12 );
my @b = ( 2, 3, 4, 5, 6 );
my @ans;

foreach my $unit_a (@a)
{
  my $match = bsearch($unit_a, \@b);
  if ($match != -1)
  {
    push @ans, $unit_a; 
  }
}

foreach my $x (@ans)
{
  print "$x\n";
}

sub bsearch($)
{
  my ($unit, $ref_list) = @_;
  my @list = @$ref_list;
  return bsearch_x($unit, 0, $#list, $ref_list);
}

sub bsearch_x($)
{
  my ($unit, $from, $to, $ref_list) = @_;
  my @list = @$ref_list;
  if ($from > $to)
  {
    return -1;
  }
  my $pos = int(($from + $to) / 2);
  my $x = $list[$pos] - $unit;
  if ($x == 0)
  {
    return $unit;
  }
  elsif ($x > 0)
  {
    return bsearch_x($unit, $from, $pos - 1, $ref_list);
  }
  else
  {
    return bsearch_x($unit, $pos + 1, $to, $ref_list);
  }
}

この工夫で、比較は9回に減らすことができます。O記法ではO(M log 2 N)と遙かに少ない演算で同じ結果が得られます。Mが4個、Nが5個の場合には20回から9回への減少ですが、前回のようにMが15万個、Nが96万個の場合には、総当たりの方法では1440億回もの比較が必要ですが、最適化後の方法では150000×log ₂ 960000を計算すると約298万回の比較と、遙かに少ない計算量で同じ処理を行えます。

FINDSPOTの初期実装では、前述の総当たりの方法で論理演算を行っていましたが、現在は後述のアルゴリズムで論理演算を済ます工夫を取り入れています。