WO2015029187A1

WO2015029187A1 - データベース管理システム及び計算機システム

Info

Publication number: WO2015029187A1
Application number: PCT/JP2013/073181
Authority: WO
Inventors: 悠登早水; 和生合田; 喜連川　優; 信男河村
Original assignee: Hitachi Ltd; University of Tokyo NUC
Current assignee: Hitachi Ltd; University of Tokyo NUC
Priority date: 2013-08-29
Filing date: 2013-08-29
Publication date: 2015-03-05
Anticipated expiration: 2016-02-29
Also published as: US10885030B2; JPWO2015029187A1; EP3040865A1; JP5999574B2; EP3040865A4; EP3040865B1; US20160232206A1

Abstract

　データベースへのクエリのクエリ実行プランに基づいてクエリを実行しクエリ実行結果をクエリ発行元に返す第１のクエリ実行部と、データの読込み要求を受け付けた際、読込み要求されたデータがバッファに格納されていなければ、読込み要求されたデータを、データベースから読み込んでバッファに格納し、読込み要求の発行元に提供し、読込み要求されたデータが既にバッファに格納されていれば、読込み要求されたデータをバッファから読み込み読込み要求の発行元に提供するバッファ管理部とを有するデータベース管理システムに、第２のクエリ実行部が追加される。第２のクエリ実行部は、クエリ実行プランに基づいてクエリを実行し、クエリ実行手続きにおいて、必要なデータの読込み要求をバッファ管理部に発行する。これにより、第１のクエリ実行部がデータの読込み要求を発行した際には、既に、当該データがバッファに格納されていることがあり得る。

Description

データベース管理システム及び計算機システム

　本発明は、データ入出力、例えば、データ処理技術およびデータベース管理技術に関する。

　企業における戦略的な活動においては、企業が抱える大量の業務データ等の活用が不可欠である。当該業務データ等の活用のためには、当該業務データ等をデータベースに蓄積し、当該データベースにおいて解析処理を行うデータベース管理システムが既に考案されている。

　データベース管理システムは、データベースに対するクエリを受け付け、当該クエリを実行し、その実行結果を出力する。この際、一般に、データベース管理システムは、クエリ実行手続きに必要な１つ以上のデータベースオペレーションを所定の順序で逐次的に実行する。

　即ち、データベース管理システムが１つのクエリを実行する際には、あるデータベースオペレーションの実行が完了してから、別のデータベースオペレーションの実行を開始する。あるデータベースオペレーションを実行するためにデータベースからデータを読み込む必要がある場合には、データの読込み要求をデータベースに発行し、その読込み要求に応じてデータがデータベースから読み込まれるまで別のデータベースオペレーションを実行することはできず、よって、当該読込みによってクエリの実行が中断する。ゆえに、１つのクエリの実行に要する時間が長くなる場合がある。

　これに対して、特許文献１に開示された技術が知られている。特許文献１によるデータベース管理システムは、クエリを実行する際に、データベースオペレーションの実行に要するデータの読込み要求の都度に、タスクを生成し、このようにして生成されたタスクを並行して実行することにより、データベースオペレーションを並行して実行し、また、データ読込み要求を多重的に発行する。これにより、１つのクエリの実行に要する時間が短縮される場合がある。

特許第４６１１８３０号公報

　一般に、データベースサーバにおいては、１つ以上のデータベースオペレーションを所定の順序で逐次的に実行するタイプのデータベース管理システムが採用されている。１つのクエリの実行に要する時間を短縮するためには、そのようなタイプの既存のデータベース管理システムを、特許文献１に従って動的にタスクを生成する機能を有するタイプのデータベース管理システムに改変することが一つの手段として考えられる。しかしながら、このような改変は、多くの場合、データベース管理システムの抜本的な改変を伴い、プログラムコードを大幅に書き換える必要があり、簡単ではない。

　このような問題は、データベース管理システムに限らず、データの入出力、例えば、データの読込みを必要とする他のコンピュータプログラム或いは計算機システム等のシステムについても存在し得る。

　本発明の目的は、既存のシステムを抜本的に改変することなく、１つの処理要求の実行に要する時間を短縮することにある。例えば、本発明の目的は、既存のデータベース管理システムを抜本的に改変することなく、１つのクエリの実行に要する時間を短縮することにある。

　データベース管理システムが、クエリ受付部と、クエリ実行プラン生成部と、第１のクエリ実行部と、第２のクエリ実行部と、バッファ管理部とを有する。例えば、データベース管理システムは、コンピュータプログラムであり、計算機において実行されることにより、クエリ受付部と、クエリ実行プラン生成部と、第１のクエリ実行部と、第２のクエリ実行部、バッファ管理部とを計算機に構成する。

　クエリ受付部は、データベースに対するクエリをクエリ発行元から受け付ける。クエリ実行プラン生成部は、受け付けたクエリに基づいて受け付けたクエリを実行するために必要な１以上のデータベースオペレーションと１以上のデータベースオペレーションの実行手順とを表す情報を含むクエリ実行プランを生成する。第１のクエリ実行部および第２のクエリ実行部は、それぞれ、生成されたクエリ実行プランに基づいてデータベースオペレーションを実行することにより、クエリを実行し、その実行結果を得る。この際、第１のクエリ実行部および第２のクエリ実行部は、それぞれ、データベースオペレーションの実行に必要なデータの読込み要求をバッファ管理部に発行してもよい。バッファ管理部は、例えば、第１のクエリ実行部および第２のクエリ実行部のいずれかからデータの読込み要求を受け付けた際、読込み要求されたデータがバッファに既に格納されていれば、バッファからデータを読み込み、読込み要求の発行元のクエリ実行部に提供し、読込み要求されたデータがバッファに格納されていなければ、当該データの読込み要求をデータベースに発行し、当該読込み要求によって読込まれたデータを、バッファに格納して、読込み要求の発行元のクエリ実行部に提供する。

　第１のクエリ実行部および第２のクエリ実行部のうち、第１のクエリ実行部は、クエリの実行結果を、クエリ発行元に返答する。即ち、第１のクエリ実行部は、クエリの実行結果をクエリ発行元に返答するようになっており、第２のクエリ実行部は、クエリの実行結果をクエリ発行元に返答しないようになっている。

　バッファ管理部は、第１のクエリ実行部からデータの読込み要求を受け付けた場合、読込み要求されたデータが、既に当該データの読込み要求を第２のクエリ実行部から受け、それによって当該データが既にデータベースから読み込まれバッファに格納されている場合には、バッファから当該データを読み込み第１のクエリ実行部に提供してよい。

　この際、第１のクエリ実行部は、１つ以上のデータベースオペレーションを所定の順序で逐次的に実行するクエリ実行部であってよい。第２のクエリ実行部は、特許文献１に従って動的にタスクを生成するクエリ実行部であってよい。

　第１のクエリ実行部が、クエリの実行において、データベースオペレーションの実行にデータを必要とした際に、既に第２のクエリ実行部からの読込み要求によってバッファ管理部により当該データがバッファに格納されていれば、第１のクエリ実行部は、バッファから当該データを読み込めばよく、データベースから新たに当該データを読み込む必要はない。即ち、第２のクエリ実行部によって、第１のクエリ実行部によるクエリの実行に要する時間を短縮することができる場合がある。よって、本発明によれば、第１のクエリ実行部を有する既存のデータベース管理システムを抜本的に改変することなく、１つのクエリの実行に要する時間を短縮することが期待される。

実施例１にかかる計算機システムの構成を示す。実施例１にかかるデータベースの表および索引の定義を示す。実施例１にかかるＰａｒｔ表を示す。実施例１にかかるＬｉｎｅｉｔｅｍ表を示す。実施例１にかかるクエリを示す。実施例１にかかるクエリ実行プランを示す。実施例１にかかるクエリ実行の実行インスタンス木を示す。実施例１にかかるクエリ実行プラン情報の構成を示す。実施例１にかかる統計情報の構成を示す。実施例１にかかるクエリ実行部状態管理情報の構成を示す。実施例１にかかる加速部状態管理情報の構成を示す。実施例１にかかる協調制御情報の構成を示す。実施例１にかかるクエリを受け付け、クエリ実行プランを生成し、クエリを実行する手続きを示す。実施例１にかかる協調制御情報を生成する手続きを示す。実施例１にかかる第１のクエリ実行手続きを示す。実施例１にかかる第２のクエリ実行手続きの流れを示す。実施例１にかかる実行インスタンスの協調性を算出する手続きを示す。実施例１にかかる実行インスタンスを実行する手続きを示す。実施例１による効果を説明するタイムチャートである。実施例２にかかるデータベースバッファ管理情報の構成を示す。実施例３かかる統計情報の構成を示す。実施例４にかかる計算機システムの構成を示す。

　以下、図面を参照しながら、幾つかの実施例を説明する。データベース管理システムへのクエリの発行元としては、データベース管理システムの内部のコンピュータプログラムであってよく、もしくは、外部のコンピュータプログラムであってよい。例えば、クエリ発行元は、データベース管理システムを有するデータベースサーバ内で実行されるコンピュータプログラム（例えばアプリケーションプログラム）であってもよいし、データベースサーバに接続されたクライアント計算機等の装置で実行されるコンピュータプログラム（例えば、アプリケーションプログラム）であってもよい。

　図１は、実施例１にかかる計算機システムの構成を示す。

　データベースサーバ４０１は、計算機であって、例えば、パーソナルコンピュータ、ワークステーションまたはメインフレームであってよく、もしくは、これらの計算機において仮想化プログラムによって構成された仮想的な計算機であってよい。データベースサーバ４０１は、ネットワークアダプタ４１３、メモリ４１６、ストレージ装置４１５及びそれらに接続されたプロセッサ４１４を有する。プロセッサ４１４は、例えば、マイクロプロセッサであり、コンピュータプログラムを実行する。プロセッサ４１４により実行されるコンピュータプログラムは、例えば、オペレーティングシステム４１７、データベース管理システム４１２、データベース管理システム４１２にクエリを発行するアプリケーションプログラム４１１である。メモリ４１６は、例えば、揮発性のＤＲＡＭ（Dynamic Random-Access Memory）等であり、プロセッサ４１４によって実行されるプログラムと、プログラムが使用するデータを一時的に記憶する。ストレージ装置４１５は、例えば、不揮発性の磁気ディスク、フラッシュメモリ等であり、プログラムおよびプログラムが使用するデータを格納する。ネットワークアダプタ４１３は、通信ネットワーク４０３とデータベースサーバ４０１を接続する。アプリケーションプログラム４１１は、データベースサーバ４０１ではなく、通信ネットワーク４０３に接続される別の計算機（図示しない）で動作するものであってもよい。プロセッサ４１４は、ネットワークアダプタ４１３およびメモリ４１６等に接続された制御デバイスに含まれている要素であってもよい。制御デバイスは、プロセッサ４１４のほかに、データの暗号化や復号を行う回路等の専用のハードウェア回路を含んでもよい。

　データベースサーバ４０１は、性能や冗長性を高めるために、プロセッサ４１４、メモリ４１６、ストレージ装置４１５およびネットワークアダプタ４１３のいずれか１つの要素を複数有してもよい。データベースサーバ４０１は、キーボードやポインティングデバイス等の入力デバイス（図示しない）と液晶ディスプレイ等の出力デバイス（図示しない）を有してもよい。入力デバイスおよび出力デバイスは、プロセッサ４１４に接続されていてよい。入力デバイスと出力デバイスは一体であってもよい。

　データベースサーバ４０１では、データベース管理システム４１２がアプリケーションプログラム４１１から発行されたクエリを実行し、当該クエリの実行において、データベース４５１からデータを読み込むために、もしくは、データベース４５１にデータを書き込むために、当該データベース４５１を格納する外部ストレージ装置４０２に対する入出力要求をオペレーティングシステム４１７に発行する。オペレーティングシステム４１７は、当該入出力要求を受け付け、外部ストレージ装置４０２へ入出力要求を発行する。

　外部ストレージ装置４０２は、複数の記憶デバイスを含む記憶デバイス群４５１を有する装置であり、例えば、ディスクアレイ装置であるが、それに代えて、単一の記憶デバイスであってもよい。外部ストレージ装置４０２は、データベースサーバ４０１が有するデータベース管理システム４１２が管理するデータベース４５１を記憶するが、データベース４５１のデータに加えて、プログラムを記憶してもよい。外部ストレージ装置４０２は、データベースサーバ４０１から入出力要求を受け付け、当該入出力要求に従いデータの読み書きを行い、その結果をデータベースサーバ４０１に返す。

　外部ストレージ装置４０２は、記憶デバイス群４５１に加えて、ネットワークアダプタ４４１およびこれらに接続されたストレージコントローラ４４２を有する。

　ネットワークアダプタ４４１は、外部ストレージ装置４０２を通信ネットワーク４０３に接続し、これを介して、データベースサーバ４０１と接続される。通信ネットワーク４０３を介した通信プロトコルとしては、例えば、ファイバチャネル（ＦＣ）、ＳＣＳＩ（Small　Computer　System　Interface）、又は、ＴＣＰ／ＩＰ（Transmission　Control　Protocol／Internet　Protocol）が採用されてよい。例えば、ファイバチャネルもしくはＳＣＳＩが採用される場合、データベースサーバ４０１のネットワークアダプタ４１３および外部ストレージ装置４０２のネットワークアダプタ４４１は、ホストバスアダプタと呼ばれることがある。

　記憶デバイス群４５１が有する記憶デバイスは、不揮発性の記憶媒体を有するデバイスであって、例えば、磁気ディスクドライブ、フラッシュメモリドライブ、その他半導体メモリドライブである。記憶デバイス群４５１は、ＲＡＩＤ（Redundant Array of Independent Disks）機構を有し、所定のＲＡＩＤレベルでデータを記憶してもよい。記憶デバイス群４５１の記憶空間に基づく論理的な記憶デバイス（例えば、論理ユニット、論理ボリューム、ファイルシステムボリューム）が、データベースサーバ４０１に提供され、当該論理的な記憶デバイス上にデータベース４５１が格納されてもよい。

　ストレージコントローラ４４２は、例えば、メモリおよびプロセッサを含み、データベースサーバ４０１からの入出力要求に応じて、データベース４５１を格納した記憶デバイス群４５１との間でデータの読込み、もしくは、書込みを行う。例えば、ストレージコントローラ４４２は、データベースサーバ４０１から、データの読込み要求を受け付けると、当該要求に従って記憶デバイス群４５１からデータを読み込み、読み込んだデータをデータベースサーバ４０１に返す。

　外部ストレージ装置４０２は、性能や冗長性を高めるために、ストレージコントローラ４４２等の構成要素を複数有してもよい。

　データベース管理システム４１２は、データベース４５１を管理する。データベース４５１は、１以上の表４６２を含み、更に１以上の索引４６１を含んでよい。表４６２は、１以上のレコードの集合であり、レコードは１以上のカラムから構成される。索引４６１は、表４６２の１以上のカラム等を対象として作成されるデータ構造であり、当該索引４６１が対象とするカラム等を含む選択条件による表４６２へのアクセスを高速化するためのものである。例えば、表４６２は、対象とするカラムの値の毎に、表４６２の中で当該値を含むレコードを特定するための情報を保持するデータ構造である。データ構造としては、例えばＢ木等が用いられる。レコードを特定するための情報としては、物理アドレスや論理的な行ＩＤ等が用いられることがある。更に、データベース４５１は、データベース統計４６３を含んでよい。データベース統計４６３は、例えば、索引４６１のエントリ数を表す情報、表４６２のレコード数を表す情報、カラム毎の値の最大値、平均値、最小値、カラム毎の値分布等、データベースが含むデータに関する情報を含む。

　データベース管理システム４１２は、クエリ受付部４２１、クエリ実行プラン生成部４２２、クエリ実行プラン情報４２３、統計情報４２７、クエリ実行部４２４（第１のクエリ実行部の一例）、クエリ実行部状態管理情報４２５、加速部有効性判定部４２６、加速部４２８（第２のクエリ実行部の一例）、加速部状態管理情報４２９、協調制御情報生成部４３０、協調制御情報４３１、データベースバッファ管理部４３２、データベースバッファ５５１およびデータベースバッファ管理情報５５０を含む。

　クエリ受付部４２１は、アプリケーションプログラム４１１が発行するクエリを受け付ける。クエリは、例えば、構造化問合せ言語（ＳＱＬ、Structured Query Language）によって記述される。

　クエリ実行プラン生成部４２２は、クエリ受付部４２１が受け付けたクエリから、当該クエリを実行するために必要な１以上のデータベースオペレーションを含むクエリ実行プランを生成する。クエリ実行プランは、例えば、１以上のデータベースオペレーションと、データベースオペレーションの実行順序の関係を含む情報であり、クエリ実行プラン情報４２３に格納される。クエリ実行プランは、データベースオペレーションをノード、データベースオペレーションの実行順序の関係をエッジとする木構造で表されることがある。クエリ実行プラン生成部４２２は、クエリ実行プランを生成する際に、統計情報４２７を用いてもよい。

　クエリ実行部４２４は、クエリ実行プラン生成部４２２が生成したクエリ実行プランに従って、クエリ受付部４２１が受け付けたクエリを実行し、その実行結果をアプリケーションプログラム４１１に返す。この際、クエリ実行部４２４は、既存のデータベース管理システム４１２で採用されている技術に従い、クエリ実行プランにおけるデータベースオペレーションを所定の順序に従って実行し、クエリの実行結果をクエリ発行元であるアプリケーションプログラム４１１に返すようになっている。この際、クエリ実行部４２４は、データベースオペレーションの実行に必要なデータの読込み要求をデータベースバッファ管理部４３２に発行し、その読込み要求に応じてデータベースバッファ管理部４３２が返したデータを使用して、当該データベースオペレーションを実行する。クエリ実行部４２４は、クエリを実行する際に、その実行状態をクエリ実行部状態管理情報４２５に格納して、利用してもよい。

　加速部４２８は、同様に、クエリ実行プラン生成部４２２が生成したクエリ実行プランに従って、クエリ受付部４２１が受け付けたクエリを実行する。この際、加速部４２８は、特許文献１に記載の技術が適用されたクエリ実行部でよい。具体的には、加速部４２８は、（ａ）データベースオペレーションを実行するためのタスクを生成し、（ｂ）生成されたタスクを実行することで、当該タスクに対応したデータベースオペレーションに必要なデータの読込み要求をデータベースバッファ管理部４３２に発行し、（ｃ）（ｂ）で実行されたタスクに対応したデータベースオペレーションの実行結果に基づき別のデータベースオペレーションを実行する必要がある場合には、その別のデータベースオペレーションをそれぞれ実行する１以上のタスクを新たに生成し、（ｄ）その新たに生成した１以上のタスクのそれぞれについて（ｂ）及び（ｃ）を行う。また、加速部４２８は、このようにして生成された１以上のタスクを並行して実行してよい。加速部４２８は、２以上の実行可能なタスクが存在する場合には、それら２以上のタスクのうちの少なくとも２つのタスクを並行して実行してよい。加速部４２８は、クエリを実行する際に、その実行状態を加速部状態管理情報４２９に格納して、利用してもよい。更に、加速部４２８は、クエリ実行部状態管理情報４２５および協調制御情報４３１にそれぞれ格納された情報に基づいて、実行可能なタスクを決定してよい。加速部４２８は、データベースオペレーションの実行に要するデータの読込み要求をデータベースバッファ管理部４３２に発行し、その要求に応じてデータベースバッファ管理部４３２が返したデータを使用して、当該データベースオペレーションを実行する。なお、上記において、加速部４２８は、１のタスクで複数のデータベースオペレーションを実行してもよい。また、加速部４２８は、都度に新たにタスクを生成することはせず、同じタスクにおいて次のデータベースオペレーションを実行してもよい。タスクの実装としては、例えば、オペレーティングシステム４１７が実現するプロセスやカーネルスレッド等のほか、ライブラリ等が実現するユーザスレッドを用いてよい。なお、上記において、クエリ実行部４２４とは異なり、加速部４２８はクエリの実行結果をアプリケーションプログラム４１１に返すことはしなくてよく、また、加速部４２８は必ずしもクエリの全体を実行する必要はない。

　データベースバッファ管理部４３２は、データベース４５１のデータを一時的に格納するためのデータベースバッファ５５１を管理する。データベースバッファ５５１は、メモリ４１６上に構成され、１以上のデータベースページを含む。データベースバッファ５５１が含むデータベースページの数は、所定の数に制限されていることがある。データベースバッファ管理部４３２は、データベース４５１のデータをデータベースバッファ５５１に読み込み、データベースバッファ５５１に格納されているデータをデータベース４５１に書き出す。データベースバッファ管理部４３２は、クエリ実行部４２４もしくは加速部４２８からデータの読込み要求を受け付けた際、読込み要求されたデータが既にデータベースバッファ５５１に格納されていれば、当該データを読込み要求の発行元であるクエリ実行部４２４もしくは加速部４２８に返し、一方、読込み要求されたデータがデータベースバッファ５５１に格納されていなければ、当該データをデータベース４５１から読み込み、読み込まれたデータを、データベースバッファ５５１に格納して、読込み要求の発行元であるクエリ実行部４２４もしくは加速部４２８に返す。クエリ実行部４２４および加速部４２８が、データベースバッファ管理部４３２にデータの読込みを要求する方法は同様であってよい。データベースバッファ管理部４３２は、データベース４５１を管理する際に、管理のための情報をデータベースバッファ管理情報５５０に格納して、利用してもよい。

　データベース管理システム４１２は、既存のデータベース管理システムに対して、主に、図１の破線枠内に示すプログラムモジュール、すなわち、加速部４２８、加速部有効性判定部４２６および協調制御情報生成部４３０が追加された（例えばアドインされた）データベース管理システムであると言える。既存のデータベース管理システムは、主に、クエリ実行部４２４、クエリ実行プラン生成部４２２、クエリ実行部４２４、データベースバッファ管理部４３２から構成されるが、本実施例のデータベース管理システム４１２は、加えて、主に、加速部４２８、加速部有効性判定部４２６および協調制御情報生成部４３０を有しており、これによって、１つのクエリの実行に要する時間を短縮することができる場合がある。即ち、データベース管理システム４１２の抜本的な改変なしに、１つのクエリの実行に要する時間を短縮することが期待される。

　前述したクエリ受付部４２１、クエリ実行プラン生成部４２２、クエリ実行部４２４、加速部４２８、加速部有効性判定部４２６、協調制御情報生成部４３０およびデータベースバッファ管理部４３２は、データベース管理システム４１２がプロセッサ４１４で実行されることによって実現されるが、これらのうち少なくとも１の構成要素が行う処理の少なくとも一部が、ハードウェアによって実現されていてもよい。データベース管理システム４１２をはじめとするコンピュータプログラムは、プログラムソースからデータベースサーバ４０１にインストールされていてもよい。プログラムソースは、例えば、データベースサーバ４０１が読み取り可能な記憶媒体であってもよい。

　図１に示すデータベース管理システム４１２の構成は一例に過ぎない。例えば、ある構成要素は複数の構成要素に分割されていてもよく、複数の構成要素が１つの構成要素に統合されていてもよい。

　図２は、実施例１にかかるデータベースの表４６２および索引４６１の定義を示す。

　データベース４５１は、表４６２として、例えば、整数型の値を格納するカラムｃ１および整数型の値を格納するカラムｃ２を含むＰａｒｔ表と、整数型の値を格納するカラムｃ３および文字型の値を格納するカラムｃ４を含むＬｉｎｅｉｔｅｍ表とを有する。また、データベース４５１は、索引４６１として、カラムｃ１の値に基づいたＰａｒｔ表に関する索引（Ｐａｒｔ索引）と、カラムｃ３の値に基づいたＬｉｎｅｉｔｅｍ表に関する索引（Ｌｉｎｅｉｔｅｍ索引）とを有する。

　図３は、実施例１にかかるＰａｒｔ表を示す。

　データベース４５１のＰａｒｔ表の各レコードは、カラムｃ１の値と、カラムｃ２の値から構成されている。

　図４は、実施例１にかかるＬｉｎｅｉｔｅｍ表を示す。

　データベース４５１のＬｉｎｅｉｔｅｍ表の各レコードは、カラムｃ３の値と、カラムｃ４の値から構成されている。

　図５は、実施例１にかかるクエリを示す。

　図５に示すクエリは、図２から図４までに示すデータベース４５１に対するクエリの一例である。図５に示すクエリは、Ｐａｒｔ表及びＬｉｎｅｉｔｅｍ表から、カラムｃ１の値が「１３０」であり、かつ、カラムｃ２の値とカラムｃ３の値とが同じであるものについて、カラムｃ１の値とカラムｃ４の値とを抽出することを意味する。

　図６は、実施例１にかかるクエリ実行プランを示す。

　図６に示すクエリ実行プランは、データベース管理システム４１２が図５に示すクエリを受け付けた場合に、クエリ実行プラン生成部４２２により生成されるクエリ実行プランの一例を示している。

　図６に示すクエリ実行プランは、Ｐａｒｔ表を外表としＬｉｎｅｉｔｅｍ表を内表とする２表のネステッドループ索引結合を意味し、具体的には、Ｐａｒｔ索引による索引検索を行うデータベースオペレーションＯＰ１と、当該索引検索の結果に基づきＰａｒｔ表からレコードを取得するデータベースオペレーションＯＰ２と、当該レコード取得の結果に基づきＬｉｎｅｉｔｅｍ索引による索引検索を行うデータベースオペレーションＯＰ３と、当該索引検索の結果に基づきＬｉｎｅｉｔｅｍ表からレコードを取得するデータベースオペレーションＯＰ４と、当該レコード取得の結果に基づき出力する結果レコードを生成するデータベースオペレーションＯＰ５からなる。

　図７は、実施例１にかかるクエリ実行の実行インスタンス木を示す。

　まず実行インスタンスなる概念を説明する。例えば、クエリ実行部４２４がクエリを実行する際に、あるデータベースオペレーションを実行して、その結果に基づき、別のデータベースオペレーションを実行することがある。この際、前段のデータベースオペレーションの実行の結果として得た複数のレコードの各々に対して、後段のデータベースオペレーションを実行することがある。即ち、後段のデータベースオペレーションを複数回実行することとなるが、その各々の実行においては、異なる入力値（状態の値であってもよい）に対して同一のデータベースオペレーションを実行することを意味する。このようなデータベースオペレーションの各々の実行を「実行インスタンス」と称し、この際の入力値を「実行コンテキスト」と称する。

　クエリ実行部４２４によって図５に示すクエリを図６に示すクエリ実行プランで実行した場合を考えると、データベースオペレーションの実行は図７に示す様で描かれる。図７は、実行インスタンスをノードとし、実行インスタンス間の従属関係をエッジとするグラフである。データベースオペレーションＯＰ１は、ｃ１＝１３０を条件としてＰａｒｔ索引による索引検索を行うものであるため、これを１つの実行インスタンス（＃１）としている。データベースオペレーションＯＰ１の実行の結果、ｃ１＝１３０に合致するＰａｒｔ表のレコード｜１３０｜ｉｄ１３１｜への参照が得られ、当該レコードを取得するためのデータベースオペレーションＯＰ２が呼び出される。図７においては、レコード｜１３０｜ｉｄ１３１｜を取得するためのデータベースオペレーションＯＰ２の実行を１つの実行インスタンス（＃２）としている。更に、データベースオペレーションＯＰ２の実行の結果、ｃ２＝ｃ３＝ｉｄ１３１を条件としてＬｉｎｅｉｔｅｍ索引による索引検索を行うデータベースオペレーションＯＰ３が呼び出される。図７においては、これを１つの実行インスタンス（＃３）としている。データベースオペレーションＯＰ３の実行の結果、ｃ３＝ｉｄ１３１に合致するＬｉｎｅｉｔｅｍ表のレコード｜ｉｄ１３１｜Ｄ｜への参照が得られ、当該レコードを取得するためのデータベースオペレーションＯＰ４が呼び出される。図７においては、レコード｜ｉｄ１３１｜Ｄ｜を取得するためのデータベースオペレーションＯＰ４の実行を１つの実行インスタンス（＃４）としている。この結果、更にデータベースオペレーションＯＰ５が呼び出されて実行され、結果レコード｜１３０｜Ｄ｜が生成される。図７においては、これを１つの実行インスタンス（＃５）としている。その後、実行インスタンス（＃３）の実行の結果によって、更にｃ３＝ｉｄ１３１に合致するＬｉｎｅｉｔｅｍ表のレコード｜ｉｄ１３１｜Ｅ｜への参照が得られることから、実行インスタンス（＃３）から更に当該レコードを取得するためのデータベースオペレーションＯＰ４が呼び出される。図７においては、レコード｜ｉｄ１３１｜Ｄ｜を取得するためのデータベースオペレーションＯＰ４の実行を１つの実行インスタンス（＃６）としている。この結果、更にデータベースオペレーションＯＰ５が呼び出されて実行され、結果レコード｜１３０｜Ｅ｜が生成される。更にその後、実行インスタンス（＃１）の実行の結果によって、ｃ１＝１３０に合致するＰａｒｔ表のレコード｜１３０｜ｉｄ１３２｜への参照が得られ、当該レコードを取得するためのデータベースオペレーションＯＰ２が呼び出される。図７においては、レコード｜１３０｜ｉｄ１３２｜を取得するためのデータベースオペレーションＯＰ２の実行を１つの実行インスタンス（＃８）としている。以降、同様にデータベースオペレーションの実行結果に基づき、次のデータベースオペレーションが呼び出されて実行される。即ち、実行インスタンスから別の実行インスタンスが生成されて実行される。この様は、図７の木構造のように示すことができる場合があることから、本実施例においては当該図面を「実行インスタンス木」と称することとする。

　クエリ実行部４２４は、データベースオペレーションを所定の順序で逐次的に実行するものであるため、クエリ実行部４２４によるクエリの実行は、図７の実行インスタンス木を、根の実行インスタンス（＃１）から開始して、既定の順序に従って、全ての実行インスタンスを実行していくことに相当する。例えば、規定の順序とは、（＃１）－＞（＃２）－＞（＃３）－＞（＃４）－＞（＃５）－＞（＃６）－＞（＃７）－＞（＃８）－＞・・・という順序であってよい。この際、各々の実行インスタンスについて、当該実行インスタンスが実行される順序を示す順序番号なる値を考える。例えば、実行インスタンスの順序番号としては、クエリ実行部４２４によって実行インスタンスが実行される順に自然数をインクリメントすることによって得た値をもって割り当てることとしてもよい。例えば、上記の例においては、実行インスタンス（＃１）の順序番号を１とし、実行インスタンス（＃２）の順序番号を２とし、実行インスタンス（＃３）の順序番号を３とし、以下同様に割り当ててもよい。

　一方、加速部４２８は、基本的にクエリ実行部４２４と同様に、図５に示すクエリを図６に示すクエリ実行プランで実行する。よって、加速部４２８によるクエリ実行は、クエリ実行部４２４と基本的に同じ実行インスタンス木をもって表すことができる。しかしながら、加速部４２８は動的にタスクを生成しながらクエリを実行するものであるため、実行インスタンスを実行する順序は、クエリ実行部４２４のそれとは異なる。即ち、根の実行インスタンス（＃１）から開始するものの、その順序は必ずしも既定の順序の通りとはならない可能性がある。例えば、図７の例においては、実行インスタンス（＃１）においてデータベースオペレーションＯＰ１を実行した結果、クエリ実行部４２４によるクエリ実行手続きでは必ず実行インスタンス（＃２）が最初に実行されるが、加速部４２８によるクエリ実行手続きでは実行インスタンス（＃２）が最初に実行されるかもしれないし、実行インスタンス（＃８）が先に辿られるかもしれない。また、加速部４２８による実行インスタンスの実行順序には再現性がない場合がある。例えば、最初にクエリが実行された際には、実行インスタンス（＃１）の後には最初に実行インスタンス（＃８）が実行されたとしても、次に同じクエリが実行された場合には実行インスタンス（＃１）の後には最初に実行インスタンス（＃１６）が辿られる可能性も否めない。

　本実施例においては、加速部４２８がクエリを実行する際にデータベース４５１から読み込んだデータが、データベースバッファ５５１に格納される場合がある。クエリ実行部４２４が同じクエリを並行して実行する際に、新たにデータベース４５１からデータを読み込むことなくデータベースバッファ５５１からデータを読み込めばよいという場合が生じる可能性があり、これによって、クエリ実行部４２４によるクエリ実行手続きに要する時間が短縮される可能性がある。このような時間の短縮の効果を高めるためには、まず加速部４２８がデータベースバッファ５５１にデータを格納してから、同じデータをクエリ実行部４２４がデータベースバッファ５５１から取得するようなことが望ましい。換言すれば、クエリ実行手続きにおける同じ実行インスタンスについては、加速部４２８が先行して実行することが望ましい。更には、データベースバッファ５５１の容量は有限であることから、加速部４２８がデータベースバッファ５５１にデータを格納してから、一定の時間もしくはステップ内に同じデータをクエリ実行部４２４がデータベースバッファ５５１から取得するようなことが望ましい。換言すれば、クエリ実行手続きにおける同じ実行インスタンスについては、加速部４２８が先行して実行するものの、クエリ実行部４２４があまり大きく遅れずに実行することが望ましい。まとめると、クエリ実行部４２４による実行インスタンスの実行順序は規定のものであるため、加速部４２８はクエリ実行部４２４による実行インスタンスの実行順序を参考に、実行インスタンスの実行順序を調整することによって、クエリ実行部４２４によるクエリの実行に要する時間を短縮する効果を高めることが期待される。具体的な手続きについては後述する。

　なお、実行インスタンス木として、木構造を例に説明したが、これはグラフであってもよい。例えば、複数の実行インスタンスから単一の実行インスタンスへエッジが張られるような場合があってもよい。これは、前者の実行インスタンスにおけるデータベースオペレーションの実行結果を全て得て、後者の実行インスタンスにおけるデータベースオペレーションが呼び出されることを意味する。

　図８は、実施例１にかかるクエリ実行プラン情報４２３の構成を示す。

　クエリ実行プラン情報４２３は、図６に示すクエリ実行プランのメモリ４１６上における情報である。クエリ実行プラン情報４２３は、開始データベースオペレーションテーブル８０１とデータベースオペレーションテーブル８０２から構成される。開始データベースオペレーションテーブル８０１は、クエリの実行において、最初に実行するデータベースオペレーションを示す。データベースオペレーションテーブル８０２は、クエリの実行において実行されるデータベースオペレーションの一覧である。

　開始データベースオペレーションテーブル８０１は、１のレコードを有し、属性としては、開始データベースオペレーションＩＤ８１１を有する。開始データベースオペレーションＩＤ８１１は、クエリの実行において、最初に実行するデータベースオペレーションを指し示すデータベースオペレーションＩＤを示す。

　データベースオペレーションテーブル８０２は、データベースオペレーション毎にレコードを有し、属性としては、データベースオペレーションＩＤ８２１、次のデータベースオペレーションＩＤ８２２、データベースオペレーション概要８２３、データベースオペレーション詳細８２４を有する。データベースオペレーションＩＤ８２１は、クエリ実行プラン中のデータベースオペレーションを一意に識別するためのＩＤである。次のデータベースオペレーションＩＤ８２２は、当該データベースオペレーションがその実行後に呼び出す次のデータベースオペレーションのデータベースオペレーションＩＤである。データベースオペレーション概要８２３は、当該データベースオペレーションによって行われる処理の種別を表す。データベースオペレーション詳細８２４は、当該データベースオペレーションによって行われる処理の詳細を表す。

　図９は、実施例１にかかる統計情報４２７の構成を示す。

　統計情報４２７は、データベース４５１が含むデータに関する情報を含むもので、例えば、データベース４５１が有するデータベース統計４６３の全部もしくは一部のメモリ４１６上における情報であるが、更にデータベース４５１が含む情報に基づき構成してもよい。統計情報４２７は、一般統計情報テーブル９０１を含む。一般統計情報テーブル９０１は、データベース４５１が含む表４６２もしくは索引４６１におけるに関する情報を含み、例えば、索引４６１のエントリ数を表す情報、表４６２のレコード数を表す情報、カラム毎の値の最大値、平均値、最小値、カラム毎の値分布等を含む。

　一般統計情報テーブル９０１は、統計項目毎にレコードを有し、属性としては、例えば、表９１１、列９１２、統計値９１３を有する。表９１１は、統計項目が関連する表を表す。列９１２は、統計項目が関連する列を表す。ただし、特定の列に関連しない場合は、列９１２は「－」とする。統計値９１３は、統計の種別の具体的な値を表す。図９においては、第１の統計項目は、Ｐａｒｔ表のｃ１列に関する度数分布を意味しており、ｃ１の値が０～９９９であるレコードの数は２０，０００、１０００～１９９９であるレコードの数は５０，０００であることを意味している。第２の統計項目は、Ｌｉｎｅｉｔｅｍ表のｃ３列に関するカージナリティが１，０００，０００であることを意味している。第３の統計項目は、Ｌｉｎｅｉｔｅｍ表の全行数が６，０００，０００であることを意味している。

　図１０は、実施例１にかかるクエリ実行部状態管理情報４２５の構成を示す。

　クエリ実行部状態管理情報４２５は、実行中データベースオペレーションテーブル１００１とスタック中データベースオペレーションテーブル１００２を有する。実行中データベースオペレーションテーブル１００１は、クエリ実行部４２４において現在実行中のデータベースオペレーションの実行情報を管理する。即ち、当該テーブル１００１は、クエリ実行部４２４において現在実行中の実行インスタンスの情報を管理する。スタック中データベースオペレーションテーブル１００２は、クエリ実行部４２４においてスタックされたデータベースオペレーションの実行情報を管理する。即ち、当該テーブル１００２は、クエリ実行部４２４において現在までにスタックされた実行インスタンスの情報を管理する。

　クエリ実行部４２４は、逐次的にデータベースオペレーションを実行するものであるから、実行中のデータベースオペレーションの数は１であり、即ち、実行中の実行インスタンスの数は１である。実行中データベースオペレーションテーブル１００１は、常に１のレコードを有する。属性としては、データベースオペレーションＩＤ１０１１、実行コンテキスト１０１２を有する。データベースオペレーションＩＤ１０１１は、現在実行中のデータベースオペレーションを示すデータベースオペレーションＩＤである。実行コンテキスト１０１２は、当該データベースオペレーションの実行コンテキストである。例えば、図１０の例においては、クエリ実行部４２４は、現在データベースオペレーションＯＰ３を実行しており、当該データベースオペレーションは実行コンテキストとしてシブリング＃：１の情報を有しており、即ち、親のデータベースオペレーションにとって１番目のデータベースオペレーションの呼び出しであることを意味している。

　スタック中データベースオペレーションテーブル１００２は、スタックされたデータベースオペレーションの実行、即ち、スタックされた実行インスタンスの毎にレコードを有し、属性としては、スタック深度１０２１、データベースオペレーションＩＤ１０２２、実行コンテキスト１０２３を有する。スタック深度１０２１は、スタックされた順序を示す。データベースオペレーションＩＤ１０２２は、スタックされたデータベースオペレーションを示すデータベースオペレーションＩＤである。実行コンテキスト１０２３は、スタックされたデータベースオペレーションの実行コンテキストである。例えば、図１０の例においては、クエリ実行部４２４は、最初にデータベースオペレーションＯＰ１の実行をスタックしている。データベースオペレーションＯＰ１は開始データベースオペレーションであることから、実行コンテキストはここでは示されていない。また、図１０の例においては、クエリ実行部４２４は、次にデータベースオペレーションＯＰ２の実行をスタックしている。当該データベースオペレーションは実行コンテキストとしてシブリング＃：２の情報を有しており、即ち、親のデータベースオペレーションＯＰ１にとって２番目のデータベースオペレーションの呼び出しであることを意味している。

　図１１は、実施例１にかかる加速部状態管理情報４２９の構成を示す。

　加速部状態管理情報４２９は、実行中実行インスタンステーブル１１０１と、キュー中実行インスタンステーブル１１０２と、実行済実行インスタンステーブル１１０３を有する。実行中実行インスタンステーブル１１０１は、加速部４２８において現在実行中の実行インスタンスの情報を管理する。キュー中実行インスタンステーブル１１０２は、現在加速部４２８においてキューイングされた実行待ち状態の実行インスタンスの情報を管理する。実行済実行インスタンステーブル１１０３は、既に加速部４２８において実行された実行済状態の実行インスタンスの情報を管理する。

　実行中実行インスタンステーブル１１０１は、実行中の実行インスタンスの毎にレコードを有し、属性としては、実行インスタンスＩＤ１１１１、データベースオペレーションＩＤ１１１２、実行コンテキスト１１１３、親実行インスタンスＩＤ１１１４、予測順序番号１１１５を有する。実行インスタンスＩＤ１１１１は、現在実行中の実行インスタンスを示す実行インスタンスＩＤである。データベースオペレーションＩＤ１１１２は、当該実行インスタンスにおいて実行するデータベースオペレーションを示すデータベースオペレーションＩＤである。実行コンテキスト１１１３は、当該実行インスタンスにおいてデータベースオペレーションを実行する際の実行コンテキストである。親実行インスタンスＩＤ１１１４は、当該実行インスタンスを生成した親の実行インスタンスを示す実行インスタンスＩＤである。予測順序番号１１１５は、当該実行インスタンスについて、後述する手続きによって予測された順序番号である。例えば、図１１の例においては、加速部４２８は少なくとも＃４の実行インスタンスと＃１０の実行インスタンスを並行して実行中である。更に例えば、＃４の実行インスタンスは、データベースオペレーションＯＰ４を実行し、この際の実行コンテキストとしてはシブリング＃：１であり親の実行インスタンス＃３にとって１番目の実行インスタンスの生成であり、後述する手続きによって予測された順序番号は４である。

　キュー中実行インスタンステーブル１１０２は、キューイングされた実行待ち状態の実行インスタンスの毎にレコードを有し、属性としては、実行インスタンスＩＤ１１２１、データベースオペレーションＩＤ１１２２、実行コンテキスト１１２３、親実行インスタンスＩＤ１１２４、予測順序番号１１２５を有する。実行インスタンスＩＤ１１２１は、キューイングされた実行待ち状態の実行インスタンスを示す実行インスタンスＩＤである。データベースオペレーションＩＤ１１２２は、当該実行インスタンスにおいて実行するデータベースオペレーションを示すデータベースオペレーションＩＤである。実行コンテキスト１１２３は、当該実行インスタンスにおいてデータベースオペレーションを実行する際の実行コンテキストである。親実行インスタンスＩＤ１１２４は、当該実行インスタンスを生成した親の実行インスタンスを示す実行インスタンスＩＤである。予測順序番号１１２５は、当該実行インスタンスについて、後述する手続きによって予測された順序番号である。例えば、図１１の例においては、加速部４２８は少なくとも＃６の実行インスタンスと＃１２の実行インスタンスと＃１４の実行インスタンスをキューイングしている。更に例えば、＃６の実行インスタンスは、データベースオペレーションＯＰ４を実行し、この際の実行コンテキストとしてはシブリング＃：２であり親の実行インスタンス＃３にとって２番目の実行インスタンスの生成であり、後述する手続きによって予測された順序番号は６である。

　実行済実行インスタンステーブル１１０３は、実行済状態の実行インスタンスの毎にレコードを有し、属性としては、実行インスタンスＩＤ１１３１、データベースオペレーションＩＤ１１３２、実行コンテキスト１１３３、親実行インスタンスＩＤ１１３４、予測順序番号１１３５を有する。実行インスタンスＩＤ１１３１は、実行済状態の実行インスタンスを示す実行インスタンスＩＤである。データベースオペレーションＩＤ１１３２は、当該実行インスタンスにおいて実行するデータベースオペレーションを示すデータベースオペレーションＩＤである。実行コンテキスト１１３３は、当該実行インスタンスにおいてデータベースオペレーションを実行する際の実行コンテキストである。親実行インスタンスＩＤ１１３４は、当該実行インスタンスを生成した親の実行インスタンスを示す実行インスタンスＩＤである。予測順序番号１１３５は、当該実行インスタンスについて、後述する手続きによって予測された順序番号である。例えば、図１１の例においては、加速部４２８は少なくとも＃１、＃２、＃８、＃３、＃９の実行インスタンスの実行を完了している。更に例えば、＃１の実行インスタンスは、データベースオペレーションＯＰ１を実行し、当該データベースオペレーションは開始データベースオペレーションであることから親の実行インスタンスは存在せず、実行コンテキストも特に記録されず、後述する手続きによって予測された順序番号は１である。

　図１２は、実施例１にかかる協調制御情報４３１の構成を示す。

　協調制御情報４３１は、クエリ実行部４２４によるクエリの実行に要する時間を短縮する効果を高めることを目的として、後述の手続きによって、加速部４２８がクエリ実行部４２４による実行インスタンスの実行順序を参考として実行インスタンスの実行順序を調整するためのものである。クエリの実行に要する実行インスタンスの全容、例えば図７に示す実行インスタンス木は、クエリの実行が完了して初めてそのすべてが判明するものであり、クエリを実行する前にもしくはクエリを実行している途中にその全容を把握することは不可能である。しかしながら、データベース４５１に関する統計情報４２７や、クエリ実行プラン等の情報を用いることにより、完全な精度ではないものの、実行インスタンスの全容を予測することは可能であり、当該予測情報を用いて、加速部４２８による実行インスタンスの実行順序を調整することにより、クエリ実行部４２４によるクエリの実行に要する時間を短縮する効果を高めることが期待される。本実施例においては、協調制御情報生成部４３０が、後述の手続きによって、データベースに関する統計情報４２７や、クエリ実行プラン等の情報を用いることにより、実行インスタンスの全容を予測し、予測した情報を協調制御情報４３１としてメモリ４１６に格納する。また、後述の手続きによって、協調制御情報４３１を用いて、加速部４２８による実行インスタンスの実行順序が調整される。

　協調制御情報４３１は、開始予測実行インスタンステーブル１２０１と予測実行インスタンステーブル１２０２を有する。開始予測実行インスタンステーブル１２０１は、クエリの実行において、加速部４２８における最初に実行すると予測される実行インスタンスを示す。予測実行インスタンステーブル１２０２は、クエリの実行において、加速部４２８が実行すると予測される実行インスタンスの一覧である。

　開始予測実行インスタンステーブル１２０１は、１のレコードを有し、属性としては、開始予測実行インスタンスＩＤ１２１１を有する。開始予測実行インスタンスＩＤ１２１１は、クエリの実行において、加速部４２８における最初に実行すると予測される実行インスタンスを指し示す実行インスタンスＩＤを示す。

　予測実行インスタンステーブル１２０２は、加速部４２８が実行すると予測される実行インスタンスの毎にレコードを有し、属性としては、予測実行インスタンスＩＤ１２２１、データベースオペレーションＩＤ１２２２、予測実行コンテキスト１２２３、子予測実行インスタンスＩＤ１２２４、親予測実行インスタンスＩＤ１２２５、予測順序番号１２２６を有する。予測実行インスタンスＩＤ１２２１は、加速部４２８が実行すると予測される実行インスタンスを示す予測実行インスタンスＩＤである。データベースオペレーションＩＤ１２２２は、当該予測実行インスタンスにおいて実行されるデータベースオペレーションを示すデータベースオペレーションＩＤである。予測実行コンテキスト１２２３は、当該予測実行インスタンスにおいてデータベースオペレーションを実行する際に予測される実行コンテキストである。子予測実行インスタンスＩＤ１２２４は、当該予測実行インスタンスによって生成されることが予測される予測実行インスタンスを示す予測実行インスタンスＩＤである。親予測実行インスタンスＩＤ１２２５は、当該予測実行インスタンスを生成することが予測される予測実行インスタンスを示す予測実行インスタンスＩＤである。予測順序番号１２２６は、当該予測実行インスタンスがクエリ実行部４２４によって実行されると予測されるその実行の順序番号である。例えば、図１２の例は、クエリの実行においては、＃＃１、＃＃２、＃＃３等と一覧される実行インスタンスが生成されるものと予測されている。予測実行インスタンス＃＃１は、最初に生成されるものであり、データベースオペレーションＯＰ１を実行し、最初に生成されるものであることから実行コンテキストは特になく、親の実行インスタンスもなく、順序番号は１であり、更に＃＃２、＃＃８、＃＃１６、＃＃２２等の予測実行インスタンスを生成するものであることが予測されている。予測実行インスタンス＃＃２は、データベースオペレーションＯＰ２を実行し、予測実行インスタンス＃１から実行コンテキストとしてはシブリング：１として即ち１番目として生成されるものであり、順序番号は２であり、更に＃＃３の予測実行インスタンスを生成するものであることが予測されている。

　以下では、更に図面を参照して、本実施例で行われる種々の処理を説明する。

　図１３は、実施例１にかかるクエリを受け付け、クエリ実行プランを生成し、クエリを実行する手続きを示す。なお、図１３は、１つのクエリを受け付けた場合の手続きを示すが、２以上のクエリを受け付けた場合には、データベース管理システム４１２は、その２以上のクエリのそれぞれについて並行して図１３に示す手続きを行ってもよいし、逐次的に図１３に示す手続きを行ってもよい。この際、それぞれのクエリの毎に、図８から図１２に示す情報が構成されてよい。これは、例えば、各テーブルにおいてクエリを識別する属性を設けることによって行われてよい。

　Ｓ１３０１において、クエリ受付部４２１は、アプリケーションプログラム４１１が発行するクエリを受け付け、例えば、メモリ４１６に格納する。クエリは、例えば、構造化問合せ言語（ＳＱＬ、Structured Query Language）で記載されていてもよい。

　引き続き、Ｓ１３０２において、クエリ実行プラン生成部４２２は、データベース４５１のデータベース統計４６３もしくはメモリ４１６上の統計情報４２７に基づき、クエリ受付部４２１が受け付けたクエリからクエリ実行プランを生成し、生成したクエリ実行プランを表す情報として、クエリ実行プラン情報４２３をメモリ４１６に格納する。この際、クエリ実行プラン生成部４２２は、１以上のクエリ実行プランの候補を生成して、その各々についてコスト計算を行い、例えば、コストが最小である等の基準によって、１のクエリ実行プランの候補をクエリ実行プランとして選択してもよい。また、クエリ実行プランは、Ｓ１３０１で受け付けたクエリの記述に含まれる指示、例えば、ＳＱＬヒント等に基づいて生成されてもよい。

　引き続き、Ｓ１３０３において、加速部有効性判定部４２６は、データベース管理システム４１２において加速部４２８が有効であるかどうかを判定する。具体的には、Ｓ１３０３においては、加速部有効性判定部４２６は、加速部４２８がデータベース管理システム４１２に含まれており、これが有効に動作するようになっているかを判定する。例えば、これはデータベース管理システム４１２の設定パラメータ等の設定情報を基に判定されてもよい。また、例えば、当該設定情報は、データベース管理システム４１２から参照可能なストレージ（例えば、ストレージ装置４１５もしくは外部ストレージ装置４０２）に記憶されており、その設定情報が、所定の指示を含む場合には、加速部４２８が有効であり、含まない場合には有効ではないと判定してもよい。加速部有効性判定部４２６の判定の結果が肯定的であれば、引き続きＳ１３０４ならびＳ１３０５が実行してからＳ１３０６が実行され、否定的であれば、Ｓ１３０６が実行される。

　Ｓ１３０４において、協調制御情報生成部４３０が、クエリ実行プラン生成部４２２によって生成されたクエリ実行プランに基づき、協調制御情報４３１を生成する。この手続きの詳細は後述する。

　引き続き、Ｓ１３０５において、加速部有効性判定部４２６は、クエリ実行プラン生成部４２２によって生成されたクエリ実行プランを入力として、加速部４２８を駆動する。これにより、クエリ実行部４２４によるＳ１３０６の手続きの実行と並行して、加速部４２８は図１３の右側に記載するＳ１３１１からＳ１３１２までの手続きを実行する。

　Ｓ１３０６において、クエリ実行部４２４は、クエリ実行プラン生成部４２２によって生成されたクエリ実行プランに基づき、第１のクエリ実行手続きによって受け付けたクエリを実行する。この手続きの詳細は後述する。クエリ実行部４２４は、第１のクエリ実行手続きを完了することにより、クエリの実行を完了し、クエリの実行により得た結果を、クエリ発行元であるアプリケーションプログラム４１１に返す。なお、第１のクエリ実行手続きにおいては、クエリ実行部４２４は、データベースバッファ５５１からデータを読み込む。したがって、クエリ実行部４２４は、第１のクエリ実行手続きにおいて、後述する第２のクエリ実行手続きによってデータベースバッファ５５１に既に読み込まれたデータを使用することができる。即ち、クエリ実行部４２４は、第１のクエリ実行手続きにおいて、データベースに対する入出力を伴わずにデータベースオペレーションを実行することができる場合がある。

　Ｓ１３１１において、加速部４２８は、入力されたクエリ実行プランが加速可能なクエリ実行プランであるか否かを判定する。ここで、加速可能とは、当該クエリ実行プランに基づき、第２のクエリ実行手続きを並行して実行することにより、第１のクエリ実行手続きによるクエリ実行手続きにかかる時間を短縮することが可能であることを意味する。

　Ｓ１３１１の判定（クエリ実行プランが加速可能であるか否かの判定）は、例えば、あらかじめデータベース管理システム４１２に対して加速可能であることの所定の条件を与えておき、クエリ実行プランが当該条件を満たすか否かを判定することによって行ってもよい。また、クエリ実行プランが加速可能であるか否かの判定は、上記とは別に、もしくは、上記に加えて、以下に述べる基準に基づいて行ってもよい。

　Ｓ１３１１において、加速部４２８は、第２のクエリ実行手続きによるクエリの実行に使用可能な資源の量が、所定の条件を満たしていれば、加速可能と判定し、所定の条件を満たしていなければ、加速可能ではないと判定してもよい。ここで、使用可能な資源の量としては、例えば、使用可能なメモリ４１６の容量や、データベースバッファ５５１の容量であってもよい。

　Ｓ１３１１の判定は、Ｓ１３０１で受け付けたクエリの記述に含まれる指示、例えば、ＳＱＬヒント等に基づいて行われてもよい。例えば、加速部４２８は、Ｓ１３０１で受け付けたクエリに所定の指示が含まれる場合には、当該クエリは加速可能であると判定し、含まれない場合には、加速可能ではないと判定してもよい。

　Ｓ１３１１の判定は、データベース管理システム４１２の設定パラメータ等の値に基づいて行われてもよい。例えば、加速部４２８は、データベース管理システム４１２から参照可能なストレージ（例えば、ストレージ装置４１５もしくは外部ストレージ装置４０２）に記憶された設定情報が、所定の指示を含む場合には加速可能と判定し、含まない場合には加速可能ではないと判定してもよい。

　Ｓ１３１１の判定の結果が肯定的であれば、加速部４２８はＳ１３１２を実行し、否定的であれば、加速部４２８は終了する。

　Ｓ１３１２において、加速部４２８は、クエリ実行プラン生成部４２２によって生成されたクエリ実行プランに基づき、第２のクエリ実行手続きによって受け付けたクエリを実行する。この手続きの詳細は後述する。加速部４２８は、第２のクエリ実行手続きを完了することにより、クエリの実行を完了する。この際、加速部４２８は、第２のクエリ実行手続きの実行の途中であっても、クエリ実行部４２４が第１のクエリ実行手続きを完了した場合には、第２のクエリ実行手続きの実行を停止して、終了してもよい。加速部４２８は、クエリ実行部４２４が第１のクエリ実行手続きを完了したことを、例えば、クエリ実行部状態管理情報４２５から判定してもよい。

　なお、第２のクエリ実行手続きにおいて、加速部４２８は、データベースバッファ５５１にデータベースから読み込んだデータを格納することがある。したがって、クエリ実行部４２４が、第１のクエリ実行手続きにおいて、第２のクエリ実行手続きによってデータベースバッファ５５１に既に格納されたデータを使用することができることがある。

　なお、Ｓ１３０４に示す協調制御情報４３１を生成する手続きは、上記に代えて、例えば、加速部４２８においてＳ１３１１の実行に先だって行ってもよく、もしくは、クエリ実行部４２４においてＳ１３０６の実行に先だって行ってもよい。この場合、Ｓ１３１１およびＳ１３０６の実行は、協調制御情報４３１の生成を待って行われる。

　図１４は、実施例１にかかる協調制御情報４３１を生成する手続きを示す。当該手続きは、図１３のＳ１３０４の手続きに対応する。

　Ｓ１４０１において、協調制御情報生成部４３０は、クエリ実行プラン情報４２３および統計情報４２７を参照して協調制御情報４３１を生成する。

　例えば、以下では、図８のクエリ実行プラン情報４２３および図９の統計情報４２７のうちの一般統計情報テーブル９０１の例で説明する。データベースオペレーションＯＰ１はｃ１＝１３０の条件によってＰａｒｔ表の索引検索を行う。統計情報４２７の有するＰａｒｔ表の度数分布では、ｃ１の階級０～９９９の度数は２０，０００であることから、平均的にｃ１＝１３０を満たすＰａｒｔ表のレコードの数は、２０，０００×１÷１０００＝２０であると見積られる。即ち、データベースオペレーションＯＰ１の実行の結果、２０の異なる入力に対してデータベースオペレーションＯＰ２が都度実行されると予測される。データベースオペレーションＯＰ２は、レコード参照に基づきレコードを取得する。この場合では、１のレコード参照には１のレコードが対応するため、各々のデータベースオペレーションＯＰ２の実行の結果、１のデータベースオペレーションＯＰ３が実行されると予測される。データベースオペレーションＯＰ３は、Ｐａｒｔ表から取得したレコードに基づき、ｃ２＝ｃ３の条件によってＬｉｎｅｉｔｅｍ表の索引検索を行う。統計情報４２７の有するＬｉｎｅｉｔｅｍ表のｃ３列に対するカージナリティは１，０００，０００であり、全行数は６，０００，０００であることから、平均的には１のｃ３の値に対して６，０００，０００÷１，０００，０００＝６のレコードが対応する。よって、各々のデータベースオペレーションＯＰ３の実行の結果、６の異なる入力に対してデータベースオペレーションＯＰ４が都度実行されると予測される。データベースオペレーションＯＰ４は、レコード参照に基づきレコードを取得する。この場合では、１のレコード参照には１のレコードが対応するため、各々のデータベースオペレーションＯＰ４の実行の結果、１のデータベースオペレーションＯＰ５が実行されると予測される。以上のような手続きによって、統計的な一様性を仮定すると、以下のような実行インスタンス木が予測される。
・データベースオペレーションＯＰ１に対応する実行インスタンスは１である。これが、最初に実行する実行インスタンス（予測実行インスタンス）とされる。
・この実行インスタンスから２０の実行インスタンス（データベースオペレーションＯＰ２を実行）が生成される。即ち、データベースオペレーションＯＰ２に対応する実行インスタンスは２０である。
・この各々の実行インスタンスから１の実行インスタンス（データベースオペレーションＯＰ３を実行）が生成される。即ち、データベースオペレーションＯＰ３に対応する実行インスタンスは２０である。
・この各々の実行インスタンスから６の実行インスタンス（データベースオペレーションＯＰ４を実行）が生成される。即ち、データベースオペレーションＯＰ４に対応する実行インスタンスは１２０である。
・この各々の実行インスタンスから１の実行インスタンス（データベースオペレーションＯＰ５を実行）が生成される。即ち、データベースオペレーションＯＰ５に対応する実行インスタンスは１２０が生成される。

　このような予測実行インスタンス木は、図１２に示す構造でメモリ４１６に格納される。予測実行インスタンス木上において、開始予測実行インスタンスから開始して、クエリ実行部４２４におけるクエリの実行手順に基づき、予測実行インスタンスを辿っていくことにより、各々の予測実行インスタンスにおける予測順序番号を算出することができる。

　この際、協調制御情報生成部４３０は、クエリ実行プラン情報４２３および統計情報４２７を参照して、予測実行インスタンス木の全情報をあらかじめ生成し、予測実行インスタンスを辿ることによって、例えば上記の例においては、データベースオペレーションＯＰ１に対応する実行インスタンスの予測順序番号を１、１番目に実行されるデータベースオペレーションＯＰ２に対応する実行インスタンス（即ち、シブリング＃：１）の予測順序番号を２として、同様に値をインクリメントすることにより予測順序番号を得ていってもよい。また、協調制御情報生成部４３０は、予測実行インスタンス木に関する部分的な情報を生成しておいて、のちに協調制御情報４３１が参照された際に、これを算出可能なようにしておいてもよい。例えば、また、上記の例においては、データベースオペレーションＯＰ２に対応する実行インスタンスは、平均的に１のデータベースオペレーションＯＰ３に対応する実行インスタンスを生成し、データベースオペレーションＯＰ３に対応する実行インスタンスは、平均的に６のデータベースオペレーションＯＰ３に対応する実行インスタンスを生成し、データベースオペレーションＯＰ３に対応する実行インスタンスは、平均的に１のデータベースオペレーションＯＰ４に対応する実行インスタンスを生成し、データベースオペレーションＯＰ４に対応する実行インスタンスは、平均的に１のデータベースオペレーションＯＰ５に対応する実行インスタンスを生成すると予測されている。協調制御情報生成部４３０は、このような統計的な概要情報のみをメモリ４１６に格納しておいて、のちに協調制御情報４３１が参照された際に、これを用いて、例えば、２番目に実行されるデータベースオペレーションＯＰ２に対応する実行インスタンス（即ち、シブリング＃：２）の予測順序番号を、２＋１＋１×６＋１×６×１＋１＝１６と計算によって求めてもよい。

　図１５は、実施例１にかかる第１のクエリ実行手続きを示す。第１のクエリ実行手続きは、図１３のＳ１３０６の手続きに対応する。

　Ｓ１５０１において、クエリ実行部４２４は、クエリ実行プラン情報４２３を参照し、開始データベースオペレーションをｘ（メモリ４１６上の局所変数）に設定する。

　引き続き、Ｓ１５０２において、クエリ実行部４２４は、ｘをクエリ実行部状態管理情報４２５の実行中データベースオペレーションテーブル１００２に反映する。

　引き続き、Ｓ１５０３において、クエリ実行部４２４は、ｘの実行に必要なデータベースページをデータベース４５１から取得する。この際、クエリ実行部４２４は、当該データベースページの読込み要求をデータベースバッファ管理部４３２に発行する。データベースバッファ管理部４３２は、当該データベースページがデータベースバッファ５５１に既に格納されていれば、格納されているデータベースページをデータベースバッファ５５１からクエリ実行部４２４に返し、格納されていなければ、データベース４５１が格納されている外部ストレージ装置４０２に読込み要求を発行してデータベース４５１から読み込まれた当該データベースページをデータベースバッファ５５１に格納しクエリ実行部４２４に返す。この際、本実施例によれば、クエリ実行部４２４によって実行される第１のクエリ実行の手続きにおいては、データベースオペレーションの実行に必要なデータベースページは、加速部４２８によって実行される第２のクエリ実行手続きによって既にデータベースバッファ５５１に格納されている場合がある。なお、ｘの実行にデータベースページが必要ない場合には、Ｓ１５０３の手続きは行わなくてよい。

　引き続き、Ｓ１５０４において、クエリ実行部４２４は、ｘを実行する。この際、Ｓ１５０３で読み込んだデータベースページを用いてよい。

　引き続き、Ｓ１５０５において、クエリ実行部４２４は、Ｓ１５０４において行ったｘの実行結果に基づき、更にクエリ実行プラン情報４２３を参照して、実行するべき次のデータベースオペレーションがあるかどうかを判定する。判定の結果が肯定的であれば、Ｓ１５０６が実行され、否定的であれば、Ｓ１５０７が実行される。

　Ｓ１５０６において、クエリ実行部４２４は、更にｘに設定されているデータベースオペレーションをクエリ実行部状態管理情報４２５のスタック中データベースオペレーションテーブル１００２に退避し、新たにｘに実行するべき次のデータベースオペレーションを設定し、Ｓ１５０２を実行する。

　Ｓ１５０７において、クエリ実行部４２４は、ｘの実行に必要なデータベースページであって未読込みのものがデータベース４５１にあるかどうかを判定する。判定の結果が肯定的であれば、Ｓ１５０３が実行され、否定的であれば、Ｓ１５０８が実行される。

　Ｓ１５０８において、クエリ実行部４２４は、クエリ実行部状態管理情報４２５の実行中データベースオペレーションテーブルからｘを削除する。

　引き続き、Ｓ１５０９において、クエリ実行部４２４は、クエリ実行部状態管理情報４２５のスタック中データベースオペレーションテーブル１００２を参照し、実行するべきデータベースオペレーションが積まれているかどうかを判定する。判定の結果が肯定的であれば、Ｓ１５１０が実行され、否定的であれば、クエリ実行部４２４における第１のクエリ実行手続きが終了する。

　Ｓ１５１０において、クエリ実行部４２４は、クエリ実行部状態管理情報４２５のスタック中データベースオペレーションテーブル１００２から最上位の（スタック深度の値の最も大きい）データベースオペレーションを取り出し、ｘに設定し、Ｓ１５０２を実行する。

　例えば、図７を用いて、Ｓ１５０１からＳ１５１０までのクエリ実行部４２４によるクエリの実行を説明すると、以下の通りである。
（０１）クエリ実行部４２４は、索引条件ｃ１＝１３０に基づきＰａｒｔ索引を検索するためのデータベースオペレーションＯＰ１の実行を開始する。
（０２）クエリ実行部４２４は、データベースオペレーションＯＰ１の実行によって、索引条件ｃ１＝１３０を満たす最初のＰａｒｔ表のレコード｜１３０｜ｉｄ１３１｜への参照を得る。
（０３）クエリ実行部４２４は、Ｐａｒｔ表のレコード｜１３０｜ｉｄ１３１｜への参照に基づきＰａｒｔ表からレコードを取得するためのデータベースオペレーションＯＰ２の実行を開始する。
（０４）クエリ実行部４２４は、データベースオペレーションＯＰ２の実行によって、Ｐａｒｔ表からレコード｜１３０｜ｉｄ１３１｜を取得する。
（０５）クエリ実行部４２４は、Ｐａｒｔ表から取得したレコードに基づき索引条件ｃ３＝ｉｄ１３１に基づきＬｉｎｅｉｔｅｍ索引を検索するためのデータベースオペレーションＯＰ３の実行を開始する。
（０６）クエリ実行部４２４は、データベースオペレーションＯＰ３の実行によって、索引条件ｃ３＝ｉｄ１３１を満たす最初のＬｉｎｅｉｔｅｍ表のレコード｜ｉｄ１３１｜Ｄ｜への参照を得る。
（０７）クエリ実行部４２４は、Ｌｉｎｅｉｔｅｍ表のレコード｜ｉｄ１３１｜Ｄ｜への参照に基づきＬｉｎｅｉｔｅｍ表からレコードを取得するためのデータベースオペレーションＯＰ４の実行を開始する。
（０８）クエリ実行部４２４は、データベースオペレーションＯＰ４の実行によって、Ｌｉｎｅｉｔｅｍ表からレコード｜ｉｄ１３１｜Ｄ｜を取得する。
（０９）クエリ実行部４２４は、結果レコードを生成するためのデータベースオペレーションＯＰ５の実行を開始する。
（１０）クエリ実行部４２４は、データベースオペレーションＯＰ５の実行によって、結果レコード｜１３０｜Ｄ｜を出力する。
（１１）クエリ実行部４２４は、データベースオペレーションＯＰ３の実行によって、索引条件ｃ３＝ｉｄ１３１を満たす２番目のＬｉｎｅｉｔｅｍ表のレコード｜ｉｄ１３１｜Ｅ｜への参照を得る。
（１２）クエリ実行部４２４は、Ｌｉｎｅｉｔｅｍ表のレコード｜ｉｄ１３１｜Ｅ｜への参照に基づきＬｉｎｅｉｔｅｍ表からレコードを取得するためのデータベースオペレーションＯＰ４の実行を開始する。
（１３）クエリ実行部４２４は、データベースオペレーションＯＰ４の実行によって、Ｌｉｎｅｉｔｅｍ表からレコード｜ｉｄ１３１｜Ｅ｜を取得する。
（１４）クエリ実行部４２４は、結果レコードを生成するためのデータベースオペレーションＯＰ５の実行を開始する。
（１５）クエリ実行部４２４は、データベースオペレーションＯＰ５の実行によって、結果レコード｜１３０｜Ｄ｜を出力する。
クエリ実行部４２４は、この後、同様にクエリの実行を進める。上記において、（０１）（０２）の手順は図７に示す実行インスタンス（＃１）に、（０３）（０４）の手順は実行インスタンス（＃２）に、（０５）（０６）の手順は実行インスタンス（＃３）に、（０７）（０８）の手順は実行インスタンス（＃４）に、（０９）（１０）の手順は実行インスタンス（＃５）に、（１１）の手順は実行インスタンス（＃６）に、（１２）（１３）の手順は実行インスタンス（＃７）に、（１４）（１５）の手順は実行インスタンス（＃８）に対応している。

　図１６は、実施例１にかかる第２のクエリ実行手続きを示す。第２のクエリ実行手続きは、図１３のＳ１３１２の手続きに対応する。

　Ｓ１６０１において、加速部４２８は、クエリ実行プラン情報４２３を参照し、最初のデータベースオペレーションを実行するための実行インスタンスを生成し、加速部状態管理情報４２９のキュー中実行インスタンステーブル１１０２（キュー）に格納する。例えば、加速部４２８は、クエリ実行プラン情報４２３を参照し、開始データベースオペレーションＩＤ８１１に示されるデータベースオペレーションを実行するための実行インスタンスを生成してよい。

　引き続き、Ｓ１６０２において、加速部４２８は、キュー中実行インスタンステーブル１１０２が空であるか否かを判定する。この判定の結果が肯定的である場合には、加速部４２８は第２のクエリ実行手続きを終了し、否定的である場合には、加速部４２８はＳ１６０３を実行する。

　Ｓ１６０３において、加速部４２８は、キュー中実行インスタンステーブル１１０２から１の実行インスタンスを取り出す。

　Ｓ１６０４において、加速部４２８は、後述する実行インスタンスの協調性を算出する手続きを実行し、Ｓ１６０３で取り出した実行インスタンスの協調性を算出する。ここで、協調性とは、加速部４２８が当該実行インスタンスを実行することにより、並行してクエリ実行部４２４が実行する第１のクエリ実行手続きによって行われるクエリの実行にかかる時間を短縮することが可能であるという意味であってもよい。

　引き続き、Ｓ１６０５において、加速部４２８は、Ｓ１６０４において算出した協調性がケースＡであるかを判定する。この判定の結果が肯定的であれば、加速部４２８はＳ１６０６を実行し、否定的であれば、加速部４２８は１６０７を実行する。

　Ｓ１６０６において、加速部４２８は、Ｓ１６０３において取り出した実行インスタンスを実行することはせず、当該実行インスタンスを破棄し、Ｓ１６０２を実行する。

　Ｓ１６０７において、加速部４２８は、Ｓ１６０４において算出した協調性がケースＣであるかを判定する。この判定の結果が肯定的であれば、加速部４２８はＳ１６０８を実行し、否定的であれば、加速部４２８は１６０９を実行する。

　Ｓ１６０８において、加速部４２８は、Ｓ１６０３において取り出した実行インスタンスを実行することはせず、当該実行インスタンスをキュー中実行インスタンステーブル１１０２に戻し、Ｓ１６０２を実行する。

　Ｓ１６０９において、加速部４２８は、Ｓ１６０３で取り出した実行インスタンスを実行するためのタスクを生成する。タスクは生成されることによって、プロセッサ４１４によって実行されることとなる。これによって、加速部４２８は、各々のタスクにおいてＳ１６１１を実行する。

　Ｓ１６１１において、加速部４２８は、Ｓ００９８で生成されたタスクにおいて、後述する実行インスタンスを実行する手続きを実行する。これによって実行インスタンスに対応するデータベースオペレーションを実行する。

　本実施例によれば、プロセッサ４１４は、複数のタスクを並行して実行することが可能である。Ｓ１６０９において生成され、実行されたタスクにおいては、Ｓ１６１１に示すように実行インスタンスが実行され、これによってデータベースオペレーションが実行される。データベースオペレーションを実行する際にデータベースから読み込んだデータベースページはデータベースバッファ５５１に格納される場合がある。これによって、クエリ実行部４２４が第１のクエリ実行手続きを実行する際に、新たにデータベースからデータベースページを読み込むことなくデータベースバッファ５５１からデータベースページを読み込めばよいという場合が生じる可能性があり、これによって、クエリ実行部４２４によるクエリ実行に要する時間が短縮される可能性がある。

　図１７は、実施例１にかかる実行インスタンスの協調性を算出する手続きを示す。実行インスタンスの協調性を算出する手続きは、図１６のＳ１６０４の手続きに対応する。

　Ｓ１７０１において、加速部４２８は、クエリ実行部４２４が現在実行中のデータベースオペレーションの実行が相当する、予測実行インスタンス木における予測順序番号を同定し、当該予測順序番号をＸ（メモリ４１６上の局所変数）に設定する。具体的には、クエリ実行部状態管理情報４２５を参照し、クエリ実行部４２４が現在実行中のデータベースオペレーションの実行およびスタックしているデータベースオペレーションの実行に関する情報を取得し、更に、協調制御情報４３１を参照し、クエリ実行部４２４が現在実行中のデータベースオペレーションの実行に近似していると思われる、予測実行インスタンス木上の予測実行インスタンスを同定する。例えば、図１０の例で説明すると、現在実行中のデータベースオペレーションＯＰ３については、最初にデータベースオペレーションＯＰ１によってその２番目の子のデータベースオペレーションとしてデータベースオペレーションＯＰ２が生成され、更にそのデータベースオペレーションＯＰ２の１番目のデータベースオペレーションＯＰ３として生成されたことが分かる。このような生成の経緯を用いて図１２に示す予測実行インスタンス木においては、最初に予測実行インスタンス＃＃１が生成され、その２番目の子の予測実行インスタンスとして＃＃８が生成され、更にその１番目の子の予測実行インスタンスとして＃＃９が生成されていることが分かる。即ち、図１０におけるクエリ実行部４２４が現在実行中のデータベースオペレーションは、図１２の予測実行インスタンス木上における予測実行インスタンス＃＃９に相当することが分かり、その予測順序番号は９であることが分かる。なお、予測実行インスタンス木上において、クエリ実行部４２４が現在実行中のデータベースオペレーションに相当する予測実行インスタンスが存在しない場合は、その近傍の（例えば、最も近い親である）予測実行インスタンスの予測順序番号を以って、当該データベースオペレーションの予測順序番号としてもよい。

　引き続き、Ｓ１７０２において、加速部４２８は、加速部４２８がこれから実行しようとしている実行インスタンスが相当する、予測実行インスタンス木における予測順序番号を同定し、当該予測順序番号をＹ（メモリ４１６上の局所変数）に設定する。具体的には、加速部状態管理情報４２９を参照し、加速部４２８がこれから実行しようとしている実行インスタンスの実行および実行済の実行インスタンスに関する情報を取得し、更に、協調制御情報４３１を参照し、加速部４２８がこれから実行しようとしている実行インスタンスに近似していると思われる、予測実行インスタンス木上の予測実行インスタンスを同定する。例えば、図１１の例で説明すると、現在実行中の実行インスタンス＃１０については、最初に実行インスタンス＃１によってその２番目の子の実行インスタンスとして実行インスタンス＃８が生成され、更にその実行インスタンス＃８の１番目の実行インスタンスとして実行インスタンス＃９が生成され、更にその実行インスタンス＃９の１番目の実行インスタンスとして生成されたことが分かる。このような生成の経緯を用いて図１２に示す予測実行インスタンス木においては、最初に予測実行インスタンス＃＃１が生成され、その２番目の子の予測実行インスタンスとして＃＃８が生成され、その１番目の子の予測実行インスタンスとして＃＃９が生成され、更にその１番目の子の予測実行インスタンスとして＃＃１０が生成されていることが分かる。即ち、図１１における加速部４２８がこれから実行しようとしている実行インスタンス＃１０は、図１２の予測実行インスタンス木上における予測実行インスタンス＃＃１０に相当することが分かり、その予測順序番号は１０であることが分かる。なお、予測実行インスタンス木上において、現在実行中の実行インスタンスに相当する予測実行インスタンスが存在しない場合は、その近傍の（例えば、最も近い親である）予測実行インスタンスの予測順序番号を以って、当該実行インスタンスの予測順序番号としてもよい。

　引き続き、Ｓ１７０３およびＳ１７０５において、加速部４２８は、ＸとＹの先行関係を判定する。

　例えば、クエリ実行部４２４による第１のクエリ実行手続きにおいて、データベースオペレーションの実行に必要なデータベースページが、既に、加速部４２８による第２のクエリ実行手続きによってデータベース４５１から読み込まれてデータベースバッファ５５１に格納されている場合、クエリ実行部４２４は新たにデータベース４５１からデータベースページを読み込むことなくデータベースバッファ５５１からデータベースページを読み込めばよく、これによって、クエリの実行に要する時間を短縮する効果が期待される。このような効果を期待するためには、例えば、同じ実行インスタンスに対応するデータベースオペレーションの実行が、クエリ実行部４２４による第１のクエリ実行手続きにおいて行われるより以前に、加速部４２８による第２のクエリ実行手続きにおいて行われている必要がある。即ち、クエリ実行部４２４による第１のクエリ実行手続きに対して、加速部４２８による第２のクエリ実行手続きが先行していることが、クエリの実行に要する時間を短縮するために望ましい。一方で、例えば、同じ実行インスタンスに対応するデータベースオペレーションの実行が、加速部４２８による第２のクエリ実行手続きにおいて行われた後、相当の時間が経過して、クエリ実行部４２４による第１のクエリ実行手続きにおいて行われた場合、加速部４２８による第２のクエリ実行手続きにおいて当該データベースオペレーションの実行に必要なデータベースページが一旦データベースバッファ５５１に格納されたものの、クエリ実行部４２４による第１のクエリ実行手続きが当該データベースページを必要とした際には既にデータベースバッファ５５１からデータベースバッファ管理部４３２により追い出されており、これによって、クエリの実行に要する時間を短縮する効果が生じないという可能性がある。即ち、クエリ実行部４２４による第１のクエリ実行手続きに対して、加速部４２８による第２のクエリ実行手続きが先行している度合いが、一定の範囲に収まっていることが、クエリの実行に要する時間を短縮するためには望ましい。

　以上を勘案すると、それぞれの実行インスタンスに対応するデータベースオペレーションの実行に着目した際に、加速部４２８による第２のクエリ実行手続きにおける当該データベースオペレーションの実行は、クエリ実行部４２４による第１のクエリ実行手続きにおける当該データベースオペレーションの実行に対して、先行しており、しかしながら、その先行具合は一定の範囲に収まっていることが、クエリの実行に要する時間を短縮するためには望ましい。

　具体的には、Ｓ１７０３において、加速部４２８は、ＸがＹに先行しているかを判定し、その結果が肯定的である場合にはＳ１７０４を実行し、否定的である場合にはＳ１７０５を実行する。

　引き続き、Ｓ１７０４において、加速部４２８は、協調性をケースＡと判定し、実行インスタンスの協調性を算出する手続きを終了する。即ち、ケースＡとは、クエリ実行部４２４が実行中のデータベースオペレーションの方が、加速部４２８が実行しようとしている実行インスタンスに対して、予測実行インスタンス木上において先行していることを表す。この場合、加速部４２８が実行しようとしている実行インスタンスを実行することによって、クエリ実行部４２４によるクエリ実行に要する時間を短縮する効果は望めない。

　Ｓ１７０５において、加速部４２８は、ＹがＸに先行している度合いが所定の値以上であるかを判定し、その結果が肯定的である場合にはＳ１７０６を実行し、否定的である場合にはＳ１７０７を実行する。

　Ｓ１７０６において、加速部４２８は、協調性をケースＣと判定し、実行インスタンスの協調性を算出する手続きを終了する。即ち、ケースＣとは、クエリ実行部４２４が実行中のデータベースオペレーションに対して、加速部４２８が実行しようとしている実行インスタンスが、予測実行インスタンス木上において所定の値以上先行していることを表す。この場合、加速部４２８が実行しようとしている実行インスタンスを実行することによって、クエリ実行部４２４によるクエリ実行に要する時間を短縮する効果は望めない。

　Ｓ１７０７において、加速部４２８は、協調性をケースＢと判定し、実行インスタンスの協調性を算出する手続きを終了する。即ち、ケースＢとは、クエリ実行部４２４が実行中のデータベースオペレーションに対して、加速部４２８が実行しようとしている実行インスタンスが、予測実行インスタンス木上において所定の値未満で先行していることを表す。この場合、加速部４２８が実行しようとしている実行インスタンスを実行することによって、クエリ実行部４２４によるクエリ実行に要する時間を短縮する効果はある場合がある。

　なお、上記のＸとＹの先行度の判定に関する場合分けの境界（例えば、Ｙ＝Ｘの場合等）については、境界が接するいずれかの場合に準じて判定してもよい。

　また、上記の手続きに限らず、所定の条件を満たす場合には、実行インスタンスの協調性をケースＢと判定してもよい。所定の条件とは、実行インスタンスが、クエリの実行が開始されて最初の所定の数の実行インスタンスの実行の範囲に収まっているかであってよい。もしくは、所定の条件とは、実行インスタンスが、予測実行木上における開始予測実行インスタンスから所定の世代内の子実行インスタンスの範囲に収まっているかであってよい。もしくは、所定の条件とは、実行インスタンスにかかるデータベースオペレーションが、クエリ実行プラン予測上における開始データベースオペレーションから所定の世代内の子データベースオペレーションの範囲に収まっているかであってよい。また、所定の条件は、データベース管理システム４１２の設定パラメータ等の値に基づいて判定されてもよい。例えば、データベース管理システム４１２から参照可能なストレージ（例えば、ストレージ装置４１５もしくは外部ストレージ装置４０２）に記憶された設定情報に基づき、所定の条件が満たされているか判定されてもよい。

　上述の手続きでは、単に、予測実行インスタンス木上における順序関係に着目し、その先行度を以って協調性を判定したが、更にこれに代えて、もしくは、これに加えて、加速部４２７は、実行インスタンスにおいてデータベースオペレーションの実行に要するデータベースページの量を考慮してもよい。具体的には、Ｓ１７０５においては、加速部４２７は、クエリ実行部４２４が実行中のデータベースオペレーションに相当する予測実行インスタンスから、加速部４２８がこれから実行しようとしている実行インスタンスに相当する予測実行インスタンスに至るまでに、全予測実行インスタンスを実行するのに要するデータベースページの量を予測し、当該量が所定の値以上であるかを判定し、当該判定の結果が肯定的である場合にはケースＣと判定し、否定的である場合にはケースＢと判定してもよい。この際、データベースページの量は、データベースオペレーションの実行に要するデータベースページの量の他、当該データベースページをデータベースバッファ５５１上に格納するのに必要な容量（例えば、データベースページの数等）であってもよい。また、ここで、所定の値とは、データベースバッファ５５１のうちその時点で利用可能な容量の値としてもよい。

　Ｓ１７０１およびＳ１７０２のそれぞれに関して上述した手続きでは、実行インスタンスの協調性を算出する都度に、予測順序番号を算出しているが、これに代えて、加速部４２８が、図１６に示す手続きにおいて加速部状態管理情報４２９を更新する際に、事前に予測順序番号を算出して、それぞれクエリ実行部状態管理情報４２５および加速部状態管理情報４２９に格納しておいてもよい。予測順序番号を格納するために、クエリ実行部状態管理情報４２５および加速部状態管理情報４２９はそれぞれ属性として予測順序番号を有してもよい。本明細書においては、可読性のために、図１０に示すクエリ実行部状態管理情報４２５は予測順序番号を有さず、図１１に示す加速部状態管理情報４２９は予測順序番号１１１５を有している。

　Ｓ１７０１およびＳ１７０２のそれぞれに関して上述した手続きでは、実行インスタンスに相当する予測実行インスタンス木における予測実行インスタンスが同定され、当該予測実行インスタンスの予測順序番号をもって協調性の算出が行われているが、これに加えて、実行インスタンス木と予測実行インスタンス木の差異に基いて当該予測順序番号を修正した上で協調性の算出が行われてよい。例えば、図７の例で説明すると、実行インスタンス＃３の子の実行インスタンス＃４、＃６が生成されず、かつ予測実行インスタンス木は図１２の例の通りに生成されるという仮定をおいた場合、図７における実行インスタンス＃４から＃７に相当される実行インスタンスは生成されず、図７における実行インスタンス＃８に相当するものが、当該仮定の下では順序番号が４である実行インスタンス＃４として生成される。当該実行インスタンスは親実行インスタンスが＃１であり、シブリング＃：２であるので、上述の手続きによると当該実行インスタンスに相当する予測実行インスタンスは＃８であり、予測順序番号は８と算出され、実行インスタンス木と予測実行インスタンス木の差異によって順序番号と予測順序番号に差分が生じる。実行インスタンスの予測順序番号が算出されたのちに、当該差分が、加速部状態管理情報４２９と協調制御情報４３１を照合することで算出され、予測順序番号が当該差分に基づき修正された上で、協調性の算出が行われてよい。

　図１８は、実施例１にかかる実行インスタンスを実行する手続きを示す。実行インスタンスを実行する手続きは、図１６のＳ１６１１の手続きに対応する。

　Ｓ１８０１において、加速部４２８は、実行インスタンスを加速部状態管理情報４２９の実行中実行インスタンステーブル１１０１に格納する。

　引き続き、Ｓ１８０２において、加速部４２８は、実行インスタンスにおけるデータベースオペレーションの実行に必要なデータベースページをデータベースから読み込む。この際、加速部４２８は、当該データベースページの読込み要求をデータベースバッファ管理部４３２に発行する。データベースバッファ管理部４３２は、当該データベースページがデータベースバッファ５５１に既に格納されていれば、格納されているデータベースページをクエリ実行部４２４に返し、格納されていなければ、データベース４５１が格納されている外部ストレージ装置４０２に読込み要求を発行することにより当該データベースページをデータベース４５１から読み込みクエリ実行部４２４に返す。この際、本実施例によれば、加速部４２８によって実行される第２のクエリ実行手続きによって既にデータベースバッファ５５１に格納されたデータベースページを、クエリ実行部４２４によって実行される第１のクエリ実行手続きにおいて、データベースオペレーションの実行に用いることができる場合がある。なお、実行インスタンスにおけるデータベースオペレーションの実行にデータベースページが必要ない場合には、Ｓ１８０２の手続きは行われなくてよい。

　引き続き、Ｓ１８０３において、加速部４２８は、実行インスタンスにおけるデータベースオペレーションを実行する。この際、Ｓ１８０２で取得したデータベースページを用いてよい。

　引き続き、Ｓ１８０４において、加速部４２８は、Ｓ１８０３において行った実行インスタンスにおけるデータベースオペレーションの実行結果に基づき、更にクエリ実行プラン情報４２３を参照して、実行するべき次のデータベースオペレーションがあるかどうかを判定する。判定の結果が肯定的であれば、Ｓ１８０５が実行され、否定的であれば、Ｓ１８０６が実行される。

　Ｓ１８０５において、加速部４２８は、Ｓ１８０３において行った実行インスタンスにおけるデータベースオペレーションの実行結果に基づき、実行するべき次のデータベースオペレーションを実行するための実行インスタンスを生成して、加速部状態管理情報４２９のキュー中実行インスタンステーブル１１０２に格納し、Ｓ１８０６を実行する。例えば、データベースオペレーションの実行結果に基づき、異なるデータのそれぞれについてデータベースオペレーションを実行する必要がある場合には、加速部４２８は、そのそれぞれについて実行インスタンスを生成してもよい。この際、加速部４２８は、複数の実行インスタンスを生成して格納する場合に、一括して複数の実行インスタンスを生成して、その後にキュー中実行インスタンステーブル１１０２に格納してもよいし、実行インスタンスを生成する都度にキュー中実行インスタンステーブル１１０２に格納してもよい。

　Ｓ１８０６において、加速部４２８は、実行インスタンスにおけるデータベースオペレーションの実行に必要なデータベースページであって未読込みのものがデータベース４５１にあるかどうかを判定する。判定の結果が肯定的であれば、Ｓ１８０２が実行され、否定的であれば、Ｓ１８０７が実行される。

　Ｓ１８０７において、加速部４２８は、実行インスタンスを加速部状態管理情報４２９の実行中実行インスタンステーブル１１０１から削除し、加速部状態管理情報４２９の実行済実行インスタンステーブル１１０３に格納する。

　ここで実行インスタンスを実行する手続きが完了することによって、図１６における左下図により、タスクの実行も終了する。しかし、これに代えて、更に図１６におけるＳ１６０２からＳ１６０９に至る手続きが再帰的に行われてもよい。この際、加速部４２８は、Ｓ１６０９でタスクを生成することなく、Ｓ１６１１に相当する手続きによって当該実行インスタンスを直接実行してもよい。

　次に、本実施例による効果を説明する。なお、加速部４２７により実行される実行インスタンスは、前述したように、待機中であればキュー中実行インスタンステーブル１１０２に格納され、実行中であれば実行中実行インスタンステーブル１１０１に格納され、実行済みであれば実行済実行インスタンステーブル１１０３に格納されるが、説明の冗長を避けるため、以下の説明では、加速部４２７により実行される実行インスタンスのテーブル１１０１～１１０３に対する格納に関する記載を省略する。

　図１９は、実施例１による効果を説明するタイムチャートである。図１９においては、図９に示す実行インスタンス木の一部（実行インスタンス（＃１）～（＃１６））を実行する際のタイムチャートを示している。図１９において、角丸の四角は、実行インスタンスを示し、その上の数字は、実行インスタンスＩＤを示す。また、実行インスタンス内の五角形は、実行インスタンスに対応したデータベースオペレーションの実行に必要なデータベースページを読み込む場合の読込みにかかる時間を示し、＞状の記号は、実行インスタンスでの演算にかかる時間を示している。また、加速部４２８がデータベースバッファ５５１に格納できるデータベースページ（データ）の最大数は、１０であるとする。このため、加速部４２８によりデータベースバッファ５５１に格納されるデータベースページの数を１０以下とするように、加速部４２８が実行可能な実行インスタンスの範囲を、クエリ実行部４２４が実行している実行インスタンス以降（この実行インスタンスを含む）に実行される１０個の実行インスタンスとしている。

　クエリ実行部４２４が単独でクエリを実行する場合には、図１９の上図に示すように、所定の順序で実行インスタンスを実行する。そして、クエリ実行部４２４は、各実行インスタンスにおいては、実行インスタンスに対応したデータベースオペレーションの実行に必要なデータベースページがあれば、そのデータベースページの読込み要求をデータベースバッファ管理部４３２に発行する。データベースバッファ管理部４３２が、読込み要求されたデータベースページをデータベース４５１から読み込んでデータベースバッファ５５１に格納し、そのデータベースページをクエリ実行部４２４に返す。クエリ実行部４２４は、データベースバッファ管理部４３２から、読込み要求したデータベースページを受け、そのデータベースページを用いて演算を実行する。したがって、新たなデータベースページを読み込む実行インスタンスにおいては、新たなデータベースページをデータベース４５１から読み込む処理が発生するために比較的長い時間がかかる。

　一方、実施例１に示したように、クエリ実行部４２４による第１のクエリ実行手続きと、加速部４２８による第２のクエリ実行手続きとを並行して実行する場合には、図１９の下図に示すように、クエリ実行部４２４が単独でクエリ処理を実行する場合に比して、１つのクエリの実行に要する時間を短縮することが期待できる。以下、その具体例を説明する。

　まず、クエリが実行されると、クエリ実行部４２４及び加速部４２８の各々により、実行インスタンス（＃１）が実行される。クエリ実行部４２４及び加速部４２８は、それぞれ実行インスタンス（＃１）で使用するデータベースページの読込み要求をデータベースバッファ管理部４３２に発行する。データベースバッファ管理部４３２は、読込み要求されたデータベースページがデータベースバッファ５５１に無ければ、そのデータベースページをデータベースから読み込み、読み込んだデータベースページをデータベースバッファ５５１に格納し、そのデータベースページを、読込み要求の発行元に返す。加速部４２８は、実行インスタンス（＃１）を実行することにより、実行インスタンス（＃１）を実行中実行インスタンステーブル１１０１に格納し、実行インスタンス（＃１）の子実行インスタンスである実行インスタンス（＃２）、（＃８）、（＃１６）、（＃２２）、・・・を生成してキュー（キュー中実行インスタンステーブル１１０２）に格納する。

　実行インスタンス（＃１）が終了すると、クエリ実行部４２４は、実行インスタンス（＃２）を実行する。クエリ実行部４２４は、実行インスタンス（＃２）に対応したデータベースオペレーションの実行に必要なデータベースページの読込み要求を、加速部４２８よりも先又は後に、データベースバッファ管理部４３２に発行する。一方、加速部４２８は、クエリ実行部４２４が実行している実行インスタンス（＃２）以降の１０個の実行インスタンス、即ち、実行インスタンス（＃２）～（＃１１）を加速効果があると判定するので、キューに格納されている実行インスタンス（＃２）、（＃８）の処理を並列に実行する。なお、実行インスタンス（＃１６）、（＃２２）、・・・等の実行は保留されている。加速部４２８が実行インスタンス（＃２）を実行することにより、加速部４２８は、子実行インスタンスである実行インスタンス（＃３）を生成してキューに格納し、実行インスタンス（＃８）を実行することにより、子実行インスタンスである実行インスタンス（＃９）を生成してキューに格納する。

　実行インスタンス（＃２）が終了すると、クエリ実行部４２４は、実行インスタンス（＃３を実行する。クエリ実行部４２４は、実行インスタンス（＃３）に対応するデータベースオペレーションの実行に必要なデータベースページの読込み要求を、加速部４２８よりも先に又は後に、データベースバッファ管理部４３２に発行する。一方、加速部４２８は、クエリ実行部４２４が実行している実行インスタンス（＃３）以降の１０個の実行インスタンス、即ち、実行インスタンス（＃３）～（＃１２）を加速効果があると判定するので、キューに格納されている実行インスタンス（＃３）、（＃９）を並列に実行する。加速部４２８は、実行インスタンス（＃３）を実行することにより、子実行インスタンスである実行インスタンス（＃４）、（＃６）を生成してキューに格納し、実行インスタンス（＃９）を実行することにより、子実行インスタンスである実行インスタンス（＃１０）、（＃１２）、（＃１４）を生成してキューに格納する。

　実行インスタンス（＃３）が終了すると、クエリ実行部４２４は、実行インスタンス（＃４）を実行する。クエリ実行部４２４は、実行インスタンス（＃４）に対応したデータベースオペレーションの実行に必要なデータの読込み要求を、加速部４２８よりも先に又は後に、データベースバッファ管理部４３２に発行する。一方、加速部４２８は、クエリ実行部４２４が実行している実行インスタンス（＃４）以降の１０個の実行インスタンス、即ち、実行インスタンス（＃４）～（＃１３）を加速効果があると判定するので、キューに格納されている実行インスタンス（＃４）、（＃６）、（＃１０）、（＃１２）の処理を並列に実行する。加速部４２８は、実行インスタンス（＃４）、（＃６）、（＃１０）、及び（＃１２）を実行することにより、子実行インスタンスである実行インスタンス（＃５）、（＃７）、（＃１１）、及び（＃１３）を生成してキューに格納する。

　実行インスタンス（＃４）が終了すると、クエリ実行部４２４は、実行インスタンス（＃５）を実行する。クエリ実行部４２４は、実行インスタンス（＃５）の実行では、データベース４５１へのアクセスを必要としないので、早期に処理が終了する。一方、加速部４２８は、クエリ実行部４２４が実行している実行インスタンス（＃５）以降の１０個の実行インスタンス、即ち、実行インスタンス（＃５）～（＃１４）を加速効果があると判定するので、キューに格納されている実行インスタンス（＃５）、（＃７）、（＃１１）、（＃１３）、及び（＃１４）の処理を並列に実行する。実行インスタンス（＃５）、（＃７）、（＃１１）、及び（＃１３）の実行では、データベース４５１へのアクセスを必要としないので、早期に処理が終了する。また、加速部４２８は、実行インスタンス（＃１４）を実行することにより、子実行インスタンスである実行インスタンス（＃１５）を生成してキューに格納する。

　実行インスタンス（＃５）が終了すると、クエリ実行部４２４は、実行インスタンス（＃６）を実行する。ここで、クエリ実行部４２４は、実行インスタンス（＃６）に対応したデータベースオペレーションの実行に必要なデータベースページの読込み要求をデータベースバッファ管理部４３２に発行するが、当該データベースページの読込み要求が既に加速部４２８により発行されたために当該データベースページはデータベースバッファ５５１に格納されている。このため、データベースバッファ管理部４３２は、データベース４５１に当該データベースページの読込み要求を発行することなく、当該データベースページをクエリ実行部４２４に提供し、クエリ実行部４２４は、当該データベースページを使用して実行インスタンス（＃６に対応したデータベースオペレーションを実行することができる。このため、クエリ実行部４２４は、実行インスタンス（＃６）を早期に終了することができる。

　加速部４２８は、クエリ実行部４２４において実行インスタンス（＃６）が終了した後に、実行インスタンス（＃１６）を実行する。加速部４２８は、実行インスタンス（＃１４）が終了した後に、実行インスタンス（＃１５）を実行する。

　実行インスタンス（＃６）を終了した後には、クエリ実行部４２４は、同様にして、実行インスタンス（＃７）～（＃１６）について、直前の実行インスタンスが終了した後に逐次実行する。この際、実行する実行インスタンス（＃７）～（＃１６）で使用するデータベースページが、それぞれ既に加速部４２８からの読込み要求によりデータベースバッファ５５１に既に格納されているので、データベースバッファ管理部４３２は、それぞれのデータベースページの読込み要求をデータベース４５１へ発行することなく、クエリ実行部４２４に、それぞれのデータベースページを提供する。クエリ実行部４２４は、それぞれのデータベースページをデータベースバッファ管理部４３２から受け、それぞれのデータベースページを使用して実行インスタンス（＃７）～（＃１６）のそれぞれを実行することができる。このため、クエリ実行部４２４は、これら実行インスタンスを迅速に終了することができる。

　このように、実施例１によると、クエリ実行部４２４がデータベースバッファ管理部４３２に読込み要求したデータベースページは、既にデータベースバッファ管理部４３２が加速部４２８から読込み要求されてデータベース４５１から読み込みデータベースバッファ５５１に格納済みである可能性がある。このため、クエリ実行部４２４が単独でクエリ処理を実行する場合に比して、１つのクエリの実行に要する時間を短縮することができる。

　以下、実施例２を説明する。その際、実施例１との相違点を主に説明し、実施例１との共通点については説明を省略或いは簡略する。

　データベースバッファ管理部４３２は、データベースバッファ管理情報５５０を基に、データベースバッファ５５１内のデータベースページ（データ）のうち追い出し対象とするデータベースページを決定する。この決定は、任意のタイミング、例えば、データベースバッファ管理部４３２がデータベースバッファ５５１の空き容量が所定容量未満になったことを検出したタイミングで行われて良い。

　図２０は、実施例２にかかるデータベースバッファ管理情報５５０の構成を示す。

　データベースバッファ管理情報５５０は、データベースバッファ管理テーブル２００１を有する。データベースバッファ管理テーブル２００１は、データベースバッファ５５１に格納されているデータベースページ毎にレコードを有し、属性としては、データベースページＩＤ２０１１、アクセス頻度２０１２、加速部格納フラグ２０１３、クエリ実行部提供フラグ２０１４を有する。データベースページＩＤ２０１１は、データベースページのＩＤである。アクセス頻度２０１２は、データベースページへのアクセス頻度（読込み頻度）を表す。加速部格納フラグ２０１３は、データベースページが加速部４２８により格納されたデータベースページであるか否かを表す。クエリ実行部提供フラグ２０１４は、データベースページがクエリ実行部４２４からの読込み要求によりデータベースバッファ５５１から提供されたか否かを表す。

　データベースバッファ管理部４３２は、データベースバッファ管理情報５５０内のデータベースバッファ管理テーブル２００１を基に、クエリ実行部４２４から読込み要求されたデータベースページが加速部４２８からの読込み要求により既にデータベースバッファ５５１に格納されているか否かを知ることができる。当該データベースページは、加速部格納フラグ２０１３が「１」でありクエリ実行部提供フラグ２０１４が「０」であるデータベースページである。当該データベースページがクエリ実行部４２４に提供された場合、データベースバッファ管理部４３２は、当該データベースページに対応するクエリ実行部提供フラグ２０１４を「０」から「１」に更新する。

　また、データベースバッファ管理部４３２は、データベースバッファ管理情報５５０内のデータベースバッファ管理テーブル２００１を基に、データベースバッファ５５１内のデータベースページのうち追い出し対象とするデータベースページを決定することができる。

　第１の例として、データベースバッファ管理部４３２は、クエリ実行部格納フラグ２０１４が「１」であるデータベースページ、すなわち、既にクエリ実行部４２４に提供されたデータベースページを、追い出し対象として決定することができる。言い換えれば、データベースバッファ管理部４３２は、加速部格納フラグ２０１３が「１」であるがクエリ実行部格納フラグ２０１４が「０」であるデータベースページを、追い出し対象にしない。

　第２の例として、データベースバッファ管理部４３２は、データベースバッファ５５１内の複数のデータベースページにそれぞれ対応した複数のアクセス頻度２０２２を基に、それら複数のデータベースページのうちの追い出し対象を決定することができる。言い換えれば、データベースバッファ管理部４３２は、クエリ実行部提供フラグ２０１４が「１」であるが故に追い出し対象とされたデータベースページを、アクセス頻度２０２２を基に絞り込むことができる。例えば、データベースバッファ管理部４３２は、クエリ実行部提供フラグ２０１４が「１」であるデータベースページのうち、アクセス頻度２０２２が相対的に低いデータベースページのみを、追い出し対象としてよい。これにより、アクセス頻度２０２２が相対的に高いデータベースページはデータベースバッファ５５１に残るので、データベース４５１へのアクセス頻度の軽減が期待され、故に、１つのクエリの実行に要する時間の一層の短縮化が期待される。

　以下、実施例３を説明する。その際、実施例１及び２との相違点を主に説明し、実施例１及び２との共通点については説明を省略或いは簡略する。

　図２１は、実施例３にかかる統計情報４２７の構成を示す。

　統計情報４２７は、一般統計情報テーブル９０１に加えて、クエリ固有統計情報テーブル２１０１を含んでよい。クエリ固有統計情報テーブル２１０１は、データベースに対する特定のクエリの実行におけるデータベースが含む表４６２もしくは索引４６１におけるに関する情報を含み、例えば、特定のクエリの実行における選択条件を満足するレコードに関するカラム毎の値の最大値、平均値、最小値、カラム毎の値分布等を含む。

　クエリ固有統計情報テーブル２１０１は、統計項目毎にレコードを有し、属性としては、例えば、表２１１１、列２１１２、統計値２１１３を有する。表２１１１は、統計項目が関連する表を表す。列２１１２は、統計項目が関連する列を表す。ただし、特定の列に関連しない場合は「－」とする。統計値２１１３は、統計の種別の具体的な値を表す。図９においては、第１の統計項目は、Ｐａｒｔ表のｃ１列に対してｃ１＝１３０の選択条件を満足するレコードの数が７であることを意味している。第２の統計項目は、Ｌｉｎｅｉｔｅｍ表のｃ３列について、Ｐａｒｔ表のｃ２列とＬｉｎｅｉｔｅｍ表のｃ３列についてのｃ２＝ｃ３による結合演算を行うと、Ｐａｒｔ表の１レコードに対してＬｉｎｅｉｔｅｍ表の３レコードが対応することを意味している。

　図１４のＳ１４０１において、協調制御情報生成部４３０は、更に、統計情報４２７の含むクエリ固有統計情報テーブル２１０１を参照して協調制御情報４３１を生成してよい。

　例えば、以下では、図８のクエリ実行プラン情報４２３および図２１の統計情報４２７のうちのクエリ固有統計情報テーブル２１０１の例で説明する。データベースオペレーションＯＰ１はｃ１＝１３０の条件によってＰａｒｔ表の索引検索を行う。統計情報４２７によると、直接的にｃ１＝１３０を満たすＰａｒｔ表のレコードの数は７であることが分かる。即ち、データベースオペレーションＯＰ１の実行の結果、７の異なる入力に対してデータベースオペレーションＯＰ２が都度実行されると予測される。データベースオペレーションＯＰ２はレコード参照に基づきレコードを取得する。この場合では、１のレコード参照には１のレコードが対応するため、各々のデータベースオペレーションＯＰ２の実行の結果、１のデータベースオペレーションＯＰ３が実行されると予測される。データベースオペレーションＯＰ３は、Ｐａｒｔ表から取得したレコードに基づき、ｃ２＝ｃ３の結合条件によるＬｉｎｅｉｔｅｍ表の結合率は３であることが分かり、１のｃ３の値に対して３のレコードが対応する。よって、各々のデータベースオペレーションＯＰ３の実行の結果、３の異なる入力に対してデータベースオペレーションＯＰ４が都度実行されると予測される。データベースオペレーションＯＰ４はレコード参照に基づきレコードを取得する。この場合では、１のレコード参照には１のレコードが対応するため、各々のデータベースオペレーションＯＰ４の実行の結果、１のデータベースオペレーションＯＰ５が実行されると予測される。以上のような手続きによって、統計的な一様性を仮定すると、以下のような実行インスタンス木が予測される。
・データベースオペレーションＯＰ１に対応する実行インスタンスは１である。これを最初に実行する実行インスタンス（予測実行インスタンス）とする。
・この実行インスタンスから７の実行インスタンス（データベースオペレーションＯＰ２を実行）が生成される。即ち、データベースオペレーションＯＰ２に対応する実行インスタンスは７である。
・この各々の実行インスタンスから１の実行インスタンス（データベースオペレーションＯＰ３を実行）が生成される。即ち、データベースオペレーションＯＰ３に対応する実行インスタンスは７である。
・この各々の実行インスタンスから３の実行インスタンス（データベースオペレーションＯＰ４を実行）が生成される。即ち、データベースオペレーションＯＰ４に対応する実行インスタンスは２１である。
・この各々の実行インスタンスから１の実行インスタンス（データベースオペレーションＯＰ５を実行）が生成される。即ち、データベースオペレーションＯＰ５に対応する実行インスタンスは２１が生成される。

　このような予測実行インスタンス木は図１２に示す構造でメモリ４１６に格納される。予測実行インスタンス木上において、開始予測実行インスタンスから開始して、クエリ実行部４２４におけるクエリの実行手順に基づき、予測実行インスタンスを辿っていくことにより、各々の予測実行インスタンスにおける予測順序番号を算出することができる。

　実施例３によれば、統計情報４２７が、クエリに固有の統計情報テーブル２１０１を含み、そのテーブル２１０１を基に、予測実行インスタンスにおける予測順序番号が算出される。これにより、順序番号の予測の正確性の向上が期待され、故に、１つのクエリの実行に要する時間を短縮することが一層期待される。

　以下、実施例４を説明する。その際、実施例１乃至３との相違点を主に説明し、実施例１乃至３との共通点については説明を省略或いは簡略する。

　図２２は、実施例４にかかる計算機システムの構成を示す。

　データベースサーバ４０１に、アプリケーションサーバ３１０２が通信ネットワーク３１１２を介して通信可能に接続されており、また、外部ストレージ装置４０２が、通信ネットワーク４０３を介して通信可能に接続されている。アプリケーションサーバ３１０２に、通信ネットワーク３１１１を介してクライアント端末３１０１が通信可能に接続されている。また、データベースサーバ４０１に、加速サーバ４０４が通信ネットワーク４０５を介して通信可能に接続されている。データベースサーバ４０１は、データベースを管理するデータベース管理システムを実行する。データベースサーバ４０１のデータベース管理システムは、例えば、実施例１のデータベース管理システム４１２における加速部４２８、加速部有効性判定部４２６および協調制御情報生成部４３０を除いたものであっても良い。加速サーバ４０４は、例えば、実施例１の加速部４２８、加速部有効性判定部４２６および協調制御情報生成部４３０を有するサーバである。外部ストレージ装置４０２は、データベース４１５を格納する。アプリケーションサーバ３１０２は、データベースサーバ４０１で実行されるデータベース管理システムにクエリを発行するアプリケーションを実行する。クライアント端末３１０１は、アプリケーションサーバ３１０２で実行されるアプリケーションに要求を出す。クライアント端末３１０１、又は、アプリケーションサーバ３１０２は、複数存在しても良い。

　アプリケーションサーバ３１０２、データベースサーバ４０１及び外部ストレージ装置４０２に、それぞれ、通信ネットワーク３１１４、３１１５及び３１１６をそれぞれ介してアプリケーションサーバ管理端末３１０３、データベースサーバ４０１管理端末３１０４及びストレージ管理端末３１０５が接続されている。アプリケーションサーバ管理端末３１０３は、アプリケーションサーバ３１０２を管理する端末であり、データベースサーバ４０１管理端末３１０４は、データベースサーバ４０１を管理する端末であり、ストレージ管理端末３１０５は、外部ストレージ装置４０２を管理する端末である。管理端末３１０３～３１０５のうちの少なくとも２つが共通（一体）であっても良い。通信ネットワーク３１１１～３１１６のうちの少なくとも２つが共通（一体）であっても良い。

　実施例４では、下記の処理の流れが実行されて良い。
（Ｓ２２０１）アプリケーションサーバ３１０２が、クライアント端末３１０１から要求（以下、クライアント要求）を受信する。
（Ｓ２２０２）アプリケーションサーバ３１０２が、Ｓ２２０１で受信したクライアント要求に従いクエリを生成し、生成したクエリをデータベースサーバ４０１に発行する。
（Ｓ２２０３）データベースサーバ４０１が、アプリケーションサーバ３１０２からのクエリを受け付け、クエリ実行プランを作成する。そのクエリ実行プランを基に、データベースサーバ４０１のクエリ実行部４２４等や、加速サーバ４０４の加速部４２８等が、前述した処理を行う。この処理において、データベースサーバ４０１が必要とするデータベースページが加速サーバ４０４の読込み要求によりデータベースバッファ５５１に既に格納されていることがあるので、データベースサーバ４０１が外部ストレージ装置４０２にアクセスする頻度が減り、故に、１つのクエリの実行に要する時間を短縮することが期待される。
（Ｓ２２０４）データベースサーバ４０１が、クエリの実行結果をアプリケーションサーバ３１０２に送信する。
（Ｓ２２０５）アプリケーションサーバ３１０２が、クエリの実行結果を受信し、その実行結果に従う、Ｓ２２０１で受信したクライアント要求に対する回答を、クライアント端末３１０１に送信する。

　なお、アプリケーションサーバ３１０２へのクライアント要求、又は、データベースサーバ４０１へ発行されるクエリは同時に複数あっても良い。

　実施例４によると、既存のデータベース管理システムを有するデータベースサーバ４０１とは、別に、加速サーバ４０４を有することにより、データベースサーバ４０１における１つのクエリの実行に要する時間を短縮することが期待できる。

　以上、幾つかの実施例を説明したが、本発明は、これらの実施例に限定されるものでなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。

　例えば、本発明は、データベース管理システムによるデータベースとの入出力（例えば、データ読込み）以外のデータ入出力、例えば、ファイルシステムがファイルへの入出出力を行うことにも適用できる。そのようなファイルシステムのような計算機システムは、例えば、処理要求を処理要求発行元から受け付ける処理要求受付部と、当該処理要求に基づいてオペレーションを実行することにより当該処理要求を実行し当該処理要求の実行結果を処理要求発行元に返す第１の処理要求実行部と、当該処理要求に基づいてオペレーションを実行することにより処理要求を実行する第２の処理要求実行部と、第１及び第２の処理要求実行部のいずれかからデータの読込み要求を受け付けた際、読込み要求されたデータがバッファに格納されていなければ、読込み要求されたデータをストレージから読み込んでバッファに格納し、読込み要求されたデータを、第１及び第２の処理要求実行部のうち、読込み要求の発行元の処理要求実行部に提供するバッファ管理部とを有してよい。読込み要求の発行元が第１の処理要求実行部であり、読込み要求されたデータが第２の処理要求実行部から既に読込み要求されたことによりバッファに格納されていれば、バッファ管理部は、読込み要求されたデータをバッファから読み込み第１の処理要求実行部に提供する。このように、データベース以外の分野に適用が期待される計算機システムは、上記の説明において、データベースオペレーションをオペレーションと読み替え、クエリを処理要求と読み替えることで、実現することが期待できる。

　４１２…データベース管理システム

Claims

　データベースを管理するデータベース管理システムであって、
　前記データベースへのクエリをクエリ発行元から受け付けるクエリ受付部と、
　前記受け付けたクエリに基づいて前記受け付けたクエリを実行するために必要な１以上のデータベースオペレーションと前記１以上のデータベースオペレーションの実行手順とを表す情報を含んだクエリ実行プランを生成するクエリ実行プラン生成部と、
　前記生成したクエリ実行プランに基づいてデータベースオペレーションを実行することにより前記クエリを実行し前記クエリの実行結果を前記クエリ発行元に返す第１のクエリ実行部と、
　前記生成したクエリ実行プランに基づいてデータベースオペレーションを実行することにより前記クエリを実行する第２のクエリ実行部と、
　前記第１及び第２のクエリ実行部のいずれかからデータの読込み要求を受け付けた際、読込み要求されたデータがバッファに格納されていなければ、前記読込み要求されたデータを前記データベースから読み込んで前記バッファに格納し、前記読込み要求されたデータを、前記第１及び第２のクエリ実行部のうち、前記読込み要求の発行元のクエリ実行部に提供するバッファ管理部と
を有し、
　前記読込み要求の発行元が前記第１のクエリ実行部であり、前記読込み要求されたデータが前記第２のクエリ実行部から既に読込み要求されたことにより前記バッファに格納されていれば、前記バッファ管理部は、前記読込み要求されたデータを前記バッファから読み込み前記第１のクエリ実行部に提供する、
データベース管理システム。
　前記第２のクエリ実行部は、前記クエリの実行において、
（ａ）データベースオペレーションを実行するための実行インスタンスを生成すること、
（ｂ）生成された実行インスタンスを実行することで、前記実行インスタンスに対応したデータベースオペレーションの実行に必要なデータを前記バッファ管理部へ読込み要求すること、
（ｃ）（ｂ）で実行された前記実行インスタンスに対応した前記データベースオペレーションの実行結果に基づき、別のデータベースオペレーションを実行する必要がある場合には、前記実行結果に基づき前記別のデータベースオペレーションをそれぞれ実行する１以上の実行インスタンスを新たに生成すること、及び、
（ｄ）前記新たに生成した１以上の実行インスタンスのそれぞれについて（ｂ）及び（ｃ）を行うこと、
を行い、
少なくとも２以上の実行インスタンスを並行して実行する、
請求項１に記載のデータベース管理システム。
　前記第２のクエリ実行部は、前記第１のクエリ実行部によるクエリ実行の状況に基づいて、前記並行して実行する少なくとも２以上の実行インスタンスのうち、実行を延期する実行インスタンスを決定する、
請求項２に記載のデータベース管理システム。
　前記第２のクエリ実行部は、前記第１のクエリ実行部によるクエリ実行の状況に基づいて、前記並行して実行する少なくとも２以上の実行インスタンスのうち、実行を破棄する実行インスタンスを決定する、
請求項３に記載のデータベース管理システム。
　更に、前記生成したクエリ実行プランに基づいて制御情報を生成する制御情報生成部を有し、
　前記第１のクエリ実行部によるクエリ実行の状況は、前記制御情報に基づいて得られる、前記第１のクエリ実行部が実行しているデータベースオペレーションの第１予測順序番号であり、
　前記第２のクエリ実行部は、前記並行して実行する少なくとも２以上の実行インスタンスについて前記制御情報を基にそれぞれ得られる第２予測順序番号と、前記並行して実行する少なくとも２以上の実行インスタンスにそれぞれ対応したデータベースオペレーションの前記第１予測順序番号とに基づいて、前記並行して実行する少なくとも２以上の実行インスタンスのうち、実行を延期する実行インスタンスを決定する、
請求項３に記載のデータベース管理システム。
　前記第２のクエリ実行部は、更に前記バッファの利用可能な容量に基づいて、前記並行して実行する少なくとも２以上の実行インスタンスのうち、実行を延期する実行インスタンスを決定する、
請求項５に記載のデータベース管理システム。
　前記制御情報生成部は、前記第１のクエリ実行部によるデータベースオペレーションの実行および前記第２のクエリ実行部によるデータベースオペレーションの実行の少なくとも一方の情報に基づき、前記制御情報を更新する、
請求項５に記載のデータベース管理システム。
　前記制御情報生成部は、前記クエリ実行プランもしくは前記データベースから取得した統計情報に基づき前記制御情報を生成する、
請求項５に記載のデータベース管理システム。
　更に、前記制御情報生成部は、前記第１のクエリ実行部におけるクエリ実行の記録および前記第２のクエリ実行部におけるクエリ実行の記録の少なくとも一方の情報であるクエリ固有統計情報に基づき前記制御情報を生成する、
請求項８に記載のデータベース管理システム。
　前記第１のクエリ実行部による前記クエリの実行が完了すると、前記第２のクエリ実行部は前記クエリの実行を停止する、
請求項１に記載のデータベース管理システム。
　所定の条件が満たされていれば、前記第２のクエリ実行部は、前記クエリを実行し、前記所定の条件が満たされていなければ、前記第２のクエリ実行部は、前記クエリを実行しない、
請求項１に記載のデータベース管理システム。
　前記所定の条件は、前記クエリ実行プランについての所定の条件である、
請求項１１に記載のデータベース管理システム。
　前記所定の条件は、クエリの実行に使用可能な資源の量についての所定の条件である、
請求項１１に記載のデータベース管理システム。
　前記所定の条件は、データベース管理に関する所定の設定情報についての所定の条件である、
請求項１１に記載のデータベース管理システム。
　前記所定の条件は、前記クエリが含む指示についての所定の条件である、
請求項１１に記載のデータベース管理システム。
　前記バッファ管理部は、前記バッファに格納されたそれぞれのデータについて、そのデータは前記第２のクエリ実行部からの読込み要求に応答して前記バッファに格納されてその後に前記第１のクエリ実行部には未だ提供されていないデータであるか否かを識別するためのバッファ管理情報を管理しており、
　前記バッファ管理部は、前記バッファ管理情報に基づき前記バッファから追い出しの対象となるデータを決定する、
請求項１に記載のデータベース管理システム。
　データベースを管理する計算機システムであって、
　プロセッサと
　バッファと
を有し、
　前記プロセッサが、
　　前記データベースへのクエリをクエリ発行元から受け付け、
　　前記受け付けたクエリに基づいて前記受け付けたクエリを実行するために必要な１以上のデータベースオペレーションと前記１以上のデータベースオペレーションの実行手順とを表す情報を含んだクエリ実行プランを生成し、
　　前記生成したクエリ実行プランに基づいてデータベースオペレーションを実行することにより前記クエリを実行する第１のクエリ実行手続きを行い、
　　前記生成したクエリ実行プランに基づいてデータベースオペレーションを実行することにより前記クエリを実行する第２のクエリ実行手続きを行い、
　　前記第１及び第２のクエリ実行のいずれかにおいて必要なデータが前記バッファに格納されていなければ、前記必要なデータを前記データベースから読み込んで前記バッファに格納し、前記必要なデータを、前記第１及び第２のクエリ実行のうち前記必要なデータを必要とするクエリ実行手続きにおいて使用し、
　　前記必要なデータを必要とするクエリ実行手続きが前記第１のクエリ実行手続きであり、前記必要なデータが前記第２のクエリ実行手続きにおいて既に必要とされたことにより前記バッファに格納されていれば、前記バッファから前記必要なデータを読込み前記第１のクエリ実行手続きにおいて使用し、
　　前記第１及び第２のクエリ実行のうちの前記第１のクエリ実行手続きによるクエリ実行結果を前記クエリ発行元に返す、
計算機システム。
　データベースを管理するデータベース管理方法であって、
　前記データベースへのクエリをクエリ発行元から受け付け、
　前記受け付けたクエリに基づいて前記受け付けたクエリを実行するために必要な１以上のデータベースオペレーションと前記１以上のデータベースオペレーションの実行手順とを表す情報を含んだクエリ実行プランを生成し、
　前記生成したクエリ実行プランに基づいてデータベースオペレーションを実行することにより前記クエリを実行する第１のクエリ実行手続きを行い、
　前記生成したクエリ実行プランに基づいてデータベースオペレーションを実行することにより前記クエリを実行する第２のクエリ実行手続きを行い、
　前記第１及び第２のクエリ実行のいずれかにおいて必要なデータがバッファに格納されていなければ、前記必要なデータを前記データベースから読み込んで前記バッファに格納し、前記必要なデータを、前記第１及び第２のクエリ実行のうち前記必要なデータを必要とするクエリ実行手続きにおいて使用し、
　前記必要なデータを必要とするクエリ実行手続きが前記第１のクエリ実行手続きであり、前記必要なデータが前記第２のクエリ実行手続きにおいて既に必要とされたことにより前記バッファに格納されていれば、前記バッファから前記必要なデータを読込み前記第１のクエリ実行手続きにおいて使用し、
　前記第１及び第２のクエリ実行のうちの前記第１のクエリ実行手続きによるクエリ実行結果を前記クエリ発行元に返す、
データベース管理方法。
　データベースへのクエリをクエリ発行元から受け付けるクエリ受付部と、前記受け付けたクエリに基づいて前記受け付けたクエリを実行するために必要な１以上のデータベースオペレーションと前記１以上のデータベースオペレーションの実行手順とを表す情報を含んだクエリ実行プランを生成するクエリ実行プラン生成部と、前記生成したクエリ実行プランに基づいてデータベースオペレーションを実行することにより前記クエリを実行する第１のクエリ実行手続きを行い前記第１のクエリ実行手続きによるクエリ実行結果を前記クエリ発行元に返す第１のクエリ実行部と、データの読込み要求を受け付けた際、読込み要求されたデータがバッファに格納されていなければ、前記読込み要求されたデータを、前記データベースから読み込んで前記バッファに格納し、前記読込み要求の発行元に提供し、読込み要求されたデータが既にバッファに格納されていれば、前記読込み要求されたデータを前記バッファから読み込み前記読込み要求の発行元に提供するバッファ管理部とを、計算機に実行されることにより前記計算機に構成するデータベース管理システム、を支援するためのコンピュータプログラムであって、
　前記生成したクエリ実行プランに基づいてデータベースオペレーションを実行することにより前記クエリを実行する第２のクエリ実行手続きを行い、
　前記第２のクエリ実行手続きにおいて、必要なデータの読込み要求を前記バッファ管理部に発行する、
ことを前記計算機に実行させるコンピュータプログラム。