(57)【特許請求の範囲】
【請求項１】
データベースのデータ検索装置であって、
属性と属性値とを含む検索条件を受け付ける検索条件入力手段と、
前記検索条件に対応する、前記データベースから取得した属性のインデックスを保持手段に保持させる保持制御手段と、
前記属性値それぞれについて、前記検索条件として受け付けられ検索に利用される回数から前記属性のインデックスの再利用性としてヒット率を解析する解析手段と、
前記ヒット率が高い属性のインデックスを優先的に前記保持手段から利用する検索実行計画を生成する生成手段と、を備えることを特徴とするデータ検索装置。
【請求項２】
前記解析手段は、インデックス中での前記属性値の格納位置を取得して格納位置変化度を解析することを特徴とする請求項１に記載のデータ検索装置。
【請求項３】
前記解析手段は、前記属性値の出現頻度を求め、閾値を参照して前記出現頻度を解析することを特徴とする請求項１に記載のデータ検索装置。
【請求項４】
前記各属性における前記属性値の出現頻度の最大値を求めることを特徴とする請求項３に記載のデータ検索装置。
【請求項５】
前記属性における前記属性値の出現頻度の平均値を求めることを特徴とする請求項３に記載のデータ検索装置。
【請求項６】
前記検索条件入力手段から入力される検索条件が、バインド変数であることを特徴とする請求項１に記載のデータ検索装置。
【請求項７】
前記検索条件入力手段から入力される検索条件は、動的なバインド変数を用いた検索条件と静的な変数を用いた検索条件とが混在する場合、
前記保持制御手段は、前記静的な変数の検索条件に対応する属性のインデックスを前記保持手段に優先的に保持させることを特徴とする請求項２に記載のデータ検索装置。
【請求項８】
データベースのデータ検索方法であって、
属性と属性値とを含む検索条件を受け付ける検索条件入力工程と、
前記検索条件に対応する、前記データベースから取得した属性のインデックスを保持手段に保持させる保持制御工程と、
前記属性値それぞれについて、前記検索条件として受け付けられ検索に利用される回数から前記属性のインデックスの再利用性としてヒット率を解析する解析工程と、
前記ヒット率が高い属性のインデックスを優先的に前記保持手段から利用する検索実行計画を生成する生成手段と、を備えることを特徴とするデータ検索方法。
【請求項９】
データベースのデータ検索方法をコンピュータに実行させるプログラムであって、
属性と属性値とを含む検索条件を受け付ける検索条件入力手順と、
前記検索条件に対応する、前記データベースから取得した属性のインデックスを保持手段に保持させる保持制御手順と、
前記属性値それぞれについて、前記検索条件として受け付けられ検索に利用される回数から前記属性のインデックスの再利用性としてヒット率を解析する解析手順と、前記ヒット率が高い属性のインデックスを優先的に前記保持手段から利用する検索実行計画を生成する生成手順と、をコンピュータに実行させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータベースエンジンを用いた高速な検索処理を行うデータ検索装置及び方法に関する。
【背景技術】
【０００２】
近年のフラッシュメモリ容量の増加に伴い、デジタルカメラやフォトフレーム、インクジェット複合機等、計算資源に制約がある省資源機器においても、数万枚から数十万枚のデータを保存できる記憶容量を持つようになっている。また、認識技術等の向上によって、人名や地名をはじめとした多様な属性値が付与可能となっており、これらの属性値を用いて、多種多量のデータ検索を高速に行う必要性が、省資源機器においても高まっている。写真データの場合、日付や撮影パラメータ、位置情報であるＧＰＳ（Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ）座標などの属性値が撮影時に付与されるほか、お気に入り度合いや印刷指定等の属性値が再生時に付与される。これらの属性値を格納する枠組みとしては、Ｅｘｉｆ（Ｅｘｃｈａｎｇｅａｂｌｅ  ｉｍａｇｅ  ｆｉｌｅ  ｆｏｒｍａｔ）が代表的である。ユーザ所望のデータを検索する場合には、これらの属性値を用いることが有益である。しかしながら、データ、及び属性値が多種多量である場合に、各データに対して全走査を行って検索処理を行うことは計算量が膨大となり、応答時間の遅延を招いてしまう。
【０００３】
そこで検索を高速に行えるようにするため、索引情報を納めたインデックスをあらかじめ構築しておき、検索時にインデックスを利用することで応答時間を短縮する手法が一般的である。もし複数のインデックスが利用可能な場合には、所定のインデックスが選択され、使用されることになる。この時検索条件に応じて、どのインデックスを優先的に用いるかということが応答速度向上のために重要となる。例えば、インデックスの選択は件数が少なく絞込み効果が高いカラムを優先的に用いる等、インデックスを保持しているキャッシュのヒット率を考慮しないルールを用いるのが一般的である。
【０００４】
しかしながら検索を繰り返し実行する際、データベースファイルからのデータ読み出しが頻繁に行われ、キャッシュのヒット率が応答速度に大きく影響する。これは主記憶であるＲＡＭに比較して、データベースファイルが置かれる外部記憶部の転送速度が遅く、頻繁なデータ読み出しが装置全体の演算性能を低下させるためである。一般的には、この問題を解決するためにＲＡＭや主記憶部にキャッシュ機構等の中間層を設けて読み書き頻度を抑制するが、省資源機器では計算資源の制約からキャッシュ機構が小容量であり、特にその影響度が大きくなる。例えばデジタルカメラ等においては、ＰＣとカメラの間でメタデータを同期・更新するため、大量件数のレコード検索・更新が発生し、キャッシュのヒット率が落ち、データベースファイルからのデータ読み出しが頻発しがちである。
【０００５】
従来、検索インデックス選択方法に着眼した検索装置としては、例えば特許文献１のように、事前にデータ分布等の分析結果を用いてインデックスを選択する手法や、検索コストが低くなるようデータベースファイルの再構築を行う手法が存在する。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平０７−３１１６９９公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、これらの先行技術は資源の潤沢なＰＣやサーバでの動作を前提としている。データ分布の事前解析やデータベースファイルの再構築は、計算資源が限定される省資源機器には適さない。  そのため、省資源機器ではデータの分布の如何に関わらず、指示された検索条件に応じたインデックス選択制御を計算資源に頼らずに行わざるを得ない。待機時間等に解析処理や再構築処理を行うことも考えられるが、電力や計算力に限りがある場合が多い。
【０００８】
本発明は上記の問題に鑑みてなされたものであり、データ分布の事前解析処理や、データベースファイルの再構築処理が困難な省資源機器においても応答性能を向上させ、検索機能の利便性を高めることを目的とする。具体的には検索条件の履歴を解析し、キャッシュのヒット率が高くなるインデックスを選択することによって実現する。
【課題を解決するための手段】
【０００９】
本発明に係るデータベースのデータ検索装置は、属性と属性値とを含む検索条件を受け付ける検索条件入力手段と、前記検索条件に対応する、前記データベースから取得した属性のインデックスを保持手段に保持させる保持制御手段と、前記属性値それぞれについて、前記検索条件として受け付けられ検索に利用される回数から前記属性のインデックスの再利用性としてヒット率を解析する解析手段と、前記ヒット率が高い属性のインデックスを優先的に前記保持手段から利用する検索実行計画を生成する生成手段。
【発明の効果】
【００１０】
本発明に依れば、検索条件を解析してキャッシュのヒット率の高い検索処理を実行することにより、検索処理の応答性を改善でき、ユーザの利便性が高まる。
【図面の簡単な説明】
【００１１】
【図１】本実施形態によるデータ検索装置の制御に係る主要部の構成を示す図である
【図２】本実施形態の効果が表れる例を端的に示す図である
【図３】本実施形態で用いるフラッシュメモリカードと、データ例としてＥｘｉｆの属性値の代表例と、インデックスＢ−Ｔｒｅｅインデックスの一例を示す図である
【図４】本実施形態によるデータ検索装置の機能ブロック図である
【図５】本実施形態で用いる検索対象データの例と、検索対象データのインデックスの例と、検索履歴の例を示す図である
【図６】本実施形態で用いる検索指示を記述したＳＱＬ文の例と、検索処理を実行したときの画面を示す図である
【図７】第１の実施形態の処理の流れを示すフローチャートである
【図８】同一属性値出現頻度を用いた検索条件履歴解析処理の流れを示すフローチャートである
【図９】格納位置変化度を用いた検索条件履歴解析処理の流れを示すフローチャートである
【図１０】第２の実施形態の効果が表れる例を端的に示す図である
【図１１】第２の実施形態の処理の流れを示すフローチャートである
【発明を実施するための形態】
【００１２】
以下、本発明を適用した好適な実施形態を、添付図面を参照しながら詳細に説明する。
【００１３】
（第１の実施形態）基本動作
図１は本実施形態を適用する装置を示す構成図である。本実施形態の装置全体１０００を図１であらわしている。マイクロプロセッサＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１００１は，情報処理のための演算，論理判断等を行う。システムバス１００９を介して，それらのバスに接続された各構成要素を制御する。読出し専用の固定メモリＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１００２は，本実施形態で実行される処理プログラム等の制御プログラムコードを記憶する。書き込み可能なＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１００３は，各構成要素からの各種データの一時記憶に用いられる。入力部１００４には，ユーザからの指示が入力される。液晶パネル等の表示部１００８では，その表示部における画像情報の表示を表示コントローラ１００５で制御する。外部記憶部１００６では，各種データ及び画像情報が格納される。また，これらのデータを格納する記憶媒体としては，メモリカード，ＨＤＤ，ＤＶＤ−ＲＡＭなどを用いることができる。通信部１００７では，他の機器と接続することができる。
【００１４】
かかる各構成要素からなる撮影装置においては，入力部１００４からの各種の入力及び通信部１００７から供給されるネットワーク経由の各種入力に応じて作動するものである。よって，入力部１００４からの入力及び通信部１００７からの入力が供給されると，まず，インタラプト信号がＣＰＵ１００１に送られる。そして，そのＣＰＵ１００１がＲＯＭ１００２，ＲＡＭ１００３，外部記憶部１００６に記憶してある各種の制御信号を読出し，それらの制御信号に従って，各種の制御が行われる。
【００１５】
また，本実施形態に係わるプログラムを格納した記憶媒体をシステムあるいは装置に供給し，そのシステムあるいは装置が，記憶媒体に格納されたプログラムコードを読み出し実行することによっても本実施形態は達成される。
【００１６】
図２は本実施形態が効果的な状況を示した図である。日付と人名をＡＮＤ条件で結合した検索を日付の属性を固定しながら、人名の属性値を変更して繰り返し実行している。検索のストーリーとしては、例えば、ユーザがある日付の写真から、友人が写った写真を一人ずつ選びたいときなどに、日付を固定し、人名のみを切り替えた検索を行うなどである。
【００１７】
データベースエンジンは、当初は人名の属性値を優先した方が件数の絞り込み効果が高いと判断して人名インデックスを用いて実行計画を作成し、検索処理を行う（１回目、２回目）。実行計画とは、データベースエンジン内部においてどのような手順で検索処理を実行するかの計画を記述したものである。一般的には、データ分布が散在している属性に対してインデックスを用いると検索速度が向上する。日付には限度があるが、被写体となる人名の属性値は、地名に比べて散在することが考えられるため、１回目の検索では人名インデックスが選択される。
【００１８】
続いて日付が固定されていることを検知した段階（３回目）で日付インデックスの方がデータベースキャッシュの再利用性が高いと判断し、日付インデックスに切り替えた実行計画を再生成し、検索処理を行う。この結果、類似した属性値が指定されて連続検索が実行される系において、前段の検索処理で読み込んだインデックスが後段の検索で再利用される可能性が高まり、検索応答速度を高速化することができる。
【００１９】
上記に示した実施形態を実現するための構成要素と動作原理の詳細を以下に示す。
【００２０】
図３（ａ）は外部記憶部の例として、デジタルカメラ向けメモリカードの内部構成を示した図である。メモリカード３０００の内部には、写真や映像をはじめとした各種データがＤＣＦ（Ｄｅｓｉｇｎ  ｒｕｌｅ  ｆｏｒ  Ｃａｍｅｒａ  Ｆｉｌｅ  ｓｙｓｔｅｍ）に準拠した形で格納される（３００１）。また、写真や映像のデータにはデータの内容を説明する付加情報である属性値が付与されている。写真データの場合、日付や撮影パラメータ、ＧＰＳ座標などを格納する枠組みであるＥｘｉｆ（Ｅｘｃｈａｎｇｅａｂｌｅ  ｉｍａｇｅ  ｆｉｌｅ  ｆｏｒｍａｔ）が代表的な例である（３００２）。
【００２１】
図３（ｂ）に示したのはＥｘｉｆが持つ属性値の一例であり、日付、ＧＰＳ座標、地名、撮影機器メーカー、撮影機器機種名、人名等が格納されている。また、検索処理を高速に行えるようにするため、インデックス格納領域３００３に、索引情報を格納した各種インデックス（３００４〜３００７）をあらかじめ構築し、構築済みのインデックスを検索時に利用することで応答時間を短縮する手法が一般的である。インデックスはＢ−Ｔｒｅｅやハッシュ等のデータ構造を持ち、検索キーとデータを紐付けておくことで高速な検索が可能になる。インデックス格納領域３００３には、日付のインデックス３００４、ＧＰＳ座標のインデックス３００５、地名のインデックス３００６、そして人名のインデックス３００７を保持している。
【００２２】
図３（ｃ）は地名インデックス３００６が、Ｂ−Ｔｒｅｅインデックスの構造をもつ場合の図である。Ｂ−Ｔｒｅｅインデックスは階層構造を持つインデックスであり、データの挿入、検索、及び削除が容易に行える特長を持つ。インデックスレコード３００８は地名からデータファイル名へのインデックスレコードを表している。
【００２３】
図４（ａ）は本実施形態に係る外部記憶部１００６の構成図である。おもにデータ格納部４００１、インデックス格納部４００３及び検索条件履歴格納部４０１２から構成される。データ格納部４００１に格納される各データ４００２は撮影、スキャン、外部からの転送等によって生成されるデータである。インデックス格納部４００３は、後述するデータベースエンジン４００５及び検索アプリケーション４００９によって生成された各インデックス３００４〜３００７を格納するものであり、外部記憶部１００６に配置される。データ格納部４００１とデータ格納部３００１、各データ４００２と各データ３００２、インデックス格納領域３００３とインデックス格納部４００３は同じ機能を果たすものである。
【００２４】
図４（ｂ）はＲＡＭ１００３の構成を表す図である。おもにファイルキャッシュ４００４、及びデータベースキャッシュ４００８から構成される。ファイルキャッシュ４００４は、外部記憶部１００６に対するアクセス要求データをＲＡＭ１００３を経由して受け渡しするようにして、データベースエンジン４００５や検索アプリケーション４００９からの要求に対して応答速度を向上させるために配置される。
【００２５】
図４（ｃ）は本実施形態に係る機能ブロック図である。検索条件入力部４０１３は、ユーザからの検索指示を受け付ける。検索結果表示制御部４０１４は、検索条件入力部４０１３に与えられた検索条件による検索結果をユーザに提示する。データベースエンジン４００５は、データ検索装置の検索処理を高速に行うために利用される。検索アプリケーション４００９は、インデックス登録処理部４００６及びインデックス検索処理部４００７を実行し、その処理結果を得る。また検索処理や登録処理の応答速度を高速化するためデータベースキャッシュ４００８が用いられる。データベースキャッシュ４００８は検索アプリケーション４００９とデータ格納部４００１及びインデックス格納部４００３の中間にあり、一度アクセスしたデータをＲＡＭ１００３上に一定量確保しておくことにより、外部記憶部へのアクセス頻度を下げるバッファである。データ検索装置の検索処理を実行する検索アプリケーション４００９は、データ登録処理部４０１０及びデータ検索処理部４０１１から構成される。データ検索処理部４０１１は検索条件入力部４０１３から受けた検索指示によって検索処理を実行し、検索結果表示制御部４０１４に検索処理の結果を返却する処理を行う。データ登録処理部４０１０はデータが追加・削除される時に実行され、データ格納部４００１にデータを登録・削除する。また、データ登録処理部４０１０はインデックス登録処理部４００６を呼び出して検索処理の高速化のため必要な各インデックス３００４〜３００７を更新し、インデックス格納部４００３に格納する処理を行う。
【００２６】
図５（ａ）中のデータ表５００１は本実施形態に係る検索データベースの例である。各データを一意に区別するためのキーとしてＲｏｗＩＤを付与し、データベースファイル等に表形式で保存することを想定している。ＲｏｗＩＤは、データベースあるいはテーブルにおいて重複しないようにユニークに発番・付与される数値であり、一般的なデータベースエンジンで利用されている。
【００２７】
図５（ｂ）は本実施形態に係るインデックス格納部４００３に格納されたインデックスの例である。各データ４００２に付与されたＥｘｉｆデータ３００２のインデックスを、インデックス登録処理部４００６によって予め生成しておくことで検索条件に合致するデータを素早く発見し、高速に検索処理を実行できる。例えば日付インデックス３００４は、日付とＲｏｗＩＤとを結びつけたデータマップを、人名インデックス３００７は人名とＲｏｗＩＤとを結びつけたデータマップを保持している。結び付けられたＲｏｗＩＤからデータを一意に特定し、検索結果を提示することが可能である。
【００２８】
図５（ｃ）は検索条件履歴格納部４０１２に格納される検索条件履歴の例である。ユーザが指定した検索条件の履歴を参照できる。
【００２９】
図６（ａ）は本実施形態に係るユーザからの検索指示を表現したＳＱＬ（Ｓｔｒｕｃｔｕｒｅｄ  Ｑｕｅｒｙ  Ｌａｎｇｕａｇｅ）文の例である。ユーザが指定した検索条件に応じて検索条件入力部４０１３等で生成する。生成したＳＱＬ文はインデックス検索処理部４００７によって解釈・実行され、データ検索処理が行われる。なお、図６（ａ）に示した例には検索条件値を変数化するためのバインド変数「？」を指定している。このバインド変数を活用することでＳＱＬ文を繰り返し生成することなく動的に検索条件を変更できるため、検索処理を高速に行える。
【００３０】
図６（ｂ）は検索結果表示制御部４０１４によって検索結果を表示したユーザインターフェースの例である。領域６００１は検索条件表示領域である。ボックス６００２はユーザが指定した検索条件を選択するドロップダウンボックスである。また、領域６００３は検索条件に基づいて領域に検索結果をサムネイルで一覧表示する検索結果表示領域である。領域６００４は検索結果のページ数を提示する検索情報表示領域である。
【００３１】
次に、以上の構成に基づく動作概要を以下に説明する。
【００３２】
まず、インデックスを用いた検索機能について説明する。検索アプリケーション４００９のデータ登録処理部４０１０によって、各データ４００２がデータ格納部４００１に格納される。また、データベースエンジン４００５のインデックス登録処理部４００６によって、各インデックス３００４〜３００７が作成される。この状況において、検索条件入力部４０１３によってユーザからの検索指示が検索アプリケーション４００９に渡され、データ検索処理部４０１１が実行される。このとき、検索に用いるインデックスが複数利用可能な場合（日付インデックス３００４やＧＰＳ座標インデックス３００５等）、優先的に用いるインデックスによって、データベースエンジン内におけるデータ走査処理の順番が変わる。またインデックスに格納されるデータ量やデータ分布が属性毎に異なるため、最終的に得られる結果は同じでもインデックスの選択方法によって検索に必要なコスト・応答時間が変化する。よって、データ検索処理部４０１１がデータベースエンジン４００５を呼び出し、インデックス検索処理部４００７を実行する際、データベースエンジン４００５は、検索コスト及び応答時間がもっとも小さくなるインデックスを推定し、選択することが重要となる。
【００３３】
一般にデータベースファイルが置かれる外部記憶部１００６（ＨＤＤ、Ｆｌａｓｈ  Ｍｅｍｏｒｙ等）へのアクセス速度はＲＡＭ１００３に比べて遅い。そのため、多くの基本システム（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）は外部記憶部の入出力の応答時間を短縮するため、ＲＡＭ１００３に利用頻度の高いデータを一時的に保持するファイルキャッシュ４００４及びファイルの先読み機構を用意する。しかし、特にデジタルカメラなどの計算資源に制約がある組み込みデバイスにおいては、これらの機能を潤沢に利用できないのが現実である。そのため、データベースエンジン４００５はなるべくデータ格納部４００１及びインデックス格納部４００３へのアクセス頻度を減らすことが重要である。インデックス登録処理部４００６及びインデックス検索処理部４００７を実行する際におけるデータ格納部４００１及びインデックス格納部４００３へのアクセス頻度を減らすために、データベースエンジン４００５は独自のデータベースキャッシュ４００８というバッファを持つ。しかし、前記のファイルキャッシュ機構と同様、組み込みデバイスにおいては資源に制限があるために潤沢に用意することができず、限られた資源の中でデータベースキャッシュのヒット率等で表現される再利用性を高める必要がある。キャッシュのヒット率は、例えば、分母：アクセス要求数、分子：アクセス対象がキャッシュに残っていた回数などで計算できる。
【００３４】
データベースエンジン４００５は検索処理を実行する際、事前に設定されたルールや、登録されたデータ分布からの推測等により検索処理に必要な計算コストを見積もり、そのコストが最も小さくなるインデックスを推定して選択し、検索処理を実行する。例えば、図６（ａ）に示す人名と日付の組み合わせ検索では、一般に人名が日付に比べて属性数が少なく、ＤＢファイル中に散在する可能性が高い。そのため日付インデックスよりも人名インデックスを優先した方が検索結果の候補を少なくし、素早く絞り込むことが期待できる。よってデータベースエンジン４００５は人名インデックス３００７を優先的に用いて検索処理を実行し、検索アプリケーション４００９は検索結果を受け取る。そして検索結果表示制御部４０１４が検索アプリケーション４００９の処理結果を受けて図６（ｂ）に示すような検索結果をユーザに提示する。
【００３５】
しかし、日付の検索値を固定し、人名の検索値のみを変えて複数回連続検索する場合、人名インデックスを優先すると、ＤＢファイル中に散在するデータを繰返し走査することになる。その結果データベースキャッシュ及びファイルキャッシュ双方の再利用性が低下し、不連続なディスクアクセスが頻発して応答速度が遅くなる。特に小容量のキャッシュサイズである場合には、検索候補を少なくすることによる高速化の効果よりも、不連続なディスクアクセスによる応答速度劣化が上回る場合が多い。例えば、日付条件「２０１０／５／２０」を固定し、人名を毎回変更して検索を実行する場合に、非連続値である人名のインデックスを優先すると、不連続にデータ格納部４００１へのアクセスが起こる。データベースキャッシュ、ファイルキャッシュ双方の効果が得られず、結果として応答速度が劣化する。
【００３６】
本実施形態は上記の問題を解決するために、検索条件の履歴を検索条件履歴５００２のように記録し、その履歴を用いてデータベースキャッシュの再利用性を向上させ、応答速度を改善するものである。具体的には検索値の履歴を参照し、各属性に指定された検索条件に同一値、或いは類似値の繰り返しを検出した時点で、繰返しを検出したインデックスを優先的に用いるよう変更するものである。
【００３７】
本実施形態の詳細について、図７に示すデータベースエンジンのフローチャートを用いて説明する。
【００３８】
まずステップＳ７００１において、検索アプリケーション４００９によって発行されたＳＱＬ文を解析する。続いてステップＳ７００２において、解析した検索条件を検索条件履歴格納部４０１２に記録する。ステップＳ７００３では記録された検索条件履歴の取得・解析を行い、検索対象となる各属性についてデータベースキャッシュの再利用性の指標として、ヒット率をそれぞれ算出・判定する。ヒット率は、例えば、分母：アクセス要求数、分子：アクセス対象がキャッシュに残っていた回数などで計算できる。ステップＳ７００４において前記解析結果を基に、データベースキャッシュのヒット率が閾値以上の属性が存在するか否かを判定する。いずれの属性も閾値を超えない場合は、ステップＳ７００５において予め定められたルールベースの実行計画を生成する。また、閾値を超える属性が存在する場合は、ステップＳ７００６において検索条件に対応した検索実行手順をデータベースキャッシュの再利用性が高くなるように検索実行計画を生成する。すなわち、ループの２回目以降では、仮に同じクエリが実行された場合でも、再利用性に応じて実行計画が再生成されることになる。
【００３９】
この時、データベースエンジンはデータベースキャッシュの再利用性が高い属性のインデックスを優先的に利用して実行計画を再生成する。インデックス以外に実行計画の生成に考慮する要素として、データベースファイル走査処理に用いる内部カーソルの開始位置を考慮する構成も有効である。内部カーソルとは、データベースエンジンがデータベースを走査するためのものあり、内部カーソルの開始位置とは、データベースの走査をどこから開始するかを決めるものである。前段の検索で走査が行われたときにデータ分布を記憶しておき、その分布情報を基に開始位置を決定すれば走査処理を省略することができる。そうすることによって、類似した検索条件が連続する場合に、前段の検索処理で走査し終えた部分の走査を省略するなど、応答速度を高速化する効果を期待できる。
【００４０】
検索実行計画が確定したら、ステップＳ７００７において検索処理を実行し、ステップＳ７００８によって検索アプリケーションに結果を返却する。ステップＳ７００９では、検索アプリケーションの指示によって検索が続行されるか否かを判定する。検索が続行される場合にはステップＳ７０１０に推移して必要な初期化処理を行い、再びステップＳ７００１に戻る。以上の処理が繰り返し実行されると、データベースキャッシュの再利用性が高い検索処理が実行され、ステップＳ７００７及びステップＳ７００８における応答速度を高速化することが可能となる。
【００４１】
なお、データベースキャッシュの再利用性を判定する基準として、検索条件の同一属性値出現頻度がまず挙げられる。図８に示したのは、同一属性値出現頻度を用いた場合の、ステップＳ７００３の詳細である。同一属性値出現頻度を用いた場合のステップＳ７００３は、ステップＳ８００２〜Ｓ８００５から構成され、各属性についてループ処理される。ステップＳ８００２では、過去ｎ回分の検索条件履歴を照会し、ステップＳ８００３において、属性値を解析して検索条件に指定された各属性値の出現頻度を算出する。属性毎に複数の属性値があるので、属性毎に複数の出現頻度が存在する。算出した複数の出現頻度のうち、最も高いものかそれに類するものをその属性の代表出現頻度とする。その代表出現頻度についてステップＳ８００４において同一属性値出現頻度閾値と比較し、閾値以上である場合にはステップＳ８００５に推移して検索データ再利用性の高い属性としてマークし、そうでない場合には何もしない。検索条件値に同一属性値が高頻度に指定される系では、期待する検索結果の保存位置が前段の検索結果周辺に集中していることが期待できるためである。なお、前述した属性代表出現頻度としては、出現頻度の最大値だけではなく、出現頻度の平均値を用いる構成にすることもできる。例えば、出現頻度が、人名Ａが１０回、人名Ｂが１回、地名Ｃが９回、地名Ｄが８回だった場合、人名の代表出現頻度は最大値を用いると１０回、平均値を用いると５．５回となり、地名の代表出現頻度は最大値を用いると９回、平均値を用いると８．５回となる。地名の属性が再利用性の高い属性ということが分かる。このようにすれば、検索条件の履歴数が多くなった場合に、ユーザの検索意図をより正確に汲み取れる効果が得られる。
【００４２】
前述のデータベースキャッシュの再利用性を判定する別の基準としては、検索条件に合致するデータの、インデックス内部における格納位置の変化度を属性毎に計測し、その位置の変化度が小さい属性を再利用性の高いものとして用いることも考えられる。格納位置の変化度が小さい属性を優先することで、検索データの再利用性を高めることが期待できるためである。図９に示したのは格納位置変化度を用いた場合のステップＳ７００３の詳細である。格納位置変化度を用いた場合のステップＳ７００３は、ステップＳ９００２〜Ｓ９００５から構成され、図８のフローと同様に各属性についてループ処理される。図８のフローとの違いは、ステップＳ９００２及びステップＳ９００３にあり、同一属性値の出現頻度の代わりにインデックス内の格納位置の変化度を用い、検索データの再利用性が高い属性を判定する点が異なる。この場合においても、前段の合致データ周辺に次回以降の検索結果が集中していることが期待できる。
【００４３】
図８および図９に示したいずれの方法も、一般的にユーザ或いは検索アプリケーションが指定する検索条件が、一定の文脈をもって連続実行されることを想定して応答速度を高速化することを期待している。
【００４４】
このような処理をすることで、例えば、図２の状況で効果が期待できる。検索条件として日付条件「２０１０／５／２０」の変化がないことを履歴によって判定し、３回目から日付インデックスを用いた実行計画に切り替えることによって、それ以降のデータベースキャッシュの再利用性が向上し、応答速度の改善が期待できる。また、不連続なアクセスを抑制することによってファイルキャッシュの効果を得ることが期待でき、データベースキャッシュの再利用性が向上するためファイルアクセス自体を減少させることができる。
【００４５】
上記に示した処理は、事前のデータ分布等の解析処理に依存せず実現可能であり、負荷の少ない最適化処理をユーザや検索アプリケーションが、実行する文脈を考慮して実行する。なお、実施する場合、計算資源や処理負荷に応じて、検索履歴解析時に参照する履歴数や解析対象の属性数を変化させ、検索条件履歴解析の処理負荷を調整することも可能である。このことにより、本発明は計算資源が潤沢ではない環境においても適用可能である。もちろん、ＰＣ等の計算資源が潤沢な環境において、事前に実行されるクエリの検索条件を静的に解析しておき、それらを活用した最適化と本実施形態と併用してもよい。
【００４６】
例えば、大量画像に対するインデックス作成とデータ分布の解析とをＰＣ等で事前に実行しておくことにより、計算資源的に省資源機器のみでは実現が困難なデータ検索も可能になる。また検索データの再利用手段としては、データベースキャッシュに限らず、外部記憶部に検索処理の途中結果等をソートして一時的に保存しておき、検索時に再利用をする等によって外部記憶部に対するランダムアクセスを回避することも効果的である。
【００４７】
（第２の実施形態）
次に、本発明の第２の実施形態として、検索条件として与えられるＳＱＬ文中にバインド変数が存在する場合における検索処理方法について詳細に説明する。本実施形態は第１の実施形態と同様の構成を持つ。
【００４８】
一般にデータベースエンジンにはバインド変数を指定可能にする機構を備えている。これは同様なクエリを繰返し実行する際に、ＳＱＬ文の再解釈を行わず、実行計画を固定したままバインド変数を差し替えて実行可能にすることを目的としている。このことにより実行計画の再生成の計算を省略して、検索条件値のみを差し替えて繰り返し検索処理を実行できるため、応答速度を高速化できる。しかしながら、キャッシュの再利用性が低い実行計画が作成された場合に、実行計画の再生成を省略して繰り返し検索処理を行うことは必ずしも応答速度の改善にはつながらない。
【００４９】
そこで本実施形態は第１の実施形態に加え、ＳＱＬ文中にバインド変数が指定された場合に、バインド変数に代入された履歴を記録及び解析し、実行計画の再生成を行って検索処理の応答速度を高速化するものである。
【００５０】
図１０は本実施形態が最も効果を発揮する状況を示した図である。第１の実施形態と同様に、人名と日付を組み合わせた検索を行う状況であるが、それぞれ人名の属性値にバインド変数１、日付の属性値にバインド変数２が指定されている。図１０に示した例では、１回目は人名の属性の方が絞り込み効果が高いと判断されて、人名インデックスが選択されている。続いて検索処理を繰返す過程で日付の属性値として繰り返し「２０１０／５／２０」が代入されていることを検知した時点で、日付インデックスに切り替えて実行計画を再生成し、検索処理を実行する。このことによってデータベースキャッシュの利用効率を高め、応答速度を高速化することが可能になる。
【００５１】
処理の詳細について図１１に示したフローチャートを用いて説明する。
【００５２】
まず、ステップＳ１１００１において、検索アプリケーション４００９によって発行されたＳＱＬ文を解析する。続いてステップＳ１１００２において、前記解析結果を基に、検索条件に対応する検索処理をどのように実行するかを決定する検索実行計画を生成し、ステップＳ１１００３において、バインド変数に検索値が代入される。また同時に、ステップＳ１１００４において、バインド変数に代入された検索条件値を検索条件履歴格納部４０１２に記録する。ステップＳ１１００５では記録されたバインド値履歴の取得・解析を行い、検索対象となる各属性についてデータベースキャッシュの再利用性としてヒット率をそれぞれ算出する。そしてステップＳ１１００６において、生成済みの検索実行計画のデータベースキャッシュの再利用性を前記のヒット率を用いて判定し、より利用効率が高いインデックスが存在した場合にはステップＳ１１００７に推移して検索実行計画を再生成する。また同時に、ステップＳ１１００８において、代入済みのバインド変数を新しい検索実行計画に再代入する。検索実行計画が確定したらステップＳ１１００９において、検索処理を実行し、ステップＳ１１０１０によって検索アプリケーションに結果を返却する。ステップＳ１１０１１において、検索アプリケーションの指示によって検索が続行される場合には、ステップＳ１１０１２に推移して必要な初期化処理を行い、再びステップＳ１１００３に戻る。以上の処理を行うことで、ステップＳ１１００９及びステップＳ１１０１０における応答速度を高速化することが可能となる。なお、ステップＳ１１００２とステップＳ１１００７の処理内容は同一である。
【００５３】
データベースキャッシュの再利用性を判定する基準としては、第１の実施形態と同様に、検索条件の同一値出現頻度、或いは検索条件に合致するデータのインデックス内部における相対位置の変化度を用いる構成にできる。そのことによってデータベースファイルへの連続的なアクセスを促せる効果がある。また、ＳＱＬ文に静的な条件指定とバインド変数を用いた条件指定が混在している場合には、静的な条件に対応するインデックスを優先的に選択する構成にすることもできる。これは繰返し実行時に静的な条件は変更されないことが明らかであり、静的な条件に対応するインデックスの再利用性が高く、キャッシュのヒット率を上げる効果が高いためである。
【００５４】
本実施形態も図２に示した例において適用可能であり、第１の実施形態のステップＳ７００１のようなＳＱＬ文解析を行うことなく、属性値の部分であるバインド変数を比較することによってより小さいコストで検索処理を実行することが可能となる。
【００５５】
（その他の実施例）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【符号の説明】
【００５６】
４００１  データ格納部
４００２  データ
４００３  インデックス格納部
４００４  ファイルキャッシュ
４００５  データベースエンジン
４００６  インデックス登録処理部
４００７  インデックス検索処理部
４００８  データベースキャッシュ
４００９  検索アプリケーション
４０１０  データ登録処理部
４０１１  データ検索処理部
４０１２  検索条件履歴格納部
４０１３  検索条件入力部
４０１４  検索結果表示制御部
【図１】
0005713652.tif 000002
【図２】
0005713652.tif 000003
【図３】
0005713652.tif 000004
【図４】
0005713652.tif 000005
【図５】
0005713652.tif 000006
【図６】
0005713652.tif 000007
【図７】
0005713652.tif 000008
【図８】
0005713652.tif 000009
【図９】
0005713652.tif 000010
【図１０】
0005713652.tif 000011
【図１１】
0005713652.tif 000012