検索エンジンを作る

第18回 プロパティ検索式の最適化ポイント

この記事を読むのに必要な時間:およそ 3 分

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

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

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

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

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

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

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

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

表1

インデックス済み文書数 100万件
グループ番号10の文書 95万件
公開フラグ0 4万件
公開フラグ1 96万件
"地磁気センサー"を含む 400件
[ 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ヵ所にまとめて連続して記述するのが,検索エンジン側のプロパティ検索最適化の効果を引き出すポイントです。

著者プロフィール

工藤智行(くどうともゆき)

有限会社サイパック取締役社長。システム構築・管理のコンサルティング,ローカライゼーション,文書処理や障害者向けソフトウェアを中心とするプログラミングを長年手がける。 近著『UNIXプログラミングの道具箱』『システム管理現場の鉄則FreeBSD編』等

URLhttp://www.cypac.co.jp/

著書

コメント

コメントの記入