(19)【発行国】日本国特許庁(JP)
【公報種別】再公表特許(A1)
(11)【国際公開番号】WO2013098918
(43)【国際公開日】20130704
【発行日】20150430
(54)【発明の名称】データベースシステム及びデータベース管理方法
(51)【国際特許分類】
   G06F 17/30 20060101AFI20150403BHJP
   G06F 12/00 20060101ALI20150403BHJP
【FI】
   !G06F17/30 414A
   !G06F12/00 520A
【審査請求】有
【予備審査請求】未請求
【全頁数】25
【出願番号】2013551059
(21)【国際出願番号】JP2011080077
(22)【国際出願日】20111226
(81)【指定国】 AP(BW,GH,GM,KE,LR,LS,MW,MZ,NA,RW,SD,SL,SZ,TZ,UG,ZM,ZW),EA(AM,AZ,BY,KG,KZ,MD,RU,TJ,TM),EP(AL,AT,BE,BG,CH,CY,CZ,DE,DK,EE,ES,FI,FR,GB,GR,HR,HU,IE,IS,IT,LT,LU,LV,MC,MK,MT,NL,NO,PL,PT,RO,RS,SE,SI,SK,SM,TR),OA(BF,BJ,CF,CG,CI,CM,GA,GN,GQ,GW,ML,MR,NE,SN,TD,TG),AE,AG,AL,AM,AO,AT,AU,AZ,BA,BB,BG,BH,BR,BW,BY,BZ,CA,CH,CL,CN,CO,CR,CU,CZ,DE,DK,DM,DO,DZ,EC,EE,EG,ES,FI,GB,GD,GE,GH,GM,GT,HN,HR,HU,ID,IL,IN,IS,JP,KE,KG,KM,KN,KP,KR,KZ,LA,LC,LK,LR,LS,LT,LU,LY,MA,MD,ME,MG,MK,MN,MW,MX,MY,MZ,NA,NG,NI,NO,NZ,OM,PE,PG,PH,PL,PT,QA,RO,RS,RU,RW,SC,SD,SE,SG,SK,SL,SM,ST,SV,SY,TH,TJ,TM,TN,TR,TT,TZ,UA,UG,US,UZ,VC,VN
(71)【出願人】
【識別番号】000005108
【氏名又は名称】株式会社日立製作所
【住所又は居所】東京都千代田区丸の内一丁目6番6号
(74)【代理人】
【識別番号】110000279
【氏名又は名称】特許業務法人ウィルフォート国際特許事務所
(72)【発明者】
【氏名】礒松 紘平
【住所又は居所】東京都千代田区丸の内一丁目6番6号 株式会社日立製作所内
(72)【発明者】
【氏名】濱田 信輔
【住所又は居所】東京都千代田区丸の内一丁目6番6号 株式会社日立製作所内
(72)【発明者】
【氏名】伊藤 徹
【住所又は居所】東京都千代田区丸の内一丁目6番6号 株式会社日立製作所内
(72)【発明者】
【氏名】木村 耕治
【住所又は居所】東京都千代田区丸の内一丁目6番6号 株式会社日立製作所内
(57)【要約】
データベースシステムは、記憶デバイスに対するインタフェースと、インタフェースを通じて記憶デバイスにアクセスする制御デバイスとを有する。記憶デバイスは、複数の項目の値を有する行を複数管理する表と、1以上の項目の値により行を特定可能にするための複数のノードによる木構造で構成されたインデクスとを記憶する。制御デバイスは、検索クエリの検索条件に含まれる項目値条件を特定し、項目値条件に対応するインデクスのノードが参照不可であるか否かを判定し、ノードが参照不可である場合に、参照不可のノードが管理する項目値の範囲を特定し、特定した範囲に対して検索条件を満たす行を検索する。
【特許請求の範囲】
【請求項1】
記憶デバイスに対するインタフェースと、
前記インタフェースを通じて前記記憶デバイスにアクセスする制御デバイスと
を有し、
前記記憶デバイスが、複数の項目の値を有する行を複数管理する表と、1以上の前記項目の値により前記行を特定可能にするための複数のノードを含む木構造で構成されたインデクスとを記憶し、
前記制御デバイスは、
前記表に対する検索クエリの検索条件に含まれる項目値条件を特定し、
前記項目値条件に対応する前記インデクスの前記ノードが参照不可であるか否かを判定し、
前記ノードが参照不可である場合に、前記参照不可のノードが管理する項目値の範囲を特定し、特定した前記範囲に対して前記検索条件を満たす行を検索する
データベースシステム。
【請求項2】
前記制御デバイスは、
前記参照不可のノードが、前記インデクスにおける中間ノードである場合に、前記ノードと同じ段における直前のノードが管理する項目値に基づいて、前記参照不可のノードが管理する項目値の範囲を特定する
請求項1に記載のデータベースシステム。
【請求項3】
前記制御デバイスは、
前記参照不可のノードが、前記インデクスにおける中間ノードである場合に、前記参照不可のノードの下位のノードを特定し、
前記下位のノードを用いて、前記特定した前記範囲に対して前記検索条件を満たす行を検索する
請求項2に記載のデータベースシステム。
【請求項4】
前記記憶デバイスは、前記インデクスの各段における先頭のノードのノード番号を含む段数管理情報を記憶し、
前記制御デバイスは、
前記参照不可のノードが、前記インデクスにおける中間ノードである場合に、前記参照不可のノードの上位のノードの、前記参照不可のノードの直前のノードのエントリがあれば、当該エントリに従って前記直前のノードを経由して下位のノードを特定し、
前記参照不可のノードの直前のノードのエントリがなければ、前記段数管理情報に基づいて、下位の段のノードを特定し、特定したノードを経由して下位のノードを特定する
請求項3に記載のデータベースシステム。
【請求項5】
前記制御デバイスは、
前記参照不可のノードが、ルートノードである場合に、前記段数管理情報に基づいて、下位の最前のノードを特定し、特定したノード及び当該ノードから接続された各ノードを用いて、前記検索条件を満たす行を検索する
請求項1に記載のデータベースシステム。
【請求項6】
前記記憶デバイスは、前記インデクスが対象とする1以上の前記項目を含む複数項目について対象とする他のインデクスを記憶し、
前記制御デバイスは、
前記参照不可のノードが、リーフノードである場合に、前記他のインデクスに基づいて、前記参照不可のノードと同じ項目値の範囲を検索する
請求項1に記載のデータベースシステム。
【請求項7】
前記ノードは、ヘッダと、フッタとに、整合性確認用の情報を格納するように管理されており、
前記制御デバイスは、
前記ノードの前記ヘッダの整合性確認用の情報と、前記フッタの整合性確認用の情報とに基づいて、当該ノードが参照不可か否かを判定する
請求項1に記載のデータベースシステム。
【請求項8】
前記ノードに排他がかけられているか否かに基づいて、当該ノードが参照不可か否かを判定する
請求項1に記載のデータベースシステム。
【請求項9】
前記ノードは、当該ノードに接続される下位のノードのページ番号又は、当該ノードに接続される行を示す行IDと、項目の値とを含む1以上のエントリを、前記エントリの前記項目の値に従って並べて格納し、
前記制御デバイスは、
前記ノードの前記エントリが前記項目の値に従って並んでいるか否かに基づいて、当該ノードが参照不可であるか否かを判定する
請求項1に記載のデータベースシステム。
【請求項10】
前記ノードは、前記下位のノード又は前記接続されている行に対するポインタが設けられており、
前記制御デバイスは、
前記ポインタにより対応付けられているノードのページ番号又は行の行IDと、前記ノードが格納しているページ番号又は行IDとが一致しているか否かにより、前記ノードが参照不可であるか否かを判定する
請求項1に記載のデータベースシステム。
【請求項11】
前記制御デバイスは、前記ポインタにより対応付けられている前記ノードに排他がかけられているか否かに基づいて、当該ノードが参照不可か否かを判定する
請求項1に記載のデータベースシステム。
【請求項12】
検索対象とするノード又は行を示す1以上の検索プログラム情報を格納可能な検索プログラム情報キューを有し、
前記制御デバイスは、前記検索プログラム情報キューから逐次前記検索プログラム情報を取得し、
前記取得した検索プログラム情報が示す前記ノードが参照不可であるか否かを判定し、
前記ノードから参照不可でなく、且つ検索条件に該当するエントリを検出した場合に、当該エントリを検索対象とするための検索プログラム情報を出力して、前記検索プログラム情報キューに登録する
請求項1に記載のデータベースシステム。
【請求項13】
前記制御デバイスは、
前記参照不可のノードの下位のノードから、参照不可でなく、且つ検索条件に該当するエントリを検出した場合に、当該エントリを検索対象とするための検索プログラム情報を出力して、前記検索プログラム情報キューに登録する
請求項12に記載のデータベースシステム。
【請求項14】
前記制御デバイスは、
複数の前記検索プログラム情報に基づいた処理を並行して実行する
請求項12に記載のデータベースシステム。
【請求項15】
複数の項目の値を有する行を複数管理する表と、1以上の前記項目の値により前記行を特定可能にするための複数のノードを含む木構造で構成されたインデクスとを記憶する記憶デバイスにおけるインデクスを用いて前記表を検索するデータベース管理方法であって、
前記表に対する検索クエリの検索条件に含まれる項目値条件を特定し、
前記項目値条件に対応する前記インデクスの前記ノードが参照不可であるか否かを判定し、
前記ノードが参照不可である場合に、前記参照不可のノードが管理する項目値の範囲を特定し、特定した前記範囲に対して前記検索条件を満たす行を検索する
データベース管理方法。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、表と、表の行(レコード)を検索するためのインデクスとを管理するデータベースシステム及びデータベース管理方法に関する。
【背景技術】
【0002】
データベースには、データベースに格納されている表のレコードを高速に検索できるようにするために、表のレコードについてのインデクスを管理しているものがある。このようなデータベースを管理するデータベースシステムでは、データベースの表を更新する場合には、インデクスも併せて更新するようにしている。
【0003】
データベースシステムにおいて、インデクスの更新時に、ライトエラーが発生してしまうと、インデクスのデータが壊れてしまい、インデクスを用いて表のレコードの検索を実行することができなくなってしまう虞がある。ここで、インデクスのデータが壊れてしまっている状態を、「論理破壊」ということとする。
【0004】
このような状況に対して、データベースのサービス提供を停止せずに、データベースを修復する技術が知られている(例えば、特許文献1参照)。
【先行技術文献】
【特許文献】
【0005】
【特許文献1】特開2009−252148号公報
【発明の概要】
【発明が解決しようとする課題】
【0006】
上記したように、データベースの修復が行われる場合においては、修復しているインデクスを用いた表の検索を実行することができず、表を直に検索することとなり、検索処理に長時間を要することとなる。また、検索処理の負荷が大きくなるので、同じデータベースを利用した他の検索処理の性能に対しても悪影響を及ぼすこととなる。
【0007】
本発明は、上記課題に鑑みなされたものであり、その目的は、インデクスに論理破壊が発生した場合であっても、適切且つ迅速に検索を実行することのできる技術を提供することにある。
【課題を解決するための手段】
【0008】
データベースシステムは、記憶デバイスに対するインタフェースと、インタフェースを通じて記憶デバイスにアクセスする制御デバイスとを有する。記憶デバイスは、複数の項目の値を有する行を複数管理する表と、1以上の項目の値により行を特定可能にするための複数のノードによる木構造で構成されたインデクスとを記憶する。制御デバイスは、検索クエリの検索条件に含まれる項目値条件を特定し、項目値条件に対応するインデクスのノードが参照不可であるか否かを判定し、ノードが参照不可である場合に、参照不可のノードが管理する項目値の範囲を特定し、特定した範囲に対して検索条件を満たす行を検索する。
【0009】
データベースシステムが、前述の記憶デバイスを含んでいても良い。
【図面の簡単な説明】
【0010】
【図1】図1は、実施形態に係るデータベースシステムの処理概要の一例を説明する図である。
【図2】図2は、実施形態に係るデータベースシステムを含む計算機システムの一例の構成図である。
【図3】図3は、実施形態に係る検索クエリの一例を説明する図である。
【図4】図4は、実施形態に係る表の構成の一例を示す図である。
【図5】図5は、実施形態に係るインデクスの構成の一例を示す図である。
【図6】図6は、実施形態に係るインデクスのノードの構成の一例を示す図である。
【図7】図7は、実施形態に係るインデクス段数管理表の一例を示す図である。
【図8】図8は、実施形態に係るインデクス管理表の一例を示す図である。
【図9】図9Aは、実施形態に係る検索プログラム情報の構成の一例を示す図である。図9Bは、実施形態に係る検索プログラム情報の第1の例を示す図である。図9Cは、実施形態に係る検索プログラム情報の第2の例を示す図である。図9Dは、実施形態に係る検索プログラム情報の第3の例を示す図である。図9Eは、実施形態に係る検索プログラム情報の第4の例を示す図である。図9Fは、実施形態に係る検索プログラム情報管理キューの一例を示す図である。
【図10】図10は、実施形態に係る参照不可ノード管理情報の構成の一例を示す図である。
【図11】図11は、実施形態に係るインデクス検索処理の一例のフローチャートである。
【図12】図12は、実施形態に係るノード参照検知処理の一例のフローチャートである。
【図13】図13は、実施形態に係るエントリ参照検知処理の一例のフローチャートである。
【図14】図14は、実施形態に係る参照不可箇所特定処理の一例のフローチャートである。
【図15】図15は、実施形態に係る代替検索プログラム選定処理の一例のフローチャートである。
【図16】図16Aは、実施形態に係る検索プログラム情報の第1の具体例を示す図である。図16Bは、実施形態に係る検索プログラム情報の第2の具体例を示す図である。図16Cは、実施形態に係る検索プログラム情報の第3の具体例を示す図である。
【発明を実施するための形態】
【0011】
実施形態について、図面を参照して説明する。なお、以下に説明する実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている諸要素及びその組み合わせの全てが発明の解決手段に必須であるとは限らない。
【0012】
なお、以下の説明では、「aaa表」の表現にて各種情報を説明することがあるが、各種情報は、表以外のデータ構造で表現されていてもよい。データ構造に依存しないことを示すために「aaa表」を「aaa情報」と呼ぶことができる。
【0013】
また、以下の説明では、「プログラム」、又は、プログラムのモジュールを主語として処理を説明する場合があるが、プログラムやプログラムモジュールは、制御デバイス(例えばプロセッサ(例えばCPU(Central Processing Unit)))によって実行されることで、定められた処理を、適宜に記憶資源(例えばメモリ)及び/又は通信インタフェースデバイス(例えばインタフェース)を用いながら行うため、処理の主語が制御デバイスとされてもよい。プログラム、プログラムモジュールを主語として説明された処理は、制御デバイス或いはその制御デバイスを有する装置やシステム(例えば、サーバ装置)が行う処理としても良い。また、制御デバイスは、処理の一部又は全部を行うハードウェア回路を含んでも良い。プログラムは、プログラムソースからインストールされても良い。プログラムソースは、例えば、プログラム配布サーバ又は記憶メディアであっても良い。
【0014】
まず、実施形態の処理概要について説明する。
【0015】
図1は、実施形態に係るデータベースシステムの処理概要の一例を説明する図である。
【0016】
例えば、外部記憶装置1001と、サーバ装置2100とで構成されるデータベースシステムにおいて、インデクス検索部2120が、検索クエリ3010に対応するインデクスのルートノードや、検索プログラム管理キュー8100に登録された検索プログラム情報8110が示すノードを対象に検索を実行する。この際に、ノード参照検知部2113がノード9100における参照不可を検知し、エントリ参照検知部2114がノード9100のエントリ9104における参照不可を検知する。参照不可が検知されると、参照不可箇所特定部2115が、ノードの種別(ルートノード、中間ノード、リーフノード)に応じて、参照不可のノードによる検索範囲を特定して、参照不可ノード管理情報11000を生成する。
【0017】
代替検索プログラム選定部2116は、参照不可ノード管理情報11000に基づいて、参照不可のノードによる検索範囲を検索するための検索プログラム情報を選定する。これにより、インデクス検索部2120により、参照不可ノードの検索範囲に対しても適切に検索され、検索結果が得られることとなる。
【0018】
次に、本発明の一実施形態について、詳細に説明する。
【0019】
図2は、本発明の一実施形態に係るデータベースシステムを含む計算機システムの構成図である。
【0020】
計算機システムは、端末装置2150と、サーバ装置2100と、外部記憶装置1001とを有する。端末装置2150と、サーバ装置2100とは、ネットワーク2160を介して接続されている。外部記憶装置1001は、サーバ装置2100の内部バス2104に接続されている。ここで、サーバ装置2100と、外部記憶装置1001とにより、データベースシステムが構成される。
【0021】
端末装置2150は、例えば、データベースシステムを利用するアプリケーションを実行し、サーバ装置2100に対して、データベース内の表6100に対する検索要求(検索クエリ)を発行する。
【0022】
図3は、実施形態に係る検索クエリの一例を説明する図である。
【0023】
検索クエリ3010は、例えば、検索対象の表(6100等)を指定する表指定記述3011と、検索条件を指定する検索条件記述3012とが含まれる。図3に示す検索クエリ3010は、SQLを用いた検索クエリの一例であり、表“T1”を対象として、キー“C1”の値が“50”と“200”との間にあるとの検索条件を満たす行を選択することを要求している。
【0024】
図2の説明に戻り、外部記憶装置1001は、表6100と、インデクス管理表7100と、インデクス段数管理表10000と、インデクス4100、7112、7113とを格納する。外部記憶装置1001において、表は、複数備えてもよい。
【0025】
図4は、実施形態に係る表の構成の一例を示す図である。
【0026】
表6100は、行ID6101と、行内容6102とを有する行(レコード)を複数格納する。行ID6101は、表6100内で、行を一意に識別するIDを格納する。行内容6102は、複数の項目(6102、6103、6104、・・・)を含む。各項目は、項目に対応する値を格納する。図4に示す表名が“T1”の表6100は、項目として、C1、C2、C3、・・・等を有する。C1、C2、C3は、例えば、一つで、又は組み合わせて検索用のキーとして用いることができる。
【0027】
図5は、実施形態に係るインデクスの構成の一例を示す図である。図6は、実施形態に係るインデクスのノードの構成の一例を示す図である。
【0028】
インデクス(4100等)は、複数のノード(ページ)9100により木構造に構成されている。従って、インデクス(4100等)において、各ノード9100は、最上位のノードであるルートノードと、最下位のノードであるリーフノードと、ルートノードとリーフノードとの間にある中間ノードとに分けられる。なお、図5では、インデクスのノードの階層は、3段であり、中間ノードについては1段となっているが、ノードの階層は、3段より多くてもよく、その場合には、2以上の段に中間ノードが存在することとなる。
【0029】
ノード9100は、図6に示すように、ヘッダ部整合性確認情報9101と、前ページ番号9102と、後ページ番号9103と、エントリ9104と、インデクス段数9105と、自ページ番号9106と、フッタ部整合性確認情報9107とを含む。
【0030】
ヘッダ部整合性確認情報9101は、時刻データ等、当該ノードであるページの更新時に一意に決まる値を格納する。ヘッダ部整合性確認情報9101に格納される値は、ノードが正常に更新されていれば、フッタ部整合性確認情報9107に格納される値と同一となる。
【0031】
前ページ番号9102は、同一の階層における、対応するノードの直前のノード(前ページ)のページ番号を格納する。なお、対応するノードが、階層における先頭である場合には、ナル値が格納される。後ページ番号9103は、同一の階層における、対応するノードの直後のノード(後ページ)のページ番号を格納する。なお、対応するノードが、階層における最後尾である場合には、ナル値が格納される。ここで、本実施形態では、インデクスが同一階層においては、キー値の小さいエントリを管理するノードから順に並んでおり、前ページは、当該ページよりもキー値が小さいエントリを管理し、後ページと、当該ページよりもキー値が大きいエントリを管理している。
【0032】
エントリ9104は、当該ノードが、ルートノード又は中間ノードである場合には、当該エントリを示す番号(エントリ番号(エントリ#))と、当該ノードに接続される直下の階層のノード(下位ノード)のページ番号と、対応する下位ノードで管理するキー値の最大値とを対応付けて格納する。また、エントリ9104は、当該ノードが、リーフノードである場合には、エントリ#と、キー値と、対応するキー値を有する表6100の行のID(行ID)とを対応付けて格納する。エントリ9104は、ノード9100において、1以上備えることができる。本実施形態では、エントリ9104は、キー値の最大値に基づいて昇順となるように配置されている。
【0033】
インデクス段数9105は、インデクス4100における対応するノードの階層の段数を格納する。本実施形態では、リーフノードの段数が1であり、それより上位の階層のノードの段数は、2、3、・・・となる。自ページ番号9106は、当該ノードのページ番号を格納する。フッタ部整合性確認情報9107は、時刻データ等、当該ノードであるページの更新時に一意に決まる値を格納する。ノードが正常に更新されている場合であれば、ヘッダ部整合性確認情報9101に格納される値と同一となる。
【0034】
図6に示すノード9100は、図5に示すインデクスにおける2段目の最後(右端)のノードを示しており、当該ノード9100において、前ページ番号9102には、前ページのページ番号である“#8”が格納され、後ページ番号9103には、後ろページがないので、ナル値が設定され、エントリ9104としては、ページ番号“#4”と、当該ページ番号のノードの最大のキー値である“130”とが対応付けられたエントリ#が“0006”のエントリと、ページ番号“#3”と、当該ページ番号のノードの最大のキー値である“160”とが対応付けられたエントリ#が“0007”のエントリと、ページ番号“#9”と、当該ページ番号のノードの最大のキー値である“200”とが対応付けられたエントリ#が“0008”のエントリとがあり、インデクス段数には、“2”が格納され、自ページ番号には、“#5”が格納されている。
【0035】
ここで、例えば、図5に示すページ番号が”#8”のノード9100において、論理破壊が発生すると、当該ノード9100の各エントリ9104として格納されている、”#4”、”#3”、及び”#9”のノードに対しては、当該ノード9100を用いて辿ることができなくなってしまう。
【0036】
図7は、実施形態に係るインデクス段数管理表の一例を示す図である。
【0037】
インデクス段数管理表10000は、各インデクスに対応して設けられる。インデクス段数管理表10000は、段数10001と、ページ番号(#)10002とを含む。段数10001は、対応するインデクスに含まれる各段の段数を格納する。本実施形態では、リーフノードの段数を1としている。ページ#10002は、対応する段のノードにおいて、管理しているキー値の最大値が最も小さいノード(ページ)のページ番号を格納する。このインデクス段数管理表10000によると、各段における先頭のノードを特定することができる。
【0038】
同図に示すインデクス段数管理表10000は、図5に示す構成のインデクス“IDX1”に対応するインデクス段数管理表10000であり、3段目においては、ページ#1が管理しているキー値の最大値が最も小さく、2段目においては、ページ#8が管理しているキー値の最大値が最も小さく、1段目においては、ページ#2が管理しているキー値の最大値が最も小さいことを示している。
【0039】
図8は、実施形態に係るインデクス管理表の一例を示す図である。
【0040】
インデクス管理表7100は、表名7101と、インデクス名7102と、構成列7103とを有するレコードを管理する。表名7101は、インデクスが対象とする表6100の名称(表名)を格納する。インデクス名7102は、対応するインデクスの名称(インデクス名)を格納する。構成列7103は、対応するインデクスを構成している、すなわち、インデクスの対象としている列(項目)を格納する。構成列7103は、複数の列を格納してもよい。例えば、インデクス管理表7100の一番上のレコードは、“T1”の表6100の“IDX1”のインデクス4100は、項目“C1”により構成していることを示しており、インデクス管理表7100の3番目のレコードは、“T1”の表6100の“IDX3”のインデクス7113は、項目“C1”及び“C3”により構成していることを示している。
【0041】
図2の説明に戻り、サーバ装置2100は、インタフェース2101と、CPU2102と、メモリ2103とを有する。インタフェース2101と、CPU2102と、メモリ2103とは、内部バス2104を介して接続されている。
【0042】
インタフェース2101は、端末装置2150との間の通信を制御する。CPU2102は、メモリ2103に格納されたプログラムを実行することにより各種処理を実行する。
【0043】
メモリ2103は、CPU2102により実行されるプログラムや、CPU2102により使用されるデータを記憶する。具体的には、メモリ2103は、データベース管理システム(DBMS)2110を記憶する。データベース管理システム2110は、プログラムモジュールとして、クエリ受付部2111と、インデクス検出部2112とを記憶する。
【0044】
クエリ受付部2111は、端末装置2150から送信された検索クエリ3010を受け付ける。クエリ受付部2111は、受け付けた検索クエリ3010に含まれている検索を実行するための検索条件を含む実行手順を作成する。インデクス検索部2112は、ノード参照検知部2113と、エントリ参照検知部2114と、参照不可箇所特定部2115と、代替検索プログラム選定部2116とを含む。ノード参照検知部2113は、インデクスに対して、ノード単位での排他、又は論理破壊による参照不可を検知する。エントリ参照検知部2114は、インデクスに対して、ノード内のエントリ単位での排他、又は論理破壊による参照不可を検知する。参照不可箇所特定部2115は、インデクスの論理破壊による参照不可能な箇所のキー値の範囲を特定する。代替検索プログラム選定部2116は、インデクスの参照不可能なキー値範囲の検索を実行する代替検索プログラムを選定する。
【0045】
また、データベース管理システム2110は、データとして、検索プログラム情報管理キュー8100と、参照不可ノード管理情報11000とを記憶する。検索プログラム情報管理キュー8100は、検索時に用いる検索プログラム情報を格納する。参照不可ノード管理情報11000は、参照不可ノードに関する情報を格納する。
【0046】
図9Aは、実施形態に係る検索プログラム情報の構成の一例を示す図である。図9Bは、実施形態に係る検索プログラム情報の第1の例を示す図である。図9Cは、実施形態に係る検索プログラム情報の第2の例を示す図である。図9Dは、実施形態に係る検索プログラム情報の第3の例を示す図である。図9Eは、実施形態に係る検索プログラム情報の第4の例を示す図である。図9Fは、実施形態に係る検索プログラム情報管理キューの一例を示す図である。
【0047】
検索プログラム情報8110は、図9Aに示すように、検索プログラムID8111と、第1領域8112と、第2領域8113とを含む。検索プログラムID8111は、検索プログラム、又は代替検索プログラムのIDを格納する。第1領域8112、第2領域8113は、検索プログラム情報8110の種類に応じて図9B乃至図9Eに示すよう各種情報を記憶する。
【0048】
通常の検索を行うための検索プログラム情報8110は、図9Bに示すように、第1領域8112は、検索を開始するエントリ(元エントリ)の番号を格納する。第2領域8113は、元エントリの親となる親エントリの番号を格納する。
【0049】
参照不可であるノードに対する検索を代替するための検索(代替検索)を行うための検索プログラム情報8110は、図9Cに示すように、検索プログラムID8111には、代替検索プログラムを示すIDを格納する。第1領域8112は、検索を開始するエントリ(元エントリ)の番号を格納する。第2領域8113は、元エントリの親となる親エントリの番号を格納する。なお、親エントリが参照不可である場合には、第2領域8113には、当該親エントリを参照するエントリの番号を格納する。例えば、元エントリが図5に示すエントリ#0018である場合において、ノード#5が参照不可である場合には、第2領域8113には、参照不可であるノード#5を参照するエントリ#0002が格納される。
【0050】
代替インデクスを用いて代替検索を行うための検索プログラム情報8110は、図9Dに示すように、検索プログラムID8111には、代替検索プログラムを示すIDを格納する。第1領域8112は、検索に利用する代替インデクスのルートノード番号(#)を格納する。第2領域8113は、代替インデクスを使用することを示すフラグ(代替インデクス使用フラグ)を格納する。
【0051】
テーブルを用いて代替検索を行うための検索プログラム情報8110は、図9Eに示すように、検索プログラムID8111には、代替検索プログラムを示すIDを格納する。第1領域8112は、テーブル(表)の先頭データページ番号(#)を格納する。第2領域8113は、テーブルスキャンを行うことを示すフラグ(テーブルスキャンフラグ)を格納する。
【0052】
検索プログラム情報管理キュー8100は、図9Fに示すように、1以上の検索プログラム情報8110を格納可能である。検索プログラム情報管理キュー8100に格納されている検索プログラム情報8110は、インデクス検索部2120により一つずつ取り出されて実行されることとなる。
【0053】
図10は、実施形態に係る参照不可ノード管理情報の構成の一例を示す図である。
【0054】
参照不可ノード管理情報11000は、参照不可ノード検索範囲11001と、参照不可ノードノード種別11002と、前エントリ番号(#)11003とを格納する。
【0055】
参照不可ノード検索範囲11001は、キー値最小値11001aと、キー値最大値11001bとを含む。キー値最小値11001aは、参照不可となったノード(参照不可ノード)による検索範囲であるキー値の最小値を格納する。キー値最大値11001bは、参照不可ノードによる検索範囲であるキー値の最大値を格納する。なお、参照不可ノードがルートノードである場合には、キー値最小値11001a、キー値最大値11001bには、ナル値が格納される。
【0056】
参照不可ノードノード種別11002は、参照不可ノードのノード種別を格納する。ノード種別は、ルートノード、中間ノード、リーフノードのいずれかである。
【0057】
前エントリ番号(#)11003は、参照不可ノードをエントリとして含むノード(親ノード)における前のエントリ(前エントリ)の番号を格納する。ここで、前エントリとは、参照不可ノードの範囲とするキー値よりも小さいキー値を持っている直前のノードのエントリである。なお、前エントリがない場合には、ナル値が格納される。
【0058】
例えば、図4に示すインデクスにおけるページ#5のノードが参照不可ノードとなった場合には、参照不可ノード管理情報11000は、図10に示すように、キー値最小値11001aに、“100”が格納され、キー値最大値11001bに、“200”が格納され、参照不可ノードノード種別11002に、“中間ノード”が格納され、前エントリ#11003に、“#0001”が格納される。
【0059】
次に、本実施形態のサーバ装置2100による処理動作について説明する。
【0060】
図11は、実施形態に係るインデクス検索処理のフローチャートである。
【0061】
インデクス検索処理(ステップS100)は、CPU2102がインデクス検索部2112を実行することにより実現される。インデクス検索処理において、CPU2102が、クエリ受付部2111から検索要求を受け取り(ステップS101)、検索要求に対する初回の検索であるか否か、すなわち、一度でも結果を返したか否かを判定する(ステップS102)。
【0062】
この結果、最初の検索である場合(ステップS102でYes)には、CPU2102は、処理をステップS105に進める一方、最初の検索でない場合(ステップS102でNo)には、検索プログラム情報管理キュー8100から検索プログラム情報8110を取得することを試みる(ステップS103)。
【0063】
CPU2102は、検索プログラム情報管理キュー8100で検索プログラム情報8110が枯渇しているか否かを判定する(ステップS104)。この結果、検索プログラム情報が枯渇している場合(ステップS104でYes)には、検索要求に対応する検索処理を終えたことを意味するので、CPU2102は、処理を終了する一方、検索プログラム情報8110が枯渇していない場合(ステップS104でNo)には、処理をステップS105に進める。
【0064】
ステップS105では、CPU2102は、初回検索の場合(ステップS102でYes)には、ルートノードに移動し、検索プログラム情報8110を取得した場合には、検索プログラム情報8110で指定されているノードに移動する。なお、検索プログラム情報8110に代替インデクス使用フラグが設定されている場合には、CPU2102は、代替インデクスを用いて、検索条件のキーの値に着目して、検索を実行する。例えば、CPU2102は、参照不可ノード管理情報11000の参照不可ノード検索範囲11001のキー値の範囲を検索範囲として、代替インデクスを用いて検索を実行する。
【0065】
次いで、CPU2102は、対象のノードに対する参照状態を検知するノード参照検知処理を実行する(ステップS200)。
【0066】
次いで、CPU2102は、ノード参照検知処理の結果に基づいて、参照不可を検知したか否かを判定し(ステップS106)、参照不可を検知していない場合(ステップS106でNo)には、ノード内の最初のエントリをカレントポジションとして記憶し(S115)、ノード内に他のエントリが存在する場合(S116:Yes)、検索条件を満たすエントリが存在する間、ステップS107〜ステップS111のループ処理を実行する。
【0067】
ループ処理においては、CPU2102は、対象のノードにおける検索条件を満たすエントリを1件取得し(ステップS108)、当該エントリに対する参照状態を検知するエントリ参照検知処理を実行する(ステップS400)。次いで、CPU2102は、参照不可を検知していない場合(ステップS109でNo)には、検索IDを決定し、当該検索IDを含み、取得したエントリのエントリ#を第1領域8112に格納し、現在の元エントリを第2領域8113に格納した検索プログラム情報8110を作成し、検索プログラム情報管理キュー8100に登録し(ステップS110)、ステップS111に進む。
【0068】
一方、ノードについて参照不可を検知した場合(ステップS106でYes)又はエントリについて参照不可を検知した場合(ステップS109でYes)には、CPU2102は、参照不可箇所特定処理を実行し(ステップS600)、代替検索プログラム選定処理を実行し(ステップS700)、ステップS102に処理を進める。
【0069】
検索条件を満たすすべてのエントリに対して、ステップS107〜ステップS111の処理を実行した場合には、CPU2102は、対象のノードがリーフノードであるか否かを判定し(ステップS112)、リーフノードでない場合(ステップS112でNo)には、他の検索処理を継続するために、ステップS102に処理を進める一方、リーフノードである場合(ステップS112でYes)には、検索条件を満たす行IDを取得して返却し(ステップS113)、ステップS102に処理を進める。
【0070】
例えば、図11に示す処理のステップS103において、図5に示すリーフノード#4に対する検索をするための検索プログラム情報8110(第1領域8112にエントリ#0006を含み、第2領域8113にエントリ#0002を含む)を取得した場合には、検索条件が(50≦キー(C1)≦200)であるとすると、図11に示すステップS110において、第1領域8112にエントリ#0019、#0020を含む2つの検索プログラム情報が作成されて検索プログラム情報管理キュー8100に登録され、ステップS113でエントリ#0018に対応する行IDを取得し、当該行IDを検索結果の一部として返す処理が実行される。
【0071】
図12は、実施形態に係るノード参照検知処理のフローチャートである。
【0072】
ノード参照検知処理(ステップS200)は、CPU2102がノード参照検知部2113を実行することにより実現される。ノード参照検知処理において、CPU2102が、対象のノードに排他がかけられているか否かを確認し(ステップS201)、さらに、対象のノード9100のヘッダ部整合性確認情報9101の値と、フッタ部整合性確認情報9107の値とが一致しているか否かにより、論理的な整合性が取れているか否か、言い換えれば、論理破壊が発生していないか否かを確認する(ステップS202)。
【0073】
この確認の結果に基づいて、CPU2102は、対象ノードが排他又は論理破壊が発生していることにより参照不可であるか否かを判定する(ステップS203)。判定の結果、参照不可である場合(ステップS203でYes)には、参照不可検知をリターンコードとして設定し(ステップS204)、処理を終了する一方、参照不可でない場合(ステップS203でNo)には、そのまま処理を終了する。
【0074】
図13は、実施形態に係るエントリ参照検知処理のフローチャートである。
【0075】
エントリ参照検知処理(ステップS400)は、CPU2102がエントリ参照検知部2114を実行することにより実現される。エントリ参照検知処理において、CPU2102が、対象のエントリに排他がかけられているか否かを確認し(ステップS401)、さらに、対象のエントリのキー値について、論理的な整合性が取れているか否か、言い換えれば、論理破壊が発生していないか否かを確認する(ステップS402)。本実施形態では、対象のエントリ9104のキー値が、当該ノード中の前のエントリのキー値より大きく、後ろのエントリのキー値より小さくなっているか否かを確認する。
【0076】
次いで、CPU2102は、対象のノードがリーフノードであるか否かを判定し(ステップS403)、リーフノードでない場合(ステップS403でNo)には、エントリの下位ノードのページ番号についての整合性を確認する(ステップS404)。具体的には、CPU2102は、エントリ9104中のページ番号と、エントリ9104とポインタで接続されている下位のノード9100の自ページ番号9106のページ番号とが一致しているか否かを確認する。
【0077】
一方、リーフノードである場合(ステップS403でYes)には、エントリの行IDについての整合性を確認する(ステップS405)。具体的には、CPU2102は、エントリ9104中の行IDと、エントリ9104とポインタで接続されている表6100の行が持つ行ID6101とが一致しているか否かを確認する。
【0078】
これらの確認の結果に基づいて、CPU2102は、対象エントリが排他又は論理破壊が発生していることにより参照不可であるか否かを判定する(ステップS406)。判定の結果、参照不可である場合(ステップ406でYes)には、参照不可検知をリターンコードとして設定し(ステップS407)、処理を終了する一方、参照不可でない場合(ステップS406でNo)には、そのまま処理を終了する。
【0079】
図14は、実施形態に係る参照不可箇所特定処理のフローチャートである。
【0080】
参照不可箇所特定処理(ステップS600)は、CPU2102が参照不可箇所特定部2115を実行することにより実現される。参照不可箇所特定処理において、CPU2102が、ノード9100のインデクス段数9105と、インデクス段数管理表10000とに基づいて、対象のノードのノード種別を求めて、参照不可ノード管理情報11000に登録する(ステップS601)。
【0081】
次いで、CPU2102は、対象のノードに、検索プログラム情報8110の元エントリがその検索プログラム情報8110に存在するか否かを判定する(ステップS602)。この結果、元エントリが存在しない場合(ステップS602のNo)には、当該ノードがルートノードであることを意味しているので、CPU2102は、参照不可ノード管理情報11000のキー値最小値11001aと、キー値最大値11001bにナル値を登録し(ステップS612)、処理を終了する。なお、元エントリは、検索プログラム情報作成時に、作成される検索プログラム情報に設定されて良い。
【0082】
一方、元エントリが存在する場合(ステップS602のYes)には、CPU2102は、元エントリのキー値を、参照不可ノード管理情報11000のキー値最大値11001bに登録し(ステップS603)、元エントリに対する前エントリが存在するか否かを判定する(ステップS604)。
【0083】
この結果、前エントリが存在する場合(ステップS604でYes)には、CPU2102は、前エントリのキー値を、参照不可ノード管理情報11000のキー値最小値11001bに登録し(ステップS605)、前エントリのエントリ番号を、参照不可ノード管理情報11000の前エントリ#11003に登録し(ステップS606)、処理を終了する。
【0084】
一方、前エントリが存在しない場合(ステップS604でNo)には、CPU2102は、さらに、元エントリに対する親エントリが検索プログラム情報に存在するか否かを判定し(ステップS607)、親エントリが存在しない場合(ステップS607でNo)には、参照不可ノード管理情報11000のキー値最小値11001aにナル値を登録し(ステップS608)、処理を終了する。なお、親エントリは、検索プログラム情報作成時に、作成される検索プログラム情報に設定されて良い。
【0085】
一方、親エントリが存在する場合(ステップS607でYes)には、CPU2102は、親エントリに対する前エントリが存在するか否かを判定し(ステップS609)、親エントリに対する前エントリが存在しない場合(ステップS609でNo)には、参照不可ノード管理情報11000のキー値最小値11001aにナル値を登録し(ステップS608)、処理を終了する。
【0086】
一方、親エントリに対する前エントリが存在する場合(ステップS609でYes)には、参照不可ノード管理情報11000のキー値最小値11001aに前エントリのキー値を登録し(ステップS610)、親エントリに対する前エントリのエントリ番号を、参照不可ノード管理情報11000の前エントリ#11003に登録し(ステップS611)、処理を終了する。上記処理により、各ノードにおけるキー値の範囲を適切に参照不可ノード管理情報11000に格納することができる。
【0087】
図15は、実施形態に係る代替検索プログラム選定処理の一例のフローチャートである。ここで、当該フローチャートの説明において、図16A乃至図16Cを適宜参照する。図16Aは、実施形態に係る検索プログラム情報の第1の具体例を示す図である。図16Bは、実施形態に係る検索プログラム情報の第2の具体例を示す図である。図16Cは、実施形態に係る検索プログラム情報の第3の具体例を示す図である。
【0088】
代替検索プログラム選定処理(ステップS700)は、CPU2102が代替検索プログラム選定部2116を実行することにより実現される。代替検索プログラム選定処理において、CPU2102が、参照不可ノード管理情報11000からノード種別、ノード検索範囲(キー値の範囲)を取得し(ステップS701)、対象のノードのノード種別がリーフノードであるか否かを判定する(ステップS702)。
【0089】
この結果、対象のノードがリーフノードである場合(ステップS702でYes)には、CPU2102は、インデクス管理表7100から当該インデクスと同じ構成列を含むインデクスを代替インデクスとして検索し(ステップS703)、代替インデクスがあるか否かを判定する(ステップS704)。
【0090】
代替インデクスがある場合(ステップS704でYes)には、代替インデクスから参照不可ノードと同様のキー値の範囲を検索するための検索プログラム情報8110を作成し(ステップS705)、ステップS707に処理を進める。ステップS705で作成される検索プログラム情報8110は、図16Aに示すように、
代替検索プログラムIDをプログラムID8111に含み、代替インデクスのルートノードのページ番号を第1領域8112に含み、代替インデクス使用を示すフラグを第2領域8113に含む。
【0091】
このような検索プログラム情報8110をインデクス検索部2120が取得すると、既にある他のインデクスの一部を利用して検索する処理を実行することとなるので、迅速に検索を行うことができる
【0092】
一方、代替インデクスがない場合(ステップS704でNo)には、表6100から参照不可ノードと同様のキー値の範囲を検索するための検索プログラム情報を作成し(ステップS706)、ステップS707に処理を進める。ステップS706で作成される検索プログラム情報8110は、図16Bに示すように、代替検索プログラムIDをプログラムID8111に含み、表6100の先頭があるページ番号を第1領域8112に含み、テーブルをスキャンすること示すフラグを第2領域8113に含む。
【0093】
このような検索プログラム情報8110をインデクス検索部2120が取得すると、表6100に対する検索を参照不可ノードと同様のキー値範囲に限って検索を行うので、すべての表6100から直接検索する場合に比して、検索処理の時間及び負荷を低減することができる。なお、参照不可ノードのキー値範囲は、参照不可ノード管理情報11000から取得することができる。
【0094】
ステップS707では、作成した検索プログラム情報8110を検索プログラム情報管理キュー8100に登録し、処理を終了する。
【0095】
一方、リーフノードではない場合(ステップS702でNo)には、CPU2102は、対象のノードがルートノードであるか否かを判定する(ステップS708)。対象のノードがルートノードである場合(ステップS708でYes)には、CPU2102は、インデクス段数管理表10000に基づいて、下位ノードに移動し(ステップS709)、ノード参照検知処理を実行する(ステップS200)。一方、対象のノードがルートノードでない場合(ステップS708でNo)には、CPU2102は、インデクス段数管理表10000、又は前エントリに基づいて、下位ノードに移動し(ステップS710)、ノード参照検知処理を実行する(ステップS200)。ここで、下位ノードとは、対象のノードが持つエントリが示すすべてのノードを意味している。
【0096】
例えば、図5に示すインデクスにおいて、ノード#5が参照不可である場合において、下位ノードに移動する方法としては、ノード#5の元エントリ(エントリ#0002)の前エントリ(エントリ#0001)を特定し、当該エントリ#0001に基づいて、ノード#8に移動し、ノード#8の最後のエントリ(エントリ#0005)に基づいて、ノード#6に移動し、ノード#6が持つ後ページ#に基づいて、ノード#4、すなわち、ノード#5の下位のノードの中の先頭のノード(直下ノード)に移動する。
【0097】
ここで、直下ノードに辿る方法としては、以下に示す方法がある。例えば、対象のノードを参照するエントリ(元エントリ)がない場合には、インデクス段数管理表10000に基づいて、直下ノードまで辿ることができる。また、元エントリが存在し、元エントリの前のエントリ(前エントリ)が存在する場合には、元エントリの前エントリを用いて、直下ノードまで辿ることができる。また、元エントリが存在するが、親エントリが存在しない場合には、インデクス段数管理表10000に基づいて、直下ノードまで辿ることができる。また、元エントリが存在するが、元エントリの前エントリが存在しない場合であって、親エントリの前エントリが存在する場合には、親エントリの前エントリに基づいて、直下ノードまで辿ることができる。また、元エントリ、親エントリが存在するが、元エントリの前エントリ、及び、親エントリの前エントリが存在しない場合には、インデクス段数管理表10000に基づいて、直下ノードまで辿ることができる。
【0098】
次いで、CPU2102は、ノード参照検知処理の結果に基づいて、参照不可を検知したか否かを判定し(ステップS711)、参照不可を検知していない場合(ステップS711でNo)には、参照不可ノードのキー値の範囲内のエントリの数だけ、ステップS711〜ステップS716のループ処理を実行する。ここで、ステップS711〜ステップS716は、対象とするノードの下位ノードのエントリを対象にして実行される。例えば、図5に示すルートノードであるノード#1が参照不可の場合には、ノード#8、ノード#5のエントリが対象となり、ノード#5が参照不可の場合には、ノード#4、ノード#3、ノード#9のエントリが対象になる。
【0099】
ループ処理においては、CPU2102は、対象のエントリを1件取得して、当該エントリに対する参照状態を検知するエントリ参照検知処理を実行する(ステップS400)。
次いで、CPU2102は、参照不可を検知していない場合(ステップS713でNo)には、キー値が検索条件に合致しているか否かを判定し(ステップS714)、検索条件に合致している場合には、検索IDを決定し、当該検索IDを含み、当該エントリのエントリ#を第1領域8112に格納した検索プログラム情報8110を作成し、検索プログラム情報管理キュー8100に登録し(ステップS715)、ステップS716に進む。
【0100】
ここで、例えば、ノード#5が参照不可である場合においては、ステップS711〜ステップS716のループ処理によって、図16Cに示すように、第1領域8112に、ノード#4以降のノードのエントリであって、検索条件を満たすエントリの全てエントリ、すなわち、エントリ#0018からエントリ0026#のそれぞれのエントリに対する検索をするための検索プログラム情報8110が作成される。
【0101】
一方、ノードについて参照不可を検知した場合(ステップS711でYes)又はエントリについて参照不可を検知した場合(ステップS713でYes)には、CPU2102は、参照不可箇所特定処理を実行し(ステップS600)、代替検索プログラム選定処理を実行し(ステップS700)、処理を終了する。
【0102】
参照不可ノードのキー値の範囲内のすべてのエントリに対して、ステップS712〜ステップS716の処理を実行した場合には、CPU2102は、対象のノードがリーフノードであるか否かを判定し(ステップS111)、処理を終了する。この処理により、参照不可ノードによる検索範囲について、検索を適切に実行することができるようになる。
【0103】
以上、実施形態を説明したが、本発明は、この実施形態に限定されるものでなく、その趣旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【0104】
例えば、上記実施形態では、インデクスをキー値の小さい方から検索する構成としていたが、例えば、キー値の大きい方から検索する構成としてもよい。この場合には、各ノードは、下位の各ノードのエントリとして、各ノードのキー値の最小値を管理するようにし、同一の段においては、大きいキー値を管理するノードが前のノードとなるようにし、インデクス段数管理表では、各段のキー値の最大値を管理するページ番号を管理するようにすればよい。このようにした場合には、参照不可ノードが中間ノードであれば、参照不可ノードよりも大きいキー値を管理する隣接するノードを辿って、参照不可ノードの下位ノードを特定するようにすればよい。
【0105】
また、上記実施形態では、検索プログラム情報を一つずつ取り出して、逐次実行する例を示していたが、本発明はこれに限られず、例えば、検索プログラム情報を複数取り出して、それぞれに基づいた検索を並行して実行するようにしてもよい。
【符号の説明】
【0106】
2100:サーバ装置、1001:外部記憶装置、2150:端末装置
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【国際調査報告】