(57)【要約】  データベースが、複数のデータブロックを含む。複数のデータブロックの各々が、そのデータブロックに対応した１以上のレコードに記録されている複数のカラム値が格納されている複数のデータページを含む。複数のデータページの各々には、そのデータページに対応した１つのカラムにおける２以上のカラム値が格納されている。データベースサーバは、複数のデータブロックから、データブロックを選択し、選択されたデータブロックから、スキャン対象のデータページを特定する。
2016166789.tif 000002
【特許請求の範囲】
【請求項１】
クエリを受け付けるクエリ受付部と、
前記クエリを実行し、複数のレコードを有するデータベースに対するＩ／Ｏ要求を前記クエリの実行において発行するクエリ実行部と
を有し、
前記データベースが、複数のデータブロックを含み、
前記複数のデータブロックの各々が、そのデータブロックに対応した１以上のレコードに記録されている複数のカラム値が格納されている複数のデータページを含み、
前記複数のデータページの各々には、そのデータページに対応した１つのカラムにおける２以上のカラム値が格納されており、
前記クエリ実行部は、
（Ａ）前記複数のデータブロックから、データブロックを選択し、
（Ｂ）（Ａ）で選択されたデータブロックから、スキャン対象のデータページを特定する、
データベース管理システム。
【請求項２】
前記複数のデータブロックの各々について、そのデータブロックに関連付けられた管理情報があり、
前記管理情報は、ディレクトリ情報を含み、
前記ディレクトリ情報は、そのディレクトリ情報を含む管理情報に対応したデータブロックに含まれる複数のデータページの各々について、そのデータページに対応したカラムのＩＤと、そのデータページにおける２以上のカラム値が記録されている１以上のレコードのＩＤを表し、
前記クエリ実行部は、（Ｂ）において、（Ａ）で選択したデータブロックに対応した管理情報を参照して、前記スキャン対象のデータページを特定する、
請求項１記載のデータベース管理システム。
【請求項３】
前記複数のデータブロックの各々が、そのデータブロックに対応する管理情報の少なくとも一部を含んでいる、
請求項２記載のデータベース管理システム。
【請求項４】
前記複数のデータブロックの各々が、そのデータブロックに対応する管理情報の全てを含んでおり、
前記クエリ実行部は、前記データベースの少なくとも一部が格納されている外部ストレージ装置に対し、（Ａ）で選択されたデータブロックの読出し要求を発行することにより、その選択されたデータブロックを前記外部ストレージ装置から読み出し、読み出されたデータブロック内の複数のデータページ及び管理情報をメモリ領域に格納し、
前記クエリ実行部は、（Ｂ）において、前記メモリ領域に格納されている管理情報を参照し、前記メモリ領域に格納されている複数のデータページから、前記スキャン対象のデータページを特定する、
請求項３記載のデータベース管理システム。
【請求項５】
前記クエリ実行部は、１以上のスキャン対象のデータページの各々について、逐次に、
メモリ領域を確保し、
データページを、確保されたメモリ領域に読み出し、
そのデータブロックの処理が完了した場合、前記確保されたメモリ領域を解放する、
請求項１記載のデータベース管理システム。
【請求項６】
前記複数のデータブロックの各々について、そのデータブロックに対応する管理情報のうちの少なくともディレクトリ情報が、前記データベースの少なくとも一部が格納されている外部ストレージ装置の連続した領域に格納されており、
前記クエリ実行部が、（Ａ）で選択したデータブロックに対応する管理情報におけるディレクトリ情報の１つの読出し要求を発行することにより、そのディレクトリ情報を前記外部ストレージ装置から読み出し、
（Ｂ）において参照されるディレクトリ情報は、前記読み出されたディレクトリ情報である、
請求項２記載のデータベース管理システム。
【請求項７】
１以上のデータブロックの各々について、そのデータブロック内の１以上のデータページの各々に、２以上のカラム値が圧縮されたデータである圧縮データが格納されており、
前記１以上のデータブロックの各々について、そのデータブロックに関連付いている管理情報が、そのデータブロック内の各データページについて、圧縮方式を表す情報を含み、
前記クエリ実行部は、（Ｂ）において、（Ａ）で選択されたデータブロックに対応した管理情報を参照して、前記スキャン対象のデータページに対応する圧縮方式を特定し、特定された圧縮方式に従い、前記スキャン対象のデータページ内のデータを処理する、
請求項２記載のデータベース管理システム。
【請求項８】
データロード部を更に有し、
前記データベースの構成は、前記データロード部により構築された構成であり、
前記データロード部が、格納先とするデータブロックの各々について、
（Ｐ）１以上のレコードを決定し、
（Ｑ）（Ｐ）で決定された１以上のレコードに記録されている複数のカラム値の各々を、そのカラム値を含むカラムに対応したデータページに格納する、
請求項１記載のデータベース管理システム。
【請求項９】
（Ｐ）において決定されたレコードの数は、格納先のデータブロックに格納可能なレコードの数のうちの最大数である、
請求項８記載のデータベース管理システム。
【請求項１０】
前記データロード部が、データページ毎に、（Ｐ）において決定された１以上のレコードに記録されている複数のカラム値のうちのそのデータページに対応したカラムにおける２以上のカラム値を、そのデータページに対応した圧縮方式に従って格納するようになっている、
請求項９記載のデータベース管理システム。
【請求項１１】
前記データロード部が、（Ｐ）において、
（ｐ１）レコードを取得し、
（ｐ２）そのレコードと既に取得済のレコードとを含んだデータの格納後のサイズが、格納先のデータブロックのサイズ以下か否かを判断し、
（ｐ３）（ｐ２）の判断結果が肯定の場合、更に（ｐ１）及び（ｐ２）を実行し、
（ｐ２）の判断結果が否定の場合、前記データロード部が、（Ｑ）を実行する、
請求項１０記載のデータベース管理システム。
【請求項１２】
前記データロード部が、（Ｑ）において、格納先のデータブロックに関連付ける管理情報を生成し、
前記管理情報は、ディレクトリ情報を含み、
前記ディレクトリ情報は、そのディレクトリ情報を含む管理情報に対応したデータブロックに含まれる複数のデータページの各々について、そのデータページに対応したカラムのＩＤと、そのデータページにおける２以上のカラム値が記録されている１以上のレコードのＩＤを表し、
前記クエリ実行部は、（Ｂ）において、（Ａ）で選択したデータブロックに対応した管理情報を参照して、前記スキャン対象のデータページを特定する、
請求項８記載のデータベース管理システム。
【請求項１３】
前記クエリ実行部が、前記クエリの実行において、
（Ｃ）前記スキャン対象のデータページについて、前記クエリで指定されたカラム毎に中間データの生成及び出力を行い、
前記クエリで指定された各カラムについて、前記中間データは、そのカラムにおけるカラム値にそれぞれ対応した値を有し、
各フラグは、そのフラグに対応した値が、前記クエリで指定されている条件に適合しているか否かに応じた値である、
請求項１記載のデータベース管理システム。
【請求項１４】
クエリを実行し、複数のレコードを有するデータベースに対するＩ／Ｏ要求を前記クエリの実行において発行するプロセッサと、
前記Ｉ／Ｏ要求に従うＩ／Ｏ対象のデータが少なくとも一時格納されるメモリと
を有し、
前記データベースが、複数のデータブロックを含み、
前記複数のデータブロックの各々が、そのデータブロックに対応した１以上のレコードに記録されている複数のカラム値が格納されている複数のデータページを含み、
前記複数のデータページの各々には、そのデータページに対応した１つのカラムにおける２以上のカラム値が格納されており、
前記プロセッサは、
（Ａ）前記複数のデータブロックから、データブロックを選択し、
（Ｂ）（Ａ）で選択されたデータブロックから、スキャン対象のデータページを特定する、
データベースサーバ。
【請求項１５】
（Ｘ）クエリを受け付け、
（Ｙ）前記クエリの実行において、複数のレコードを有するデータベースに対するＩ／Ｏ要求を発行し、
前記データベースが、複数のデータブロックを含み、
前記複数のデータブロックの各々が、そのデータブロックに対応した１以上のレコードに記録されている複数のカラム値が格納されている複数のデータページを含み、
前記複数のデータページの各々には、そのデータページに対応した１つのカラムにおける２以上のカラム値が格納されており、
（Ｙ）において、
（Ａ）前記複数のデータブロックから、データブロックを選択し、
（Ｂ）（Ａ）で選択されたデータブロックから、スキャン対象のデータページを特定する、
データベース管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、データベース管理に関する。
【背景技術】
【０００２】
企業活動において、大量に生じる業務データの活用は不可欠になっている。大量の業務データを効率良く蓄積及び解析するためのデータベース（以下、「ＤＢ」）として、カラムストアデータベース（以下、「カラムストアＤＢ」）が知られている。一般に、データベースは、表を含み、表は、複数のローを有し、各ローに、複数のデータ項目（カラム）にそれぞれ対応した複数の値（カラム値）が記録されている。カラムストアＤＢでは、複数のレコード内の複数のカラム値が、カラム毎に、カラムに対応した領域に格納される。カラムストアＤＢは、サーバの主記憶メモリに格納することも可能である。しかし、主記憶メモリは、通常、外部ストレージ装置と比較して単位容量当たり価格（例えばビットコスト）が高い。このため、大規模データを扱うシステムでは、一般に、カラムストアＤＢは、外部ストレージ装置に格納される。【０００３】
上述したように、カラムストアＤＢでは、複数のレコード内の複数のカラム値が、カラム毎に、カラムに対応した領域に格納される。このため、外部ストレージ装置から分析対象のカラムに対応したカラム値のみ読み出すことで、ＤＢ全体を読み出す方法と比較して、読み出されるデータの量を削減できる利点がある。しかし、一方で、１以上のカラムにそれぞれ対応した１以上のカラム値を組み合わせて元のレコードを再構成する処理が発生する（１つの「レコード」は、１つのローと同じ構成であることもあれば、ローの一部のカラム値で構成されることもある）。大規模データを扱うシステムでは、膨大な数のレコードが扱われる。問合せ（クエリ）を短時間で処理するために、レコード再構成処理を高速に実現することが重要である。【０００４】
レコード再構成処理を高速に実現するためには、レコード再構成処理におけるスキャン対象領域を削減できることが必要である。【０００５】
特許文献１には、例えば以下の技術が開示されている。ＰＡＸ（Partition Attributes Across）ページが用意され、ＰＡＸページが、複数のカラムにそれぞれ対応した複数のミニページに分割される（例えば、図６Ａ、図６Ｂ）。ローストアページ内の複数のレコードにおける複数のカラム値が、カラム毎に、ミニページに格納される。特許文献１の技術によると、ローストアページ内の全てのカラム値が、カラム毎に、そのカラムに対応したミニページに格納される。１レコードのデータは１つのＰＡＸページ内に全て格納されているため、再構成対象レコードに必要なカラム値が複数ページにわたって格納されることが生じない。つまり、１レコードの１ページ内での再構成（復元）が保証されている。【０００６】
特許文献２には、例えば以下の技術が開示されている。各カラムがデータファイルに格納され、各データファイル（カラム）が、複数のブロックに分割される。カラム毎に、ポジションインデックスが用意される（図５及び図６）。各ポジションインデックスに、ブロック毎の位置（開始位置及びファイルオフセット）が記録されている。特許文献２の技術によると、処理対象カラムに対応したポジションインデックスを参照して、処理対象カラムに対応したブロック集合（データファイル）から、再構成処理対象レコードのカラム値を含むブロックを特定できる。このため、ブロック集合全体をスキャンする方法と比較してスキャン対象領域を削減することが可能である。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】ＵＳ２０１０／０２０５３５１
【特許文献２】ＵＳ２０１１／００１６１５７
【発明の概要】
【発明が解決しようとする課題】
【０００８】
特許文献１では、カラム単位（ミニページ単位）でのデータ処理を行うが、読み出しは一般にページ単位で行われるため、スキャン対象領域の削減ができないが、特許文献２では、カラム部分単位（ブロック単位）での読み出しのため、スキャン対象領域の削減が可能である。【０００９】
一方、特許文献１では、１つのＰＡＸページ内でのレコードの再構成が保証されている。しかし、特許文献２では、レコードの再構成は保証されていない。なぜなら、各ブロックに格納されているカラム値の数が同じとは限らないからである。例えば、２つのデータファイルからそれぞれ２つのブロックを読み出しても、再構成対象レコードに必要なカラム値が無いこともあり得る。【００１０】
このため、特許文献１及び２の両方の技術を組み合わせても、レコード再構成の保証とレコード再構成処理の高速化（スキャン対象領域の削減）の両方を実現することはできない。
【課題を解決するための手段】
【００１１】
データベースが、複数のデータブロックを含む。複数のデータブロックの各々が、そのデータブロックに対応した１以上のレコードに記録されている複数のカラム値が格納されている複数のデータページを含む。複数のデータページの各々には、そのデータページに対応した１つのカラムにおける２以上のカラム値が格納されている。データベースサーバは、複数のデータブロックから、データブロックを選択し、選択されたデータブロックから、スキャン対象のデータページを特定する。
【発明の効果】
【００１２】
レコード再構成の保証とレコード再構成処理の高速化（スキャン対象領域の削減）の両方を実現できる。
【図面の簡単な説明】
【００１３】
【図１】図１は、実施例１に係る計算機システムの構成例を示す。
【図２】図２は、実施例１に係る表の一例を示す。
【図３】図３は、実施例１に係るデータブロックの一例を示す。
【図４】図４は、実施例１に係るクエリの一例を示す。
【図５】図５は、実施例１に係る中間データの一例を示す。
【図６】図６は、実施例１に係るデータロード処理の流れの一例を示す。
【図７】図７は、実施例１に係るレコード格納処理の流れの一例を示す。
【図８】図８は、実施例１に係るクエリ実行処理の流れの一例を示す。
【図９】図９は、実施例２に係る格納データの一例を示す。
【図１０】図１０は、実施例３に係るクエリ実行処理の流れの一例を示す。
【図１１】図１１は、実施例１に係るクエリ実行処理の流れの別の一例を示す。
【図１２】図１２は、実施例１に係る索引の一例を示す。
【図１３】図１３は、実施例１に係るＤＢ構成の概要の一例を示す。
【発明を実施するための形態】
【００１４】
以下、図面を参照しながら、幾つかの実施例を説明する。なお、以下の説明により本発明が限定されるものではない。また、以下の説明では、データベースを「ＤＢ」、データベース管理システムを「ＤＢＭＳ」と言う。ＤＢサーバは、例えばＤＢＭＳを実行するサーバである。ＤＢＭＳに対するクエリの発行元は、ＤＢＭＳの外部のコンピュータプログラム（例えばアプリケーションプログラム）で良い。外部のコンピュータプログラムは、ＤＢサーバ内で実行されるプログラムでも良いし、ＤＢサーバに接続された装置（例えばクライアント計算機）で実行されるプログラムでも良い。
【００１５】
また、以下の説明では、要素の識別情報として、ＩＤ（例えば番号）が使用されるが、それに代えて又は加えて他種の識別情報が使用されてもよい。
【００１６】
また、以下の説明では、同種の要素を区別しないで説明する場合には、参照符号又は参照符号における共通番号を使用し、同種の要素を区別して説明する場合は、その要素の参照符号を使用又は参照符号に代えてその要素に割り振られたＩＤを使用することがある。
【００１７】
また、以下の説明では、Ｉ／Ｏ（Input/Output）要求は、書込み要求又は読出し要求であり、アクセス要求と呼ばれてもよい。
【００１８】
また、以下の説明では、「プログラム」を主語として処理を説明する場合があるが、プログラムは、プロセッサ（例えばＣＰＵ（Central  Processing  Unit））によって実行されることで、定められた処理を、適宜に記憶部（例えばメモリ）及び／又はインターフェースデバイス（例えば通信ポート）等を用いながら行うため、処理の主語がプロセッサとされてもよい。プログラムを主語として説明された処理は、プロセッサあるいはそのプロセッサを有する装置又はシステムが行う処理としてもよい。また、プロセッサは、処理の一部または全部を行うハードウェア回路を含んでもよい。プログラムは、プログラムソースから計算機のような装置にインストールされてもよい。プログラムソースは、例えば、プログラム配布サーバまたは計算機が読み取り可能な記憶メディアであってもよい。プログラムソースがプログラム配布サーバの場合、プログラム配布サーバはプロセッサ（例えばＣＰＵ）と記憶部を含み、記憶部はさらに配布プログラムと配布対象であるプログラムとを記憶してよい。そして、プログラム配布サーバのプロセッサが配布プログラムを実行することで、プログラム配布サーバのプロセッサは配布対象のプログラムを他の計算機に配布してよい。また、以下の説明において、２以上のプログラムが１つのプログラムとして実現されてもよいし、１つのプログラムが２以上のプログラムとして実現されてもよい。
【実施例１】
【００１９】
図１３は、実施例１に係るＤＢ１８０構成の概要の一例を示す。【００２０】
ＤＢ１８０は、例えば、索引と表を含み、ＤＢ１８０のうちの少なくとも表が、複数のデータブロック３００を含む。複数のデータブロック３００の各々が、そのデータブロック３００に対応した１以上のレコードに記録されている複数のカラム値が格納されている複数のデータページ１３０２を含む。複数のデータページ１３０２の各々には、そのデータページ１３０２に対応した１つのカラムにおける２以上のカラム値が格納されている。【００２１】
ＤＢサーバ（ＤＢＭＳ）は、クエリの実行において、複数のデータブロック３００から、データブロック３００を選択し、選択されたデータブロック３００から、スキャン対象のデータページ１３０２を特定する。【００２２】
データブロック３００が、１以上のレコードに対応しており、１レコードの再構成に必要なデータを全て保持している。このため、レコードの再構成が保証されている。また、データブロック３００内の各データページ１３０２は、そのデータページ１３０２に対応した１つのカラムにおける２以上のカラム値が格納されており、データベースサーバは、選択されたデータブロック３００から、スキャン対象のデータページ１３０２を特定する。このため、レコード再構成処理の高速化（スキャン対象領域の削減）を実現できる。つまり、レコード再構成の保証とレコード再構成処理の高速化の両方を実現できる。【００２３】
このようなＤＢ構成は、ＤＢサーバ（ＤＢＭＳ）により構築可能である。例えば、ＤＢサーバ（ＤＢＭＳ）は、ＤＢ格納領域を一定サイズの領域（データページ１３０２）に分割し、更に、連続領域にある複数個のデータページ１３０２を纏めて一定サイズの領域（データブロック３００）を構成する。ＤＢサーバ（ＤＢＭＳ）は、レコードをカラム毎に分割してＤＢ１８０に格納する場合、１以上のレコードの各々について、その１レコードを構成する全てのカラム値を、同一データブロック３００に格納する。【００２４】
レコード再構成の保証とレコード再構成処理の高速化の両方を実現するための別の方法として、以下の一比較例が考えられる。すなわち、上述したＰＡＸページ内の各ミニページが、一定サイズの領域（以下、セグメント）に分割される。ミニページ毎に、セグメントとその位置との対応関係を表す情報を含んだ管理情報（例えば上述したポジションインデックス）が関連付けられる。ＰＡＸページは、特定のレコードに対応しており、ポジションインデックスを参照することによりスキャン対象のセグメントの特定が可能であると考えられる。このため、この比較例によれば、レコード再構成の保証とレコード再構成処理の高速化の両方を実現することが可能であると考えられる。【００２５】
しかし、カラム値のサイズは、カラム（データ項目）によって異なる。例えば、４桁程度のＩＤを示すカラム値と、人間の住まいの住所を示すカラム値とでは、サイズが異なる。このため、比較例では、ミニページ領域毎に、空き領域が発生するおそれがある。つまり、容量効率が低いと考えられる。この課題は、特に、２以上のカラム値の単位で圧縮が行われる場合は、一層大きいと考えられる。なぜなら、カラム値の内容や圧縮方式によって圧縮率が異なるからである。【００２６】
本実施例によれば、図１３に示すように、データブロック３００においてデータページ１３０２が連続しているので、比較例のような課題は生じにくい。なお、本実施例では、カラムによって、カラムに対応するデータページの数が異なる（図１３の例では、カラム１に対応したデータページ数は２であるが、カラム２に対応したデータページ数は４である）。なぜなら、上述したように、データページのサイズは一定であるが、カラム値は、カラムによって異なるためである。また、少なくとも１つのカラムについて圧縮が採用される場合、圧縮後のカラム値のサイズは、圧縮の有無等を含む圧縮方式によって異なるからである。【００２７】
ところで、大規模データを扱うシステムにおいて、比較例の技術が採用されると、単位領域が、ページを分割することにより得られた領域（ミニページ）を更に分割することにより得られたセグメントであり、管理情報の総サイズがかなり大きくなるおそれがある。このため、Ｉ／Ｏ性能（例えば読出し性能）の大幅な低下を引き起こすおそれがある。具体的には、例えば、小規模データを扱うシステムにおいては、管理情報の総サイズは小さく、故に、主記憶メモリ上に全てのミニページの管理情報を格納できると考えられる。しかし、ペタバイト級やエクサバイト級の大規模データを扱うシステムでは、管理情報の総サイズがテラバイト級やペタバイト級に増大し、全てのミニページの管理情報を主記憶メモリに格納することは困難であると考えられる。また、比較例の技術において、ページ毎に空き領域が発生することを無くすために、セグメント指定に代えてミニページオフセット指定を採用することが考えられるが、そうすると、管理情報のサイズが一層大きくなる。これらの場合、少なくとも一部のミニページの管理情報を外部ストレージ装置に格納する必要がある。そのため、管理情報への参照が発生する都度に外部ストレージ装置に対して管理情報の読出し要求を発行する必要が生じ得る。結果として、データ読出し待ち時間が発生し、処理時間が増大することになる。【００２８】
本実施例では、管理情報１３０３が、複数のデータブロック３００の各々に関連付けられる。管理情報１３０３は、ディレクトリ情報を含む。ディレクトリ情報は、そのディレクトリ情報を含む管理情報１３０３に対応したデータブロック３００に含まれる複数のデータページ１３０２の各々について、そのデータページ１３０２に対応したカラムのＩＤと、そのデータページ１３０２における２以上のカラム値が記録されている１以上のレコードのＩＤを表す。ＤＢサーバ（ＤＢＭＳ）は、選択したデータブロック３００に対応した管理情報１３０３を参照して、スキャン対象のデータページ１３０２を特定する。【００２９】
管理情報１３０３は、ディレクトリ情報以外の情報（例えばヘッダ情報）を含んでよい。１以上のデータブロック３００の各々について、管理情報１３０３の少なくとも一部が、そのデータブロック３００に含まれてもよい。例えば、管理情報１３０３の全てが、その管理情報１３０３に対応したデータブロック３００に含まれていてよい。それにより、データブロック３００をデータソース（例えば外部ストレージ装置）から主記憶メモリに読み出すことで、データブロック３００内の複数のデータページ１３０２と共に管理情報１３０３も主記憶メモリ（例えばワーク領域）に格納されることになる。なお、図１３の例示の通り、管理情報１３０３の少なくとも一部（例えば全部）が、データブロック３００の外に存在してもよい。【００３０】
１以上のデータブロック３００の各々について、そのデータブロック３００内の１以上のデータページ１３０２の各々に、２以上のカラム値が圧縮されたデータである圧縮データが格納されてよい。その１以上のデータブロック３００の各々について、そのデータブロック３００に関連付いている管理情報１３０３が、そのデータブロック３００内の各データページ１３０２について、圧縮方式を表す情報を含んでよい。圧縮方式を表す情報は、管理情報１３０３において、ディレクトリ情報、ヘッダ情報又は他の情報に含まれてよい。ＤＢサーバ（ＤＢＭＳ）は、選択されたデータブロック３００に対応した管理情報１３０３を参照して、スキャン対象のデータページ１３０２を特定すると共に、そのデータページ１３０２に対応する圧縮方式を特定できる。ＤＢサーバ（ＤＢＭＳ）は、特定された圧縮方式に従い、スキャン対象のデータページ１３０２内のデータを処理（例えば伸張）できる。圧縮方式は、例えば、圧縮の有無と、圧縮有りの場合は圧縮方法（例えば圧縮アルゴリズム）とを表してよい。【００３１】
以下、実施例１を詳細に説明する。【００３２】
図１は、実施例１に係る計算機システムの構成例を示す。【００３３】
ＤＢサーバ１００が通信ネットワーク４０３を介して外部ストレージ装置４０２に接続されている。通信ネットワーク４０３を介した通信のプロトコルとしては、例えば、ＦＣ（Fibre  Channel）、ＳＣＳＩ（Small  Computer  System  Interface）、又は、ＴＣＰ／ＩＰ（Transmission  Control  Protocol／Internet  Protocol）が採用されて良い。【００３４】
ＤＢサーバ１００は、計算機、例えば、パーソナルコンピュータ、ワークステーション又はメインフレーム、もしくは、これらのいずれかによって構成される仮想的な計算機（仮想マシン）である。ＤＢサーバ１００は、ネットワークアダプタ１５５、メモリ１０５、ローカル記憶デバイス１６５及びそれらに接続されたプロセッサ（典型的にはマイクロプロセッサ）１６０を有する。プロセッサ１６０は、コンピュータプログラム、例えば、ＯＳ（Operating  System）１４５と、ＤＢＭＳ４１２と、ＤＢＭＳ４１２にクエリを発行するＡＰ（Application  Program）１１０とを実行する。メモリ１０５は、主記憶メモリの一例であり、プロセッサ１６０によって実行されるプログラムと、プログラムが使用するデータとを一時的に記憶する。ローカル記憶デバイス１６５は、プログラム、及びプログラムが使用するデータを格納する。ネットワークアダプタ１５５は、通信ネットワーク４０３とＤＢサーバ１００とを接続する。ＡＰ１１０は、ＤＢサーバ１００ではなく、通信ネットワーク４０３に接続される図示しない別の計算機で動作しても良い。【００３５】
なお、ＤＢサーバ１００は、性能面や冗長性の観点から、プロセッサ１６０、メモリ１０５、ローカル記憶デバイス１６５及びネットワークアダプタ１５５のうちの少なくとも１つの要素を複数備えていても良い。また、ＤＢサーバ１００は、図示しない入力デバイス（例えば、キーボード及びポインティングデバイス）と表示デバイス（例えば液晶ディスプレイ）とを有して良い。入力デバイスと表示デバイスは一体になっていても良い。【００３６】
ＤＢサーバ１００では、ＤＢＭＳ４１２が、ＡＰ１１０から発行されたクエリを実行し、そのクエリの実行に伴い、外部ストレージ装置４０２に格納されたＤＢ１８０に対するＩ／Ｏ要求をＯＳ１４５に発行する。ＯＳ１４５が、ＤＢＭＳ４１２から発行されたＩ／Ｏ要求を、外部ストレージ装置４０２に送信する。【００３７】
外部ストレージ装置４０２は、本実施例では、ディスクアレイ装置のような、複数の記憶デバイスを含む記憶デバイス群１７５を有する装置であるが、それに代えて、単一の記憶デバイスであっても良い。外部ストレージ装置４０２は、ＤＢサーバ１００が使用するデータ及びプログラムを記憶する。外部ストレージ装置４０２は、ＤＢサーバ１００に対する二次記憶装置（第２の記憶デバイス）の一例である。外部ストレージ装置４０２は、ＤＢサーバ１００からＩ／Ｏ要求を受信し、Ｉ／Ｏ要求に対応した処理を実行し、処理結果をＤＢサーバ１００に送信する。【００３８】
外部ストレージ装置４０２は、ネットワークアダプタ１７１、記憶デバイス群１７５及びそれらに接続されたコントローラ１７２を有する。【００３９】
ネットワークアダプタ１７１は、外部ストレージ装置４０２を通信ネットワーク４０３に接続する。【００４０】
記憶デバイス群１７５は、１つ以上の記憶デバイスを含む。記憶デバイスは、不揮発性の記憶媒体であって、例えば、磁気ディスク、フラッシュメモリ、その他半導体メモリがある。記憶デバイス群１７５は、ＲＡＩＤ（Redundant  Array  of  Independent  Disks）に従い所定のＲＡＩＤレベルでデータを記憶するグループであっても良い。記憶デバイス群１７５の記憶空間に基づく論理的な記憶デバイス（論理ボリューム）がＤＢサーバ１００に提供されても良い。記憶デバイス群１７５は、ＤＢ１８０を記憶する。【００４１】
コントローラ１７２は、例えば、メモリ及びプロセッサを含んでおり、ＤＢサーバ１００からのＩ／Ｏ要求に従って、ＤＢ１８０を記憶した記憶デバイス群１７５にデータを入出力する。例えば、コントローラ１７２は、ＤＢサーバ１００からの書込み要求に従う書込み対象のデータを記憶デバイス群１７５に格納したり、ＤＢサーバ１００からの読出し要求に従う読出し対象のデータを記憶デバイス群１７５から読み出し、そのデータをＤＢサーバ１００に送信したりする。【００４２】
なお、外部ストレージ装置４０２は、性能面や冗長性確保の観点から、コントローラ１７２等の要素を複数備えても良い。【００４３】
ＤＢＭＳ４１２は、業務データを含んだＤＢ１８０を管理する。ＤＢ１８０は、１以上の表１８２を含み、更に１以上の索引を含んでよい。表１８２は、１以上のロー（レコード）の集合であり、レコードは１以上のカラムから構成される。少なくとも表１８２が、複数のデータブロック３００で構成されてよい。索引１８１は、表１８２の１以上のカラム等を対象として生成されるデータ構造であり、当該索引１８１が対象とするカラム等を含む選択条件による表１８２へのアクセスを高速化するためのものである。例えば、索引１８１は、対象とするカラムのカラム値毎に、表１８２の中で当該値を含むレコードを特定するための情報を保持するデータ構造である。データ構造としては、例えばＢ木等が用いられる。レコードを特定するための情報としては、物理アドレスや論理的なローＩＤ等が用いられることがある。【００４４】
ＤＢＭＳ４１２は、クエリ受付部１２０、クエリ実行プラン生成部１２５、データロード部１３０、クエリ実行部１３５及びＤＢバッファ管理部１４０を含む。【００４５】
クエリ受付部１２０は、ＡＰ１１０のようなクエリ発行元が発行するクエリを受け付ける。クエリは、例えばＳＱＬ（Structured  Query  Language）で記述されている。【００４６】
クエリ実行プラン生成部１２５は、クエリ受付部１２０が受け付けたクエリについて、当該クエリを実行するために必要な１つ以上のＤＢオペレーションを有するクエリ実行プランを生成する。クエリ実行プランは、例えば、クエリの実行の際に行うべきＤＢオペレーションの実行順序を木構造で定義した情報であり、メモリ１０５に格納される。【００４７】
データロード部１３０は、上述した複数のデータブロック３００を含んだＤＢ１８０を構築する。データロード部１３０は、ディレクトリ情報生成部１３１を有し、ディレクトリ情報生成部１３１が、管理情報１３０３のうちの少なくともディレクトリ情報を生成する。【００４８】
クエリ実行部１３５は、クエリ受付部１２０が受け付けたクエリを実行し、実行結果をクエリ発行元に返す。具体的には、例えば、クエリ実行部１３５は、クエリ実行プラン生成部１２５が生成したクエリ実行プランに従って、クエリ実行プランに含まれる情報であるＤＢオペレーションを実行する。その際、クエリ実行部１３５は、ＤＢオペレーションを実行するためのタスクを生成して（例えば動的に生成して）実行できる。タスクとしては、任意のモジュールを採用することができる。例えば、タスクは、ＯＳ１４５が管理するプロセス又はスレッドでも良いし、ＤＢＭＳ４１２で実装される疑似プロセス又は疑似スレッドでも良い。クエリ実行部１３５は、ディレクトリ情報を取得するディレクトリ情報取得部１３６と、データページ１３０２を取得するデータページ取得部１３７とを有する。【００４９】
ＤＢバッファ管理部１４０は、ＤＢ１８０内のページを一時的に格納するための１以上の記憶領域（バッファ領域）を管理する。ＤＢバッファ管理部１４０は、バッファ領域の確保及び解放を制御する。【００５０】
図１に示すＤＢＭＳ４１２の構成は一例に過ぎない。例えば、或る構成要素は複数の構成要素に分割されていてもよく、複数の構成要素が１つの構成要素に統合されていてもよい。【００５１】
図２は、ＤＢＭＳ４１２に格納される表１８２の一例を示す。【００５２】
図２に例示する表１８２の一例は、ｉｔｅｍ＿ｉｄ、ｃａｔｅｇｏｒｙ、ｓｉｚｅ及びｐｒｉｃｅといった４つのカラム（データ項目）から構成されるｉｔｅｍ表２０１である。ｉｔｅｍ表２０１は、１以上のロー（レコード）から成るレコード集合に分割され、各レコード集合は、一定サイズのデータブロック３００に格納される。図２の表１８２は、論理的な構成であり、図２の表２０１が、上述した複数のデータブロック３００に分割され格納される。図２の表２０１の一部が格納されたデータブロック３００の一例が図３である。【００５３】
図３は、データブロック３００の一例を示す。【００５４】
データブロック３００は、ブロックヘッダ部３１０とデータページ部３４０とを含む。ブロックヘッダ部３１０は、データブロック３００に関連付けられている管理情報１３０３の一例であり、具体的には、例えば、ヘッダ情報３２０とディレクトリ情報３３０とを含む。【００５５】
ヘッダ情報３２０は、カラムと、そのカラムにおけるカラム値の圧縮方式と、そのカラム内のカラム値を格納しているデータページ１３０２との対応関係を表す。具体的には、例えば、ヘッダ情報３２０は、カラム毎にエントリを含む。各エントリに格納される情報として、カラムのＩＤと、そのカラムにおけるカラム値の圧縮方式と、そのカラム内の全てのカラム値を格納している１以上のデータページ１３０２のＩＤとがある。【００５６】
ディレクトリ情報３３０は、データページ１３０２と、カラムと、レコードとの対応関係を表す。具体的には、例えば、ディレクトリ情報３３０は、このディレクトリ情報３３０が関連付けられているデータブロック３００内の複数のデータページ１３０２の各々について、エントリを含む。各エントリに格納される情報として、データページ１３０２のＩＤと、そのデータページ１３０２に対応したカラムと、そのデータページ１３０２に格納されているカラム値を有するレコードのＩＤとがある。【００５７】
データページ部３４０は、複数のデータページ１３０２で構成されており、複数のデータページ１３０２には、このデータブロック３００に対応したレコード集合（１以上のレコード）に格納されている全てのカラム値が格納されている。但し、各データページ１３０２には、１つのカラム内のカラム値が格納され、他のカラム内のカラム値は格納されない。【００５８】
図４は、クエリの一例を示す。【００５９】
図２の表２０１に関し、受け付けるクエリの一例が、図４で示すような、ＳＱＬで記述されたクエリである。【００６０】
図５は、中間データの一例を示す。【００６１】
クエリ実行部１３５が、クエリの実行において、スキャン対象のデータページ１３０２について、そのクエリで指定されたカラム毎に、中間データの生成及び出力を行うことができる。中間データの一例が、図５に示す条件評価ビット列５０１である（図５では、条件１〜３にそれぞれ対応した条件評価ビット列５０１Ａ〜５０１Ｃが示されている）。クエリで指定された各カラムについて、条件評価ビット列５０１は、そのカラムにおけるカラム値にそれぞれ対応したビット、つまりいわゆるビットマップである。各ビットは、そのビットに対応したカラム値が、クエリで指定されている条件に適合しているか否かに応じた値となる。例えば、各ビットは、そのビットに対応したカラム値が、クエリで指定されている条件に適合していれば「１」であり、そのビットに対応したカラム値が、クエリで指定されている条件に適合していなければ「０」である。このような構成の条件評価ビット列５０１を用いて射影処理を行うことで射影処理の高速化が期待できる。詳細は後述する。【００６２】
以下、本実施例で行われる処理を説明する。【００６３】
図６は、データロード処理の流れの一例を示す。【００６４】
データロード部１３０が、データロード要求を受け付け、その要求に応答して、データロード処理（入力データの格納処理）を行う。データロード要求の要求元は、例えば、ＤＢサーバ１００のクライアント計算機（ユーザ）でもよいし、ＤＢサーバ１００の管理システム（図示せず）（管理者）でもよい。【００６５】
（Ｓ６０１）データロード処理が開始されると、データロード部１３０は、ＤＢバッファ管理部１４０を呼び出して（又はデータロード部１３０自身により）、メモリ１０５からワーク領域を確保する。【００６６】
（Ｓ６０２）データロード部１３０は、格納対象レコードが残っている否かを判断する。その判断結果が肯定の場合、Ｓ６０３が実行され、その判断結果が否定の場合、Ｓ６１１が実行される。【００６７】
（Ｓ６０３）データロード部１３０が、格納対象レコードを外部ストレージ装置４０２から取得する。但し、この段階では、その格納対象レコードは、ワーク領域以外の一時領域に格納され、ワーク領域には格納されない。【００６８】
（Ｓ６０４）データロード部１３０が、格納先データブロック３００が確保済みか否かを判断する。その判断結果が肯定の場合、Ｓ６０５が実行され、その判断結果が否定の場合、Ｓ６０６が実行される。【００６９】
（Ｓ６０６）データロード部１３０が、格納先データブロック３００を確保する。確保されるデータブロック３００は、空きのデータブロック３００である。【００７０】
（Ｓ６０５）データロード部１３０が、直前のＳ６０３で取得した格納対象レコード（一時領域内の格納対象レコード）と、ワーク領域内のレコードとを格納形式に変換した場合の格納データサイズ（予想される格納後データのサイズ）を算出し、算出された格納データサイズが、格納先データブロック３００のサイズ以下か否かを判断する。その判断結果が肯定の場合、Ｓ６１０が実行され、その判断結果が否定の場合、Ｓ６０７が実行される。【００７１】
（Ｓ６１０）データロード部１３０が、Ｓ６０３で取得した格納対象レコードをワーク領域に追加する。その後、再度Ｓ６０２が実行される。【００７２】
（Ｓ６０７）データロード部１３０が、ワーク領域に格納されているレコード集合をデータブロック３００へ格納する処理であるレコード格納処理（図７）を実行する。【００７３】
（Ｓ６０８）データロード部１３０が、格納先データブロック３００の解放を行う。【００７４】
（Ｓ６０９）データロード部１３０が、ワーク領域のクリア（例えば、ワーク領域内のレコード集合の削除）を実行する。その後、再度Ｓ６０４が実行される。【００７５】
（Ｓ６１１）データロード部１３０が、上述のレコード格納処理（図７）を行う。【００７６】
（Ｓ６１２）データロード部１３０が、格納先データブロック３００を解放する。【００７７】
（Ｓ６１３）データロード部１３０が、ワーク領域を解放する。これにより、処理が終了する。【００７８】
このデータロード処理により、例えば以下のことが行われる。すなわち、ｉｔｅｍ表２０１のデータロードの実行において、データロード部１３０は、ワーク領域を確保し（Ｓ６０１）、格納対象レコードの”ｉｔｅｍ＿ｉｄ”、“ｃａｔｅｇｏｒｙ”、”ｓｉｚｅ”、“ｐｒｉｃｅ”のカラム値を、確保したワーク領域に格納する（Ｓ６１０）。その際、データロード部１３０は、格納対象レコード及び既にワーク領域に格納されたレコードを格納形式に変換した場合の格納データサイズを算出し、その格納データサイズがデータブロック３００のサイズ以下か否かを判断する（Ｓ６０５）。Ｓ６０５の判断結果が否定の場合、データロード部１３０は、ワーク領域内のレコード集合をデータブロック３００へ格納するレコード格納処理を実行し（Ｓ６０７）、ワーク領域をクリアする（Ｓ６０９）。なお、「ワーク領域のクリア」とは、例えば、ワーク領域が空にされることであるが、ワーク領域は確保されたままである。ワーク領域の確保を解除するためには、「ワーク領域の解放」が行われる。【００７９】
図７は、レコード格納処理の流れの一例を示す。【００８０】
（Ｓ７０１）データロード部１３０が、ワーク領域に保持されたレコード集合を格納形式に変換し、格納先データブロック３００に格納する。これにより、レコード集合内の複数のカラム値が、複数のデータページ１３０２に格納される。【００８１】
（Ｓ７０２）データロード部１３０が、ヘッダ情報３２０を生成し、ヘッダ情報３２０を、格納先データブロック３００に格納する。例えば、データロード部１３０は、レコード集合におけるカラム毎にエントリを含んだヘッダ情報３２０を生成する。データロード部１３０は、各エントリに、カラムのＩＤと、圧縮方式と、そのカラムに対応したカラム値が格納されている１以上のデータページ１３０２の各々のＩＤとを登録する。各エントリに情報が登録されたヘッダ情報３２０が、格納先データブロック３００に格納される。【００８２】
（Ｓ７０３）データロード部１３０（ディレクトリ情報生成部１３１）が、ディレクトリ情報３３０を生成し、格納先データブロック３００に格納する。例えば、データロード部１３０（ディレクトリ情報生成部１３１）は、格納先データブロック３００におけるページ毎にエントリを含んだディレクトリ情報３３０を生成する。データロード部１３０（ディレクトリ情報生成部１３１）は、各エントリに、データページ１３０２のＩＤと、カラムのＩＤと、そのデータページ１３０２に格納されているカラム値を有する１以上のレコードの各々のＩＤ（例えば、１以上のデータページ１３０２にそれぞれ対応した１以上のレコードＩＤの先頭と末端）とを登録する。各エントリに情報が登録されたディレクトリ情報３３０が、格納先データブロック３００に格納される。【００８３】
このレコード格納処理により、例えば以下のことが行われる。データロード部１３０は、ワーク領域に格納されたレコードを格納形式に変換して、データブロック３００のデータページ部３４０に格納する（Ｓ７０１）。データロード部１３０は、ヘッダ情報３２０を生成し、そのヘッダ情報３２０を格納先データブロック３００に格納する（Ｓ７０２）。図３のヘッダ情報３２０の例によれば、ｉｔｅｍ＿ｉｄのカラム値が、辞書圧縮方式で圧縮されていること、及び、データページ１とデータページ２に格納されていることがわかる。ディレクトリ情報生成部１３１は、ディレクトリ情報３３０を生成し、そのディレクトリ情報３３０を格納先データブロック３００に格納する（Ｓ７０３）。図３のディレクトリ情報３３０の例によれば、データページ１にレコードＩＤ１〜１００のｉｔｅｍ＿ｉｄのカラム値が格納されていることがわかる。【００８４】
次に、クエリ実行処理の流れを説明する。【００８５】
クエリ受付部１２０は、クライアント計算機のようなクエリ発行元からクエリを受け付ける。例えば、クエリ受付部１２０は、図４のクエリを受け付ける。クエリ実行プラン生成部１２５は、そのクエリに基づきクエリ実行プランを生成する。クエリ実行部１３５は、クエリ実行時に、ヘッダ情報３２０を取得し、ディレクトリ情報取得部１３６によりディレクトリ情報３３０を取得する。クエリ実行部１３５は、取得したヘッダ情報３２０及びディレクトリ情報３３０を用いて、データページ取得部１３７により処理対象データページ１３０２を取得する。【００８６】
図８は、クエリ実行処理の流れの一例を示す。【００８７】
（Ｓ８０１）クエリ受付部１２０が、クエリ発行元からクエリを受け付ける。【００８８】
（Ｓ８０２）クエリ実行プラン生成部１２５は、そのクエリに基づきクエリ実行プランを生成する。【００８９】
（Ｓ８０３）クエリ実行部１３５が、生成されたクエリ実行プランに基づいて、検索処理対象のデータブロック群を特定する。ここでは、例えば、或る表（例えばitem表）のブロック全体が読み出される。【００９０】
（Ｓ８１８）クエリ実行部１３５が、処理対象データブロック群に、未処理のデータブロック３００が存在するか否かを判断する。その判断結果が否定の場合、処理が終了する。その判断結果が肯定の場合、Ｓ８０４が実行される。【００９１】
（Ｓ８０４）クエリ実行部１３５が、検索処理対象のデータブロック群から未処理のデータブロック３００を選択する。【００９２】
（Ｓ８０５）クエリ実行部１３５が、ＤＢバッファ管理部１４０を呼び出し、ＤＢバッファ管理部１４０が、バッファ領域を確保し、Ｓ８０４で選択されたデータブロック３００内のブロックヘッダ部３１０及び処理対象カラムを格納するデータページ集合を読み出す。データページ集合は、データブロック３００単位で読み出されてもよいし、ブロックヘッダ部３１０のみが読み出されそのブロックヘッダ部３１０から特定されたデータページ集合が読み出されてもよい。【００９３】
（Ｓ８０９）クエリ実行部１３５が、未処理の処理対象カラムが残っているか否かを判断する。その判断結果が否定の場合、Ｓ８１３が実行され、その判断結果が肯定の場合、Ｓ８１０が実行される。【００９４】
（Ｓ８１０）クエリ実行部１３５が、ブロックヘッダ部３１０のヘッダ情報３２０を、例えばバッファ領域からワーク領域に取得する。ディレクトリ情報取得部１３６が、データブロック３００内のブロックヘッダ部３１０からディレクトリ情報３３０を取得する。クエリ実行部１３５が、取得されたヘッダ情報３２０とディレクトリ情報３３０を用いて、処理対象のデータページ集合を特定する。【００９５】
（Ｓ８１１）データページ取得部１３７が、特定されたデータページ集合を、例えばバッファ領域からワーク領域に取得する。クエリ実行部１３５が、取得されたデータページ集合に含まれるデータページ１３０２毎に、条件評価を行い、条件評価の結果として条件評価ビット列５０１（中間データの一例）を生成する。【００９６】
（Ｓ８１３）クエリ実行部１３５は、未処理の射影対象カラムが残っているか否かを判断する。その判断結果が否定の場合、Ｓ８１７が実行され、その判断結果が肯定の場合、Ｓ８１４が実行される。【００９７】
（Ｓ８１４）クエリ実行部１３５が、ブロックヘッダ部３１０のヘッダ情報３２０を取得する。ディレクトリ情報取得部１３６が、データブロック３００内のブロックヘッダ部３１０からディレクトリ情報３３０を取得する。クエリ実行部１３５が、取得されたヘッダ情報３２０とディレクトリ情報３３０を用いて、処理対象のデータページ集合を特定する。【００９８】
（Ｓ８１５）データページ取得部１３７が、特定されたデータページ集合を取得する。クエリ実行部１３５が、生成された条件評価ビット列５０１を参照しながら、条件評価結果がＴＲＵＥのレコード（ビット「１」に対応したカラム値を有するレコード）について、取得されたデータページ集合に含まれるカラム値の射影処理を行う。【００９９】
（Ｓ８１７）クエリ実行部１３５が、データブロック処理での読み出し処理に利用した領域を解放する。【０１００】
このクエリ実行処理により、例えば以下のことが行われる。【０１０１】
クエリ受付部１２０がクエリを受け付け（Ｓ８０１）、クエリ実行プラン生成部１２５が表１８２スキャン方式の実行プランを生成する（Ｓ８０２）。クエリ実行部１３５は、実行プランを参照してアクセス対象の表１８２を取得し、表１８２を格納するデータブロック群を特定する（Ｓ８０３）。【０１０２】
クエリ実行部１３５は、データブロック群から未処理データブロック３００があれば（Ｓ８１８）、未処理データブロック３００を選択する（Ｓ８０４）。ＤＢバッファ管理部１４０が、データブロック３００内のブロックヘッダ部３１０及び処理対象カラムを格納するデータページ集合を読み出す（Ｓ８０５）。ここで、ブロックヘッダ部３１０及び処理対象カラムを格納するデータページ１３０２を含むデータブロック３００全体が読み出されてもよい。或いは、データ読出し処理が２フェーズに分けられてよい。１フェーズ目で、ブロックヘッダ部３１０のみが読み出され、ブロックヘッダ部３１０を参照することにより必要なデータページ１３０２が特定されてよい。２フェーズ目で、必要なデータページ１３０２のみが読み出されてもよい。図４に例示の検索クエリによれば、“ｃａｔｅｇｏｒｙ＝１０”と“ｐｒｉｃｅ＞＝２００”と”ｓｉｚｅ＝Ｌ”の３つの条件がある。図３の例によれば、“ｃａｔｅｇｏｒｙ”カラムが格納されているデータページ１３０２はデータページ３（ＩＤ「３」のデータページ１３０２）であること、データページ３にデータは非圧縮で格納されること、“ｐｒｉｃｅ”カラムが格納されているデータページ１３０２はデータページ７であること、データページ７にはデータは非圧縮で格納されること、“ｓｉｚｅ”カラムが格納されているデータページ１３０２はデータページ４、５及び６であること、データページ４〜６には圧縮方式「ランレングス」で圧縮されたデータが格納されることがわかる。また、図４に例示の検索クエリによれば、“ｉｔｅｍ＿ｉｄ”の射影がある、図３の例によれば、射影対象カラムのデータページ１３０２は、データページ１及び２であること、データページ１及び２に圧縮方式「辞書圧縮」で圧縮されたデータが格納されることがわかる。【０１０３】
クエリ実行部１３５は、未処理の条件評価対象カラムが残っているか否かを判断する（Ｓ８０９）。その判断結果が肯定の場合、ディレクトリ情報取得部１３６が、データブロック３００内のブロックヘッダ部３１０よりディレクトリ情報３３０を取得し、処理対象のデータページ集合を特定する（Ｓ８１０）。データページ取得部１３７が、特定されたデータページ集合であるデータページ３〜７を取得する。クエリ実行部１３５は、取得されたデータページ集合に含まれるデータに対して条件評価を行い、条件評価対象カラムについて、それぞれ、中間データとして、図５に例示した条件評価ビット列５０１Ａ〜５０１Ｃを生成する（Ｓ８１１）。図５は、図４で示したクエリ実行における条件評価ビット列の一例である。ｉｔｅｍ表２０１の１〜８番目のレコードに対し、“ｃａｔｅｇｏｒｙ＝１０"を評価すると、表１８２の上から４〜６番目のレコードが条件に合致するため、図５の条件評価ビット列５０１Ａでは、左から４〜６番目のビットが１、他のビットは０となる。【０１０４】
クエリ実行部１３５は、全ての条件評価が完了すると射影処理を行う。なお、条件評価が完了した時点で、全レコードの条件評価結果がＦＡＬＳＥであった場合、以降の射影処理が省略されてもよい。クエリ実行部１３５は、未処理の射影対象カラムが残っているか否かを判断する（Ｓ８１３）。その判断結果が肯定の場合、クエリ実行部１３５がブロックヘッダ部３１０のヘッダ情報３２０を取得し、ディレクトリ情報取得部１３６がデータブロック３００内のブロックヘッダ部３１０よりディレクトリ情報３３０を取得する。クエリ実行部１３５が、取得されたヘッダ情報３２０とディレクトリ情報３３０を用いて、処理対象のデータページ集合を特定する（Ｓ８１４）。データページ取得部１３７が、特定されたデータページ集合を取得し、クエリ実行部１３５が、生成された条件評価ビット列５０１を参照しながら、条件評価結果がＴＲＵＥのレコードについて、取得されたデータページ集合に含まれるカラム値の射影処理を行う（Ｓ８１５）。射影対象のレコードは、３つの条件を全て満たす必要があるため、レコードに対応する条件評価ビット列５０１のビットがいずれも１のレコードである。すなわち、１〜８番目のビットのうち、５番目と６番目である。【０１０５】
１つのブロックにおける全ての射影処理が完了すると、クエリ実行部１３５が、そのデータブロック３００で読み出し処理に利用した領域を解放する（Ｓ８１７）。【０１０６】
次に、クエリ実行プラン生成部１２５がクエリ実行プランとして索引検索を選択する場合のクエリ実行処理の流れの一例を、図１１を参照して説明する。【０１０７】
図１１は、クエリ実行処理の流れの別の一例を示す。なお、図１１の説明では、図８の説明と共通する点については説明を省略又は簡略する。【０１０８】
（Ｓ１１０１）クエリ受付部１２０は、クエリ発行元からクエリを受け付ける。【０１０９】
（Ｓ１１０２）クエリ実行プラン生成部１２５は、実行プランを生成する。【０１１０】
（Ｓ１１１８）生成された実行プランに基づいて、クエリ実行部１３５が、索引検索処理を行い、未処理の索引エントリが残っているか否かを判断する。その判断結果が肯定の場合、未処理の索引エントリが選択され、Ｓ１１０４が実行される。その判断結果が否定の場合、検索処理が終了する。【０１１１】
（Ｓ１１０４）クエリ実行部１３５が、選択された索引エントリを参照し、処理対象レコードを格納するデータブロック３００を特定する。【０１１２】
（Ｓ１１０５）クエリ実行部１３５が、ＤＢバッファ管理部１４０を呼び出し、ＤＢバッファ管理部１４０が、データブロック３００内のブロックヘッダ部３１０及び処理対象カラムを格納するデータページ集合を読み出す。【０１１３】
（Ｓ１１０９）クエリ実行部１３５が、未処理の条件評価対象カラムが残っているか否かを判断する。その判断結果が肯定の場合、Ｓ１１１０が実行され、その判断結果が否定の場合、Ｓ１１１３が実行される。【０１１４】
（Ｓ１１１０）クエリ実行部１３５が、ブロックヘッダ部３１０のヘッダ情報３２０を取得する。ディレクトリ情報取得部１３６が、データブロック３００内のブロックヘッダ部３１０よりディレクトリ情報３３０を取得する。クエリ実行部１３５が、取得されたヘッダ情報３２０とディレクトリ情報３３０を用いて、処理対象のデータページ１３０２を特定する。【０１１５】
（Ｓ１１１１）データページ取得部１３７が、特定されたデータページ１３０２を取得し、クエリ実行部１３５が、取得されたデータページ１３０２に格納された処理対象レコードのカラム値について条件評価を行う。【０１１６】
（Ｓ１１１３）クエリ実行部１３５が、未処理の射影対象カラムが残っているか否かを判断する。その判断結果が肯定の場合、Ｓ１１１４が実行され、その判断結果が否定の場合、Ｓ１１１７が実行される。【０１１７】
（Ｓ１１１４）クエリ実行部１３５が、ブロックヘッダ部３１０のヘッダ情報３２０を取得する。ディレクトリ情報取得部１３６が、データブロック３００内のブロックヘッダ部３１０よりディレクトリ情報３３０を取得する。クエリ実行部１３５が、取得されたヘッダ情報３２０とディレクトリ情報３３０を用いて、処理対象のデータページ１３０２を特定する。【０１１８】
（Ｓ１１１５）データページ取得部１３７が、特定されたデータページ１３０２を取得する。クエリ実行部１３５が、条件評価結果がＴＲＵＥである場合に、取得されたデータページ１３０２に格納された処理対象レコードのカラム値について射影処理を行う。【０１１９】
（Ｓ１１１７）クエリ実行部１３５が、データブロック３００処理で読み出し処理に利用した領域を解放する。【０１２０】
図１２に、索引１８１の一例であるｓｉｚｅ索引１２０１の一例を示す。リーフ部分には、索引１２０１のキー値とデータブロックＩＤとレコードＩＤとの組である索引エントリが格納される。図１２の例では、索引１８１のキー値“Ｌ”と、データブロックＩＤ“データブロック１”と、レコードＩＤ“レコード１”が格納されている。【０１２１】
このクエリ実行処理により、例えば以下のことが行われる。【０１２２】
クエリには、”ｓｉｚｅ＝Ｌ”の条件指定があるため、クエリ実行部１３５は、ｓｉｚｅ索引１２０１に対し“ｓｉｚｅ＝Ｌ”を満たす索引エントリを検索し、その結果得られる５つの索引エントリ１２０２〜１２０６から、索引エントリを１つ選択する。クエリ実行部１３５は、その選択された索引エントリを参照し、処理対象レコードを格納するデータブロック３００（例えばデータブロック１）を特定する（Ｓ１１０４）。続いて、ＤＢバッファ管理部１４０が、データブロック３００内のブロックヘッダ部３１０及び処理対象カラムを格納するデータページ集合を読み出す（Ｓ１１０５）。【０１２３】
未処理の条件評価対象カラムが残っている場合（Ｓ１１０９）、クエリ実行部１３５は、ヘッダ情報３２０とディレクトリ情報３３０を用いて、処理対象のデータページ１３０２を特定する（Ｓ１１１０）。データページ取得部１３７が、特定されたデータページ１３０２を取得し、クエリ実行部１３５が、取得されたデータページ１３０２に格納された処理対象レコードのカラム値について条件評価を行う（Ｓ１１１１）。処理対象レコードが“レコード１”の場合、条件“ｃａｔｅｇｏｒｙ＝１０”に対してはＦＡＬＳＥとなる。【０１２４】
クエリ実行部１３５は、全ての条件評価が完了すると射影処理を行う。クエリ実行部１３５は、未処理の射影対象カラムが残っている場合、ヘッダ情報３２０とディレクトリ情報３３０を用いて、処理対象のデータページ１３０２を特定する（Ｓ１１１４）。条件評価結果がＴＲＵＥである場合、クエリ実行部１３５は、取得されたデータページ１３０２に格納された処理対象レコードのカラム値について射影処理を行う（Ｓ１１１５）。“レコード１”は、条件評価において、条件“ｃａｔｅｇｏｒｙ＝１０”に対してＦＡＬＳＥとなるため、射影処理が行われない。“レコード５”は、条件評価において条件“ｃａｔｅｇｏｒｙ＝１０”に対してＴＲＵＥ、かつ条件“ｐｒｉｃｅ＞＝２００”に対してＴＲＵＥであるため、ｉｔｅｍ＿ｉｄのカラム値“５”が射影される。
【実施例２】
【０１２５】
以下、実施例２を説明する。その際、実施例１との相違点を主に説明し、実施例１との共通点については説明を省略又は簡略する。【０１２６】
図９は、実施例２におけるデータブロック及びディレクトリ情報の一例を示す。【０１２７】
実施例１との相違点は、データブロック９００のブロックヘッダ部９１０がディレクトリ情報９３０を含まないこと、ディレクトリ情報９３０がデータブロックＩＤ９５１を含むことである。データブロックＩＤ９５１は、ディレクトリ情報９３０に関連付けられているデータブロック９００のＩＤである。ディレクトリ情報９３０内のデータブロックＩＤ９５１を参照することで、そのディレクトリ情報９３０に関連付けられているデータブロック９００を特定することができる。【０１２８】
実施例２では、複数のデータブロック９００にそれぞれ対応する複数のディレクトリ情報９３０が、連続領域（例えば、外部ストレージ装置４０２が提供する記憶空間における連続した領域）に格納される。これにより、シーケンシャルリードにより複数のディレクトリ情報９３０を読み出すこと、言い換えれば、一度のデータ読出し要求で複数のディレクトリ情報９３０を読み出すことが可能となる。複数のディレクトリ情報９３０を逐次的に読み出す場合と比較して、ディレクトリ情報９３０の読出しに要する時間を削減することができる。【０１２９】
なお、ディレクトリ情報９３０に代えて又は加えて、管理情報における他の情報、例えばヘッダ情報３２０も、データブロック９００に含まれないでよい。つまり、管理情報の全部又は一部が、データブロック９００の外に存在してよい。
【実施例３】
【０１３０】
以下、実施例３を説明する。その際、実施例１との相違点を主に説明し、実施例１との共通点については説明を省略又は簡略する（なお、実施例３は、実施例２に適用されてもよい）。【０１３１】
図１０は、実施例３に係るクエリ実行処理の流れの一例を示す。【０１３２】
図８との相違点は、Ｓ８０５に代えてＳ１００５が行われることと、Ｓ１０２０、Ｓ１０２１、Ｓ１０２２及びＳ１０２３が更に行われることである。なお、図１０のＳ１００１、Ｓ１００２、Ｓ１００３、Ｓ１０１８、Ｓ１００４、Ｓ１００９、Ｓ１０１０、Ｓ１０１１、Ｓ１０１３、Ｓ１０１４、Ｓ１０１５及びＳ１０１７は、それぞれ、図８のＳ８０１、Ｓ８０２、Ｓ８０３、Ｓ８１８、Ｓ８０４、Ｓ８０９、Ｓ８１０、Ｓ８１１、Ｓ８１３、Ｓ８１４、Ｓ８１５及びＳ８１７と同じ（又は実質的に同じ）処理である。【０１３３】
具体的には、Ｓ１００４の後、クエリ実行部１３５´が、データブロック３００内のブロックヘッダ部３１０のみを読み出す（Ｓ１００５）。【０１３４】
条件評価処理を実行する際に、クエリ実行部１３５´が、ヘッダ情報３２０及びディレクトリ情報３３０を取得し、処理対象データページ集合を特定する（Ｓ１０１０）。なお、このとき、クエリ実行部１３５´は、クエリと既処理の条件評価結果とを合わせて参照し、処理対象の条件評価処理を省略可能なレコードを特定し、当該レコードを除外した処理対象レコード集合を特定し、処理対象レコード集合を格納する処理対象データページ集合を特定してもよい。続いて、クエリ実行部１３５´は、特定された処理対象データページ１３０２を読み出し（Ｓ１０２０）、データページ集合に対して条件評価処理を実行し、条件評価ビット列５０１を生成し（Ｓ１０１１）、条件評価処理で読み出し処理に利用した領域を解放する（Ｓ１０２１）。【０１３５】
同様に、射影処理を実行する際に、クエリ実行部１３５´は、ヘッダ情報３２０及びディレクトリ情報３３０を取得して処理対象データページ集合を特定する（Ｓ１０１４）。なお、このとき、クエリ実行部１３５´は、条件評価結果を合わせて参照し、処理対象の射影処理を省略可能なレコードを特定し、当該レコードを除外した処理対象レコード集合を特定し、処理対象レコード集合を格納する処理対象データページ集合を特定してもよい。続いて、クエリ実行部１３５´は、特定された処理対象データページ１３０２を読み出し（Ｓ１０２２）、データページ集合に対して射影処理を実行し（Ｓ１０１５）、射影処理で読み出し処理に利用した領域を解放する（Ｓ１０２３）。【０１３６】
実施例３によれば、クエリ実行処理の進捗に合わせて必要なページが主記憶メモリに読み出され、処理完了後に当該領域が解放される。このため、同時に確保する必要のある主記憶メモリ領域を削減することができる。また、処理の進捗に合わせて、処理対象データページ１３０２を特定するため、不要なデータページ１３０２の読み出し処理を削減することができる。【０１３７】
以上、幾つかの実施例を説明したが、これらは本発明の説明のための例示であって、本発明の範囲をこれらの実施例にのみ限定する趣旨ではない。本発明は、他の種々の形態でも実行することが可能である。例えば、インメモリデータベースに本発明が適用されてもよい（具体的には、例えば、ＤＢ１８０の全てがＤＢサーバ１００内のメモリ１０５に格納されてもよい）。
【符号の説明】
【０１３８】
１００…ＤＢ（データベース）サーバ
【図１】
2016166789.tif 000003
【図２】
2016166789.tif 000004
【図３】
2016166789.tif 000005
【図４】
2016166789.tif 000006
【図５】
2016166789.tif 000007
【図６】
2016166789.tif 000008
【図７】
2016166789.tif 000009
【図８】
2016166789.tif 000010
【図９】
2016166789.tif 000011
【図１０】
2016166789.tif 000012
【図１１】
2016166789.tif 000013
【図１２】
2016166789.tif 000014
【図１３】
2016166789.tif 000015
【国際調査報告】
2016166789.tif 000016
2016166789.tif 000017
2016166789.tif 000018
2016166789.tif 000019