検索要求制御装置、検索要求制御プログラム及び検索要求制御方法
【課題】ハイトラフィック技術にインデックス技術を採用した場合のデータの検索効率を向上させる。
【解決手段】検索要求制御装置１は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割部１１と、検索要求集合分割部１１によって分割された複数の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出部１２と、平均レスポンス算出部１２によって算出された平均レスポンスが最短の複数の部分集合について、処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理部１３とを備える。
【解決手段】検索要求制御装置１は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割部１１と、検索要求集合分割部１１によって分割された複数の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出部１２と、平均レスポンス算出部１２によって算出された平均レスポンスが最短の複数の部分集合について、処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理部１３とを備える。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索要求制御装置、検索要求制御プログラム及び検索要求制御方法に関する。
【背景技術】
【０００２】
近年、データベースシステム等のデータの検索において、検索要求が同時に送られてくる場合であってもデータの検索時間を短縮できるハイトラフィック技術が用いられることがある。ハイトラフィック技術とは、複数の検索要求から１つのオートマトンを生成し、生成したオートマトンを利用して検索対象データとマッチングさせる技術である。図１３は、ハイトラフィック技術を用いたデータの検索の一例を説明する図である。
【０００３】
図１３に示すように、例えばデータベースシステムは、同時に送られてくる複数の検索要求１〜４を一体化して、一体化した検索要求に対するデータを検索対象データから一括して検索し、検索した結果を検索要求に振り分ける。これにより、同時に送られてくる検索要求の多重度が上がっても、検索要求に対するデータを一括して検索するので、データの検索時間の予測を可能とする。
【０００４】
また、データの検索時間を短縮する他の技術として、インデックス技術がある。インデックス技術とは、リレーショナルデータベースにおけるテーブルにおいて、カラムにある値を持つレコードを直接選択（検索）したり、ＸＭＬ文書等の構造を持つデータにおいて、特定のパスが指し示すデータを直接検索させたりする技術である。図１４は、インデックス技術を用いたデータの検索の一例を説明する図である。
【０００５】
図１４に示すように、検索要求１では、インデックスのパス２及びパス４が指し示すデータｄ２、ｄ４（ｄ２’、ｄ４’）を検索し、検索要求２では、インデックスのパス３及びパス４が指し示すデータｄ３、ｄ４（ｄ３’、ｄ４’）を検索する。このため、検索要求１及び検索要求２は、全体のデータを検索することなく最低限必要なデータだけを検索するので、データの検索時間を短縮できる。
【０００６】
ところが、各検索要求において、検索するデータが重複する場合がある。図１４の例では、検索要求１及び検索要求２では、パス４が指し示すデータｄ４（ｄ４’）がＤ１（Ｄ１’）に示すように重複している。この場合には、重複したデータｄ４（ｄ４’）が２回検索されるので、検索に無駄が生じる分、データの検索効率が悪くなる。
【０００７】
そこで、データの検索時間を短縮する他の技術として、ハイトラフィック技術にインデックス技術を採用した技術も考えられる。この技術では、同時に送られてくる複数の検索要求を一体化して、一体化した検索要求のインデックスのパスの和集合を作成し、作成したパスの和集合に属するパスが指し示すデータを一括して検索する。図１５は、ハイトラフィック技術にインデックス技術を採用した技術を説明する図である。
【０００８】
図１５に示すように、検索要求１では、インデックスのパス２及びパス４が指し示すデータを検索し、検索要求２では、インデックスのパス３及びパス４が指し示すデータを検索する。この場合には、検索要求１及び検索要求２のインデックスのパスの和集合パス２〜４を作成し、作成した和集合に属するパスが指し示すデータｄ２〜ｄ４（ｄ２’〜ｄ４’）を一括して検索する。これにより、各検索要求において、検索するデータが重複する場合であっても、Ｄ２（Ｄ２’）に示すように重複するデータを１度だけ検索するので、データの検索効率が向上する。
【０００９】
また、ほぼ同時に送られてくる複数の検索要求である検索式を、それぞれの予測検索速度に基づき複数の検索式集合に振り分け、予測検索速度の速い集合から順次検索を行い、対応する検索式集合内の検索式を纏めて一括検索する技術が開示されている。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００９−２５１６８６号公報
【特許文献２】特開２００７−２４１５１６号公報
【特許文献３】特開平１１−２３２３０２号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、ハイトラフィック技術にインデックス技術を採用した場合では、データの検索効率が向上しないことがあるという問題があった。すなわち、同時に送られてくる複数の検索要求で検索するデータに重複が少ない場合、重複するデータを１度だけ検索するという効果が少ないので、データの検索効率が向上しないことがある。
【００１２】
具体的な例として、データの検索効率が向上しないという問題を、図１６を用いて説明する。図１６は、ハイトラフィック技術にインデックス技術を採用した場合の課題を説明する図である。図１６に示すように、検索要求１では、インデックスのパス２及びパス４が指し示すデータを検索し、検索要求２では、インデックスのパス１及びパス３が指し示すデータを検索する。この場合には、検索要求１及び検索要求２のインデックスのパスの和集合パス１〜４を作成し、作成した和集合に属するパスが指し示すデータｄ１〜ｄ４（ｄ１’〜ｄ４’）を一括して検索する。ところが、検索要求１及び検索要求２で検索するデータに重複がないので、重複するデータを１度だけ検索するという効果がなくなり、データの検索効率が向上しない。
【００１３】
また、予測検索速度の速い検索式集合から順次検索を行なう技術であっても、検索式集合に含まれる検索式がそれぞれ全く重複しないデータを検索する場合には、データの検索効率が向上しない。
【００１４】
なお、上記課題は、データベースシステムにおけるデータの検索だけではなく、インターネット等の検索エンジンにおけるデータの検索にも同様に生じる課題である。
【００１５】
１つの側面では、ハイトラフィック技術にインデックス技術を採用した場合のデータの検索効率を向上させる検索要求制御装置等を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本願の開示する検索要求制御装置は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割部と、前記検索要求集合分割部によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出部と、前記平均レスポンス算出部によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して実行する検索要求実行部とを備える。
【発明の効果】
【００１７】
本願の開示する検索要求制御装置の一つの態様によれば、ハイトラフィック技術にインデックス技術を採用した場合のデータの検索効率を向上させることができる。
【図面の簡単な説明】
【００１８】
【図１】図１は、実施例１に係る検索要求制御装置の構成を示す機能ブロック図である。
【図２】図２は、分割による平均レスポンスの向上を説明する図である。
【図３】図３は、検索要求制御のタイムチャートを説明する図である。
【図４】図４は、実施例２に係る検索要求制御装置の構成を示す機能ブロック図である。
【図５】図５は、検索要求部分集合及び参照データ量の対応表のデータ構造の一例を示す図である。
【図６】図６は、検索要求部分集合の参照データ量の算出方法を説明する図である。
【図７】図７は、分割パターン及び平均レスポンスの対応表のデータ構造の一例を示す図である。
【図８】図８は、分割により平均レスポンスが向上するための条件を説明する図である。
【図９】図９は、実施例２に係る検索要求制御処理の手順を示すフローチャートである。
【図１０】図１０は、検索スケジュール制御処理の手順を示すフローチャートである。
【図１１】図１１は、検索要求集合化探索処理の手順を示すフローチャートである。
【図１２】図１２は、検索要求制御プログラムを実行するコンピュータのハードウェア構成を示す図である。
【図１３】図１３は、ハイトラフィック技術を説明する図である。
【図１４】図１４は、インデックス技術を説明する図である。
【図１５】図１５は、ハイトラフィック技術にインデックス技術を採用した技術を説明する図である。
【図１６】図１６は、ハイトラフィック技術にインデックス技術を採用した場合の課題を説明する図である。
【発明を実施するための形態】
【００１９】
以下に、本願の開示する検索要求制御装置、検索要求制御プログラム及び検索要求制御方法の実施例を図面に基づいて詳細に説明する。なお、以下の実施例では、データベースシステムにおけるデータの検索要求を制御する検索要求制御装置に適用した場合を示す。しかし、本実施例によりこの発明が限定されるものではなく、本発明は、例えばインターネットやイントラネット等を組み込んだシステムにおける検索エンジンにも適用可能である。また、以下の実施例では、ハイトラフィック技術にインデックス技術を採用した場合について説明するものとする。
【実施例１】
【００２０】
図１は、本実施例１に係る検索要求制御装置の構成を示す機能ブロック図である。図１に示すように、検索要求制御装置１は、検索要求集合分割部１１、平均レスポンス算出部１２及び検索処理部１３を有する。
【００２１】
検索要求集合分割部１１は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する。なお、所定期間とは、ほぼ同時となる期間を意味するが、検索要求を一括して処理するのに支障のない期間であれば良い。
【００２２】
平均レスポンス算出部１２は、検索要求集合分割部１１によって分割された複数の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。
【００２３】
検索処理部１３は、平均レスポンス算出部１２によって算出された平均レスポンスが最短の複数の部分集合について、処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する。
【００２４】
このようにして、検索要求制御装置１は、一括処理する単位となる部分集合への分割に検索要求が検索するデータの重複する度合いを用いることにより、部分集合における検索データの局所性を高めるので、データの検索効率の向上を図ることができる。さらに、検索要求制御装置１は、検索要求の平均レスポンスがより短くなるように検索要求集合を部分集合に分割しているので、分割した部分集合をそれぞれ処理することで検索要求の平均レスポンスを向上させることができる。
【００２５】
ここで、検索要求集合を部分集合に分割することにより平均レスポンスが向上することについて、図２を参照しながら説明する。図２は、分割による平均レスポンスの向上を説明する図である。図２の例では、ほぼ同時に３個の検索要求１〜３が到着するものとする。図２に示すように、検索要求１、２は、インデックスのパス１〜３が指し示すデータを検索し、検索要求３は、インデックスのパス３〜５が指し示すデータを検索する。なお、パス１〜５が指し示すデータのサイズは、全て等しいものとする。また、パス１〜５が指し示すデータ、すなわち検索対象データのサイズを「Ｓ」、検索対象データのサイズあたりにかかる検索時間を「ｋ」として説明するものとする。
【００２６】
まず、検索要求１〜３を纏めて処理する場合について、検索要求の平均レスポンスを算出する。検索要求の平均レスポンスは、検索要求１〜３を纏めて処理するので、パス１〜５を指し示すデータを一括して検索する時間となる。すなわち、検索要求の平均レスポンスは、式（１）に示すとおりである。
検索要求の平均レスポンス＝ｋ×Ｓ・・・・・式（１）
【００２７】
次に、検索要求１〜３を分割して処理する場合について、検索要求の平均レスポンスを算出する。検索要求集合分割部１１は、ほぼ同時に取得された検索要求１〜３を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する。ここでは、検索要求集合分割部１１は、パス１〜３が指し示すデータが重複する検索要求１、２を同じ部分集合とする。また、検索要求集合分割部１１は、パス３が検索要求１、２と重複するが、パス４、５が検索要求１、２と重複しない検索要求３を、検索要求１、２と異なる部分集合とする。
【００２８】
そして、平均レスポンス算出部１２は、検索要求集合分割部１１によって分割された２個の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。ここでは、平均レスポンス算出部１２は、処理順序の先行を検索要求１、２を含む部分集合、処理順序の後行を検索要求３を含む部分集合として、２個の部分集合を含む検索要求集合に含まれる検索要求の平均レスポンスを算出する。この結果、検索要求の平均レスポンスは、式（２）に示すとおりである。
検索要求の平均レスポンス＝｛２×（ｋ×Ｓ×３／５）＋１×（ｋ×Ｓ×３／５＋ｋ×Ｓ×３／５）｝／３＝ｋ×Ｓ×４／５・・・・・式（２）
【００２９】
したがって、式（１）及び式（２）を比較すると、検索要求１〜３を分割して処理する場合には、検索要求１〜３を纏めて処理する場合に比べて、検索要求の平均レスポンスが２０％向上する。
【００３０】
複数の検索要求を分割して処理する場合の検索要求のタイムチャートを、図３を参照しながら説明する。図３は、検索要求のタイムチャートを説明する図である。図３（Ａ）では、複数の検索要求を分割しない場合のタイムチャートを示し、図３（Ｂ）では、複数の検索要求を分割する場合のタイムチャートを示す。なお、図３（Ａ）（Ｂ）で示されるＱ０〜Ｑ３は、それぞれほぼ同時に到着する複数の検索要求を含む検索要求集合であるものとする。また、Ｑ１−１、Ｑ１−２は、検索要求集合Ｑ１を分割した複数の部分集合であり、Ｑ２−１、Ｑ２−２は、検索要求集合Ｑ２を分割した複数の部分集合であるものとする。
【００３１】
図３（Ａ）に示すように、複数の検索要求を分割しない場合、例えば新たに到着した検索要求集合Ｑ１は、到着の際検索処理中の検索要求集合Ｑ０の検索処理後に検索処理される。
【００３２】
一方、図３（Ｂ）に示すように、複数の検索要求を分割する場合、新たに到着した検索要求集合Ｑ１に含まれる部分集合Ｑ１−１は、到着の際検索処理中の検索要求集合Ｑ０の検索処理後に検索処理される。このとき、検索要求集合Ｑ１に含まれる部分集合Ｑ１−２は、部分集合Ｑ１−１の検索処理が終わるまで待機することとなる。そして、待機中の部分集合Ｑ１−２は、検索要求集合Ｑ１の到着後新たに到着した検索要求集合Ｑ２に含まれる部分集合Ｑ２−１と併合され、部分集合Ｑ１−１の検索処理後に検索処理されることとなる。
【実施例２】
【００３３】
［実施例２に係る検索要求制御装置の構成］
図４は、本実施例２に係る検索要求制御装置の構成を示す機能ブロック図である。図４に示すように、検索要求制御装置２は、検索要求受付部２１、検索スケジュール制御部２２、検索要求集合化探索部２３、検索処理部２４、検索結果出力部２５、不揮発性記憶部２６及び揮発性記憶部２７を有する。
【００３４】
不揮発性記憶部２６は、検索対象データ４１ｂとこれらを検索するために必要なインデックス４１ａとを記憶するデータベース４１及びインデックスパス別データ量４２を有する。インデックスパス別データ量４２は、インデックス４１ａを構成するパス毎に、各パスが指し示すデータのデータ量をあらかじめ記憶する。ここで、パスとは、検索対象のデータを参照する際にデータを指し示す経路を意味する。なお、不揮発性記憶部２６は、例えば、ハードディスク、光ディスクなどの記憶装置、又は、フラッシュメモリ（flash memory）等の不揮発性の半導体メモリ素子である。
【００３５】
揮発性記憶部２７は、検索要求部分集合及び参照データ量の対応表５１、分割パターン及び平均レスポンスの対応表５２、分割対象検索要求集合５３及び実行待機中要求集合５４を有する。なお、揮発性記憶部２７は、例えば、ＲＡＭ（Random Access Memory）等の揮発性の半導体メモリ素子である。
【００３６】
検索要求受付部２１は、外部のアプリケーションから送信された検索要求を受け付け、受け付けた検索要求を待ち行列である要求キューに入力する。
【００３７】
検索スケジュール制御部２２は、非同期的に発生するイベントを取得し、取得したイベントの種類に応じて検索要求の検索のスケジュールを制御する。具体的には、検索スケジュール制御部２２は、検索要求受付部２１から検索要求の到着イベントを取得すると、要求キューに入力されている検索要求を取り出し、取り出した検索要求を後述する検索要求集合化探索部２３に出力する。また、検索スケジュール制御部２２は、後述する検索処理部２４から検索要求の検索完了イベントを取得すると、検索要求を一括して処理する検索要求の集合の取得依頼を検索要求集合化探索部２３に出力する。そして、検索スケジュール制御部２２は、検索要求の集合の取得依頼に対する集合を検索要求集合化探索部２３から取得すると、取得した集合に含まれる検索要求を検索処理部２４に出力する。
【００３８】
検索要求集合化探索部２３は、検索スケジュール制御部２２からほぼ同時に取得した複数の検索要求に対し、平均レスポンスが向上するような分割案を探索する。さらに、検索要求集合化探索部２３は、イベント振分部３１、参照パス判定部３２、検索要求集合分割部３３、平均レスポンス算出部３４、平均レスポンス判定部３５及び分割パターン選択部３６を有する。
【００３９】
イベント振分部３１は、イベントを取得し、取得したイベントの種類に応じて処理を振り分ける。具体的には、イベント振分部３１は、検索スケジュール制御部２２からほぼ同時に取得した複数の検索要求を検索要求集合として、分割対象検索要求集合５３に記憶する。
【００４０】
ここで、分割対象検索要求集合５３は、複数の部分集合に分割される検索要求集合を記憶する。例えば、分割対象検索要求集合５３は、検索要求集合に一意に割り振られた識別番号に、検索要求集合に含まれる複数の検索要求を対応付けて記憶する。
【００４１】
また、イベント振分部３１は、検索スケジュール制御部２２から検索要求の集合の取得依頼を取得すると、検索要求集合の分割パターンを選択させるべく、当該取得依頼を分割パターン選択部３６に出力する。また、イベント振分部３１は、直近のイベントを取得したときから一定期間イベントの取得がない場合には、分割対象検索要求集合５３に記憶された検索要求集合を複数の部分集合に分割させるべく、検索要求集合の分割依頼を参照パス判定部３２に出力する。
【００４２】
参照パス判定部３２は、イベント振分部３１から検索要求集合の分割依頼を取得すると、分割対象検索要求集合５３に記憶された検索要求集合に含まれる各検索要求について、データを参照する際に用いるパスを判定する。そして、参照パス判定部３２は、各検索要求について、判定したパスを一時的に揮発性記憶部２７に記憶する。例えば、参照パス判定部３２は、各検索要求について、パス毎に参照の有無を表すフラグの列を記憶する。ここで、参照が有ることを表すフラグの値は「１」とし、参照が無いことを表すフラグの値は「０」とする。
【００４３】
検索要求集合分割部３３は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する。具体的には、検索要求集合分割部３３は、パス参照判定部３２によってパスの判定がされた複数の検索要求を、各検索要求が参照するパスが指し示すデータの重複する度合いに基づいて複数の部分集合に分割する。例えば、検索要求集合分割部３３は、参照するパスが指し示すデータが所定の割合以上重複する検索要求同士を同一の部分集合に集合化し、所定の割合以上重複しない検索要求同士を異なる部分集合に分割する。分割した２個の部分集合の組み合わせは、１個の分割パターンとなる。なお、所定の割合とは、例えば８割や９割であるが、随時変動しても良い。また、１個の分割パターンを形成する２個の部分集合は、積集合が空、且つ和集合が検索要求集合となる組み合わせであるものとする。
【００４４】
また、検索要求集合分割部３３は、検索要求集合を分割した部分集合毎に、参照するデータのデータ量を算出する。具体的には、検索要求集合分割部３３は、検索要求毎のフラグの列を用いて、部分集合に含まれる検索要求について、パス毎のフラグの論理和を算出する。なお、検索要求毎のフラグの列は、参照パス判定部３２によって揮発性記憶部２７に記憶されているものとする。そして、検索要求集合分割部３３は、算出されたパス毎のフラグの値に基づいて、インデックスパス別データ量４２を用いてパス毎の参照データ量を算出する。そして、検索要求集合分割部３３は、算出したパス毎の参照データ量を加算し、「検索要求部分集合の参照データ量」を求める。
【００４５】
また、検索要求集合分割部３３は、「検索要求部分集合の参照データ量」を部分集合に対応付けて、検索要求部分集合及び参照データ量の対応表５１に記憶する。ここで、検索要求部分集合及び参照データ量の対応表５１のデータ構造について、図５を参照しながら説明する。
【００４６】
図５は、検索要求部分集合及び参照データ量の対応表５１のデータ構造の一例を示す図である。図５に示すように、検索要求部分集合及び参照データ量の対応表５１は、キー５１ａ及び参照データ量５１ｂを対応付けて記憶する。すなわち、検索要求部分集合及び参照データ量の対応表５１は、キー５１ａに対応する値を参照データ量５１ｂとするハッシュテーブル等のマップ構造となっている。キー５１ａは、検索要求の部分集合に含まれる検索要求の識別子の集合を示す。参照データ量５１ｂは、検索要求の部分集合が参照するデータのデータ量を示す。
【００４７】
また、検索要求の部分集合（検索要求部分集合）が参照するデータのデータ量を算出する方法を、図６を参照しながら説明する。図６は、検索要求部分集合の参照データ量の算出方法を説明する図である。図６では、検索要求部分集合Ｑに検索要求ｑ１〜ｑ３が含まれる場合を例として、検索要求部分集合Ｑの参照データ量の算出方法を説明する。図６に示すように、検索要求ｑ１のフラグの列は、パス２を参照有りの「１」とし、パス２以外のパスを参照無しの「０」とする。検索要求ｑ２のフラグの列は、パス１、２を参照有りの「１」とし、パス１、２以外のパスを参照無しの「０」とする。検索要求ｑ３のフラグの列は、パス１、Ｎを参照有りの「１」とし、パス１、Ｎ以外のパスを参照無しの「０」とする。
【００４８】
検索要求集合分割部３３は、検索要求ｑ１〜ｑ３のそれぞれのフラグの列を用いて、パス毎のフラグの論理和を算出する。ここでは、算出されたパス毎のフラグの列は、パス１、２、Ｎを参照有りの「１」とし、パス１、２、Ｎ以外のパスを参照無しの「０」となる。そして、検索要求集合分割部３３は、算出されたパス毎のフラグの列の各値とインデックスパス別データ量４２に記憶されたパス毎のデータ量との内積を算出する。ここでは、算出されたパス毎のフラグの列の各値は｛１、１、０、・・・、１｝であり、インデックスパス別データ量４２に記憶されたパス毎のデータ量は｛１２３、４５６、７８９、・・・、３２１｝である。したがって、パス毎の積を求めると、結果は｛１２３、４５６、０、・・・、３２１｝となる。さらに、検索要求集合分割部３３は、計算の結果得られたパスごとのデータ量を加算し、「検索要求部分集合の参照データ量」を求める。ここでは、「検索要求部分集合の参照データ量」は、「９００」となる。
【００４９】
図４に戻って、平均レスポンス算出部３４は、検索要求集合分割部３３によって分割された複数の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。具体的には、平均レスポンス算出部３４は、検索要求集合分割部３３によって分割された分割パターンの中から順次１個の分割パターンを選択する。そして、平均レスポンス算出部３４は、選択した分割パターンに含まれる２個の部分集合の処理順序を決定する。また、平均レスポンス算出部３４は、処理順序が先行する部分集合（以降、「先行部分集合」という。）に含まれる検索要求の参照データ量を、検索要求部分集合及び参照データ量の対応表５１から読み出す。そして、平均レスポンス算出部３４は、読み出した参照データ量に基づいて、先行部分集合の検索時間を算出する。また、平均レスポンス算出部３４は、処理順序が後行する部分集合（以降、「後行部分集合」という。）に含まれる検索要求の参照データ量を、検索要求部分集合及び参照データ量の対応表５１から読み出す。そして、平均レスポンス算出部３４は、読み出した参照データ量に基づいて、後行部分集合の検索時間を算出する。
【００５０】
そして、平均レスポンス算出部３４は、先行部分集合の検索時間及び後行部分集合の検索時間に基づいて、先行部分集合及び後行部分集合の和集合である検索要求集合に含まれる検索要求の平均レスポンスを算出する。例えば、先行部分集合の検索時間をｒ１、後行部分集合の検索時間をｒ２とし、先行部分集合に含まれる検索要求の数をＮ１、後行部分集合に含まれる検索要求の数をＮ２とする。また、検索要求集合に含まれる検索要求の数をＮ０とする。すなわち、Ｎ０は、Ｎ１及びＮ２を加算した値である。このような例において、検索要求集合に含まれる検索要求の平均レスポンスｒ１２は、式（３）で表される。
ｒ１２＝｛Ｎ１×ｒ１＋Ｎ２×（ｗ２＋ｒ２）｝／Ｎ０＝ｒ１＋ｒ２×Ｎ２／Ｎ０・・式（３）
なお、ｗ２は、先行部分集合の検索処理後に処理される後行部分集合の待ち時間であり、先行部分集合の検索時間ｒ１と同値となる。
【００５１】
また、平均レスポンス算出部３４は、算出した検索要求の平均レスポンスを、分割パターンに対応付けて、分割パターン及び平均レスポンスの対応表５２に記憶する。ここで、分割パターン及び平均レスポンスの対応表５２のデータ構造について、図７を参照しながら説明する。
【００５２】
図７は、分割パターン及び平均レスポンスの対応表５２のデータ構造の一例を示す図である。図７に示すように、分割パターン及び平均レスポンスの対応表５２は、分割パターン５２ａ及び平均レスポンス５２ｂを対応付けて記憶する。すなわち、分割パターン及び平均レスポンスの対応表５２は、分割パターン５２ａをキー、平均レスポンス５２ｂを値とするＢ−Ｔｒｅｅ等のマップ構造となっている。分割パターン５２ａは、処理順序に応じた２個の部分集合を示す。この２個の部分集合は、積集合が空、すなわち重複した検索要求を持たない集合同士となっている。平均レスポンス５２ｂは、分割パターン５２ａで示される２個の部分集合における検索要求の平均レスポンスを示す。
【００５３】
平均レスポンス判定部３５は、検索要求集合を分割した２個の部分集合の平均レスポンスが検索要求集合を分割しない場合より向上しているか否かを判定する。具体的には、平均レスポンス判定部３５は、検索要求集合を分割しない場合の平均レスポンスを算出する。そして、平均レスポンス判定部３５は、平均レスポンス算出部３４によって平均レスポンスが算出された分割パターンについて、この平均レスポンスが検索要求集合を分割しない場合の平均レスポンスより短いか否かを判定する。そして、平均レスポンス判定部３５は、分割パターンについての平均レスポンスが検索要求集合を分割しない場合より短いと判定した場合に、分割しない場合より平均レスポンスが向上すると判断する。一方、平均レスポンス判定部３５は、分割パターンについての平均レスポンスが検索要求集合を分割しない場合より短いと判定した場合に、分割しない場合より平均レスポンスが向上しないと判断する。
【００５４】
ここで、検索要求集合を分割した場合における平均レスポンスが、検索要求集合を分割しない場合における平均レスポンスより向上するために満たすべき条件について、図８を参照して説明する。図８は、分割により平均レスポンスが向上するための条件を説明する図である。図８（Ａ）では、分割しない場合の検索処理コストを示し、図８（Ｂ）では、分割する場合の検索処理コストを示し、図８（Ｃ）では、分割しない場合と分割する場合の差を示す図である。なお、図８では、検索要求集合に含まれる検索要求の数をＮ０、先行部分集合に含まれる検索要求の数をＮ１、後行部分集合に含まれる検索要求の数をＮ２とする。また、検索要求集合の全体の参照データをＤ０、先行部分集合の参照データをＤ１、後行部分集合の参照データをＤ２とする。さらに、Ｓ（Ｄｎ）（ｎは、１、２）を参照データＤｎの参照データ量とし、ｒ（Ｓ（Ｄｎ））を参照データＤｎの参照データ量を検索する際の検索時間とする。
【００５５】
図８（Ａ）に示すように、分割しない場合の検索処理コストは、検索要求集合に含まれる全検索要求の参照データ量Ｓ（Ｄ０）を検索する際の検索時間ｒ（Ｓ（Ｄ０））と検索要求の数Ｎ０との積で表される。ここでは、Ｔ０で示される領域となる。すなわち、ハイトラフィック技術では、検索要求集合に含まれる複数の検索要求を一括して処理するので、検索時間は一括して処理する参照データ量に比例することとなり、検索要求集合の検索処理コストは参照データ量と検索要求の数から求められる。
【００５６】
次に、図８（Ｂ）に示すように、分割する場合の検索処理コストは、先行部分集合の検索処理コスト、後行部分集合の検索処理コスト及び後行部分集合の待ちコストの和で表される。先行部分集合の検索処理コストは、先行部分集合に含まれる検索要求の参照データ量Ｓ（Ｄ１）を検索する際の検索時間ｒ（Ｓ（Ｄ１））（以降、「ｒ１」）と検索要求の数Ｎ１との積で表される。ここでは、Ｔ１で示される領域となる。また、後行部分集合の検索処理コストは、後行部分集合に含まれる検索要求の参照データ量Ｓ（Ｄ２）を検索する際の検索時間ｒ（Ｓ（Ｄ２））（以降、「ｒ２」）と検索要求の数Ｎ２との積で表される。ここでは、Ｔ２で示される領域となる。さらに、後行部分集合の待ちコストは、後行部分集合が検索処理を実行するまでの待ち時間と一致する先行部分集合の検索時間ｒ１（以降、「ｗ２」）と検索要求の数Ｎ２の積で表される。ここでは、Ｔ３で示される領域となる。
【００５７】
次に、図８（Ｃ）に示すように、分割しない場合と分割する場合の差は、分割により検索処理コストが減少することとなる「分割によるベネフィット」Ｔ４と分割により検索処理コストが増加することとなる「分割によるコスト」Ｔ５との差分となる。ここでは、「分割によるベネフィット」Ｔ４は、後行部分集合の参照データＤ２から先行部分集合の参照データＤ１を引いたデータを検索する際の検索時間ｒ（Ｓ（Ｄ２−Ｄ１））と先行部分集合に含まれる検索要求の数Ｎ１との積となる。また、分割によりコストＴ５は、後行部分集合の参照データＤ２と先行部分集合の参照データＤ１とが共に参照するデータを検索する際の検索時間ｒ（Ｓ（Ｄ２∩Ｄ１））と後行部分集合に含まれる検索要求の数Ｎ２との積となる。
【００５８】
したがって、分割しない場合と分割する場合の差Ｊ０は、「分割によるベネフィット」Ｔ４及び「分割によるコスト」Ｔ５を用いて、式（４）で表される。
Ｊ０＝Ｔ４−Ｔ５＝Ｎ１×ｒ（Ｓ（Ｄ２−Ｄ１））−Ｎ２×ｒ（Ｓ（Ｄ２∩Ｄ１））・・・式（４）
そして、分割しない場合と分割する場合の差Ｊ０が正値となる場合、すなわち「分割によるベネフィット」Ｔ４が「分割によるコスト」Ｔ５より大きい場合に、分割により平均レスポンスが向上することとなる。つまり、「分割によるコスト」Ｔ５が小さいほど、言い換えれば後行部分集合の参照データＤ２と先行部分集合の参照データＤ１とが共に参照するデータＳ（Ｄ２∩Ｄ１）が小さいほど、分割によるメリットがより大きくなる。また、後行部分集合のみ参照し先行部分集合が参照しないデータＳ（Ｄ２−Ｄ１）が大きいほど、分割によるメリットがより大きくなる。
【００５９】
分割パターン選択部３６は、平均レスポンス判定部３５によって平均レスポンスが分割しない場合より向上すると判断された分割パターンの中から最短の平均レスポンスとなる分割パターンを選択する。具体的には、分割パターン選択部３６は、イベント振分部３１から検索要求の集合の取得依頼を取得すると、分割パターン及び平均レスポンスの対応表５２に基づいて、最短の平均レスポンスに対応付けられた分割パターンを選択する。そして、分割パターン選択部３６は、選択した分割パターンのうち先行部分集合を、先行して検索処理させるべく、検索スケジュール制御部２２に出力する。このとき、分割パターン選択部３６は、選択した分割パターンのうち後行部分集合を、実行待機中要求集合５４に記憶する。
【００６０】
ここで、実行待機中要求集合５４は、検索要求集合の分割パターンのうち先行部分集合が先行して検索処理されているとき、後続して検索処理される後行部分集合を待機させるために記憶する。例えば、実行待機中要求集合５４は、検索要求集合に一意に割り振られた識別番号に、後行部分集合に含まれる複数の検索要求を対応付けて記憶する。なお、分割パターン選択部３６は、既に実行待機中要求集合５４に直前の検索要求集合における後行部分集合が記憶されている場合には、この後行部分集合を、現在処理中の検索要求集合における先行部分集合とともに検索スケジュール制御部２２に出力する。これらの部分集合が、後述する検索処理部２４によって併合して処理されるためである。
【００６１】
検索処理部２４は、検索スケジュール制御部２２から部分集合に含まれる検索要求を取得すると、データベース４１からこれら検索要求について一括して検索処理を実行する。そして、検索処理部２４は、部分集合に含まれる検索要求について検索処理が完了すると、検索要求の検索完了イベントを検索スケジュール制御部２２に出力する。
【００６２】
検索結果出力部２５は、検索処理部２４によって一括して検索処理された部分集合毎に、各部分集合に含まれる検索要求の検索結果を出力する。
【００６３】
［実施例２に係る検索要求制御処理の手順］
次に、検索要求制御処理の手順を、図９を参照して説明する。図９は、実施例２に係る検索要求制御処理の手順を示すフローチャートである。
【００６４】
まず、検索要求制御処理は、検索要求の検索状況を判定する（ステップＳ１１）。そして、検索要求制御処理は、検索要求の検索状況が検索中であると判定する場合には（ステップＳ１１；検索中）、新たな検索要求が到着していれば分割対象の検索要求集合に加える（ステップＳ１２）。すなわち、検索要求制御処理は、検索要求集合の直前に到着した検索要求集合に関わる検索要求の検索中に、ほぼ同時を示す所定期間に到着した新たな検索要求を検索要求集合として分割対象検索要求集合５３に記憶する。そして、検索要求制御処理は、分割対象検索要求集合５３に記憶された分割対象の検索要求集合に対して、平均レスポンスが向上するような分割パターンの探索処理を行う（ステップＳ１３）。そして、検索要求制御処理は、ステップＳ１１に移行する。
【００６５】
一方、検索要求制御処理は、検索要求の検索状況が検索完了であると判定する場合には（ステップＳ１１；検索完了）、検索結果を出力する（ステップＳ１４）。そして、検索要求制御処理は、分割対象検索要求集合５３に記憶された検索要求集合について、現段階で探索された分割パターンのうち平均レスポンスが最短の分割パターンにおける先行部分集合に対して、検索処理を開始させる（ステップＳ１５）。そして、検索要求制御処理は、ステップＳ１１に移行する。
【００６６】
［検索スケジュール制御処理の手順］
次に、検索スケジュール制御部２２による検索スケジュール制御処理の手順を、図１０を参照して説明する。図１０は、検索スケジュール制御処理の手順を示すフローチャートである。
【００６７】
まず、検索スケジュール制御部２２は、イベントを待ち（ステップＳ２１）、イベントを取得したとき、取得したイベントを判定する（ステップＳ２２）。
【００６８】
そして、検索スケジュール制御部２２は、取得したイベントが検索要求の到着イベントであると判定する場合には（ステップＳ２２；検索要求の到着）、要求キューに入力されている検索要求を取り出す（ステップＳ２３）。そして、検索スケジュール制御部２２は、検索要求の検索処理中であるか否かを判定する（ステップＳ２４）。そして、検索スケジュール制御部２２は、検索要求が検索処理中であると判定する場合には（ステップＳ２４；Ｙｅｓ）、要求キューから取り出した全検索要求を分割させるべく、当該全検索要求を検索要求集合化探索部２３に出力する（ステップＳ２５）。そして、検索スケジュール制御部２２は、ステップＳ２１に処理を移行する。
【００６９】
一方、検索スケジュール制御部２２は、検索要求が検索処理中でないと判定する場合には（ステップＳ２４；Ｎｏ）、要求キューから取り出した全検索要求を検索処理させるべく、当該全検索要求を検索処理部２４に出力する（ステップＳ２６）。そして、検索スケジュール制御部２２は、ステップＳ２１に処理を移行する。
【００７０】
一方、検索スケジュール制御部２２は、取得したイベントが検索要求の検索完了イベントである場合には（ステップＳ２２；検索完了）、次に検索する検索要求を促すべく、検索要求の集合の取得依頼を検索要求集合化探索部２３に出力する（ステップＳ２７）。そして、検索スケジュール制御部２２は、検索要求集合化探索部２３からの検索要求の集合を待つ（ステップＳ２８）。
【００７１】
続いて、検索スケジュール制御部２２は、検索要求集合化探索部２３から検索要求の集合を取得すると、取得した集合が空集合か否かを判定する（ステップＳ２９）。そして、検索スケジュール制御部２２は、取得した集合が空集合であると判定する場合には（ステップＳ２９；Ｙｅｓ）、次のイベントを待つべく、ステップＳ２１に移行する。一方、検索スケジュール制御部２２は、取得した集合が空集合でないと判定する場合には（ステップＳ２９Ｎｏ）、取得した集合に含まれる検索要求を検索処理部２４に出力する（ステップＳ３０）。
【００７２】
［検索要求集合化探索処理の手順］
次に、検索要求集合化探索部２３による検索要求集合化探索処理の手順を、図１１を参照して説明する。図１１は、検索要求集合化探索処理の手順を示すフローチャートである。
【００７３】
まず、探索要求集合化探索部２３は、分割対象検索要求集合５３を空集合で初期化する（ステップＳ４１）。そして、探索要求集合化探索部２３のイベント振分部３１は、イベントを待ち（ステップＳ４２）、イベントを取得したとき、取得したイベントを判定する（ステップＳ４３）。
【００７４】
そして、イベント振分部３１は、取得したイベントが検索要求の取得イベントであると判定する場合（ステップＳ４３；検索要求の取得）、取得した検索要求を分割対象検索要求集合５３に追加する（ステップＳ４４）。すなわち、イベント振分部３１は、取得した複数の検索要求を検索要求集合として、分割対象検索要求集合５３に記憶する。
【００７５】
そして、平均レスポンス算出部３４は、取得した検索要求を加えた分割パターンでの平均レスポンスを再計算し、分割パターンに対応付けた計算結果を分割パターン及び平均レスポンスの対応表５２に更新する（ステップＳ４５）。そして、平均レスポンス算出部３４は、処理をステップＳ４２に移行する。
【００７６】
また、イベント振分部３１が直近のイベントの取得から一定期間イベントの取得がないと判定する場合（ステップＳ４３；イベントなし）、検索要求集合分割部３３は、分割対象検索要求集合５３の検索要求集合から分割パターンを生成する（ステップＳ４６）。すなわち、検索要求集合分割部３３は、それぞれの検索要求が検索するデータの重複する度合いに基づいて検索要求集合を２個の部分集合に分割し、分割パターンを生成する。例えば、検索要求集合分割部３３は、参照するパスが指し示すデータが所定の割合以上重複する検索要求同士を同一の部分集合に集合化し、所定の割合以上重複しない検索要求を異なる部分集合に分割し、これらの部分集合の組を１個の分割パターンとする。
【００７７】
続いて、検索要求集合分割部３３は、生成した分割パターンを１個選択する（ステップＳ４７）。そして、検索要求集合分割部３３は、選択した分割パターンに含まれる部分集合毎に、参照するデータのデータ量を計算し、検索要求部分集合及び参照データ量の対応表５１に追加する（ステップＳ４８）。
【００７８】
そして、平均レスポンス算出部３４は、選択した分割パターンに含まれる２個の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する（ステップＳ４９）。具体的には、平均レスポンス算出部３４は、分割パターンに含まれる２個の部分集合の処理順序を決定し、決定した処理順序が先行する先行部分集合及び処理順序が後行する後行部分集合の参照データ量を検索要求部分集合及び参照データ量の対応表５１から読み出す。そして、平均レスポンス算出部３４は、読み出した先行部分集合及び後行部分集合の参照データ量に基づいて、それぞれのデータの検索時間を算出する。さらに、平均レスポンス算出部３４は、先行部分集合及び後行部分集合のそれぞれの検索時間に基づいて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。
【００７９】
そして、平均レスポンス算出部３４は、算出した平均レスポンスを、分割パターンに対応付けて、分割パターン及び平均レスポンスの対応表５２に追加し（ステップＳ５０）、処理をステップＳ４２に移行する。
【００８０】
また、イベント振分部３１が検索要求の集合の取得依頼イベントであると判定する場合（ステップＳ４３；要求集合の取得依頼）、分割パターン選択部３６は、平均レスポンスが最短となる分割パターンを選択する（ステップＳ５１）。具体的には、分割パターン選択部３６は、分割パターン及び平均レスポンスの対応表５２に基づいて、最短の平均レスポンスに対応付けられた分割パターンを選択する。
【００８１】
そして、分割パターン選択部３６は、選択した分割パターンのうち先行部分集合に含まれる検索要求を、先行して検索処理させるべく、検索スケジュール制御部２２に出力する（ステップＳ５２）。このとき、分割パターン選択部３６は、選択した分割パターンのうち後行部分集合に含まれる検索要求を、実行待機中要求集合５４に移動する（ステップＳ５３）。そして、分割パターン選択部３６は、処理をステップＳ４１に移行する。なお、分割パターン選択部３６は、既に実行待機中要求集合５４に直前の検索要求集合における後行部分集合が記憶されている場合には、この後行部分集合を、現在処理中の検索要求集合における先行部分集合とともに検索スケジュール制御部２２に出力する。
【００８２】
［実施例２の効果］
上記実施例２によれば、検索要求集合分割部３３は、ほぼ同時に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する。そして、平均レスポンス算出部３４は、検索要求集合分割部３３によって分割された複数の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。さらに、検索処理部２４は、平均レスポンス算出部３４によって算出された平均レスポンスが最短の複数の部分集合について、処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する。
【００８３】
かかる構成によれば、検索要求集合分割部３３は、一括処理する単位となる部分集合への分割に検索要求が検索するデータの重複する度合いを用いることとした。このため、検索要求集合分割部３３は、部分集合における検索データの局所性を高めることができるので、データの検索効率の向上を図ることができる。さらに、検索要求集合分割部３３は、検索要求の平均レスポンスがより短くなるように検索要求集合を部分集合に分割することとなるので、分割した部分集合をそれぞれ処理することで検索要求の平均レスポンスを向上させることができる。
【００８４】
また、上記実施例２によれば、検索要求集合分割部３３は、検索要求集合を、当該検索要求集合の直前に取得された検索要求集合に関わる検索要求の実行中に、複数の部分集合に分割する。そして、平均レスポンス算出部３４は、検索要求集合分割部３３によって分割された複数の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。かかる構成によれば、検索要求集合の直前に取得された検索要求集合の実行完了後に次に実行すべき検索要求集合について平均レスポンスがより短くなる部分集合を選択できるので、全体の検索要求の平均レスポンスを向上させることができる。
【００８５】
また、上記実施例２によれば、検索処理部２４は、処理順序が先行する部分集合に含まれる検索要求を検索要求集合の直前に取得された検索要求の処理後に実行する。そして、検索処理部２４は、処理順序が後行する部分集合に含まれる検索要求を検索要求集合の直後に取得された検索要求と併合して処理する。かかる構成によれば、検索処理部２４は、処理順序が後行する部分集合を検索要求集合の直後に取得された検索要求と併合して処理することとした。このため、検索処理部２４は、処理順序が後行する部分集合の処理時期を無期限に延期しないので、当該部分集合を含む検索要求集合の平均レスポンスを確実に向上させることができる。
【００８６】
また、上記実施例２によれば、検索要求部分集合及び参照データ量の対応表５１は、部分集合毎にそれぞれの部分集合に含まれる検索要求が一括して検査するデータのデータ量を記憶する。そして、平均レスポンス算出部３４は、処理順序が先行する部分集合に関わるデータ量のデータを検索する検索時間及び処理順序が後行する部分集合に関わるデータ量のデータを検索する検索時間を用いて、平均レスポンスを算出する。かかる構成によれば、仮に処理順序が先行する部分集合及び処理順序が後行する部分集合に関わるデータ量が重複しない場合には、平均レスポンス算出部３４は、各部分集合に関わるデータ量のデータを検索する検索時間を要するのみとなる。このため、平均レスポンス算出部３４は、検索要求集合を分割しない場合と比べて、検索時間が短くなり、平均レスポンスを向上させることができる。
【００８７】
なお、実施例２では、分割パターン選択部３６は、分割パターン及び平均レスポンスの対応表５２に基づいて、最短の平均レスポンスに対応付けられた分割パターンを選択するものとして説明した。しかしながら、分割パターン選択部３６は、分割パターンに対応付けられた最短の平均レスポンスが分割しない場合の平均レスポンスより長い場合には、分割しないままの検索要求集合を選択するようにするようにしても良い。この場合には、平均レスポンス算出部３４が、分割しない場合の検索要求の平均レスポンスを検索要求集合に対応付けて分割パターン及び平均レスポンスの対応表５２に記憶しておく。そして、分割パターン選択部３６は、分割しない場合の検索要求の平均レスポンスを含めて最短の平均レスポンスとなる分割パターンを選択するようにすれば良い。これにより、分割パターン選択部３６は、分割しない場合の検索要求の平均レスポンスよりも長くなることがなくなり平均レスポンスを安定させることができる。
【００８８】
また、実施例２では、分割パターン選択部３６は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて２個の部分集合に分割するものとして説明した。しかしながら、分割パターン選択部３６は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて３個の部分集合に分割するようにしても良い。
【００８９】
［プログラム等］
また、この検索要求制御装置２は、既知のパーソナルコンピュータ、ワークステーションなどの情報処理装置に、上記した検索スケジュール制御部２２、検索要求集合化探索部２３等の各機能を搭載することによって実現することができる。
【００９０】
また、図示した各装置の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的態様は図示のものに限られず、その全部又は一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的又は物理的に分散・統合して構成することができる。例えば、平均レスポンス算出部３４と平均レスポンス判定部３５とを１個の部として統合しても良い。一方、平均レスポンス算出部３４を、複数の部分集合の処理順序を並び替える並び替え部と、処理順序を並び替えた複数の部分集合について平均レスポンスを算出する算出部とに分散しても良い。また、不揮発性記憶部２６等の記憶部を検索要求制御装置２の外部装置としてネットワーク経由で接続するようにしても良い。
【００９１】
また、上記実施例で説明した各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで、以下では、図１２を用いて、図４に示した検索要求制御装置２と同様の機能を有する検索要求制御プログラムを実行するコンピュータの一例を説明する。
【００９２】
図１２は、検索要求制御プログラムを実行するコンピュータのハードウェア構成を示す図である。図１２に示すように、コンピュータ１０００は、ＲＡＭ（Random Access Memory）１０１０と、ネットワークインタフェース装置１０２０と、ＨＤＤ１０３０と、ＣＰＵ（Central Processing Unit）１０４０、媒体読取装置１０５０と、入力装置１０６０と、出力装置１０７０とを有する。ＲＡＭ１０１０、ネットワークインタフェース装置１０２０、ＨＤＤ１０３０、ＣＰＵ１０４０、入力装置１０６０及び出力装置１０７０は、バス１０８０によって接続されている。
【００９３】
そして、ＨＤＤ１０３０には、図４に示した検索要求制御装置２と同様の機能を有する検索要求制御プログラム１０３１が記憶される。また、ＨＤＤ１０３０には、図４に示した不揮発性記憶部２６内の情報（データベース４１、インデックスパス別データ量４２）に対応する検索対象データ情報１０３２が記憶される。
【００９４】
そして、ＣＰＵ１０４０が検索要求制御プログラム１０３１をＨＤＤ１０３０から読み出してＲＡＭ１０１０に展開することにより、検索要求制御プログラム１０３１は、検索要求制御プロセス１０１１として機能するようになる。そして、検索要求制御プロセス１０１１は、検索対象データ情報１０３２から読み出した情報等を適宜ＲＡＭ１０１０上の自身に割り当てられた領域に展開し、この展開したデータ、例えば検索要求制御情報１０１２等に基づいて各種データ処理を実行する。
【００９５】
媒体読取装置１０５０は、検索要求制御プログラム１０３１がＨＤＤ１０３０に記憶されていない場合であっても、検索要求制御プログラム１０３１を記憶する媒体等から検索要求制御プログラム１０３１を読み取る。媒体読取装置１０５０には、例えばＣＤ−ＲＯＭや光ディスク装置がある。
【００９６】
ネットワークインタフェース装置１０２０は、外部装置とネットワーク経由で接続する装置であり、有線に対応するものであっても、無線に対応するものであっても良い。また、入力装置１０６０には、例えばキーボードやマウスがあり、出力装置１０７０には、例えばディスプレイがある。
【００９７】
なお、上記の検索要求制御プログラム１０３１は、公衆回線、インターネット、ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等を介してコンピュータ１０００に接続される他のコンピュータ（またはサーバ）等にこのプログラムを記憶させておいても良い。この場合には、コンピュータ１０００がこれらからプログラムを読み出して実行する。
【００９８】
以上の実施例に係る実施形態に関し、さらに以下の付記を開示する。
【００９９】
（付記１）所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割部と、
前記検索要求集合分割部によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出部と、
前記平均レスポンス算出部によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理部と
を有することを特徴とする検索要求制御装置。
【０１００】
（付記２）前記検索要求集合分割部は、
前記検索要求集合を、当該検索要求集合の直前に取得された検索要求集合に関わる検索要求の処理中に、複数の部分集合に分割することを特徴とする付記１に記載の検索要求制御装置。
【０１０１】
（付記３）前記検索処理部は、
前記処理順序が先行する部分集合に含まれる検索要求を前記検索要求集合の直前に取得された検索要求の処理後に処理し、前記処理順序が後行する部分集合に含まれる検索要求を前記検索要求集合の直後に取得された検索要求と併合して処理することを特徴とする付記１または付記２に記載の検索要求制御装置。
【０１０２】
（付記４）前記部分集合毎にそれぞれの部分集合に含まれる検索要求が一括して検索するデータのデータ量を記憶するデータ量記憶部を有し、
前記平均レスポンス算出部は、
前記処理順序が先行する部分集合に関わるデータ量のデータを検索する検索時間及び前記処理順序が後行する部分集合に関わるデータ量のデータを検索する検索時間を用いて、前記平均レスポンスを算出することを特徴とする付記１から付記３のいずれか１つに記載の検索要求制御装置。
【０１０３】
（付記５）所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割手順と、
前記検索要求集合分割手順によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出手順と、
前記平均レスポンス算出手順によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理手順と
をコンピュータに実行させることを特徴とする検索要求制御プログラム。
【０１０４】
（付記６）検索要求制御装置が検索要求を制御する検索要求制御方法であって、
所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割工程と、
前記検索要求集合分割工程によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出工程と、
前記平均レスポンス算出工程によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理工程と
を含むことを特徴とする検索要求制御方法。
【符号の説明】
【０１０５】
１、２ 検索要求制御装置
１１ 検索要求集合分割部
１２ 平均レスポンス算出部
１３ 検索処理部
２１ 検索要求受付部
２２ 検索スケジュール制御部
２３ 検索要求集合化探索部
２４ 検索処理部
２５ 検索結果出力部
２６ 不揮発性記憶部
２７ 揮発性記憶部
３１ イベント振分部
３２ 参照パス判定部
３３ 検索要求集合分割部
３４ 平均レスポンス算出部
３５ 平均レスポンス判定部
３６ 分割パターン選択部
４１ データベース
４１ａ インデックス
４１ｂ 検索対象データ
４２ インデックスパス別データ量
５１ 検索要求部分集合及び参照データ量の対応表
５２ 分割パターン及び平均レスポンスの対応表
５３ 分割対象検索要求集合
５４ 実行待機中要求集合
【技術分野】
【０００１】
本発明は、検索要求制御装置、検索要求制御プログラム及び検索要求制御方法に関する。
【背景技術】
【０００２】
近年、データベースシステム等のデータの検索において、検索要求が同時に送られてくる場合であってもデータの検索時間を短縮できるハイトラフィック技術が用いられることがある。ハイトラフィック技術とは、複数の検索要求から１つのオートマトンを生成し、生成したオートマトンを利用して検索対象データとマッチングさせる技術である。図１３は、ハイトラフィック技術を用いたデータの検索の一例を説明する図である。
【０００３】
図１３に示すように、例えばデータベースシステムは、同時に送られてくる複数の検索要求１〜４を一体化して、一体化した検索要求に対するデータを検索対象データから一括して検索し、検索した結果を検索要求に振り分ける。これにより、同時に送られてくる検索要求の多重度が上がっても、検索要求に対するデータを一括して検索するので、データの検索時間の予測を可能とする。
【０００４】
また、データの検索時間を短縮する他の技術として、インデックス技術がある。インデックス技術とは、リレーショナルデータベースにおけるテーブルにおいて、カラムにある値を持つレコードを直接選択（検索）したり、ＸＭＬ文書等の構造を持つデータにおいて、特定のパスが指し示すデータを直接検索させたりする技術である。図１４は、インデックス技術を用いたデータの検索の一例を説明する図である。
【０００５】
図１４に示すように、検索要求１では、インデックスのパス２及びパス４が指し示すデータｄ２、ｄ４（ｄ２’、ｄ４’）を検索し、検索要求２では、インデックスのパス３及びパス４が指し示すデータｄ３、ｄ４（ｄ３’、ｄ４’）を検索する。このため、検索要求１及び検索要求２は、全体のデータを検索することなく最低限必要なデータだけを検索するので、データの検索時間を短縮できる。
【０００６】
ところが、各検索要求において、検索するデータが重複する場合がある。図１４の例では、検索要求１及び検索要求２では、パス４が指し示すデータｄ４（ｄ４’）がＤ１（Ｄ１’）に示すように重複している。この場合には、重複したデータｄ４（ｄ４’）が２回検索されるので、検索に無駄が生じる分、データの検索効率が悪くなる。
【０００７】
そこで、データの検索時間を短縮する他の技術として、ハイトラフィック技術にインデックス技術を採用した技術も考えられる。この技術では、同時に送られてくる複数の検索要求を一体化して、一体化した検索要求のインデックスのパスの和集合を作成し、作成したパスの和集合に属するパスが指し示すデータを一括して検索する。図１５は、ハイトラフィック技術にインデックス技術を採用した技術を説明する図である。
【０００８】
図１５に示すように、検索要求１では、インデックスのパス２及びパス４が指し示すデータを検索し、検索要求２では、インデックスのパス３及びパス４が指し示すデータを検索する。この場合には、検索要求１及び検索要求２のインデックスのパスの和集合パス２〜４を作成し、作成した和集合に属するパスが指し示すデータｄ２〜ｄ４（ｄ２’〜ｄ４’）を一括して検索する。これにより、各検索要求において、検索するデータが重複する場合であっても、Ｄ２（Ｄ２’）に示すように重複するデータを１度だけ検索するので、データの検索効率が向上する。
【０００９】
また、ほぼ同時に送られてくる複数の検索要求である検索式を、それぞれの予測検索速度に基づき複数の検索式集合に振り分け、予測検索速度の速い集合から順次検索を行い、対応する検索式集合内の検索式を纏めて一括検索する技術が開示されている。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２００９−２５１６８６号公報
【特許文献２】特開２００７−２４１５１６号公報
【特許文献３】特開平１１−２３２３０２号公報
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、ハイトラフィック技術にインデックス技術を採用した場合では、データの検索効率が向上しないことがあるという問題があった。すなわち、同時に送られてくる複数の検索要求で検索するデータに重複が少ない場合、重複するデータを１度だけ検索するという効果が少ないので、データの検索効率が向上しないことがある。
【００１２】
具体的な例として、データの検索効率が向上しないという問題を、図１６を用いて説明する。図１６は、ハイトラフィック技術にインデックス技術を採用した場合の課題を説明する図である。図１６に示すように、検索要求１では、インデックスのパス２及びパス４が指し示すデータを検索し、検索要求２では、インデックスのパス１及びパス３が指し示すデータを検索する。この場合には、検索要求１及び検索要求２のインデックスのパスの和集合パス１〜４を作成し、作成した和集合に属するパスが指し示すデータｄ１〜ｄ４（ｄ１’〜ｄ４’）を一括して検索する。ところが、検索要求１及び検索要求２で検索するデータに重複がないので、重複するデータを１度だけ検索するという効果がなくなり、データの検索効率が向上しない。
【００１３】
また、予測検索速度の速い検索式集合から順次検索を行なう技術であっても、検索式集合に含まれる検索式がそれぞれ全く重複しないデータを検索する場合には、データの検索効率が向上しない。
【００１４】
なお、上記課題は、データベースシステムにおけるデータの検索だけではなく、インターネット等の検索エンジンにおけるデータの検索にも同様に生じる課題である。
【００１５】
１つの側面では、ハイトラフィック技術にインデックス技術を採用した場合のデータの検索効率を向上させる検索要求制御装置等を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本願の開示する検索要求制御装置は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割部と、前記検索要求集合分割部によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出部と、前記平均レスポンス算出部によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して実行する検索要求実行部とを備える。
【発明の効果】
【００１７】
本願の開示する検索要求制御装置の一つの態様によれば、ハイトラフィック技術にインデックス技術を採用した場合のデータの検索効率を向上させることができる。
【図面の簡単な説明】
【００１８】
【図１】図１は、実施例１に係る検索要求制御装置の構成を示す機能ブロック図である。
【図２】図２は、分割による平均レスポンスの向上を説明する図である。
【図３】図３は、検索要求制御のタイムチャートを説明する図である。
【図４】図４は、実施例２に係る検索要求制御装置の構成を示す機能ブロック図である。
【図５】図５は、検索要求部分集合及び参照データ量の対応表のデータ構造の一例を示す図である。
【図６】図６は、検索要求部分集合の参照データ量の算出方法を説明する図である。
【図７】図７は、分割パターン及び平均レスポンスの対応表のデータ構造の一例を示す図である。
【図８】図８は、分割により平均レスポンスが向上するための条件を説明する図である。
【図９】図９は、実施例２に係る検索要求制御処理の手順を示すフローチャートである。
【図１０】図１０は、検索スケジュール制御処理の手順を示すフローチャートである。
【図１１】図１１は、検索要求集合化探索処理の手順を示すフローチャートである。
【図１２】図１２は、検索要求制御プログラムを実行するコンピュータのハードウェア構成を示す図である。
【図１３】図１３は、ハイトラフィック技術を説明する図である。
【図１４】図１４は、インデックス技術を説明する図である。
【図１５】図１５は、ハイトラフィック技術にインデックス技術を採用した技術を説明する図である。
【図１６】図１６は、ハイトラフィック技術にインデックス技術を採用した場合の課題を説明する図である。
【発明を実施するための形態】
【００１９】
以下に、本願の開示する検索要求制御装置、検索要求制御プログラム及び検索要求制御方法の実施例を図面に基づいて詳細に説明する。なお、以下の実施例では、データベースシステムにおけるデータの検索要求を制御する検索要求制御装置に適用した場合を示す。しかし、本実施例によりこの発明が限定されるものではなく、本発明は、例えばインターネットやイントラネット等を組み込んだシステムにおける検索エンジンにも適用可能である。また、以下の実施例では、ハイトラフィック技術にインデックス技術を採用した場合について説明するものとする。
【実施例１】
【００２０】
図１は、本実施例１に係る検索要求制御装置の構成を示す機能ブロック図である。図１に示すように、検索要求制御装置１は、検索要求集合分割部１１、平均レスポンス算出部１２及び検索処理部１３を有する。
【００２１】
検索要求集合分割部１１は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する。なお、所定期間とは、ほぼ同時となる期間を意味するが、検索要求を一括して処理するのに支障のない期間であれば良い。
【００２２】
平均レスポンス算出部１２は、検索要求集合分割部１１によって分割された複数の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。
【００２３】
検索処理部１３は、平均レスポンス算出部１２によって算出された平均レスポンスが最短の複数の部分集合について、処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する。
【００２４】
このようにして、検索要求制御装置１は、一括処理する単位となる部分集合への分割に検索要求が検索するデータの重複する度合いを用いることにより、部分集合における検索データの局所性を高めるので、データの検索効率の向上を図ることができる。さらに、検索要求制御装置１は、検索要求の平均レスポンスがより短くなるように検索要求集合を部分集合に分割しているので、分割した部分集合をそれぞれ処理することで検索要求の平均レスポンスを向上させることができる。
【００２５】
ここで、検索要求集合を部分集合に分割することにより平均レスポンスが向上することについて、図２を参照しながら説明する。図２は、分割による平均レスポンスの向上を説明する図である。図２の例では、ほぼ同時に３個の検索要求１〜３が到着するものとする。図２に示すように、検索要求１、２は、インデックスのパス１〜３が指し示すデータを検索し、検索要求３は、インデックスのパス３〜５が指し示すデータを検索する。なお、パス１〜５が指し示すデータのサイズは、全て等しいものとする。また、パス１〜５が指し示すデータ、すなわち検索対象データのサイズを「Ｓ」、検索対象データのサイズあたりにかかる検索時間を「ｋ」として説明するものとする。
【００２６】
まず、検索要求１〜３を纏めて処理する場合について、検索要求の平均レスポンスを算出する。検索要求の平均レスポンスは、検索要求１〜３を纏めて処理するので、パス１〜５を指し示すデータを一括して検索する時間となる。すなわち、検索要求の平均レスポンスは、式（１）に示すとおりである。
検索要求の平均レスポンス＝ｋ×Ｓ・・・・・式（１）
【００２７】
次に、検索要求１〜３を分割して処理する場合について、検索要求の平均レスポンスを算出する。検索要求集合分割部１１は、ほぼ同時に取得された検索要求１〜３を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する。ここでは、検索要求集合分割部１１は、パス１〜３が指し示すデータが重複する検索要求１、２を同じ部分集合とする。また、検索要求集合分割部１１は、パス３が検索要求１、２と重複するが、パス４、５が検索要求１、２と重複しない検索要求３を、検索要求１、２と異なる部分集合とする。
【００２８】
そして、平均レスポンス算出部１２は、検索要求集合分割部１１によって分割された２個の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。ここでは、平均レスポンス算出部１２は、処理順序の先行を検索要求１、２を含む部分集合、処理順序の後行を検索要求３を含む部分集合として、２個の部分集合を含む検索要求集合に含まれる検索要求の平均レスポンスを算出する。この結果、検索要求の平均レスポンスは、式（２）に示すとおりである。
検索要求の平均レスポンス＝｛２×（ｋ×Ｓ×３／５）＋１×（ｋ×Ｓ×３／５＋ｋ×Ｓ×３／５）｝／３＝ｋ×Ｓ×４／５・・・・・式（２）
【００２９】
したがって、式（１）及び式（２）を比較すると、検索要求１〜３を分割して処理する場合には、検索要求１〜３を纏めて処理する場合に比べて、検索要求の平均レスポンスが２０％向上する。
【００３０】
複数の検索要求を分割して処理する場合の検索要求のタイムチャートを、図３を参照しながら説明する。図３は、検索要求のタイムチャートを説明する図である。図３（Ａ）では、複数の検索要求を分割しない場合のタイムチャートを示し、図３（Ｂ）では、複数の検索要求を分割する場合のタイムチャートを示す。なお、図３（Ａ）（Ｂ）で示されるＱ０〜Ｑ３は、それぞれほぼ同時に到着する複数の検索要求を含む検索要求集合であるものとする。また、Ｑ１−１、Ｑ１−２は、検索要求集合Ｑ１を分割した複数の部分集合であり、Ｑ２−１、Ｑ２−２は、検索要求集合Ｑ２を分割した複数の部分集合であるものとする。
【００３１】
図３（Ａ）に示すように、複数の検索要求を分割しない場合、例えば新たに到着した検索要求集合Ｑ１は、到着の際検索処理中の検索要求集合Ｑ０の検索処理後に検索処理される。
【００３２】
一方、図３（Ｂ）に示すように、複数の検索要求を分割する場合、新たに到着した検索要求集合Ｑ１に含まれる部分集合Ｑ１−１は、到着の際検索処理中の検索要求集合Ｑ０の検索処理後に検索処理される。このとき、検索要求集合Ｑ１に含まれる部分集合Ｑ１−２は、部分集合Ｑ１−１の検索処理が終わるまで待機することとなる。そして、待機中の部分集合Ｑ１−２は、検索要求集合Ｑ１の到着後新たに到着した検索要求集合Ｑ２に含まれる部分集合Ｑ２−１と併合され、部分集合Ｑ１−１の検索処理後に検索処理されることとなる。
【実施例２】
【００３３】
［実施例２に係る検索要求制御装置の構成］
図４は、本実施例２に係る検索要求制御装置の構成を示す機能ブロック図である。図４に示すように、検索要求制御装置２は、検索要求受付部２１、検索スケジュール制御部２２、検索要求集合化探索部２３、検索処理部２４、検索結果出力部２５、不揮発性記憶部２６及び揮発性記憶部２７を有する。
【００３４】
不揮発性記憶部２６は、検索対象データ４１ｂとこれらを検索するために必要なインデックス４１ａとを記憶するデータベース４１及びインデックスパス別データ量４２を有する。インデックスパス別データ量４２は、インデックス４１ａを構成するパス毎に、各パスが指し示すデータのデータ量をあらかじめ記憶する。ここで、パスとは、検索対象のデータを参照する際にデータを指し示す経路を意味する。なお、不揮発性記憶部２６は、例えば、ハードディスク、光ディスクなどの記憶装置、又は、フラッシュメモリ（flash memory）等の不揮発性の半導体メモリ素子である。
【００３５】
揮発性記憶部２７は、検索要求部分集合及び参照データ量の対応表５１、分割パターン及び平均レスポンスの対応表５２、分割対象検索要求集合５３及び実行待機中要求集合５４を有する。なお、揮発性記憶部２７は、例えば、ＲＡＭ（Random Access Memory）等の揮発性の半導体メモリ素子である。
【００３６】
検索要求受付部２１は、外部のアプリケーションから送信された検索要求を受け付け、受け付けた検索要求を待ち行列である要求キューに入力する。
【００３７】
検索スケジュール制御部２２は、非同期的に発生するイベントを取得し、取得したイベントの種類に応じて検索要求の検索のスケジュールを制御する。具体的には、検索スケジュール制御部２２は、検索要求受付部２１から検索要求の到着イベントを取得すると、要求キューに入力されている検索要求を取り出し、取り出した検索要求を後述する検索要求集合化探索部２３に出力する。また、検索スケジュール制御部２２は、後述する検索処理部２４から検索要求の検索完了イベントを取得すると、検索要求を一括して処理する検索要求の集合の取得依頼を検索要求集合化探索部２３に出力する。そして、検索スケジュール制御部２２は、検索要求の集合の取得依頼に対する集合を検索要求集合化探索部２３から取得すると、取得した集合に含まれる検索要求を検索処理部２４に出力する。
【００３８】
検索要求集合化探索部２３は、検索スケジュール制御部２２からほぼ同時に取得した複数の検索要求に対し、平均レスポンスが向上するような分割案を探索する。さらに、検索要求集合化探索部２３は、イベント振分部３１、参照パス判定部３２、検索要求集合分割部３３、平均レスポンス算出部３４、平均レスポンス判定部３５及び分割パターン選択部３６を有する。
【００３９】
イベント振分部３１は、イベントを取得し、取得したイベントの種類に応じて処理を振り分ける。具体的には、イベント振分部３１は、検索スケジュール制御部２２からほぼ同時に取得した複数の検索要求を検索要求集合として、分割対象検索要求集合５３に記憶する。
【００４０】
ここで、分割対象検索要求集合５３は、複数の部分集合に分割される検索要求集合を記憶する。例えば、分割対象検索要求集合５３は、検索要求集合に一意に割り振られた識別番号に、検索要求集合に含まれる複数の検索要求を対応付けて記憶する。
【００４１】
また、イベント振分部３１は、検索スケジュール制御部２２から検索要求の集合の取得依頼を取得すると、検索要求集合の分割パターンを選択させるべく、当該取得依頼を分割パターン選択部３６に出力する。また、イベント振分部３１は、直近のイベントを取得したときから一定期間イベントの取得がない場合には、分割対象検索要求集合５３に記憶された検索要求集合を複数の部分集合に分割させるべく、検索要求集合の分割依頼を参照パス判定部３２に出力する。
【００４２】
参照パス判定部３２は、イベント振分部３１から検索要求集合の分割依頼を取得すると、分割対象検索要求集合５３に記憶された検索要求集合に含まれる各検索要求について、データを参照する際に用いるパスを判定する。そして、参照パス判定部３２は、各検索要求について、判定したパスを一時的に揮発性記憶部２７に記憶する。例えば、参照パス判定部３２は、各検索要求について、パス毎に参照の有無を表すフラグの列を記憶する。ここで、参照が有ることを表すフラグの値は「１」とし、参照が無いことを表すフラグの値は「０」とする。
【００４３】
検索要求集合分割部３３は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する。具体的には、検索要求集合分割部３３は、パス参照判定部３２によってパスの判定がされた複数の検索要求を、各検索要求が参照するパスが指し示すデータの重複する度合いに基づいて複数の部分集合に分割する。例えば、検索要求集合分割部３３は、参照するパスが指し示すデータが所定の割合以上重複する検索要求同士を同一の部分集合に集合化し、所定の割合以上重複しない検索要求同士を異なる部分集合に分割する。分割した２個の部分集合の組み合わせは、１個の分割パターンとなる。なお、所定の割合とは、例えば８割や９割であるが、随時変動しても良い。また、１個の分割パターンを形成する２個の部分集合は、積集合が空、且つ和集合が検索要求集合となる組み合わせであるものとする。
【００４４】
また、検索要求集合分割部３３は、検索要求集合を分割した部分集合毎に、参照するデータのデータ量を算出する。具体的には、検索要求集合分割部３３は、検索要求毎のフラグの列を用いて、部分集合に含まれる検索要求について、パス毎のフラグの論理和を算出する。なお、検索要求毎のフラグの列は、参照パス判定部３２によって揮発性記憶部２７に記憶されているものとする。そして、検索要求集合分割部３３は、算出されたパス毎のフラグの値に基づいて、インデックスパス別データ量４２を用いてパス毎の参照データ量を算出する。そして、検索要求集合分割部３３は、算出したパス毎の参照データ量を加算し、「検索要求部分集合の参照データ量」を求める。
【００４５】
また、検索要求集合分割部３３は、「検索要求部分集合の参照データ量」を部分集合に対応付けて、検索要求部分集合及び参照データ量の対応表５１に記憶する。ここで、検索要求部分集合及び参照データ量の対応表５１のデータ構造について、図５を参照しながら説明する。
【００４６】
図５は、検索要求部分集合及び参照データ量の対応表５１のデータ構造の一例を示す図である。図５に示すように、検索要求部分集合及び参照データ量の対応表５１は、キー５１ａ及び参照データ量５１ｂを対応付けて記憶する。すなわち、検索要求部分集合及び参照データ量の対応表５１は、キー５１ａに対応する値を参照データ量５１ｂとするハッシュテーブル等のマップ構造となっている。キー５１ａは、検索要求の部分集合に含まれる検索要求の識別子の集合を示す。参照データ量５１ｂは、検索要求の部分集合が参照するデータのデータ量を示す。
【００４７】
また、検索要求の部分集合（検索要求部分集合）が参照するデータのデータ量を算出する方法を、図６を参照しながら説明する。図６は、検索要求部分集合の参照データ量の算出方法を説明する図である。図６では、検索要求部分集合Ｑに検索要求ｑ１〜ｑ３が含まれる場合を例として、検索要求部分集合Ｑの参照データ量の算出方法を説明する。図６に示すように、検索要求ｑ１のフラグの列は、パス２を参照有りの「１」とし、パス２以外のパスを参照無しの「０」とする。検索要求ｑ２のフラグの列は、パス１、２を参照有りの「１」とし、パス１、２以外のパスを参照無しの「０」とする。検索要求ｑ３のフラグの列は、パス１、Ｎを参照有りの「１」とし、パス１、Ｎ以外のパスを参照無しの「０」とする。
【００４８】
検索要求集合分割部３３は、検索要求ｑ１〜ｑ３のそれぞれのフラグの列を用いて、パス毎のフラグの論理和を算出する。ここでは、算出されたパス毎のフラグの列は、パス１、２、Ｎを参照有りの「１」とし、パス１、２、Ｎ以外のパスを参照無しの「０」となる。そして、検索要求集合分割部３３は、算出されたパス毎のフラグの列の各値とインデックスパス別データ量４２に記憶されたパス毎のデータ量との内積を算出する。ここでは、算出されたパス毎のフラグの列の各値は｛１、１、０、・・・、１｝であり、インデックスパス別データ量４２に記憶されたパス毎のデータ量は｛１２３、４５６、７８９、・・・、３２１｝である。したがって、パス毎の積を求めると、結果は｛１２３、４５６、０、・・・、３２１｝となる。さらに、検索要求集合分割部３３は、計算の結果得られたパスごとのデータ量を加算し、「検索要求部分集合の参照データ量」を求める。ここでは、「検索要求部分集合の参照データ量」は、「９００」となる。
【００４９】
図４に戻って、平均レスポンス算出部３４は、検索要求集合分割部３３によって分割された複数の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。具体的には、平均レスポンス算出部３４は、検索要求集合分割部３３によって分割された分割パターンの中から順次１個の分割パターンを選択する。そして、平均レスポンス算出部３４は、選択した分割パターンに含まれる２個の部分集合の処理順序を決定する。また、平均レスポンス算出部３４は、処理順序が先行する部分集合（以降、「先行部分集合」という。）に含まれる検索要求の参照データ量を、検索要求部分集合及び参照データ量の対応表５１から読み出す。そして、平均レスポンス算出部３４は、読み出した参照データ量に基づいて、先行部分集合の検索時間を算出する。また、平均レスポンス算出部３４は、処理順序が後行する部分集合（以降、「後行部分集合」という。）に含まれる検索要求の参照データ量を、検索要求部分集合及び参照データ量の対応表５１から読み出す。そして、平均レスポンス算出部３４は、読み出した参照データ量に基づいて、後行部分集合の検索時間を算出する。
【００５０】
そして、平均レスポンス算出部３４は、先行部分集合の検索時間及び後行部分集合の検索時間に基づいて、先行部分集合及び後行部分集合の和集合である検索要求集合に含まれる検索要求の平均レスポンスを算出する。例えば、先行部分集合の検索時間をｒ１、後行部分集合の検索時間をｒ２とし、先行部分集合に含まれる検索要求の数をＮ１、後行部分集合に含まれる検索要求の数をＮ２とする。また、検索要求集合に含まれる検索要求の数をＮ０とする。すなわち、Ｎ０は、Ｎ１及びＮ２を加算した値である。このような例において、検索要求集合に含まれる検索要求の平均レスポンスｒ１２は、式（３）で表される。
ｒ１２＝｛Ｎ１×ｒ１＋Ｎ２×（ｗ２＋ｒ２）｝／Ｎ０＝ｒ１＋ｒ２×Ｎ２／Ｎ０・・式（３）
なお、ｗ２は、先行部分集合の検索処理後に処理される後行部分集合の待ち時間であり、先行部分集合の検索時間ｒ１と同値となる。
【００５１】
また、平均レスポンス算出部３４は、算出した検索要求の平均レスポンスを、分割パターンに対応付けて、分割パターン及び平均レスポンスの対応表５２に記憶する。ここで、分割パターン及び平均レスポンスの対応表５２のデータ構造について、図７を参照しながら説明する。
【００５２】
図７は、分割パターン及び平均レスポンスの対応表５２のデータ構造の一例を示す図である。図７に示すように、分割パターン及び平均レスポンスの対応表５２は、分割パターン５２ａ及び平均レスポンス５２ｂを対応付けて記憶する。すなわち、分割パターン及び平均レスポンスの対応表５２は、分割パターン５２ａをキー、平均レスポンス５２ｂを値とするＢ−Ｔｒｅｅ等のマップ構造となっている。分割パターン５２ａは、処理順序に応じた２個の部分集合を示す。この２個の部分集合は、積集合が空、すなわち重複した検索要求を持たない集合同士となっている。平均レスポンス５２ｂは、分割パターン５２ａで示される２個の部分集合における検索要求の平均レスポンスを示す。
【００５３】
平均レスポンス判定部３５は、検索要求集合を分割した２個の部分集合の平均レスポンスが検索要求集合を分割しない場合より向上しているか否かを判定する。具体的には、平均レスポンス判定部３５は、検索要求集合を分割しない場合の平均レスポンスを算出する。そして、平均レスポンス判定部３５は、平均レスポンス算出部３４によって平均レスポンスが算出された分割パターンについて、この平均レスポンスが検索要求集合を分割しない場合の平均レスポンスより短いか否かを判定する。そして、平均レスポンス判定部３５は、分割パターンについての平均レスポンスが検索要求集合を分割しない場合より短いと判定した場合に、分割しない場合より平均レスポンスが向上すると判断する。一方、平均レスポンス判定部３５は、分割パターンについての平均レスポンスが検索要求集合を分割しない場合より短いと判定した場合に、分割しない場合より平均レスポンスが向上しないと判断する。
【００５４】
ここで、検索要求集合を分割した場合における平均レスポンスが、検索要求集合を分割しない場合における平均レスポンスより向上するために満たすべき条件について、図８を参照して説明する。図８は、分割により平均レスポンスが向上するための条件を説明する図である。図８（Ａ）では、分割しない場合の検索処理コストを示し、図８（Ｂ）では、分割する場合の検索処理コストを示し、図８（Ｃ）では、分割しない場合と分割する場合の差を示す図である。なお、図８では、検索要求集合に含まれる検索要求の数をＮ０、先行部分集合に含まれる検索要求の数をＮ１、後行部分集合に含まれる検索要求の数をＮ２とする。また、検索要求集合の全体の参照データをＤ０、先行部分集合の参照データをＤ１、後行部分集合の参照データをＤ２とする。さらに、Ｓ（Ｄｎ）（ｎは、１、２）を参照データＤｎの参照データ量とし、ｒ（Ｓ（Ｄｎ））を参照データＤｎの参照データ量を検索する際の検索時間とする。
【００５５】
図８（Ａ）に示すように、分割しない場合の検索処理コストは、検索要求集合に含まれる全検索要求の参照データ量Ｓ（Ｄ０）を検索する際の検索時間ｒ（Ｓ（Ｄ０））と検索要求の数Ｎ０との積で表される。ここでは、Ｔ０で示される領域となる。すなわち、ハイトラフィック技術では、検索要求集合に含まれる複数の検索要求を一括して処理するので、検索時間は一括して処理する参照データ量に比例することとなり、検索要求集合の検索処理コストは参照データ量と検索要求の数から求められる。
【００５６】
次に、図８（Ｂ）に示すように、分割する場合の検索処理コストは、先行部分集合の検索処理コスト、後行部分集合の検索処理コスト及び後行部分集合の待ちコストの和で表される。先行部分集合の検索処理コストは、先行部分集合に含まれる検索要求の参照データ量Ｓ（Ｄ１）を検索する際の検索時間ｒ（Ｓ（Ｄ１））（以降、「ｒ１」）と検索要求の数Ｎ１との積で表される。ここでは、Ｔ１で示される領域となる。また、後行部分集合の検索処理コストは、後行部分集合に含まれる検索要求の参照データ量Ｓ（Ｄ２）を検索する際の検索時間ｒ（Ｓ（Ｄ２））（以降、「ｒ２」）と検索要求の数Ｎ２との積で表される。ここでは、Ｔ２で示される領域となる。さらに、後行部分集合の待ちコストは、後行部分集合が検索処理を実行するまでの待ち時間と一致する先行部分集合の検索時間ｒ１（以降、「ｗ２」）と検索要求の数Ｎ２の積で表される。ここでは、Ｔ３で示される領域となる。
【００５７】
次に、図８（Ｃ）に示すように、分割しない場合と分割する場合の差は、分割により検索処理コストが減少することとなる「分割によるベネフィット」Ｔ４と分割により検索処理コストが増加することとなる「分割によるコスト」Ｔ５との差分となる。ここでは、「分割によるベネフィット」Ｔ４は、後行部分集合の参照データＤ２から先行部分集合の参照データＤ１を引いたデータを検索する際の検索時間ｒ（Ｓ（Ｄ２−Ｄ１））と先行部分集合に含まれる検索要求の数Ｎ１との積となる。また、分割によりコストＴ５は、後行部分集合の参照データＤ２と先行部分集合の参照データＤ１とが共に参照するデータを検索する際の検索時間ｒ（Ｓ（Ｄ２∩Ｄ１））と後行部分集合に含まれる検索要求の数Ｎ２との積となる。
【００５８】
したがって、分割しない場合と分割する場合の差Ｊ０は、「分割によるベネフィット」Ｔ４及び「分割によるコスト」Ｔ５を用いて、式（４）で表される。
Ｊ０＝Ｔ４−Ｔ５＝Ｎ１×ｒ（Ｓ（Ｄ２−Ｄ１））−Ｎ２×ｒ（Ｓ（Ｄ２∩Ｄ１））・・・式（４）
そして、分割しない場合と分割する場合の差Ｊ０が正値となる場合、すなわち「分割によるベネフィット」Ｔ４が「分割によるコスト」Ｔ５より大きい場合に、分割により平均レスポンスが向上することとなる。つまり、「分割によるコスト」Ｔ５が小さいほど、言い換えれば後行部分集合の参照データＤ２と先行部分集合の参照データＤ１とが共に参照するデータＳ（Ｄ２∩Ｄ１）が小さいほど、分割によるメリットがより大きくなる。また、後行部分集合のみ参照し先行部分集合が参照しないデータＳ（Ｄ２−Ｄ１）が大きいほど、分割によるメリットがより大きくなる。
【００５９】
分割パターン選択部３６は、平均レスポンス判定部３５によって平均レスポンスが分割しない場合より向上すると判断された分割パターンの中から最短の平均レスポンスとなる分割パターンを選択する。具体的には、分割パターン選択部３６は、イベント振分部３１から検索要求の集合の取得依頼を取得すると、分割パターン及び平均レスポンスの対応表５２に基づいて、最短の平均レスポンスに対応付けられた分割パターンを選択する。そして、分割パターン選択部３６は、選択した分割パターンのうち先行部分集合を、先行して検索処理させるべく、検索スケジュール制御部２２に出力する。このとき、分割パターン選択部３６は、選択した分割パターンのうち後行部分集合を、実行待機中要求集合５４に記憶する。
【００６０】
ここで、実行待機中要求集合５４は、検索要求集合の分割パターンのうち先行部分集合が先行して検索処理されているとき、後続して検索処理される後行部分集合を待機させるために記憶する。例えば、実行待機中要求集合５４は、検索要求集合に一意に割り振られた識別番号に、後行部分集合に含まれる複数の検索要求を対応付けて記憶する。なお、分割パターン選択部３６は、既に実行待機中要求集合５４に直前の検索要求集合における後行部分集合が記憶されている場合には、この後行部分集合を、現在処理中の検索要求集合における先行部分集合とともに検索スケジュール制御部２２に出力する。これらの部分集合が、後述する検索処理部２４によって併合して処理されるためである。
【００６１】
検索処理部２４は、検索スケジュール制御部２２から部分集合に含まれる検索要求を取得すると、データベース４１からこれら検索要求について一括して検索処理を実行する。そして、検索処理部２４は、部分集合に含まれる検索要求について検索処理が完了すると、検索要求の検索完了イベントを検索スケジュール制御部２２に出力する。
【００６２】
検索結果出力部２５は、検索処理部２４によって一括して検索処理された部分集合毎に、各部分集合に含まれる検索要求の検索結果を出力する。
【００６３】
［実施例２に係る検索要求制御処理の手順］
次に、検索要求制御処理の手順を、図９を参照して説明する。図９は、実施例２に係る検索要求制御処理の手順を示すフローチャートである。
【００６４】
まず、検索要求制御処理は、検索要求の検索状況を判定する（ステップＳ１１）。そして、検索要求制御処理は、検索要求の検索状況が検索中であると判定する場合には（ステップＳ１１；検索中）、新たな検索要求が到着していれば分割対象の検索要求集合に加える（ステップＳ１２）。すなわち、検索要求制御処理は、検索要求集合の直前に到着した検索要求集合に関わる検索要求の検索中に、ほぼ同時を示す所定期間に到着した新たな検索要求を検索要求集合として分割対象検索要求集合５３に記憶する。そして、検索要求制御処理は、分割対象検索要求集合５３に記憶された分割対象の検索要求集合に対して、平均レスポンスが向上するような分割パターンの探索処理を行う（ステップＳ１３）。そして、検索要求制御処理は、ステップＳ１１に移行する。
【００６５】
一方、検索要求制御処理は、検索要求の検索状況が検索完了であると判定する場合には（ステップＳ１１；検索完了）、検索結果を出力する（ステップＳ１４）。そして、検索要求制御処理は、分割対象検索要求集合５３に記憶された検索要求集合について、現段階で探索された分割パターンのうち平均レスポンスが最短の分割パターンにおける先行部分集合に対して、検索処理を開始させる（ステップＳ１５）。そして、検索要求制御処理は、ステップＳ１１に移行する。
【００６６】
［検索スケジュール制御処理の手順］
次に、検索スケジュール制御部２２による検索スケジュール制御処理の手順を、図１０を参照して説明する。図１０は、検索スケジュール制御処理の手順を示すフローチャートである。
【００６７】
まず、検索スケジュール制御部２２は、イベントを待ち（ステップＳ２１）、イベントを取得したとき、取得したイベントを判定する（ステップＳ２２）。
【００６８】
そして、検索スケジュール制御部２２は、取得したイベントが検索要求の到着イベントであると判定する場合には（ステップＳ２２；検索要求の到着）、要求キューに入力されている検索要求を取り出す（ステップＳ２３）。そして、検索スケジュール制御部２２は、検索要求の検索処理中であるか否かを判定する（ステップＳ２４）。そして、検索スケジュール制御部２２は、検索要求が検索処理中であると判定する場合には（ステップＳ２４；Ｙｅｓ）、要求キューから取り出した全検索要求を分割させるべく、当該全検索要求を検索要求集合化探索部２３に出力する（ステップＳ２５）。そして、検索スケジュール制御部２２は、ステップＳ２１に処理を移行する。
【００６９】
一方、検索スケジュール制御部２２は、検索要求が検索処理中でないと判定する場合には（ステップＳ２４；Ｎｏ）、要求キューから取り出した全検索要求を検索処理させるべく、当該全検索要求を検索処理部２４に出力する（ステップＳ２６）。そして、検索スケジュール制御部２２は、ステップＳ２１に処理を移行する。
【００７０】
一方、検索スケジュール制御部２２は、取得したイベントが検索要求の検索完了イベントである場合には（ステップＳ２２；検索完了）、次に検索する検索要求を促すべく、検索要求の集合の取得依頼を検索要求集合化探索部２３に出力する（ステップＳ２７）。そして、検索スケジュール制御部２２は、検索要求集合化探索部２３からの検索要求の集合を待つ（ステップＳ２８）。
【００７１】
続いて、検索スケジュール制御部２２は、検索要求集合化探索部２３から検索要求の集合を取得すると、取得した集合が空集合か否かを判定する（ステップＳ２９）。そして、検索スケジュール制御部２２は、取得した集合が空集合であると判定する場合には（ステップＳ２９；Ｙｅｓ）、次のイベントを待つべく、ステップＳ２１に移行する。一方、検索スケジュール制御部２２は、取得した集合が空集合でないと判定する場合には（ステップＳ２９Ｎｏ）、取得した集合に含まれる検索要求を検索処理部２４に出力する（ステップＳ３０）。
【００７２】
［検索要求集合化探索処理の手順］
次に、検索要求集合化探索部２３による検索要求集合化探索処理の手順を、図１１を参照して説明する。図１１は、検索要求集合化探索処理の手順を示すフローチャートである。
【００７３】
まず、探索要求集合化探索部２３は、分割対象検索要求集合５３を空集合で初期化する（ステップＳ４１）。そして、探索要求集合化探索部２３のイベント振分部３１は、イベントを待ち（ステップＳ４２）、イベントを取得したとき、取得したイベントを判定する（ステップＳ４３）。
【００７４】
そして、イベント振分部３１は、取得したイベントが検索要求の取得イベントであると判定する場合（ステップＳ４３；検索要求の取得）、取得した検索要求を分割対象検索要求集合５３に追加する（ステップＳ４４）。すなわち、イベント振分部３１は、取得した複数の検索要求を検索要求集合として、分割対象検索要求集合５３に記憶する。
【００７５】
そして、平均レスポンス算出部３４は、取得した検索要求を加えた分割パターンでの平均レスポンスを再計算し、分割パターンに対応付けた計算結果を分割パターン及び平均レスポンスの対応表５２に更新する（ステップＳ４５）。そして、平均レスポンス算出部３４は、処理をステップＳ４２に移行する。
【００７６】
また、イベント振分部３１が直近のイベントの取得から一定期間イベントの取得がないと判定する場合（ステップＳ４３；イベントなし）、検索要求集合分割部３３は、分割対象検索要求集合５３の検索要求集合から分割パターンを生成する（ステップＳ４６）。すなわち、検索要求集合分割部３３は、それぞれの検索要求が検索するデータの重複する度合いに基づいて検索要求集合を２個の部分集合に分割し、分割パターンを生成する。例えば、検索要求集合分割部３３は、参照するパスが指し示すデータが所定の割合以上重複する検索要求同士を同一の部分集合に集合化し、所定の割合以上重複しない検索要求を異なる部分集合に分割し、これらの部分集合の組を１個の分割パターンとする。
【００７７】
続いて、検索要求集合分割部３３は、生成した分割パターンを１個選択する（ステップＳ４７）。そして、検索要求集合分割部３３は、選択した分割パターンに含まれる部分集合毎に、参照するデータのデータ量を計算し、検索要求部分集合及び参照データ量の対応表５１に追加する（ステップＳ４８）。
【００７８】
そして、平均レスポンス算出部３４は、選択した分割パターンに含まれる２個の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する（ステップＳ４９）。具体的には、平均レスポンス算出部３４は、分割パターンに含まれる２個の部分集合の処理順序を決定し、決定した処理順序が先行する先行部分集合及び処理順序が後行する後行部分集合の参照データ量を検索要求部分集合及び参照データ量の対応表５１から読み出す。そして、平均レスポンス算出部３４は、読み出した先行部分集合及び後行部分集合の参照データ量に基づいて、それぞれのデータの検索時間を算出する。さらに、平均レスポンス算出部３４は、先行部分集合及び後行部分集合のそれぞれの検索時間に基づいて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。
【００７９】
そして、平均レスポンス算出部３４は、算出した平均レスポンスを、分割パターンに対応付けて、分割パターン及び平均レスポンスの対応表５２に追加し（ステップＳ５０）、処理をステップＳ４２に移行する。
【００８０】
また、イベント振分部３１が検索要求の集合の取得依頼イベントであると判定する場合（ステップＳ４３；要求集合の取得依頼）、分割パターン選択部３６は、平均レスポンスが最短となる分割パターンを選択する（ステップＳ５１）。具体的には、分割パターン選択部３６は、分割パターン及び平均レスポンスの対応表５２に基づいて、最短の平均レスポンスに対応付けられた分割パターンを選択する。
【００８１】
そして、分割パターン選択部３６は、選択した分割パターンのうち先行部分集合に含まれる検索要求を、先行して検索処理させるべく、検索スケジュール制御部２２に出力する（ステップＳ５２）。このとき、分割パターン選択部３６は、選択した分割パターンのうち後行部分集合に含まれる検索要求を、実行待機中要求集合５４に移動する（ステップＳ５３）。そして、分割パターン選択部３６は、処理をステップＳ４１に移行する。なお、分割パターン選択部３６は、既に実行待機中要求集合５４に直前の検索要求集合における後行部分集合が記憶されている場合には、この後行部分集合を、現在処理中の検索要求集合における先行部分集合とともに検索スケジュール制御部２２に出力する。
【００８２】
［実施例２の効果］
上記実施例２によれば、検索要求集合分割部３３は、ほぼ同時に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する。そして、平均レスポンス算出部３４は、検索要求集合分割部３３によって分割された複数の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。さらに、検索処理部２４は、平均レスポンス算出部３４によって算出された平均レスポンスが最短の複数の部分集合について、処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する。
【００８３】
かかる構成によれば、検索要求集合分割部３３は、一括処理する単位となる部分集合への分割に検索要求が検索するデータの重複する度合いを用いることとした。このため、検索要求集合分割部３３は、部分集合における検索データの局所性を高めることができるので、データの検索効率の向上を図ることができる。さらに、検索要求集合分割部３３は、検索要求の平均レスポンスがより短くなるように検索要求集合を部分集合に分割することとなるので、分割した部分集合をそれぞれ処理することで検索要求の平均レスポンスを向上させることができる。
【００８４】
また、上記実施例２によれば、検索要求集合分割部３３は、検索要求集合を、当該検索要求集合の直前に取得された検索要求集合に関わる検索要求の実行中に、複数の部分集合に分割する。そして、平均レスポンス算出部３４は、検索要求集合分割部３３によって分割された複数の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。かかる構成によれば、検索要求集合の直前に取得された検索要求集合の実行完了後に次に実行すべき検索要求集合について平均レスポンスがより短くなる部分集合を選択できるので、全体の検索要求の平均レスポンスを向上させることができる。
【００８５】
また、上記実施例２によれば、検索処理部２４は、処理順序が先行する部分集合に含まれる検索要求を検索要求集合の直前に取得された検索要求の処理後に実行する。そして、検索処理部２４は、処理順序が後行する部分集合に含まれる検索要求を検索要求集合の直後に取得された検索要求と併合して処理する。かかる構成によれば、検索処理部２４は、処理順序が後行する部分集合を検索要求集合の直後に取得された検索要求と併合して処理することとした。このため、検索処理部２４は、処理順序が後行する部分集合の処理時期を無期限に延期しないので、当該部分集合を含む検索要求集合の平均レスポンスを確実に向上させることができる。
【００８６】
また、上記実施例２によれば、検索要求部分集合及び参照データ量の対応表５１は、部分集合毎にそれぞれの部分集合に含まれる検索要求が一括して検査するデータのデータ量を記憶する。そして、平均レスポンス算出部３４は、処理順序が先行する部分集合に関わるデータ量のデータを検索する検索時間及び処理順序が後行する部分集合に関わるデータ量のデータを検索する検索時間を用いて、平均レスポンスを算出する。かかる構成によれば、仮に処理順序が先行する部分集合及び処理順序が後行する部分集合に関わるデータ量が重複しない場合には、平均レスポンス算出部３４は、各部分集合に関わるデータ量のデータを検索する検索時間を要するのみとなる。このため、平均レスポンス算出部３４は、検索要求集合を分割しない場合と比べて、検索時間が短くなり、平均レスポンスを向上させることができる。
【００８７】
なお、実施例２では、分割パターン選択部３６は、分割パターン及び平均レスポンスの対応表５２に基づいて、最短の平均レスポンスに対応付けられた分割パターンを選択するものとして説明した。しかしながら、分割パターン選択部３６は、分割パターンに対応付けられた最短の平均レスポンスが分割しない場合の平均レスポンスより長い場合には、分割しないままの検索要求集合を選択するようにするようにしても良い。この場合には、平均レスポンス算出部３４が、分割しない場合の検索要求の平均レスポンスを検索要求集合に対応付けて分割パターン及び平均レスポンスの対応表５２に記憶しておく。そして、分割パターン選択部３６は、分割しない場合の検索要求の平均レスポンスを含めて最短の平均レスポンスとなる分割パターンを選択するようにすれば良い。これにより、分割パターン選択部３６は、分割しない場合の検索要求の平均レスポンスよりも長くなることがなくなり平均レスポンスを安定させることができる。
【００８８】
また、実施例２では、分割パターン選択部３６は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて２個の部分集合に分割するものとして説明した。しかしながら、分割パターン選択部３６は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて３個の部分集合に分割するようにしても良い。
【００８９】
［プログラム等］
また、この検索要求制御装置２は、既知のパーソナルコンピュータ、ワークステーションなどの情報処理装置に、上記した検索スケジュール制御部２２、検索要求集合化探索部２３等の各機能を搭載することによって実現することができる。
【００９０】
また、図示した各装置の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的態様は図示のものに限られず、その全部又は一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的又は物理的に分散・統合して構成することができる。例えば、平均レスポンス算出部３４と平均レスポンス判定部３５とを１個の部として統合しても良い。一方、平均レスポンス算出部３４を、複数の部分集合の処理順序を並び替える並び替え部と、処理順序を並び替えた複数の部分集合について平均レスポンスを算出する算出部とに分散しても良い。また、不揮発性記憶部２６等の記憶部を検索要求制御装置２の外部装置としてネットワーク経由で接続するようにしても良い。
【００９１】
また、上記実施例で説明した各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで、以下では、図１２を用いて、図４に示した検索要求制御装置２と同様の機能を有する検索要求制御プログラムを実行するコンピュータの一例を説明する。
【００９２】
図１２は、検索要求制御プログラムを実行するコンピュータのハードウェア構成を示す図である。図１２に示すように、コンピュータ１０００は、ＲＡＭ（Random Access Memory）１０１０と、ネットワークインタフェース装置１０２０と、ＨＤＤ１０３０と、ＣＰＵ（Central Processing Unit）１０４０、媒体読取装置１０５０と、入力装置１０６０と、出力装置１０７０とを有する。ＲＡＭ１０１０、ネットワークインタフェース装置１０２０、ＨＤＤ１０３０、ＣＰＵ１０４０、入力装置１０６０及び出力装置１０７０は、バス１０８０によって接続されている。
【００９３】
そして、ＨＤＤ１０３０には、図４に示した検索要求制御装置２と同様の機能を有する検索要求制御プログラム１０３１が記憶される。また、ＨＤＤ１０３０には、図４に示した不揮発性記憶部２６内の情報（データベース４１、インデックスパス別データ量４２）に対応する検索対象データ情報１０３２が記憶される。
【００９４】
そして、ＣＰＵ１０４０が検索要求制御プログラム１０３１をＨＤＤ１０３０から読み出してＲＡＭ１０１０に展開することにより、検索要求制御プログラム１０３１は、検索要求制御プロセス１０１１として機能するようになる。そして、検索要求制御プロセス１０１１は、検索対象データ情報１０３２から読み出した情報等を適宜ＲＡＭ１０１０上の自身に割り当てられた領域に展開し、この展開したデータ、例えば検索要求制御情報１０１２等に基づいて各種データ処理を実行する。
【００９５】
媒体読取装置１０５０は、検索要求制御プログラム１０３１がＨＤＤ１０３０に記憶されていない場合であっても、検索要求制御プログラム１０３１を記憶する媒体等から検索要求制御プログラム１０３１を読み取る。媒体読取装置１０５０には、例えばＣＤ−ＲＯＭや光ディスク装置がある。
【００９６】
ネットワークインタフェース装置１０２０は、外部装置とネットワーク経由で接続する装置であり、有線に対応するものであっても、無線に対応するものであっても良い。また、入力装置１０６０には、例えばキーボードやマウスがあり、出力装置１０７０には、例えばディスプレイがある。
【００９７】
なお、上記の検索要求制御プログラム１０３１は、公衆回線、インターネット、ＬＡＮ（Local Area Network）、ＷＡＮ（Wide Area Network）等を介してコンピュータ１０００に接続される他のコンピュータ（またはサーバ）等にこのプログラムを記憶させておいても良い。この場合には、コンピュータ１０００がこれらからプログラムを読み出して実行する。
【００９８】
以上の実施例に係る実施形態に関し、さらに以下の付記を開示する。
【００９９】
（付記１）所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割部と、
前記検索要求集合分割部によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出部と、
前記平均レスポンス算出部によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理部と
を有することを特徴とする検索要求制御装置。
【０１００】
（付記２）前記検索要求集合分割部は、
前記検索要求集合を、当該検索要求集合の直前に取得された検索要求集合に関わる検索要求の処理中に、複数の部分集合に分割することを特徴とする付記１に記載の検索要求制御装置。
【０１０１】
（付記３）前記検索処理部は、
前記処理順序が先行する部分集合に含まれる検索要求を前記検索要求集合の直前に取得された検索要求の処理後に処理し、前記処理順序が後行する部分集合に含まれる検索要求を前記検索要求集合の直後に取得された検索要求と併合して処理することを特徴とする付記１または付記２に記載の検索要求制御装置。
【０１０２】
（付記４）前記部分集合毎にそれぞれの部分集合に含まれる検索要求が一括して検索するデータのデータ量を記憶するデータ量記憶部を有し、
前記平均レスポンス算出部は、
前記処理順序が先行する部分集合に関わるデータ量のデータを検索する検索時間及び前記処理順序が後行する部分集合に関わるデータ量のデータを検索する検索時間を用いて、前記平均レスポンスを算出することを特徴とする付記１から付記３のいずれか１つに記載の検索要求制御装置。
【０１０３】
（付記５）所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割手順と、
前記検索要求集合分割手順によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出手順と、
前記平均レスポンス算出手順によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理手順と
をコンピュータに実行させることを特徴とする検索要求制御プログラム。
【０１０４】
（付記６）検索要求制御装置が検索要求を制御する検索要求制御方法であって、
所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割工程と、
前記検索要求集合分割工程によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出工程と、
前記平均レスポンス算出工程によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理工程と
を含むことを特徴とする検索要求制御方法。
【符号の説明】
【０１０５】
１、２ 検索要求制御装置
１１ 検索要求集合分割部
１２ 平均レスポンス算出部
１３ 検索処理部
２１ 検索要求受付部
２２ 検索スケジュール制御部
２３ 検索要求集合化探索部
２４ 検索処理部
２５ 検索結果出力部
２６ 不揮発性記憶部
２７ 揮発性記憶部
３１ イベント振分部
３２ 参照パス判定部
３３ 検索要求集合分割部
３４ 平均レスポンス算出部
３５ 平均レスポンス判定部
３６ 分割パターン選択部
４１ データベース
４１ａ インデックス
４１ｂ 検索対象データ
４２ インデックスパス別データ量
５１ 検索要求部分集合及び参照データ量の対応表
５２ 分割パターン及び平均レスポンスの対応表
５３ 分割対象検索要求集合
５４ 実行待機中要求集合
【特許請求の範囲】
【請求項１】
所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割部と、
前記検索要求集合分割部によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出部と、
前記平均レスポンス算出部によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理部と
を有することを特徴とする検索要求制御装置。
【請求項２】
前記検索要求集合分割部は、
前記検索要求集合を、当該検索要求集合の直前に取得された検索要求集合に関わる検索要求の実行中に、複数の部分集合に分割することを特徴とする請求項１に記載の検索要求制御装置。
【請求項３】
前記検索処理部は、
前記処理順序が先行する部分集合に含まれる検索要求を前記検索要求集合の直前に取得された検索要求の処理後に処理し、前記処理順序が後行する部分集合に含まれる検索要求を前記検索要求集合の直後に取得された検索要求と併合して処理することを特徴とする請求項１または請求項２に記載の検索要求制御装置。
【請求項４】
所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割手順と、
前記検索要求集合分割手順によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出手順と、
前記平均レスポンス算出手順によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理手順と
をコンピュータに実行させることを特徴とする検索要求制御プログラム。
【請求項５】
検索要求制御装置が検索要求を制御する検索要求制御方法であって、
所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割工程と、
前記検索要求集合分割工程によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出工程と、
前記平均レスポンス算出工程によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理工程と
を含むことを特徴とする検索要求制御方法。
【請求項１】
所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割部と、
前記検索要求集合分割部によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出部と、
前記平均レスポンス算出部によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理部と
を有することを特徴とする検索要求制御装置。
【請求項２】
前記検索要求集合分割部は、
前記検索要求集合を、当該検索要求集合の直前に取得された検索要求集合に関わる検索要求の実行中に、複数の部分集合に分割することを特徴とする請求項１に記載の検索要求制御装置。
【請求項３】
前記検索処理部は、
前記処理順序が先行する部分集合に含まれる検索要求を前記検索要求集合の直前に取得された検索要求の処理後に処理し、前記処理順序が後行する部分集合に含まれる検索要求を前記検索要求集合の直後に取得された検索要求と併合して処理することを特徴とする請求項１または請求項２に記載の検索要求制御装置。
【請求項４】
所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割手順と、
前記検索要求集合分割手順によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出手順と、
前記平均レスポンス算出手順によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理手順と
をコンピュータに実行させることを特徴とする検索要求制御プログラム。
【請求項５】
検索要求制御装置が検索要求を制御する検索要求制御方法であって、
所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割工程と、
前記検索要求集合分割工程によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出工程と、
前記平均レスポンス算出工程によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理工程と
を含むことを特徴とする検索要求制御方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２０１２−１５９８８７（Ｐ２０１２−１５９８８７Ａ）
【公開日】平成２４年８月２３日（２０１２．８．２３）
【国際特許分類】
【出願番号】特願２０１１−１７２２３（Ｐ２０１１−１７２２３）
【出願日】平成２３年１月２８日（２０１１．１．２８）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２４年８月２３日（２０１２．８．２３）
【国際特許分類】
【出願日】平成２３年１月２８日（２０１１．１．２８）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]