(57)【要約】【課題】Ｋｅｙ−Ｖａｌｕｅ検索において、ＲＤＢとＤＳＥ（ドキュメント検索エンジン）から検索時間が短い方を適切に選択すること。【解決手段】ＲＤＢコスト算出部５２が、統計情報テーブルを参照してキー毎にインデックスを用いた検索コストを算出し、キー毎の検索コストとキー毎の検索結果のマージコストとに基づいてＲＤＢによる検索コストを算出する。また、ＤＳＥコスト算出部５３が、統計情報テーブルを参照してキー毎にインデックスを用いた検索コストを算出し、キー毎の検索コストとキー毎の検索結果のマージコストとに基づいてＤＳＥによる検索コストを算出する。そして、判定部５４が、ＲＤＢコスト算出部５２とＤＳＥコスト算出部５３が算出した検索コストを比較し、ＲＤＢとＤＳＥのうち検索コストが低い方を選択する。【選択図】図７
2018060379.tif 000002
【特許請求の範囲】
【請求項１】
キーと値の組で表されるデータ群をリレーショナルデータベースを用いて記憶する第１のデータベースと、キーと値の組で表されるデータ群を該データ群のデータベースを用いて記憶する第２のデータベースのいずれかを検索クエリの内容に応じて選択する検索手段選択プログラムにおいて、
前記第１のデータベースの前記検索クエリに対する検索性能を示す第１の指標を前記データ群に関するキー毎の統計情報に基づいて生成し、
前記第２のデータベースの前記検索クエリに対する検索性能を示す第２の指標を前記データ群に関するキー毎の統計情報に基づいて生成し、
前記第１の指標と前記第２の指標に基づき、前記検索クエリに対し、前記第１のデータベースまたは前記第２のデータベースのいずれかを選択する
処理をコンピュータに実行させる検索手段選択プログラム。
【請求項２】
請求項１記載の検索手段選択プログラムであって、
前記第１のデータベースおよび前記第２のデータベースの検索性能に基づき、前記第１のデータベースまたは前記第２のデータベースのいずれかを選択する、
ことを特徴とする検索手段選択プログラム。
【請求項３】
請求項１または２記載の検索手段選択プログラムであって、
前記第１のデータベースは、Ｂ木インデックスと転置インデックスを有し、
前記第１の指標を生成する処理は、
前記検索クエリに含まれるキー毎に前記Ｂ木インデックスを用いて検索するか前記転置インデックスを用いて検索するかをキーに関する検索が前方一致検索であるか中間一致検索であるかに基づいて判定し、
判定結果に基づいて前記キー毎に検索性能を示す個別指標を前記統計情報に基づいて算出し、
算出した個別指標を用いて前記第１の指標を生成する
ことを特徴とする検索手段選択プログラム。
【請求項４】
請求項３記載の検索手段選択プログラムであって、
前記第１のデータベースを選択した場合に、前記判定結果を付加して前記第１のデータベースに前記検索クエリの実行を指示する
処理をさらにコンピュータに実行させることを特徴とする検索手段選択プログラム。
【請求項５】
請求項１〜４のいずれか１つ記載の検索手段選択プログラムであって、
前記統計情報は、キー種類数、キーの値の種類数、キーの値に関するヒストグラム、キー内の単語又はグラムの種類数、キー内の単語又はグラムに関するヒストグラムを含むことを特徴とする検索手段選択プログラム。
【請求項６】
キーと値の組で表されるデータ群をリレーショナルデータベースを用いて記憶する第１のデータベースと、キーと値の組で表されるデータ群を該データ群のデータベースを用いて記憶する第２のデータベースのいずれかを検索クエリの内容に応じて選択する検索手段選択方法において、
前記第１のデータベースの前記検索クエリに対する検索性能を示す第１の指標を前記データ群に関するキー毎の統計情報に基づいて生成し、
前記第２のデータベースの前記検索クエリに対する検索性能を示す第２の指標を前記データ群に関するキー毎の統計情報に基づいて生成し、
前記第１の指標と前記第２の指標に基づき、前記検索クエリに対し、前記第１のデータベースまたは前記第２のデータベースのいずれかを選択する
処理を実行する検索手段選択方法。
【請求項７】
キーと値の組で表されるデータ群をリレーショナルデータベースを用いて記憶する第１のデータベースと、キーと値の組で表されるデータ群を該データ群のデータベースを用いて記憶する第２のデータベースのいずれかを検索クエリの内容に応じて選択する検索手段選択装置において、
前記第１のデータベースの前記検索クエリに対する検索性能を示す第１の指標を前記データ群に関するキー毎の統計情報に基づいて生成する第１生成部と、
前記第２のデータベースの前記検索クエリに対する検索性能を示す第２の指標を前記データ群に関するキー毎の統計情報に基づいて生成する第２生成部と、
前記第１の指標と前記第２の指標に基づき、前記検索クエリに対し、前記第１のデータベースまたは前記第２のデータベースのいずれかを選択する選択部と
を有する検索手段選択装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索手段選択プログラム、検索手段選択方法及び検索手段選択装置に関する。
【背景技術】
【０００２】
複数のドキュメントを記憶し、ドキュメントに関するＫＶ（Ｋｅｙ−Ｖａｌｕｅ：キーと値）を用いて一定の条件を満たすドキュメントを検索するドキュメント検索では、Ｌｕｃｅｎｅ（登録商標、以下同様）等のドキュメント検索エンジンが用いられる。ドキュメント検索では、例えば帳票について、「パソコンの売買に関する帳票を一通り取り出す」、「今年８月〜１０月の取引一式を取り出す」、「１０万円以上の取引を取り出す」といった検索が行われる。これらの例では、ＫＶは、「商品−パソコン」、「取引日−今年８月〜１０月」、「価格−１０万円以上」である。
【０００３】
ドキュメントは、複数のキーを有し、キー毎に一つの値を有する。キーの数は、固定ではなく、ドキュメントを管理するドキュメント管理システムの運用の過程で増加する。利用するキーの数は、検索により一個〜十数個まで幅がある。
【０００４】
データ群を記憶して検索を行う場合、ＲＤＢ（Relational  Data  Base）システムが用いられることが多いが、ドキュメント検索では、ＲＤＢシステムは用いられてこなかった。その理由は、ＫＶ型の検索には、ＲＤＢシステムは向かないと考えられてきたためである。なお、以下では、ＲＤＢシステムを単にＲＤＢと呼ぶ。また、ドキュメント検索エンジンをＤＳＥ（Document  Search  Engine）と表す。
【０００５】
しかしながら、実際にドキュメント検索をＲＤＢを用いて行うと、ＤＳＥを用いる場合と比較して、検索クエリによって検索時間が速い場合と遅い場合がある。図１４は、ＲＤＢとＤＳＥの検索時間を示す図である。横軸は検索クエリの複雑さを示し、縦軸は検索時間を示す。図１４に示すように、検索クエリが複雑でない場合にはＲＤＢがＤＳＥより速いが、検索クエリが複雑な場合にはＤＳＥがＲＤＢより速い。そこで、ＲＤＢとＤＳＥの検索時間を推定し、検索が速い方を選択して検索を行うドキュメント検索装置が考えられる。
【０００６】
なお、テキスト検索において、テキストの識別情報からテキストに含まれるキーワードのリストを指定する第１インデックスと、キーワードの識別情報からキーワードを含むテキストのリストを指定する第２インデックスを用いて効率的な検索を行う技術がある。
【０００７】
また、全文検索を行う際に、テキストスキャン方式とインデックススキャン方式の検索時間を予測し、短い方の検索方式で検索処理を行う技術がある。また、受け付けた検索条件から、実データの検索に要する時間を推定し、推定した結果に基づいて、処理方法を判定し、判定結果に基づいて、処理方法を自動で切り分けて実データの検索を行うシステムがある。
【０００８】
また、インデックス数を検索コストが最小となるように動的に調整することにより検索システム性能の向上を図ることができる検索システムがある。また、開発環境でのＳＱＬ文による検索所要時間をもとに、ハードウェア性能等が異なった環境でのＳＱＬ文によるデータベースの検索所要時間を予測する技術がある。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００７−１５６７３９号公報
【特許文献２】特開２００８−１５８６８５号公報
【特許文献３】特開２００６−３５０７７０号公報
【特許文献４】特開２０１１−１１３２０５号公報
【特許文献５】特開２００７−１７２５１６号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、ＲＤＢとＤＳＥの検索時間を推定し、検索が速い方を選択して検索を行うドキュメント検索装置には、検索時間の推定が正しくないと、検索が速い方を適切に選択することができないという問題がある。
【００１１】
本発明は、１つの側面では、検索方法を適切に選択することを目的とする。
【課題を解決するための手段】
【００１２】
１つの態様では、検索手段選択プログラムは、第１のデータベースと第２のデータベースのいずれかを検索クエリの内容に応じて選択する。ここで、第１のデータベースは、キーと値の組で表されるデータ群をリレーショナルデータベースを用いて記憶する。また、第２のデータベースは、キーと値の組で表されるデータ群を該データ群のデータベースを用いて記憶する。そして、検索手段選択プログラムは、第１のデータベースの検索クエリに対する検索性能を示す第１の指標をデータ群に関するキー毎の統計情報に基づいて生成する。また、検索手段選択プログラムは、第２のデータベースの検索クエリに対する検索性能を示す第２の指標をデータ群に関するキー毎の統計情報に基づいて生成する。そして、検索手段選択プログラムは、第１の指標と第２の指標に基づき、検索クエリに対し、第１のデータベースまたは第２のデータベースのいずれかを選択する。
【発明の効果】
【００１３】
１つの側面では、検索方法を適切に選択することができる。
【図面の簡単な説明】
【００１４】
【図１】図１は、実施例に係るＲＤＢによるＫＶデータの記憶方法を説明するための図である。
【図２】図２は、実施例に係るドキュメント検索装置の機能構成を示す図である。
【図３】図３は、統計情報テーブルに保存される情報を示す図である。
【図４】図４は、検索クエリの一例を示す図である。
【図５】図５は、ＲＤＢとＤＳＥの使い分けを説明するための図である。
【図６】図６は、ＫＶデータの一例を示す図である。
【図７】図７は、推定エンジンの機能構成を示す図である。
【図８】図８は、推定エンジンによる処理のフローを示すフローチャートである。
【図９】図９は、ＲＤＢコスト算出処理のフローを示すフローチャートである。
【図１０】図１０は、ＤＳＥコスト算出処理のフローを示すフローチャートである。
【図１１】図１１は、サンプリング部によるサンプリング処理のフローを示すフローチャートである。
【図１２】図１２は、更新部による更新処理のフローを示すフローチャートである。
【図１３】図１３は、実施例に係るドキュメント検索プログラムを実行するコンピュータのハードウェア構成を示す図である。
【図１４】図１４は、ＲＤＢとＤＳＥの検索時間を示す図である。
【発明を実施するための形態】
【００１５】
以下に、本願の開示する検索手段選択プログラム、検索手段選択方法及び検索手段選択装置の実施例を図面に基づいて詳細に説明する。なお、この実施例は開示の技術を限定するものではない。
【実施例】
【００１６】
まず、実施例に係るＲＤＢによるＫＶデータの記憶方法について説明する。ここで、ＫＶデータは、ＫＶデータ群である場合を含む。以下の説明では、「データ」という用語は「データ群」を含めて用いられる。図１は、実施例に係るＲＤＢによるＫＶデータの記憶方法を説明するための図である。図１に示すように、実施例に係るＲＤＢは、キーと値と帳票ＩＤとを１つのタプルとして記憶する。帳票ＩＤは、帳票を識別する識別子である。帳票は、帳票ＩＤと対応付けられて別に記憶される。したがって、実施例に係るドキュメント検索装置は、検索クエリに対して帳票ＩＤを検索することによって、対応する帳票を検索することができる。
【００１７】
図１において、例えば、帳票ＩＤが「１」である帳票には、ＫＶとして「商品−蛍光灯」、「日付−２０１５１１３０」が含まれている。また、帳票ＩＤが「１３」である帳票には、ＫＶとして「説明−１１月初めに発表された新製品の蛍光灯です。」が含まれている。
【００１８】
図１に示すように、実施例に係るＲＤＢは、全てのキーを一つの列で記憶し、全ての値を１つの列で記憶する。また、一般のＲＤＢは、ヒストグラム、頻出値と出現確率等の統計情報を列毎に算出する。したがって、一般のＲＤＢが算出する統計情報は、全てのキーに関する統計情報であり、ドキュメント検索のようにＫＶに基づいて検索を行う場合には、検索時間の推定のために用いることはできない。
【００１９】
そこで、実施例に係るドキュメント検索装置は、キー毎に統計情報を収集し、キー毎に収集した統計情報を検索時間の推定に用いる。なお、全てのキーと値をそれぞれ一つの列で記憶する代わりにキー毎にキーと値をそれぞれ一つの列で記憶する方法は、キーの数が固定でないため、用いることができない。
【００２０】
次に、実施例に係るドキュメント検索装置の機能構成について説明する。図２は、実施例に係るドキュメント検索装置の機能構成を示す図である。図２に示すように、実施例に係るドキュメント検索装置１は、ＲＤＢ記憶部２と、ＤＳＥ記憶部３と、クエリ解析部４と、推定エンジン５と、ＲＤＢ検索部６と、ＤＳＥ検索部７と、サンプリング部８と、更新部９とを有する。
【００２１】
ＲＤＢ記憶部２は、ＲＤＢが検索するＫＶデータ及びＲＤＢが検索に用いる情報を記憶する。ＲＤＢ記憶部２は、テーブル２１と、Ｂ木インデックス２２と、転置インデックス２３と、統計情報テーブル２４とを記憶する。
【００２２】
テーブル２１は、例えば図１に示したように、ＫＶと帳票を識別する識別子を対応づける。Ｂ木インデックス２２は、テーブル２１を検索する際に用いられるインデックスであり、前方一致検索で用いられる。転置インデックス２３は、テーブル２１を検索する際に用いられるインデックスであり、中間一致検索で用いられる。
【００２３】
統計情報テーブル２４には、テーブル２１に保存されたＫＶデータに関する統計情報が保存される。図３は、統計情報テーブル２４に保存される情報を示す図である。図３（ａ）はキー毎の値の統計情報を示し、図３（ｂ）は、キー毎の単語の統計情報を示し、図３（ｃ）は、帳票に関する統計情報を示す。
【００２４】
図３（ａ）に示すように、キー毎の値の統計情報には、値種類数、出現回数、値＃１〜値＃ｎ、ヒストグラムデータが含まれる。値種類数は、キーが取り得る値の数であり、例えばｋである。ここで、ｋは正の整数である。出現回数は、キーがテーブル２１に出現した回数であり、例えばｍである。ここで、ｍは正の整数である。
【００２５】
値＃１〜値＃ｎは、キーが取り得る値のうち頻度が最も高いものからｎ個の値である。値＃１〜値＃ｎには、出現確率ｐ＃１〜ｐ＃ｎがそれぞれ対応付けられる。ヒストグラムデータは、キーの値に関するヒストグラムのデータである。
【００２６】
図３（ｂ）に示すように、キー毎の単語の統計情報には、単語種類数、出現回数、単語＃１〜単語＃ｎ、ヒストグラムデータが含まれる。単語種類数は、キー内の単語の種類の数であり、例えばｒである。ここでｒは正の整数である。出現回数は、キーがテーブル２１に出現した回数であり、例えばｓである。ここで、ｓは正の整数である。
【００２７】
単語＃１〜単語＃ｎは、キー内の単語のうち頻度が最も高いものからｎ個の値である。単語＃１〜単語＃ｎには、出現確率ｑ＃１〜ｑ＃ｎがそれぞれ対応付けられる。ヒストグラムデータは、キー内の単語に関するヒストグラムのデータである。なお、単語の代わりにグラム（ｇｒａｍ）でもよい。ここで、グラムとは、文字数が一定の文字列である。
【００２８】
図３（ｃ）に示すように、帳票に関する統計情報には、ドキュメント数とキー種類数が含まれる。ドキュメント数は、テーブル２１に情報が登録されている帳票の数であり、例えばｕである。ここでｕは正の整数である。キー種類数は、全帳票に含まれるキーの種類の数であり、例えばｖである。ここでｖは正の整数である。
【００２９】
図２に戻って、ＤＳＥ記憶部３は、ＤＳＥが検索するＫＶデータ、ＤＳＥが検索に用いる情報を記憶する。ＤＳＥ記憶部３は、転置インデックス３１を記憶する。ＤＳＥは、転置インデックス３１を用いて検索を行う。
【００３０】
クエリ解析部４は、ユーザが入力した検索クエリを解析し、誤りのチェック等を行った後、推定エンジン５に渡す。図４は、検索クエリの一例を示す図である。図４の検索クエリは、「２０１５／１０／０１〜２０１５／１１／３０の期間の帳票からシャンデリア又は蛍光灯について記述された帳票のＩＤを日付でソートして最大２０個とってくる」ことを指定する。
【００３１】
推定エンジン５は、統計情報テーブル２４を参照してＲＤＢとＤＳＥの検索時間を推定し、検索が速い方を選択する。図５は、ＲＤＢとＤＳＥの使い分けを説明するための図である。図５の横軸は、検索クエリに含まれるキーの数であり、縦軸は、検索クエリに含まれるキーについて中間一致検索が行われる割合である。図５に示すように、推定エンジン５は、キーの数が多い場合、あるいは、中間一致検索の割合が多い場合にＤＳＥを選択し、キーの数が少ない場合、あるいは、中間一致検索の割合が少ない場合にＲＤＢを選択する。
【００３２】
推定エンジン５は、ＲＤＢを選択した場合には、検索クエリをヒントつきＲＤＢのクエリに変換し、ＤＳＥを選択した場合には、検索クエリをＤＳＥのクエリに変換する。ここで、ヒントとは、キー毎に前方一致検索を行うか中間一致検索を行うかと、キー毎の検索結果のマージ方法を指定する情報である。なお、推定エンジン５の詳細については後述する。
【００３３】
ＲＤＢ検索部６は、ＲＤＢ記憶部２を用いて帳票ＩＤの検索を行う。ＲＤＢ検索部６は、推定エンジン５によりＲＤＢのクエリに付加されたヒントを用いて帳票ＩＤの検索を行う。実施例では、ＲＤＢ検索部６とＲＤＢ記憶部２を合わせてＲＤＢと呼んでいる。
【００３４】
ＤＳＥ検索部７は、ＤＳＥ記憶部３を用いて帳票ＩＤの検索を行う。実施例では、ＤＳＥ検索部７とＤＳＥ記憶部３を合わせてＤＳＥと呼んでいる。
【００３５】
サンプリング部８は、テーブル２１に登録されたＫＶのうち、出現頻度が閾値以上のキーについて、ヒストグラムデータを作成するとともに、出現頻度が高い値の出現確率を算出し、統計情報テーブル２４に登録する。サンプリング部８は、例えば、一定時間間隔で処理を行う。
【００３６】
更新部９は、帳票が追加されると、統計情報テーブル２４のドキュメント数に１を加える。また、更新部９は、追加された帳票の内容を表すＫＶデータに帳票ＩＤを追加してＲＤＢ記憶部２とＤＳＥ記憶部３に追加する。図６は、ＫＶデータの一例を示す図である。図６は、日付が「２０１５／１１／３０」であり、商品名が[蛍光灯]であり、単価が「３０００」であり、数が「２０」であり、製造者が「ＡＢＣＤ  Ｉｎｃ．」であり、説明が「１１月初めに発表された新製品の蛍光灯です。」である帳票を示す。また、更新部９は、各キーについて、統計情報テーブル２４の出現回数を更新する。
【００３７】
次に、推定エンジン５の機能構成について説明する。図７は、推定エンジン５の機能構成を示す図である。図７に示すように、推定エンジン５は、取得部５１と、ＲＤＢコスト算出部５２と、ＤＳＥコスト算出部５３と、判定部５４と、ＲＤＢ指示部５５と、ＤＳＥ指示部５６と、応答部５７とを有する。
【００３８】
取得部５１は、クエリ解析部４から検索クエリを取得し、取得した検索クエリをＲＤＢコスト算出部５２とＤＳＥコスト算出部５３に渡す。
【００３９】
ＲＤＢコスト算出部５２は、取得部５１から渡された検索クエリについてＲＤＢによる検索コストを算出する。ここで、検索コストとは、検索時間の推定値である。ＲＤＢコスト算出部５２は、統計情報テーブル２４を参照してキー毎にインデックスを用いた検索コストを算出し、キー毎の検索コストとキー毎の検索結果のマージコストとに基づいてＲＤＢによる検索コストを算出する。
【００４０】
キー毎の検索コストは、前方一致検索の場合には、
Ｏ(ｌｏｇ(キー種類数)＋ｌｏｇ(キーの値の種類数))＊取得件数
である。また、キー毎の検索コストは、中間一致検索の場合には、
Ｏ(ｌｏｇ(キー種類数)＋ｌｏｇ(キー内の単語の種類数))＊取得件数
である。
【００４１】
ここで、Ｏはオーダを表し、具体的な検索コストの値は所定の係数を用いて計算される。また、取得件数は、検索により取得される帳票の件数の推定値であり、検索条件がキーの値指定又はキーの単語指定である場合には、値又は単語に対応する出現確率をドキュメント数に乗じた値である。また、検索条件がキーの範囲指定である場合には、取得件数は、ヒストグラムデータから範囲に対応して算出される出現確率をドキュメント数に乗じた値である。
【００４２】
また、ＲＤＢコスト算出部５２は、以下の３つの中から最小なものを一つ選択してマージコストを算出する。
ネステッドループ結合＝コスト：Ｏ(Ｍ＊Ｎ)
マージソート結合＝コスト：Ｏ(ＭｌｏｇＭ＋ＮｌｏｇＮ)
ハッシュ結合＝コスト：Ｏ(Ｍ＋Ｎ)
上記のコストは、キーが２つの場合であり、Ｍ、Ｎは、各キーで取得される件数の推定値である。また、「＊」は乗算を表す。
【００４３】
そして、ＲＤＢコスト算出部５２は、以下の式により検索コストを算出する。
（キーの種類数）＊(キー毎の検索コストの和）＋
（ＡＮＤ，ＯＲの数)＊（マージコスト）
【００４４】
ＤＳＥコスト算出部５３は、取得部５１から渡された検索クエリについてＤＳＥによる検索コストを算出する。ＤＳＥコスト算出部５３は、統計情報テーブル２４を参照してキー毎にインデックスを用いた検索コストを算出し、キー毎の検索コストとキー毎の検索結果のマージコストとに基づいてＤＳＥによる検索コストを算出する。
【００４５】
キー毎の検索コストは、
Ｏ(ｌｏｇ(キー種類数)＋ｌｏｇ(ドキュメント数)＋ｌｏｇ(キー内の単語の種類数))＊取得件数
である。
【００４６】
また、マージコストは、ＡＮＤ結合の場合にはほぼ０であり、ＯＲ結合の場合には、キー毎の検索コストの和に比例する。
【００４７】
そして、ＤＳＥコスト算出部５３は、以下の式により検索コストを算出する。
（キーの種類数）＊(キー毎の検索コストの和）＋
（ＯＲの数)＊（マージコスト）
【００４８】
判定部５４は、ＲＤＢコスト算出部５２とＤＳＥコスト算出部５３が算出した検索コストを比較し、ＲＤＢとＤＳＥのうち検索コストが低い方を選択する。ＲＤＢ指示部５５は、判定部５４がＲＤＢを選択した場合に、検索クエリをヒントつきＲＤＢのクエリに変換し、ＲＤＢに対してヒントつきで検索を指示する。判定部５４がＲＤＢに対してヒントつきで検索を指示することで、ＲＤＢはキー毎の統計情報に基づいて効率の良い検索を行うことができる。
【００４９】
ＤＳＥ指示部５６は、判定部５４がＤＳＥを選択した場合に、検索クエリをＤＳＥのクエリに変換し、ＤＳＥに対して検索を指示する。応答部５７は、ＲＤＢ又はＤＳＥによる検索結果をユーザが使用するクライアントに送信する。
【００５０】
次に、推定エンジン５による処理のフローについて説明する。図８は、推定エンジン５による処理のフローを示すフローチャートである。図８に示すように、推定エンジン５は、クエリ解析部４から検索クエリを受け取る（ステップＳ１）。
【００５１】
そして、推定エンジン５は、ＲＤＢによる検索コストを算出するＲＤＢコスト算出処理を行い（ステップＳ２）、ＤＳＥによる検索コストを算出するＤＳＥコスト算出処理を行う（ステップＳ３）。なお、推定エンジン５は、ＤＳＥコスト算出処理を先に行って、ＲＤＢコスト算出処理を後に行ってもよい。
【００５２】
そして、推定エンジン５は、ＲＤＢの検索コストの方が低いか否かを判定し（ステップＳ４）、ＲＤＢの検索コストの方が低い場合には、キー毎の検索やマージが、コスト計算に沿うようにヒントつきのＳＱＬ文を組み立てる（ステップＳ５）。そして、推定エンジン５は、ＲＤＢにＳＱＬを実行させ（ステップＳ６）、ユーザが使用するクライアント装置に結果を送信する（ステップＳ８）。
【００５３】
一方、ＲＤＢの検索コストの方が低くない場合には、推定エンジン５は、ＤＳＥのクエリに検索クエリを変換し、ＤＳＥに実行させる（ステップＳ７）。そして、推定エンジン５は、ユーザが使用するクライアント装置に結果を送信する（ステップＳ８）。
【００５４】
図９は、ＲＤＢコスト算出処理のフローを示すフローチャートである。図９に示すように、ＲＤＢコスト算出部５２は、検索クエリ内で未処理のキーがあるか否かを判定し（ステップＳ１１）、未処理のキーがある場合には、未処理のキーを任意に一つ選択する（ステップＳ１２）。
【００５５】
そして、ＲＤＢコスト算出部５２は、選択したキーに関する検索が前方一致検索であるか否かを判定し（ステップＳ１３）、前方一致検索である場合には、統計情報テーブル２４からキーに関連した値の統計情報を取り出す（ステップＳ１４）。そして、ＲＤＢコスト算出部５２は、統計情報からＢ木利用時のコストを計算し、コスト計算結果に加算する（ステップＳ１５）。そして、ＲＤＢコスト算出部５２は、ステップＳ１１に戻る。
【００５６】
一方、選択したキーに関する検索が前方一致検索でない場合には、ＲＤＢコスト算出部５２は、統計情報テーブル２４からキーに関連した単語の統計情報を取り出す（ステップＳ１６）。そして、ＲＤＢコスト算出部５２は、統計情報から転置インデックス利用時のコストを計算し、コスト計算結果に加算する（ステップＳ１７）。そして、ＲＤＢコスト算出部５２は、ステップＳ１１に戻る。
【００５７】
また、ステップＳ１１において未処理のキーがない場合には、ＲＤＢコスト算出部５２は、マージコストを算出し、(ＡＮＤ，ＯＲの数)を乗じたマージコストをコスト計算結果に加算する（ステップＳ１８）。
【００５８】
図１０は、ＤＳＥコスト算出処理のフローを示すフローチャートである。図１０に示すように、ＤＳＥコスト算出部５３は、検索クエリ内で未処理のキーがあるか否かを判定し（ステップＳ２１）、未処理のキーがある場合には、未処理のキーを任意に一つ選択する（ステップＳ２２）。
【００５９】
そして、ＤＳＥコスト算出部５３は、統計情報テーブル２４からキーに関連した単語の統計情報を取り出し（ステップＳ２３）、統計情報からコストを計算し、コスト計算結果に加算する（ステップＳ２４）。そして、ＤＳＥコスト算出部５３は、ステップＳ２１に戻る。
【００６０】
また、ステップＳ２１において未処理のキーがない場合には、ＤＳＥコスト算出部５３は、マージコストを算出し、(ＯＲの数)を乗じたマージコストをコスト計算結果に加算する（ステップＳ２５）。
【００６１】
このように、推定エンジン５がＲＤＢとＤＳＥの検索コストを計算し、ＲＤＢとＤＳＥのうち検索コストが低い方に検索を行わせることで、ドキュメント検索装置１は検索クエリの処理時間を短縮することができる。
【００６２】
次に、サンプリング部８によるサンプリング処理のフローについて説明する。図１１は、サンプリング部８によるサンプリング処理のフローを示すフローチャートである。図１１に示すように、サンプリング部８は、全てのキーについて処理が完了したか否かを判定し（ステップＳ３１）、全てのキーについて処理が完了した場合には、サンプリング処理を終了する。
【００６３】
一方、未処理のキーがある場合には、サンプリング部８は、未処理のキーを任意に一つ選択し（ステップＳ３２）、選んだキーがテーブル２１内に閾値以上存在するか否かを判定する（ステップＳ３３）。そして、選んだキーがテーブル２１内に閾値以上に存在しない場合には、サンプリング部８は、ステップＳ３１に戻る。
【００６４】
一方、選んだキーがテーブル２１内に閾値以上存在する場合には、サンプリング部８は、選択したキーに対応する値を指定個数取り出す（ステップＳ３４）。そして、サンプリング部８は、選択したキーに関する検索が前方一致検索用のサンプリング処理であるか否かを判定し（ステップＳ３５）、前方一致検索用のサンプリング処理である場合には、取り出した値の出現確率とヒストグラムデータを作成し、統計情報テーブル２４に保存する（ステップＳ３６）。そして、サンプリング部８は、ステップＳ３１に戻る。
【００６５】
一方、選択したキーに関する検索が前方一致検索用のサンプリング処理でない場合には、サンプリング部８は、取り出した各値を単語単位に分解し（ステップＳ３７）、分解した単位の出現確率とヒストグラムデータを作成し、統計情報テーブル２４に保存する（ステップＳ３８）。そして、サンプリング部８は、ステップＳ３１に戻る。なお、サンプリング部８は、ステップＳ３６の処理とステップＳ３７及びステップＳ３８の処理とを並列に行ってもよい。
【００６６】
このように、サンプリング部８がキー毎に指定個数の値の出現確率とヒストグラムデータ、又は、単語又はグラム単位の出現確率とヒストグラムデータを作成して統計情報テーブル２４に保存する。したがって、推定エンジン５は統計情報テーブル２４の情報を使って検索コストを算出することができる。
【００６７】
次に、更新部９による更新処理のフローについて説明する。図１２は、更新部９による更新処理のフローを示すフローチャートである。図１２に示すように、更新部９は、統計情報テーブル２４のドキュメント数をカウントアップし（ステップＳ４１）、全てのキーについて処理が完了したか否かを判定する（ステップＳ４２）。そして、全てのキーについて処理が完了した場合には、更新処理を終了する。
【００６８】
一方、未処理のキーがある場合には、更新部９は、未処理のキーを任意に一つ選択し（ステップＳ４３）、選んだキーが新規のものか否かを判定する（ステップＳ４４）。そして、更新部９は、新規のものでない場合には、ステップＳ４７に進み、新規のものである場合には、統計情報テーブル２４のキー種類数をカウントアップし（ステップＳ４５）、選んだキーの出現回数を０で初期化する（ステップＳ４６）。
【００６９】
そして、更新部９は、選んだキーの出現回数をカウントアップし（ステップＳ４７）、ステップＳ４２に戻る。
【００７０】
このように、更新部９が統計情報テーブル２４のキー種類数とキーの出現回数を更新することで、推定エンジン５は統計情報テーブル２４の情報を使って検索コストを算出することができる。
【００７１】
上述してきたように、実施例では、ＲＤＢコスト算出部５２が、統計情報テーブル２４を参照してキー毎にインデックスを用いた検索コストを算出し、キー毎の検索コストとキー毎の検索結果のマージコストとに基づいてＲＤＢによる検索コストを算出する。また、ＤＳＥコスト算出部５３が、統計情報テーブル２４を参照してキー毎にインデックスを用いた検索コストを算出し、キー毎の検索コストとキー毎の検索結果のマージコストとに基づいてＤＳＥによる検索コストを算出する。そして、判定部５４が、ＲＤＢコスト算出部５２とＤＳＥコスト算出部５３が算出した検索コストを比較し、ＲＤＢとＤＳＥのうち検索コストが低い方を予測して選択する。したがって、推定エンジン５は、ＲＤＢとＤＳＥから検索時間が短い方を適切に選択することできる。
【００７２】
また、実施例では、ＲＤＢコスト算出部５２は、キーに関する検索が前方一致検索であるか中間一致検索であるかを判定し、判定結果に基づいてキー毎の検索コストを算出する。したがって、推定エンジン５は、実際の検索で使用するインデックスに基づいて検索コストを算出することができる。
【００７３】
また、実施例では、ＲＤＢ指示部５５は、ＲＤＢに対してヒントつきで検索を指示するので、ＲＤＢはキー毎の統計情報に基づいた効率の良い検索を行うことができる。
【００７４】
また、実施例では、統計情報テーブル２４には、キー種類数、キーの値の種類数、キーの値に関するヒストグラムデータ、キー内の単語又はグラムの種類数、キー内の単語又はグラムに関するヒストグラムデータが記録される。したがって、推定エンジン５は、正確に検索コストを算出することができる。
【００７５】
なお、実施例では、ドキュメント検索装置１について説明したが、ドキュメント検索装置１が有する構成をソフトウェアによって実現することで、同様の機能を有するドキュメント検索プログラムを得ることができる。そこで、ドキュメント検索プログラムを実行するコンピュータについて説明する。
【００７６】
図１３は、実施例に係るドキュメント検索プログラムを実行するコンピュータのハードウェア構成を示す図である。図１３に示すように、コンピュータ６０は、メインメモリ６１と、ＣＰＵ６２と、ＬＡＮ（Local  Area  Network）インタフェース６３と、ＨＤＤ（Hard  Disk  Drive）６４とを有する。また、コンピュータ６０は、スーパーＩＯ（Input  Output）６５と、ＤＶＩ（Digital  Visual  Interface）６６と、ＯＤＤ（Optical  Disk  Drive）６７とを有する。
【００７７】
メインメモリ６１は、プログラムやプログラムの実行途中結果などを記憶するメモリである。ＣＰＵ６２は、メインメモリ６１からプログラムを読み出して実行する中央処理装置である。ＣＰＵ６２は、メモリコントローラを有するチップセットを含む。
【００７８】
ＬＡＮインタフェース６３は、コンピュータ６０をＬＡＮ経由で他のコンピュータに接続するためのインタフェースである。ＨＤＤ６４は、プログラムやデータを格納するディスク装置であり、スーパーＩＯ６５は、マウスやキーボードなどの入力装置を接続するためのインタフェースである。ＤＶＩ６６は、液晶表示装置を接続するインタフェースであり、ＯＤＤ６７は、ＤＶＤの読み書きを行う装置である。
【００７９】
ＬＡＮインタフェース６３は、ＰＣＩエクスプレス（ＰＣＩｅ）によりＣＰＵ６２に接続され、ＨＤＤ６４及びＯＤＤ６７は、ＳＡＴＡ（Serial  Advanced  Technology  Attachment）によりＣＰＵ６２に接続される。スーパーＩＯ６５は、ＬＰＣ（Low  Pin  Count）によりＣＰＵ６２に接続される。
【００８０】
そして、コンピュータ６０において実行されるドキュメント検索プログラムは、ＤＶＤに記憶され、ＯＤＤ６７によってＤＶＤから読み出されてコンピュータ６０にインストールされる。あるいは、ドキュメント検索プログラムは、ＬＡＮインタフェース６３を介して接続された他のコンピュータシステムのデータベースなどに記憶され、これらのデータベースから読み出されてコンピュータ６０にインストールされる。そして、インストールされたドキュメント検索プログラムは、ＨＤＤ６４に記憶され、メインメモリ６１に読み出されてＣＰＵ６２によって実行される。
【００８１】
また、実施例では、帳票を検索する場合について説明したが、本発明はこれに限定されるものではなく、任意のドキュメントを検索する場合にも同様に適用することができる。
【符号の説明】
【００８２】
１    ドキュメント検索装置
２    ＲＤＢ記憶部
３    ＤＳＥ記憶部
４    クエリ解析部
５    推定エンジン
６    ＲＤＢ検索部
７    ＤＳＥ検索部
８    サンプリング部
９    更新部
２１    テーブル
２２    Ｂ木インデックス
２３    転置インデックス
２４    統計情報テーブル
３１    転置インデックス
５１    取得部
５２    ＲＤＢコスト算出部
５３    ＤＳＥコスト算出部
５４    判定部
５５    ＲＤＢ指示部
５６    ＤＳＥ指示部
５７    応答部
６０    コンピュータ
６１    メインメモリ
６２    ＣＰＵ
６３    ＬＡＮインタフェース
６４    ＨＤＤ
６５    スーパーＩＯ
６６    ＤＶＩ
６７    ＯＤＤ
【図１】
2018060379.tif 000003
【図２】
2018060379.tif 000004
【図３】
2018060379.tif 000005
【図４】
2018060379.tif 000006
【図５】
2018060379.tif 000007
【図６】
2018060379.tif 000008
【図７】
2018060379.tif 000009
【図８】
2018060379.tif 000010
【図９】
2018060379.tif 000011
【図１０】
2018060379.tif 000012
【図１１】
2018060379.tif 000013
【図１２】
2018060379.tif 000014
【図１３】
2018060379.tif 000015
【図１４】
2018060379.tif 000016