(57)【特許請求の範囲】
【請求項１】
索引及び表を含んだデータベースに対するインターフェースを含んだ１以上のインターフェースを含むインターフェース部と、
前記インターフェース部に接続された１以上のプロセッサを含むプロセッサ部と
を有し、
前記プロセッサ部が、前記表における少なくとも１つのレコードを移動するレコード移動処理に伴い、前記索引を更新する索引更新処理を実行し、
前記プロセッサ部が、前記索引更新処理において、前記レコード移動処理において移動したレコードについて、前記索引における移動前ポインタに移動後ポインタを上書きし、
前記移動前ポインタは、移動前の格納位置にあるレコードへのポインタであり、
前記移動後ポインタは、移動後の格納位置にあるレコードへのポインタであり、
前記索引は、木構造になった複数のノードを含み、
前記複数のノードのうちの１以上のリーフノードに、キー毎のポインタが格納され、
前記１以上のリーフノードが、キー毎に、
そのキーに対応した移動され得るレコードへのポインタが格納されポインタ順にポインタがソートされない領域である第１の領域と、
そのキーに対応した移動され得ないレコードへのポインタが格納されポインタ順にポインタがソートされている領域である第２の領域と
を有する、
計算機。
【請求項２】
前記プロセッサ部が、削除対象のポインタを前記索引から探索し見つかったポインタを削除する処理である索引削除処理を実行し、
前記第１の領域についての探索は、全探索であり、
前記第２の領域についての探索は、二分探索であり、
前記索引削除処理において、前記削除対象のポインタが移動され得ないレコードへのポインタである場合に、前記第２の領域についての探索を行い、探索により見つからなかった場合に、前記第１の領域についての探索を行う
請求項１記載の計算機。
【請求項３】
前記プロセッサ部は、レコード移動処理に伴う索引更新処理を実行した後に、移動したレコードを移動前の格納位置から削除する、
請求項２記載の計算機。
【請求項４】
前記プロセッサ部は、ロー形式で格納されたレコードが追加された場合、そのレコードへのポインタを、前記第１の領域の最後尾ポインタの次に格納する、
請求項１記載の計算機。
【請求項５】
前記プロセッサ部は、前記第１の領域からポインタを検索する場合、ポインタオフセットをインクリメントしながら検索する、
請求項１記載の計算機。
【請求項６】
前記データベースが格納される論理空間が複数のページで構成されており、
前記プロセッサ部は、ページ単位でロックを取得し、
前記第１の領域が、前記第２の領域が格納される１以上のページと別の１以上のページに格納されている、
請求項１記載の計算機。
【請求項７】
前記プロセッサ部は、
前記第２の領域にポインタを格納する場合、前記第２の領域を含んだ全てのページのロックを取得し、
前記第１の領域にポインタを格納する場合、前記第１の領域を含んだ１以上のページのうちの、そのポインタが格納される場所を含んだページのみのロックを取得する、
請求項６記載の計算機。
【請求項８】
前記移動され得るレコードは、ロー形式で格納された２以上のレコードの各々であり、
前記移動され得ないレコードは、カラム形式で格納された複数のレコードの各々であり、
前記プロセッサ部が、前記２以上のレコードの格納形式をロー形式からカラム形式に変換するコンバート処理を実行し、
前記コンバート処理は、前記レコード移動処理及び前記索引更新処理を含む、
請求項１記載の計算機。
【請求項９】
前記プロセッサ部は、データソースからデータが収集される都度に、収集された１以上のデータに基づくレコードをロー形式で格納し、
前記プロセッサ部は、Ｎ件以上のレコードが蓄積される都度に、少なくともＮ件のレコードの格納形式をロー形式からカラム形式に変換する前記コンバート処理を実行する、
請求項８記載の計算機。
【請求項１０】
前記データベースが格納される論理空間が複数のページで構成されており、
各キーについて、前記第１の領域が、前記第２の領域が格納される１以上のページと別の１以上のページに格納されており、
前記プロセッサ部は、
前記第２の領域にポインタを格納する場合、前記第２の領域を含んだ全てのページのロックを取得し、
前記第１の領域にポインタを格納する場合、前記第１の領域を含んだ１以上のページのうちの、そのポインタが格納される場所を含んだページのみのロックを取得する、
請求項８記載の計算機。
【請求項１１】
索引及び表を含んだデータベースの前記表における少なくとも１つのレコードを移動するレコード移動処理を実行し、
前記レコード移動処理に伴い、前記索引を更新する索引更新処理を実行し、
前記索引更新処理は、前記レコード移動処理において移動したレコードについて、前記索引における移動前ポインタに移動後ポインタを上書きすることを含み、
前記移動前ポインタは、移動前の格納位置にあるレコードへのポインタであり、
前記移動後ポインタは、移動後の格納位置にあるレコードへのポインタであり、
前記索引は、木構造になった複数のノードを含み、
前記複数のノードのうちの１以上のリーフノードに、キー毎のポインタが格納され、
前記１以上のリーフノードが、キー毎に、
そのキーに対応した移動され得るレコードへのポインタが格納されポインタ順にポインタがソートされない領域である第１の領域と、
そのキーに対応した移動され得ないレコードへのポインタが格納されポインタ順にポインタがソートされている領域である第２の領域と
を有する、
データベース管理方法。
【請求項１２】
以下の（ａ）及び（ｂ）をコンピュータに実行させるコンピュータプログラム、
（ａ）索引及び表を含んだデータベースの前記表における少なくとも１つのレコードを移動するレコード移動処理を実行する、
（ｂ）前記レコード移動処理に伴い、前記索引を更新する索引更新処理を実行する、
前記索引更新処理は、前記レコード移動処理において移動したレコードについて、前記索引における移動前ポインタに移動後ポインタを上書きすることを含み、
前記移動前ポインタは、移動前の格納位置にあるレコードへのポインタであり、
前記移動後ポインタは、移動後の格納位置にあるレコードへのポインタであり、
前記索引は、木構造になった複数のノードを含み、
前記複数のノードのうちの１以上のリーフノードに、キー毎のポインタが格納され、
前記１以上のリーフノードが、キー毎に、
そのキーに対応した移動され得るレコードへのポインタが格納されポインタ順にポインタがソートされない領域である第１の領域と、
そのキーに対応した移動され得ないレコードへのポインタが格納されポインタ順にポインタがソートされている領域である第２の領域と
を有する、
を記録したコンピュータ読取り可能な非一時的な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、データベース管理技術に関する。
【背景技術】
【０００２】
一般に、企業活動において、大量に生じる業務データの活用が求められている。このため、膨大なデータの収集、蓄積及び分析に向け、データをカラム形式で格納する（典型的にはデータをカラム方向に圧縮して格納する）カラムストアＤＢ（データベース）の構築が増加している。【０００３】
データが追加（収集）される都度にその追加されたデータをカラム形式で格納すると、処理時間が増大する。なぜなら、追加されたデータを格納するためには、カラム形式で格納されているデータ群を一旦読み出して伸張し、追加データを加えて圧縮する処理が必要になるからである。この問題は、データの追加頻度が高いほど大きい。【０００４】
このため、収集されたデータをカラム形式で格納するケースでは、一般に、コンバート方式が採用される。コンバート方式によれば、追加されたデータが一時的にロー形式で格納され、ロー形式で複数のデータが蓄積されてから、それら複数のデータがカラム形式で格納される。データの格納形式をロー形式（ロー指向）からカラム形式（カラム指向）へコンバートする処理を、「コンバート処理」と呼ぶことができる。コンバート処理では、データ格納位置が変更される。すなわち、データが、ロー形式の格納位置からカラム形式の格納位置に移動する。【０００５】
索引を用いた検索が知られている。索引は、一般に、検索キーとポインタとを保持する。ポインタは、データの格納位置を示す。コンバート処理が行われると、データが移動するため（データ格納位置が変更されるため）、索引の更新が必要となる。索引の更新方式として、以下の２つの方式がある。【０００６】
（第１の索引更新方式）同一検索キーのポインタをポインタ順にソートする索引管理が知られている。索引において、１以上のリーフノードが、同一検索キーのポインタ集合を保持する。第１の索引更新方式によれば、対象検索キー（移動したデータに対応するポインタに対応した検索キー）を含む全リーフノードの排他ロックが取得され、移動したデータに対応するポインタが更新され、更新後のポインタを含むポインタ集合がポインタ順にソートされ、その後に、上記取得された排他ロックが解除される。【０００７】
（第２の索引更新方式）マッピング索引が知られている（例えば非特許文献１）。第２の索引更新方式によれば、移動したデータについて、マッピング索引に、移動前の位置を示すポインタと移動後の位置を示すポインタとの組であるポインタセットが登録される。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Per-&Aring;ke Larson, Adrian Birka， Eric N. Hanson， Weiyun Huang， Michal Nowakiewicz, Vassilis Papadimos, “Real-Time Analytical Processing with SQL Server”, VLDB2015
【発明の概要】
【発明が解決しようとする課題】
【０００９】
第１の索引更新方式によれば、対象検索キーについて排他ロック状態（排他中）の間、対象検索キーに対応するデータの検索処理といった他処理は中断される。このため、全体として処理性能が低下する。【００１０】
第２の索引更新方式によれば、移動したデータ毎にポインタセットがマッピング索引に登録され、結果として、マッピング索引の容量が増大する。索引は、検索性能向上のために作成される付加的な情報であり、マッピング索引も、付加的な情報であるが、そのような付加的な情報の容量として索引容量（通常の索引の容量とマッピング索引の容量との合計）が増大することは好ましくない。また、マッピング索引は、検索において参照され得るため、マッピング索引の容量が増大すると、検索性能が低下し得る。【００１１】
以上の理由から、カラムストアＤＢ、特に、収集されたデータをカラム形式で格納する環境には、好ましくない。このような課題は、格納形式をロー形式からカラム形式に変更するためのデータ移動に限らず、他の理由でデータ移動が生じるケースについてもあり得る。
【課題を解決するための手段】
【００１２】
計算機が、索引及び表を含んだデータベースの前記表における少なくとも１つのレコードを移動するレコード移動処理を実行する。また、計算機が、レコード移動処理に伴い、索引を更新する索引更新処理を実行する。索引更新処理は、前記レコード移動処理において移動したレコードについて、前記索引における移動前ポインタに移動後ポインタを上書きすることを含む。移動前ポインタは、移動前の格納位置にあるレコードへのポインタである。移動後ポインタは、移動後の格納位置にあるレコードへのポインタである。なお、「計算機」は、１以上の物理計算機であってよく、少なくとも１つの仮想計算機を含んでもよい。
【発明の効果】
【００１３】
レコード移動処理に伴う索引更新処理において索引容量の増大が生じず、且つ、索引言更新処理と並行して検索処理のような他処理が可能である。
【図面の簡単な説明】
【００１４】
【図１】実施例１に係る計算機システムの構成を示す。
【図２】実施例１に係る索引と、その索引に対応した表との一例の模式図（レコード移動前）である。
【図３】実施例１に係る索引と、その索引に対応した表との一例の模式図（レコード移動後）である。
【図４】実施例１に係る索引コンバート処理のフローチャートである。
【図５】実施例１に係る索引検索処理のフローチャートである。
【図６】実施例１に係る索引インサート処理のフローチャートである。
【図７】実施例１に係る索引削除処理フローを示す。
【図８】索引更新処理と索引検索処理との並行実行の一例を示すシーケンス図である。
【図９】ＤＢ容量推移を表す第１レポートの一例を示す。
【図１０】ＤＢ性能挙動を表す第２レポートの一例を示す。
【図１１】実施例２に係る索引と、その索引に対応した表との一例の模式図（レコード移動後）である。
【図１２】実施例２に係る索引インサート処理のフローチャートである。
【図１３】実施例２に係る索引削除処理のフローチャートである。
【発明を実施するための形態】
【００１５】
ＤＢＭＳ（データベース管理システム）へのクエリの発行元としては、ＤＢＭＳの内部のコンピュータプログラムであってよいし、外部のコンピュータプログラムであってよい。例えば、クエリ発行元は、ＤＢＭＳを有するデータベースサーバ（以下、ＤＢサーバ）内で実行されるコンピュータプログラム（例えば、アプリケーションプログラム）であってもよいし、ＤＢサーバに接続されたクライアント計算機等の装置で実行されるコンピュータプログラム（例えば、アプリケーションプログラム）であってもよい。
【００１６】
以下の説明では、「インターフェース部」は、１以上のインターフェースを含む。１以上のインターフェースは、１以上の同種のインターフェースデバイス（例えば１以上のＮＩＣ（Network Interface Card））であってもよいし２以上の異種のインターフェースデバイス（例えばＮＩＣとＨＢＡ（Host Bus Adapter））であってもよい。
【００１７】
また、以下の説明では、「記憶資源」は、１以上のメモリを含む。少なくとも１つのメモリは、揮発性メモリであってもよいし不揮発性メモリであってもよい。記憶資源は、１以上のメモリに加えて、１以上のＰＤＥＶを含んでもよい。「ＰＤＥＶ」は、物理的な記憶デバイスを意味し、典型的には、不揮発性の記憶デバイス（例えば補助記憶デバイス）でよい。ＰＤＥＶは、例えば、ＨＤＤ（Hard Disk Drive）又はＳＳＤ（Solid State Drive）でよい。
【００１８】
また、以下の説明では、「プロセッサ部」は、１以上のプロセッサを含む。少なくとも１つのプロセッサは、典型的には、ＣＰＵ（Central Processing Unit）である。プロセッサは、処理の一部または全部を行うハードウェア回路（例えばＦＰＧＡ（Field-Programmable Gate Array）又はＡＳＩＣ（Application Specific Integrated Circuit））を含んでもよい。
【００１９】
また、以下の説明では、「ｋｋｋ部」の表現にて処理部（機能）を説明することがあるが、処理部は、コンピュータプログラムがプロセッサ部によって実行されることで実現されてもよいし、ハードウェア回路（例えばＦＰＧＡ又はＡＳＩＣ）によって実現されてもよい。プログラムがプロセッサ部によって処理部が実現される場合、定められた処理が、適宜に記憶資源（例えばメモリ）及び／又は通信インターフェイスデバイス（例えば通信ポート）等を用いながら行われるため、処理部はプロセッサ部の少なくとも一部とされてもよい。処理部を主語として説明された処理は、プロセッサ部あるいはそのプロセッサ部を有する装置が行う処理としてもよい。また、プロセッサ部は、処理の一部または全部を行うハードウェア回路を含んでもよい。プログラムは、プログラムソースからプロセッサにインストールされてもよい。プログラムソースは、例えば、プログラム配布計算機または計算機が読み取り可能な記録媒体（例えば非一時的な記録媒体）であってもよい。各処理部の説明は一例であり、複数の処理部が１つの処理部にまとめられたり、１つの処理部が複数の処理部に分割されたりしてもよい。
【００２０】
以下、図面を参照しながら、幾つかの実施例を説明する。なお、以下の実施例では、レコード移動はコンバート処理において生じるが、本発明は、コンバート処理以外の理由でレコードが移動する環境にも適用することができる。
【実施例１】
【００２１】
図１は、実施例１に係る計算機システムの構成を示す。【００２２】
ＤＢサーバ１０１が通信ネットワーク４０３を介して外部ストレージ装置１１８に接続されている。通信ネットワーク４０３を介した通信のプロトコルとしては、例えば、ＦＣ（Fibre Channel）、ＳＣＳＩ（Small Computer System Interface）、又は、ＴＣＰ／ＩＰ（Transmission Control Protocol/Internet Protocol）が採用されてよい。【００２３】
ＤＢサーバ１０１は、計算機、例えば、パーソナルコンピュータ、ワークステーション又はメインフレーム、もしくは、これらのいずれかによって構成される仮想的な計算機（仮想マシン）である。ＤＢサーバ１０１は、ネットワークアダプタ１１９、メモリ１０２、ローカル記憶デバイス１１７及びそれらに接続されたプロセッサ（典型的にはマイクロプロセッサ）１１６を有する。プロセッサ１１６は、コンピュータプログラム、例えば、ＯＳ（Operating  System）１１４と、ＤＢＭＳ１０４と、ＤＢＭＳ１０４にクエリを発行するＡＰ（Application Program）１０３とを実行する。メモリ１０２は、プロセッサ１１６によって実行されるプログラムと、プログラムが使用するデータとを一時的に記憶する。ローカル記憶デバイス１１７は、プログラム、及びプログラムが使用するデータを格納する。ネットワークアダプタ１１９は、通信ネットワーク４０３とＤＢサーバ１０１とを接続する。ＡＰ１０３は、ＤＢサーバ１０１ではなく、通信ネットワーク４０３に接続される図示しない別の計算機で動作してもよい。【００２４】
なお、ＤＢサーバ１０１は、性能面や冗長性の観点から、プロセッサ１１６、メモリ１０２、ローカル記憶デバイス１１７及びネットワークアダプタ１１９のうちの少なくとも１つの要素を複数備えていてもよい。また、ＤＢサーバ１０１は、図示しない入力デバイス（例えば、キーボード及びポインティングデバイス）と表示デバイス（例えば液晶ディスプレイ）とを有してよい。入力デバイスと表示デバイスは一体になっていてもよい。【００２５】
ＤＢサーバ１０１では、ＤＢＭＳ１０４が、ＡＰ１０３から発行されたクエリを実行する。ＤＢＭＳ１０４は、クエリの実行する際に、外部ストレージ装置１１８に格納されたＤＢ１２２に対するＩ／Ｏ要求をＯＳ１１４に発行する。ＯＳ１１４が、ＤＢＭＳ１０４から発行されたＩ／Ｏ要求を、外部ストレージ装置１１８に送信する。【００２６】
外部ストレージ装置１１８は、記憶デバイス群１２１を有する装置である。それに代えて、外部ストレージ装置１１８は、単一の記憶デバイスであってもよい。外部ストレージ装置１１８は、ＤＢサーバ１０１が使用するデータ及びプログラムを記憶する。外部ストレージ装置１１８は、ＤＢサーバ１０１からＩ／Ｏ要求を受信し、Ｉ／Ｏ要求に対応した処理を実行し、処理結果をＤＢサーバ１０１に送信する。【００２７】
外部ストレージ装置１１８は、ネットワークアダプタ１１９、記憶デバイス群１２１及びそれらに接続されたコントローラ１２０を有する。【００２８】
ネットワークアダプタ１１９は、外部ストレージ装置１１８を通信ネットワーク４０３に接続する。【００２９】
記憶デバイス群１２１は、１以上の記憶デバイスを含む。記憶デバイスは、ＰＤＥＶであって、例えば、磁気ディスク、フラッシュメモリ、その他半導体メモリである。記憶デバイス群１２１は、ＲＡＩＤに従い所定のＲＡＩＤレベルでデータを記憶するグループであってもよい。記憶デバイス群１２１の記憶空間に基づいて、論理的な記憶デバイス（論理ボリューム）がＤＢサーバ１０１に提供されてもよい。記憶デバイス群１２１は、ＤＢ１２２を記憶する。【００３０】
コントローラ１２０は、例えば、メモリ及びプロセッサを含む。コントローラ１２０は、ＤＢサーバ１０１からのＩ／Ｏ要求に従って、ＤＢ１２２を記憶した記憶デバイス群１２１にデータを入出力する。例えば、コントローラ１２０は、ＤＢサーバ１０１からの書込み要求に従う書込み対象のデータを記憶デバイス群１２１に格納する。また、ＤＢサーバ１０１からの読出し要求に従う読出し対象のデータを記憶デバイス群１２１から読み出し、そのデータをＤＢサーバ１０１に送信する。【００３１】
なお、外部ストレージ装置１１８は、性能面や冗長性確保の観点から、コントローラ１２０等の要素を複数備えてもよい。【００３２】
ＤＢＭＳ１０４は、業務データを含むＤＢ１２２を管理する。ＤＢ１２２は、１以上の表１２４や索引１２３を含む。表１２４は１以上のレコードの集合であり、レコードは１以上のカラムから構成される。表１２４は、カラム形式で格納された複数のレコードを含む。すなわち、ＤＢ１２２は、カラムストアＤＢであるが、具体的には、表１２４のうちの1以上のレコードがカラム形式で格納されるＤＢである。索引１２３は、表の中の１以上のカラムを対象に作成されるデータ構造であり、当該索引１２３が対象とするカラムを含む選択条件による表へのアクセスを高速化する。例えば、索引１２３は、対象とするカラムの値毎にその値を含む表の中のレコードの位置を示すポインタを保持するデータ構造であり、Ｂ木構造等が用いられる。【００３３】
ＤＢＭＳ１０４は、クエリ受付部１０５、クエリ実行プラン生成部１０６、クエリ実行部１０７、カラムストア管理部１０９及び領域制御部４２７を含む。【００３４】
クエリ受付部１０５は、ＡＰ１０５が発行するクエリを受け付ける。クエリは、例えばＳＱＬで記述される。【００３５】
クエリ実行プラン生成部１０６は、クエリ受付部１０５が受け付けたクエリについて、該クエリを実行するために必要な１以上のＤＢオペレーションを表す情報を有するクエリ実行プランを生成する。クエリ実行プランは、例えば、クエリの実行の際に行うべきＤＢオペレーションについてその実行順序を木構造で定義した情報であり、メモリ１０２に格納される。また、クエリ実行プランは、ＤＢオペレーション毎に、タスクによる実行の際に要するメモリ資源の量を表す情報を含んでよい。例えば、或る表のレコードを読み出すＤＢオペレーションを表す情報を含むクエリ実行プランの場合、そのクエリ実行プランは、該表のレコードをメモリ１０２内に格納するためのメモリ資源量に関する情報を含んでよい。【００３６】
領域制御部４２７は、ＤＢ１２２内のデータを一時的に格納するための記憶領域（ＤＢバッファ）を管理したり、ＤＢ１２２を格納する複数の論理領域（ＤＢページ）を管理したりする。ＤＢバッファは、メモリ１０２上に構築されてもよいし、ローカル記憶デバイス１１７上に構築されてもよい。ＤＢページは、記憶デバイス群１２１に基づく論理空間の一部でよい。【００３７】
クエリ実行部１０７は、クエリ実行プラン生成部１０６が生成したクエリ実行プランに従って、クエリを実行する。クエリ実行部１０７は、レコード検索処理を実行する検索部１１０と、レコードインサート処理を実行するインサート部１１１と、レコード削除処理を実行する削除部１１２と、コンバート処理を実行するコンバート部１１３とを有する。また、クエリ実行部１０７は、索引１２３を管理する索引管理部１３１を有する。索引管理部１３１は、索引検索処理を実行する索引検索部１３２と、索引インサート処理（索引へのエントリのインサート）を実行する索引インサート部１３３と、索引削除処理（索引からのエントリの削除）を実行する索引削除部１３４と、索引更新処理（コンバート処理におけるレコード移動に伴う処理）を実行する索引コンバート部１３５を有する。【００３８】
以上が、計算機システムの概要である。なお、例えばＤＢＭＳ１０４の構成は、一例である。例えば、或る処理部が複数の処理部に分割されたり、複数の処理部の機能を統合した一つの処理部が構築されたりしてもよい。【００３９】
図２は、索引１２３とその索引１２３に対応した表１２４との一例の模式図（レコード移動前）である。【００４０】
表１２４には、７個のレコード２２０〜２２６が格納されている。このうち、レコード２２０及びレコード２２１は、ロー形式で格納されているレコードである。ロー形式で格納されているレコードは、将来的に格納位置が変更され得るレコードの一例である。残りのレコード２２２〜２２６は、カラム形式で格納されているレコードである。カラム形式で格納されているレコードは、格納位置が変更され得ないレコードの一例である。本実施例では、ロー形式で格納されるレコードの格納先も、カラム形式で格納されるレコードの格納先も、記憶デバイス群１２１に基づくＤＢページであるが、ロー形式で格納されるレコードの格納先は、メモリ１０２に基づく一時領域でもよい。なお、ロー形式で格納されるレコードは、移動され得るレコード（格納位置が変更され得るレコード）の一例である。すなわち、本実施例では、例えば、データソース（例えば１以上のセンサ）からデータが収集される都度に、収集された１以上のデータに基づくレコード（例えば収集されたデータが含む値を含んだレコード）がロー形式でＤＢＭＳ１０４により格納され、ロー形式で格納されたレコードがＮ件（Ｎは２以上の整数）以上蓄積された場合に、コンバート部１１３によりコンバート処理が行われる。コンバート処理では、少なくともＮ件のレコードの格納形式が、ロー形式からカラム形式に変換される。【００４１】
索引１２３は、Ｂ木構造の複数のノードを有する。複数のノードは、ルートノード２５１と、リーフノード２５３と、中間ノード２５２とを有する。「ルートノード」は、親ノードを有さないノードである。「リーフノード」は、子ノードを有さないノードである。「中間ノード」は、ルートノード及びリーフノード以外のノードである。【００４２】
各ノードには、検索キー及びポインタセットのうちの少なくとも検索キーが格納される。親ノードにおける検索キーを基に、参照されるべき子ノードが特定される。【００４３】
リーフノード２５３は、１以上の検索キーを保持する。リーフノード２５３には、検索キー毎に、１以上のポインタセットが格納される。「ポインタセット」は、ポインタ数と０以上のポインタとのセットである。ポインタセット内のポインタ数は、そのポインタセット内のポインタの数を表す。図２において、ポインタ数は１桁の整数であり、ポインタは、アルファベット大文字“Ｐ”と１桁以上の整数との組である。以下、ポインタ数及びポインタのような有意な情報要素が存在する領域（ノード内領域）を、便宜上、「スロット」と言う。図２の例によれば、スロット２０４及び２０７の各々に、ポインタ数が格納されており、スロット２０５〜２０６及び２０８〜２１０の各々に、ポインタ（例えばレコードの格納位置のアドレス）が格納されている。具体的には、スロット２０４〜２０６やスロット２０７〜２１０のような連続したスロットに、１つのポインタセットが格納される。すなわち、スロット２０４内のポインタ数“２”が、そのポインタ数を含んだポインタセット内のポインタ（“Ｐ１”及び“Ｐ２”）の数を表す。同様に、スロット２０７内のポインタ数“３”が、そのポインタ数を含んだポインタセット内のポインタ（“Ｐ１０”、“Ｐ１１”及び“Ｐ１３”）の数を表す。なお、本実施例では、ポインタセットはポインタ数を含むが、ポインタセットは必ずしもポインタ数を含まなくてもよい。【００４４】
リーフノード２５３は、検索キー毎にエントリを含む。「エントリ」は、検索キーとその検索キーに対応した１以上のポインタセットとが格納される領域（リーフノードの一部又は全部）を表す便宜上の言葉である。図２の例によれば、リーフノード２５３は、検索キー“１００”に対応したエントリ２６１と、検索キー“１０１”に対応したエントリ２６２とを含む。【００４５】
また、本実施例では、リーフノード２５３は、検索キー毎に、非ソートエントリ部分とソートエントリ部分とを有する。非ソートエントリ部分及びソートエントリ部分の各々には、１以上のポインタセットが格納される。図２の例によれば、検索キー“１００”に対応したエントリ２６１が、ポインタセットが格納されるスロット２０４〜２０６を含んだ非ソートエントリ部分２７１と、ポインタセットが格納されるスロット２０７〜２１０を含んだソートエントリ部分２７２とを含む。同様に、検索キー“１０１”に対応したエントリ２６２が、非ソートエントリ部分２７３と、ソートエントリ部分２７４とを含む。エントリ部分が非ソートエントリ部分であるかソートエントリ部分であるかは、例えば、エントリ部分の所定位置に設定されたフラグの値を参照する等の方法により判別可能である。以下の説明では、検索キー“１００”及び“１０１”のうち、主に、検索キー“１００”を例に取る。なお、後述するように、ＤＢページ単位でロックが取得される場合、非ソートエントリ部分２７１及びソートエントリ部分２７２は異なるＤＢページに格納されることが好ましい。例えば、ソートエントリ部分２７２がＤＢページ＃２に格納されている場合、非ソートエントリ部分２７１は、それとは異なるＤＢページ＃１に格納されていることが好ましい。１以上の第１ＤＢページに、１以上の検索キーに対応した非ソートエントリ部分が集約され、１以上の第２ＤＢページに、１以上の検索キーに対応したソートエントリ部分が集約されていてもよい。【００４６】
ソートエントリ部分２７２に格納されたポインタはポインタ順（例えばポインタにおける整数値が小さい順）にソートされるが、非ソートエントリ部分２７１に格納されたポインタはポインタ順にソートされない。非ソートエントリ部分２７１には、ロー形式で格納されたレコード（検索キー“１００”に対応したレコード）のポインタ“Ｐ１”及び“Ｐ２”、言い換えれば、将来的にレコード格納位置が更新される可能性があるポインタが格納される。ソートエントリ部分２７２には、カラム形式で格納されたレコード（検索キー“１００”に対応したレコード）のポインタ“Ｐ１０”、“Ｐ１１”及び“Ｐ１３”、言い換えれば、将来的にレコード格納位置が更新されないポインタが格納される。【００４７】
図２の例は、上述したように、レコード２２０及び２２１がロー形式で格納されている。言い換えれば、図２の例は、レコード移動前の状態の一例を示す。【００４８】
図３は、索引１２３とその索引１２３に対応した表１２４との一例の模式図（レコード移動後）である。【００４９】
ロー形式で格納されているレコード２２０及び２２１が、コンバート部１１３が行うコンバート処理により、カラム形式で格納されたレコード３０３及び３０４となる。つまり、ロー形式で格納されたレコード２２０及び２２１がそれぞれ移動することで、カラム形式で格納されたレコード３０４及び３０３となる。このように格納形式が変更されても直ちにはレコード２２０及び２２１は削除されない。【００５０】
コンバート部１１３は、レコード２２０に、移動後ポインタ３０１（“Ｐ１６”）が、レコード２２１に移動後ポインタ３０２（“Ｐ１５”）が付加される（関連付けられる）。このようなポインタ追記は、レコード移動後にコンバート部１１３により直ちに行われてよい。なお、移動後ポインタ３０１〜３０２は、レコード毎に明示的に記載してもよく、例えば、先頭レコードのみ明示的に記載し、後続レコードはレコードオフセット加算により算出できるようにしてもよい。「移動後ポインタ」とは、レコードの移動後の格納位置を示すポインタである。一方、後述の「移動前ポインタ」とは、レコードの移動前の格納位置を示すポインタである。移動後ポインタ及び移動前ポインタのいずれも、明示的なポインタで表現されてもよいし、基準の格納位置（例えば先頭レコードの格納位置）からのオフセットで表現されてもよい。【００５１】
コンバート処理（レコード移動処理）が完了した後、索引コンバート部１３５により、索引１２３の更新処理が実行される。具体的には、索引コンバート部１３５は、レコード２２０の移動前ポインタ“Ｐ１”が格納されていたスロット２０５に、移動後ポインタ“Ｐ１６”を上書きする。同様に、索引コンバート部１３５は、レコード２２１の移動前ポインタ“Ｐ２”が格納されていたスロット２０６に、移動後ポインタ“Ｐ１５”を上書きする。【００５２】
これらのポインタ上書き処理は、他の検索処理と並行実行されてよい。例えば、検索部１１０が、検索処理において、索引１２３からポインタ上書き前のポインタ“Ｐ１”を参照した場合、ポインタ“Ｐ１”から特定されるレコード２２０に付加されている移動後ポインタ“Ｐ１６”を取得し、その後に、ポインタ“Ｐ１６”を用いてレコード３０４を参照できる。一方、検索部１１０が、検索処理において、索引１２３からポインタ上書き後のポインタ“Ｐ１６”を参照した場合、そのポインタ“Ｐ１６”を用いてレコード３０４を参照できる。【００５３】
ＤＢＭＳ１０４（例えば削除部１１２）は、コンバート処理（レコード移動処理）の後、それらのレコード２２０及び２２１を削除する。削除は、例えば、移動前のレコード２２０及び２２１を参照する処理が無くなった時点で行われる。【００５４】
図４は、索引更新処理のフローチャートである。索引更新処理は、索引コンバート部１３５により実行される。【００５５】
Ｓ４００１で、索引コンバート部１３５は、索引１２３から、移動対象レコード（例えば２２０）の移動前ポインタ（例えば“Ｐ１”）が格納されているスロットを検索する。【００５６】
Ｓ４００２で、索引コンバート部１３５は、見つかったスロット（例えば移動前ポインタ“Ｐ１”が格納されているスロット）に、移動後ポインタ（例えば“Ｐ１６”）を上書きする。【００５７】
図５は、索引検索処理のフローチャートである。索引検索処理は、索引検索部１３２により実行される。【００５８】
Ｓ５００１で、索引検索部１３２は、索引１２３から、検索対象キー（例えば“１００”）が格納されているエントリ（例えば２６１）を検索する。【００５９】
Ｓ５００２で、索引検索部１３２は、見つかったエントリから全ポインタを取得する。【００６０】
図６は、索引インサート処理のフローチャートである。索引インサート処理は、索引インサート部１３３により実行される。【００６１】
Ｓ６００１で、索引インサート部１３３は、索引１２３から、インサートされたレコードの検索キーが格納されているエントリを検索する。【００６２】
Ｓ６００２で、索引インサート部１３３は、インサートされたレコードがレコード移動される可能性があるか否か（ロー形式で格納されたか否か）を判定する。具体的には、例えば、ＤＢページとして、ロー形式ＤＢページ（ロー形式格納用のＤＢページ）とカラム形式ＤＢページ（カラム形式格納用のＤＢページ）とがあり、索引インサート部１３３は、インサートされたレコードがロー形式ＤＢページに存在するか否かを判定する。【００６３】
Ｓ６００２の判定結果が真の場合（Ｓ６００２：Ｙ）、Ｓ６００３で、索引インサート部１３３は、Ｓ６００１で見つかったエントリのうちの非ソートエントリ部分の最後尾ポインタを特定する。そして、Ｓ６００５で、索引インサート部１３３は、特定した最後尾ポインタの次に、インサートされたレコードの格納位置を示すポインタを追記する。これにより、非ソートエントリ部分のポインタは、常にポインタオフセットにより特定可能となる。例えば、索引検索の最中に、コンバート処理によりポインタが上書きされた場合も、検索処理において、ポインタオフセットによりポインタを一意に特定し、ポインタオフセットをインクリメントしながら検索することで、漏れや重複なく検索処理を実行することが可能となる。【００６４】
一方、Ｓ６００２の判定結果が偽の場合（Ｓ６００２：Ｎ）、Ｓ６００４で、索引インサート部１３３は、Ｓ６００１で見つかったエントリのうちのソートエントリ部分を特定し、特定されたソートエントリ部分から、インサートされたレコードのポインタのインサート位置を特定する。そして、Ｓ６００５で、索引インサート部１３３は、特定された位置に、インサートされたレコードのポインタを追記する。【００６５】
以上の索引インサート処理において、例えば、以下の処理が行われてよい。【００６６】
すなわち、Ｓ６００４で、索引インサート部１３３は、特定されたソートエントリ部分（例えば、その非ソートエントリ部分を含んだＤＢページ）のロック（例えば排他ロック）を取得する。既にロック状態であれば、索引インサート部１３３は、ロック解除を待つ。そのソートエントリ部分がロック状態の間、Ｓ６００５で、索引インサート部１３３は、ポインタを追記し、ソートエントリ部分におけるポインタ集合をポインタ順にソートし、ソート後にロックを解除する。ポインタ追記且つソートが完了するまでロック状態であるため、ロック状態の時間は長い。また、ソートエントリ部分が２以上のＤＢページに格納されている場合、索引インサート部１３３は、それら２以上のＤＢページのロックを取得する。ソートエントリ部分における全てのポインタがソートの対象であるためである。【００６７】
一方、Ｓ６００３で、索引インサート部１３３は、非ソートエントリ部分（例えば、その非ソートエントリ部分を含んだＤＢページ）のロックを取得する。索引インサート部１３３は、ロック状態の間にポインタを追記し、ポインタの追記後にそのロックを解除する。ポインタ追記後にロックが解除されるので、ロック状態の時間が短くて済む。また、非ソートエントリ部分が２以上のＤＢページに格納されていても、その２以上のＤＢページのうち、ロックは、非ソートエントリ部分におけるポインタ追記部分（最後尾）を含んだＤＢページについてのみ取得されればよい。非ソートエントリ部分における全てのポインタがソートされることが無いからである。【００６８】
以上のように、ソートエントリ部分はロック取得（排他）がされ、非ソートエントリ部分はロック取得がされないでよい。ロック取得は、上述のように、ＤＢページ単位で行われてよい。この場合、ソートエントリ部分と非ソートエントリ部分は異なるＤＢページに格納されることが好ましい。【００６９】
図７は、索引削除処理のフローチャートである。索引削除処理は、索引削除部１３４により実行される。【００７０】
Ｓ７００１で、索引削除部１３４は、索引１２３から、削除対象レコードの検索キーが格納されているエントリを検索する。【００７１】
Ｓ７００２で、索引削除部１３４は、削除対象レコードがレコード移動される可能性があるか否か（ロー形式で格納されたか否か）を判定する。Ｓ７００２の判定は、図６のＳ６００２と同様の判定である。【００７２】
Ｓ７００２の判定結果が偽の場合（Ｓ７００２：Ｎ）、Ｓ７００３で、索引削除部１３４は、Ｓ７００１で見つかったエントリのうちのソートエントリ部分を二分探索し、削除対象レコードのポインタが入っているスロットを検索する。Ｓ７００３の二分探索により検索対象スロットが見つかった場合（Ｓ７００４：Ｙ）、索引削除部１３４は、Ｓ７００６で、見つかったスロットに入っているポインタを削除する。Ｓ７００３の二分探索で検索対象スロットが見つらなかった場合（Ｓ７００４：Ｎ）、索引削除部１３４は、Ｓ７００５で、Ｓ７００１で見つかったエントリのうちの非ソートエントリ部分を全探索し、削除対象レコードのポインタが入っているスロットを検索する。そして、索引削除部１３４は、Ｓ７００６で、Ｓ７００５の全探索で見つかったスロットに入っているポインタを削除する。【００７３】
Ｓ７００２の判定結果が真の場合（Ｓ７００２：Ｙ）、索引削除部１３４は、Ｓ７００５で、Ｓ７００１で見つかったエントリのうちの非ソートエントリ部分を全探索し、削除対象レコードのポインタが入っているスロットを検索する。そして、索引削除部１３４は、Ｓ７００６で、Ｓ７００５の全探索で見つかったスロットに入っているポインタを削除する。【００７４】
Ｓ７００２：Ｎの場合、非ソートエントリ部分よりも先にソートエントリ部分からスロットが検索される。ソートエントリ部分からの検索の方が、検索コストが低い（検索速度が速い）からである。【００７５】
図８は、索引更新処理と索引検索処理との並行実行の一例を示すシーケンス図である。【００７６】
索引検索部１３２が、領域制御部１０８に対して検索対象を含んだＤＢページＡの共有ロックを要求することにより（Ｓ８０４）、ＤＢページＡの共有ロックを取得したとする（Ｓ８０５）。ＤＢページＡが共有ロック状態の間に、索引コンバート部１３５が、領域制御部１０８に対して同一のＤＢページＡの排他ロックを要求した場合、排他ロックの取得待ちとなる。共有ロックが解除されてから（Ｓ８０６）、索引コンバート部１３５は、排他ロックを取得できる（Ｓ８１１）。【００７７】
その後、索引検索部１３２が、領域制御部１０８に対してＤＢページＢの共有ロックを要求することにより（Ｓ８０７）、ＤＢページＢの共有ロックを取得したとする（Ｓ８０８）。ＤＢページＢについて索引検索処理の間、索引コンバート部１３５は、排他ロック取得済のＤＢページＡについて索引更新処理を並行実行できる。索引コンバート部１３５は、ＤＢページＡの排他ロックを解除し（Ｓ８１２）、索引検索部１３２が、ＤＢページＢの共有ロックを解除する（Ｓ８０９）。【００７８】
図９は、第１レポート９０１の一例である。【００７９】
第１レポート９０１は、例えばＤＢ管理者向けの情報の一例であり、ＤＢ容量の推移を表す。第１レポート９０１は、カラムストア管理部１０９により表示される。カラムストア管理部１０９は、ＤＢサーバ１０１が有する表示デバイスに第１レポート９０１を表示してもよいし、ＤＢサーバ１０１に接続された遠隔の計算機に第１レポート９０１を表示してもよい（第１レポート９０１の表示用情報をその遠隔の計算機に送信してもよい）。【００８０】
第１レポート９０１は、表１２４の容量９０２と、索引１２３の容量９０３と、容量の推移（例えばグラフ）９０５と、ＤＢ最大容量に達するまでの予測された期間９０４とを含む。第１レポート９０１は、レポート記載形式の一例を示したものであり、レポート記載形式を限定するものではない。第１レポート９０１は、情報が異なる形式で記載されていてもよいし、別の情報が追加で記載されていてもよい。【００８１】
表１２４の容量の推移は、レコードの収集速度（単位時間当たりに追加されるレコード総容量）のような情報に基づきカラムストア管理部１０９により予測される。索引１２３の容量の推移は、表１２４の容量の推移に基づいてカラムストア管理部１０９により予測される。表１２４の容量に基づいて索引１２３の容量を予測できる理由は、本実施例によれば、コンバート処理によって索引１２３の容量が増大しないためである。【００８２】
図１０は、第２レポート１００１の一例である。【００８３】
第２レポート１００１は、例えばＤＢ管理者向けの情報の一例であり、ＤＢ統計情報に基づくＤＢ性能挙動を表す。第２レポート１００１は、カラムストア管理部１０９により表示される。カラムストア管理部１０９は、ＤＢサーバ１０１が有する表示デバイスに第２レポート１００１を表示してもよいし、ＤＢサーバ１０１に接続された遠隔の計算機に第２レポート１００１を表示してもよい（第２レポート１００１の表示用情報をその遠隔の計算機に送信してもよい）。また、第２レポート１００１の形式は、第１レポート９０１と同様、一例でよい。【００８４】
ＤＢ統計情報は、例えば、インサート実行回数１００２、削除実行回数１００３、コンバート実行回数１００４、検索処理中においてインサート処理により待ちが発生した回数１００５、検索処理中において削除処理により待ちが発生した回数１００６、及び、検索処理中においてコンバート処理により待ちが発生した回数１００７が記載されている。【００８５】
図１０の例によれば、コンバート処理により待ちが発生するケースは、スロットにポインタを上書きするときであり、上述したように、検索処理のような他処理をコンバート処理と並行実行することができる。このため、コンバート処理により待ちが発生した回数１００７は、コンバート実行回数１００４に比してかなり低い。なお、もし、コンバート処理により待ちが発生した回数１００７が多い場合、ＤＢページのサイズを小さくすることが、対処の一例である。【００８６】
以上、実施例１によれば、コンバート処理によって索引容量が増大せず、且つ、コンバート処理と並行して同一検索キーについて検索処理が可能である。つまり、索引容量の増大と処理性能の低下の両方を回避することができる。
【実施例２】
【００８７】
実施例２を説明する。その際、実施例１との相違点を主に説明し、実施例１との共通点については説明を省略又は簡略する。【００８８】
図１１は、実施例２に係る索引１２３とその索引１２３に対応した表１２４との一例の模式図（レコード移動後）である。【００８９】
索引１１２３のリーフエントリ１２５３は、検索キー毎にエントリを有するが、エントリは、非ソートエントリ部分を有しソートエントリ部分を有しない。つまり、エントリには、ポインタ順にポイントがソートされる領域が無い。例えば、検索キー“１００”に対応したエントリ１２６１には、ポインタ数“５”が格納されたスロット１１０７と、５つのポインタ“Ｐ１６”、“Ｐ１５”、“Ｐ１０”、“Ｐ１１”及び“Ｐ１３”がそれぞれ格納された５つのポインタ１１０１〜１１０５がある。移動前ポインタ“Ｐ１”及び“Ｐ２”に移動後ポインタ“Ｐ１６”及び“Ｐ１５”がそれぞれ上書きされるが、移動後ポインタ“Ｐ１６”及び“Ｐ１５”を含む上述の５つのポインタは、ポインタ順にソートされない。【００９０】
図１２は、実施例２に係る索引インサート処理のフローチャートである。【００９１】
Ｓ１２００１で、索引インサート部１１３３は、索引１１２３から、インサートされたレコードの検索キーが格納されているエントリを検索する。【００９２】
Ｓ１２００２で、索引インサート部１１３３は、見つかったエントリの最後尾ポインタを特定する。【００９３】
Ｓ１２００３で、索引インサート部１１３３は、特定された最後尾ポインタの次に、インサートされたレコードのポインタを追記する。【００９４】
図１３は、実施例２に係る索引削除処理のフローチャートである。【００９５】
Ｓ１３００１で、索引削除部１１３４は、索引１１２３から、削除対象レコードのキーが格納されているエントリを検索する。【００９６】
Ｓ１３００２で、索引インサート部１１３３は、Ｓ１３００１で見つかったエントリ（ポインタ群）を全探索し、削除対象レコードのポインタが入っているスロットを検索する。【００９７】
Ｓ１３００３で、索引インサート部１１３３は、Ｓ１３００２の全探索により見つかったスロットに入っているポインタを削除する。【００９８】
以上、実施例２でも、コンバート処理によって索引容量が増大せず、且つ、コンバート処理と並行して同一検索キーについて検索処理が可能である。また、実施例２によれば、常に全探索が必要なため実施例１よりも削除処理量が増えるが、実施例１に比べて索引構造の簡略化が可能である。また、分析のようなケースでは、複数のレコードをまとめて削除することが多く、個別にレコードを削除するケースは少ないと考えられるので、そのようなケースでは、削除処理量が増えることは格別のデメリットにはならないと考えられる。【００９９】
以上、幾つかの実施例を説明したが、本発明は、それらの実施例に限定されるものでなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。【０１００】
例えば、実施例１及び２のいずれも、ダイナミックミーティングのように会議中にオンデマンド分析を行って意志決定時間を短縮するケースに適用することが期待できる。
【図１】
0006680871.tif 000002
【図２】
0006680871.tif 000003
【図３】
0006680871.tif 000004
【図４】
0006680871.tif 000005
【図５】
0006680871.tif 000006
【図６】
0006680871.tif 000007
【図７】
0006680871.tif 000008
【図８】
0006680871.tif 000009
【図９】
0006680871.tif 000010
【図１０】
0006680871.tif 000011
【図１１】
0006680871.tif 000012
【図１２】
0006680871.tif 000013
【図１３】
0006680871.tif 000014