(57)【要約】      （修正有）【課題】大規模データを対象とするクエリ処理を高速かつ確実に実行する。【解決手段】クエリ処理システムＳは、第１クエリ処理装置１と、複数の第２クエリ処理装置２とを備える。第１クエリ処理装置１は、取得したクエリに基づいて複数の第２クエリ処理装置２のそれぞれに実行させる複数の演算を特定し、当該演算の実行を指示する演算指示情報を含む実行計画情報を生成するクエリ計画部１２２と、クエリの実行結果を取得し、当該実行結果を出力する出力部１２３とを有する。複数の第２クエリ処理装置２のそれぞれは、自身が実行する複数の演算のそれぞれにメモリを割り当てるとともに、当該メモリの利用状況に基づいて複数の演算のそれぞれに割り当てられているメモリの量を動的に更新するバッファ管理部２２１と、演算指示情報に基づいて、複数の演算のそれぞれを、当該演算に割り当てられたメモリ上で実行する演算実行部２２２とを有する。【選択図】図２
2018101280.tif 000002
【特許請求の範囲】
【請求項１】
第１クエリ処理装置と、複数の第２クエリ処理装置とを備え、データベースに対応するクエリを処理するクエリ処理システムであって、
前記第１クエリ処理装置は、
前記クエリを取得するクエリ取得部と、
取得した前記クエリに基づいて前記複数の第２クエリ処理装置のそれぞれに実行させる複数の演算を特定し、当該演算の実行を指示する演算指示情報を含む実行計画情報を生成するクエリ計画部と、
前記複数の第２クエリ処理装置のそれぞれで実行された前記演算の結果に基づく前記クエリの実行結果を取得し、当該実行結果を出力する出力部とを有し、
前記複数の第２クエリ処理装置のそれぞれは、
前記第２クエリ処理装置において実行される複数の演算のそれぞれにメモリ領域を割り当てるとともに、当該メモリ領域の利用状況に基づいて前記複数の演算のそれぞれに割り当てられているメモリ領域のサイズを動的に更新するメモリ管理部と、
前記実行計画情報に含まれる前記演算指示情報に基づいて、前記複数の演算のそれぞれを、当該演算に割り当てられたメモリ領域上で実行する演算実行部とを有する、
クエリ処理システム。
【請求項２】
前記メモリ管理部は、前記演算実行部が実行中の演算において新たにメモリ領域を利用する場合に、複数の演算に割り当てられているメモリ領域のうち、利用されていないメモリ領域を解放するとともに、当該実行中の演算に対してメモリ領域を新たに割り当てる、
請求項１に記載のクエリ処理システム。
【請求項３】
前記クエリ計画部は、演算の実行順序を示す順序情報を含む前記実行計画情報を生成し、
前記演算実行部は、前記順序情報と、前記演算指示情報と、前記演算指示情報に対応する演算に対して割り当てられているメモリ領域の利用状況とに基づいて、最上位の演算から順に要求駆動方式に従った演算を実行し、
前記メモリ管理部は、前記演算実行部が実行中の演算において新たにメモリ領域を利用する場合に、前記実行順序に基づいて当該演算の下位の演算を特定し、当該下位の演算に割り当てられているメモリ領域の利用状況に基づいて、当該下位の演算に割り当てられているメモリ領域を解放するとともに、当該実行中の演算に対してメモリ領域を新たに割り当てる、
請求項１又は２に記載のクエリ処理システム。
【請求項４】
前記メモリ管理部は、前記演算実行部が当該実行中の演算において新たにメモリ領域を利用する場合に、前記下位の演算のうち、実行が完了している演算に割り当てられているメモリ領域を解放するとともに、当該実行中の演算に対して当該メモリ領域を新たに割り当てる、
請求項３に記載のクエリ処理システム。
【請求項５】
前記クエリ計画部は、取得した前記クエリに基づいて複数の演算指示情報を含むタスクを生成し、当該タスクの実行を指示するタスク実行指示情報を含む前記実行計画情報を生成し、
前記演算実行部は、前記実行計画情報に含まれる前記タスク実行指示情報に基づいて、タスクに含まれる前記複数の演算を、当該演算に割り当てられたメモリ領域上で実行する、
請求項１から４のいずれか１項に記載のクエリ処理システム。
【請求項６】
前記メモリ管理部は、前記第２クエリ処理装置において利用可能なメモリ領域のサイズと、前記第２クエリ処理装置において実行される演算の数とに基づいて、前記第２クエリ処理装置において実行される前記複数の演算のそれぞれにメモリ領域を割り当てる、
請求項５に記載のクエリ処理システム。
【請求項７】
前記メモリ管理部は、前記第２クエリ処理装置において利用可能なメモリ領域のサイズと、前記第２クエリ処理装置において実行される演算の数と、当該演算の内容とに基づいて、前記第２クエリ処理装置において実行される前記複数の演算のそれぞれにメモリ領域を割り当てる、
請求項６に記載のクエリ処理システム。
【請求項８】
前記メモリ管理部は、前記第２クエリ処理装置において利用可能なメモリ領域のサイズと、前記第２クエリ処理装置で実行されるタスクの数とに基づいて、複数のタスクのそれぞれに割り当てるメモリ領域のサイズを特定し、当該タスクに割り当てるメモリ領域のサイズと、当該タスクに含まれる演算の数とに基づいて、前記第２クエリ処理装置において実行される前記複数の演算のそれぞれにメモリ領域を割り当てる、
請求項５から７のいずれか１項に記載のクエリ処理システム。
【請求項９】
前記クエリ計画部は、複数の前記タスクのうち、同一の演算を行うタスク群を特定し、当該タスク群に含まれる複数のタスクのそれぞれに割り当てられるメモリ領域のサイズに基づいて当該複数のタスクのそれぞれに入力されるデータの比率を特定し、当該データの比率に対応する情報を出力する演算を示す前記演算指示情報を、当該タスク群にデータを提供するタスクに挿入する、
請求項８に記載のクエリ処理システム。
【請求項１０】
第１クエリ処理装置と、複数の第２クエリ処理装置とを備え、データベースに対応するクエリを処理するクエリ処理システムが実行するクエリ処理方法であって、
前記第１クエリ処理装置が、前記クエリを取得するステップと、
前記第１クエリ処理装置が、取得した前記クエリに基づいて前記複数の第２クエリ処理装置のそれぞれに実行させる複数の演算を特定し、当該演算の実行を指示する演算指示情報を含む実行計画情報を生成するステップと、
前記複数の第２クエリ処理装置のそれぞれが、前記第２クエリ処理装置において実行される複数の演算のそれぞれにメモリ領域を割り当てるステップと、
前記複数の第２クエリ処理装置のそれぞれが、前記実行計画情報に含まれる前記演算指示情報に基づいて、前記複数の演算のそれぞれを、当該演算に割り当てられたメモリ領域上で実行するステップと、
前記複数の第２クエリ処理装置のそれぞれが、前記メモリ領域の利用状況に基づいて前記複数の演算のそれぞれに割り当てられているメモリ領域のサイズを動的に更新するステップと、
前記第１クエリ処理装置が、前記複数の第２クエリ処理装置のそれぞれで実行された前記演算の結果に基づく前記クエリの実行結果を取得し、当該実行結果を出力するステップと、
を有するクエリ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースに対応するクエリを処理するクエリ処理システム及びクエリ処理方法に関する。
【背景技術】
【０００２】
従来、データベースに対応するクエリを解析し、クエリに対応する複数の処理を分散して処理することにより、効率的にクエリを処理する分散データベースシステムが知られている。例えば、特許文献１には、データベースを複数のクエリ処理エンジンが共有する環境において、クエリの内容に応じてクエリを分割し、クエリ処理エンジンに自動的に分配するシステムが開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１５−１２５７２６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
データベースシステムは、データの操作や定義を行うための言語に従って記述されたクエリを解釈することによって、データに対する処理を示す演算を抽出し、各演算の処理順序を決定する。各演算の処理順序は、関係代数式として木構造をしたクエリ実行計画で表現される。分散データベースシステムでは、第１クエリ処理装置（マスター装置）がクエリを解釈することによりクエリ実行計画を作成し、複数の第２クエリ処理装置（スレーブ装置）が当該クエリ実行計画に従ってデータ処理を並列に実行する。
【０００５】
ところで、演算の中には、結合演算や集合演算等の複数のデータを組み合わせる演算や、集計演算のように、入力されるデータのデータサイズに比べて、演算時のデータサイズが大きくなる演算が存在する。
【０００６】
第２クエリ処理装置は、データ処理を自身に実装されているメモリ上で行う。メモリは有限であることから、複数のデータ処理を同時に実行する場合には、複数のデータ処理のそれぞれに割り当てられるメモリが小さく制限されることがある。このような場合において、大規模なデータのデータ処理を実行したり、演算時のデータサイズが大きくなる演算を実行したりすると、割り当てられたメモリ上でデータ処理ができなくなり、ＯＳのスワップ機構の利用によって大幅な遅延が発生したり、クエリ実行に失敗したりするという問題がある。
【０００７】
そこで、本発明はこれらの点に鑑みてなされたものであり、大規模データを対象とするクエリ処理を高速かつ確実に実行することができるクエリ処理システムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の第１の態様に係るクエリ処理システムは、第１クエリ処理装置と、複数の第２クエリ処理装置とを備え、データベースに対応するクエリを処理するクエリ処理システムであって、前記第１クエリ処理装置は、前記クエリを取得するクエリ取得部と、取得した前記クエリに基づいて前記複数の第２クエリ処理装置のそれぞれに実行させる複数の演算を特定し、当該演算の実行を指示する演算指示情報を含む実行計画情報を生成するクエリ計画部と、前記複数の第２クエリ処理装置のそれぞれで実行された前記演算の結果に基づく前記クエリの実行結果を取得し、当該実行結果を出力する出力部とを有し、前記複数の第２クエリ処理装置のそれぞれは、前記第２クエリ処理装置において実行される複数の演算のそれぞれにメモリ領域を割り当てるとともに、当該メモリ領域の利用状況に基づいて前記複数の演算のそれぞれに割り当てられているメモリ領域のサイズを動的に更新するメモリ管理部と、前記実行計画情報に含まれる前記演算指示情報に基づいて、前記複数の演算のそれぞれを、当該演算に割り当てられたメモリ領域上で実行する演算実行部とを有する。
【０００９】
前記メモリ管理部は、前記演算実行部が実行中の演算において新たにメモリ領域を利用する場合に、複数の演算に割り当てられているメモリ領域のうち、利用されていないメモリ領域を解放するとともに、当該実行中の演算に対してメモリ領域を新たに割り当ててもよい。
前記クエリ計画部は、演算の実行順序を示す順序情報を含む前記実行計画情報を生成し、前記演算実行部は、前記順序情報と、前記演算指示情報と、前記演算指示情報に対応する演算に対して割り当てられているメモリ領域の利用状況とに基づいて、最上位の演算から順に要求駆動方式に従った演算を実行し、前記メモリ管理部は、前記演算実行部が実行中の演算において新たにメモリ領域を利用する場合に、前記実行順序に基づいて当該演算の下位の演算を特定し、当該下位の演算に割り当てられているメモリ領域の利用状況に基づいて、当該下位の演算に割り当てられているメモリ領域を解放するとともに、当該実行中の演算に対してメモリ領域を新たに割り当ててもよい。
【００１０】
前記メモリ管理部は、前記演算実行部が当該実行中の演算において新たにメモリ領域を利用する場合に、前記下位の演算のうち、実行が完了している演算に割り当てられているメモリ領域を解放するとともに、当該実行中の演算に対して当該メモリ領域を新たに割り当ててもよい。
【００１１】
前記クエリ計画部は、取得した前記クエリに基づいて複数の演算指示情報を含むタスクを生成し、当該タスクの実行を指示するタスク実行指示情報を含む前記実行計画情報を生成し、前記演算実行部は、前記実行計画情報に含まれる前記タスク実行指示情報に基づいて、タスクに含まれる前記複数の演算を、当該演算に割り当てられたメモリ領域上で実行してもよい。
【００１２】
前記メモリ管理部は、前記第２クエリ処理装置において利用可能なメモリ領域のサイズと、前記第２クエリ処理装置において実行される演算の数とに基づいて、前記第２クエリ処理装置において実行される前記複数の演算のそれぞれにメモリ領域を割り当ててもよい。
【００１３】
前記メモリ管理部は、前記第２クエリ処理装置において利用可能なメモリ領域のサイズと、前記第２クエリ処理装置において実行される演算の数と、当該演算の内容とに基づいて、前記第２クエリ処理装置において実行される前記複数の演算のそれぞれにメモリ領域を割り当ててもよい。
【００１４】
前記メモリ管理部は、前記第２クエリ処理装置において利用可能なメモリ領域のサイズと、前記第２クエリ処理装置で実行されるタスクの数とに基づいて、複数のタスクのそれぞれに割り当てるメモリ領域のサイズを特定し、当該タスクに割り当てるメモリ領域のサイズと、当該タスクに含まれる演算の数とに基づいて、前記第２クエリ処理装置において実行される前記複数の演算のそれぞれにメモリ領域を割り当ててもよい。
【００１５】
前記クエリ計画部は、複数の前記タスクのうち、同一の演算を行うタスク群を特定し、当該タスク群に含まれる複数のタスクのそれぞれに割り当てられるメモリ領域のサイズに基づいて当該複数のタスクのそれぞれに入力されるデータの比率を特定し、当該データの比率に対応する情報を出力する演算を示す前記演算指示情報を、当該タスク群にデータを提供するタスクに挿入してもよい。
【００１６】
本発明の第２の態様に係るクエリ処理方法は、第１クエリ処理装置と、複数の第２クエリ処理装置とを備え、データベースに対応するクエリを処理するクエリ処理システムが実行するクエリ処理方法であって、前記第１クエリ処理装置が、前記クエリを取得するステップと、前記第１クエリ処理装置が、取得した前記クエリに基づいて前記複数の第２クエリ処理装置のそれぞれに実行させる複数の演算を特定し、当該演算の実行を指示する演算指示情報を含む実行計画情報を生成するステップと、前記複数の第２クエリ処理装置のそれぞれが、前記第２クエリ処理装置において実行される複数の演算のそれぞれにメモリ領域を割り当てるステップと、前記複数の第２クエリ処理装置のそれぞれが、前記実行計画情報に含まれる前記演算指示情報に基づいて、前記複数の演算のそれぞれを、当該演算に割り当てられたメモリ領域上で実行するステップと、前記複数の第２クエリ処理装置のそれぞれが、前記メモリ領域の利用状況に基づいて前記複数の演算のそれぞれに割り当てられているメモリ領域のサイズを動的に更新するステップと、前記第１クエリ処理装置が、前記複数の第２クエリ処理装置のそれぞれで実行された前記演算の結果に基づく前記クエリの実行結果を取得し、当該実行結果を出力するステップと、を有する。
【発明の効果】
【００１７】
本発明によれば、大規模データを対象とするクエリ処理を高速かつ確実に実行することができるという効果を奏する。
【図面の簡単な説明】
【００１８】
【図１】本実施形態に係る仮想データベースシステムの構成を示す図である。
【図２】本実施形態に係るクエリ処理システムの構成を示す図である。
【図３】本実施形態に係る演算とバッファとの関係の一例を示す図である。
【図４】本実施形態に係るクエリに対して生成された複数のタスクに含まれる演算とバッファとの関係の一例を示す図である。
【図５】本実施形態に係るバッファの増加依頼を受け付けた場合におけるバッファ管理部の処理の流れを示す図である。
【図６】本実施形態に係る演算実行部が実行する処理の流れを示すフローチャートである。
【発明を実施するための形態】
【００１９】
［仮想データベースシステムＶＤＳの概要］
図１は、本実施形態に係る仮想データベースシステムＶＤＳの構成を示す図である。仮想データベースシステムＶＤＳは、クエリ処理システムＳと、データベース３１を物理的に格納する複数の記憶装置３と、ユーザ端末４とを備え、複数のデータベース３１を仮想的に統合するシステムである。なお、図１において、ユーザ端末４は１台のみ示されているが、複数のユーザ端末４がクエリ処理システムＳに接続されているものとする。
【００２０】
クエリ処理システムＳは、ユーザ端末４からクエリを取得すると、当該クエリに対応する１以上のデータベース３１を特定する。クエリ処理システムＳは、当該クエリに基づいて、特定したデータベース３１からデータを取得して演算を実行し、当該クエリに対応する実行結果をユーザ端末４に出力する。これにより、ユーザは、データベース３１の物理的な位置を意識することなく複数のデータベース３１に格納されているデータを参照することができる。
【００２１】
図２は、本実施形態に係るクエリ処理システムＳの構成を示す図である。図２に示すように、クエリ処理システムＳは、第１クエリ処理装置１と、複数の第２クエリ処理装置２とを備える。第１クエリ処理装置１は、コンピュータであり、ＬＡＮ（Local Area Network）等を介して、ユーザ端末４と、複数の第２クエリ処理装置２とに通信可能に接続されている。第２クエリ処理装置２は、コンピュータであり、ＬＡＮ等を介して、第１クエリ処理装置１と、複数の記憶装置３とに接続されている。
【００２２】
第１クエリ処理装置１は、ユーザ端末４からクエリを取得すると、取得したクエリに基づいて複数の第２クエリ処理装置２のそれぞれに実行させる複数の演算を特定する。第１クエリ処理装置１は、第２クエリ処理装置２に、特定した演算の実行を指示する。
【００２３】
複数の第２クエリ処理装置２のそれぞれは、自身が実行する複数の演算のそれぞれにメモリを割り当てる。複数の第２クエリ処理装置２のそれぞれは、データベース３１又は他の第２クエリ処理装置２からデータを取得し、演算に割り当てられたメモリ上で、当該演算を実行する。複数の第２クエリ処理装置２のそれぞれは、メモリの利用状況に基づいて複数の演算のそれぞれに割り当てられるメモリの量を動的に更新する。
【００２４】
第１クエリ処理装置１は、複数の第２クエリ処理装置２のそれぞれで実行された演算の結果に基づくクエリの実行結果を取得し、当該実行結果をユーザ端末４に出力する。このように、クエリ処理システムＳは、複数の第２クエリ処理装置２においてクエリに対応する演算を分散して実行し、さらに第２クエリ処理装置２において、演算に割り当てられるメモリの量を動的に変更することにより、大規模データを対象とするクエリ処理を高速かつ確実に実行することができる。
続いて、第１クエリ処理装置１と、第２クエリ処理装置２との構成について説明する。なお、以下の説明において、演算に割り当てられるメモリ領域をバッファともいう。また、以下の説明において、「バッファ管理部」を「メモリ管理部」と読み替えてもよい。
【００２５】
［第１クエリ処理装置１の構成例］
第１クエリ処理装置１は、図２に示すように、記憶部１１と、制御部１２とを備える。
記憶部１１は、例えば、ＲＯＭ（Read Only Memory）及びＲＡＭ（Random Access Memory）等である。記憶部１１は、第１クエリ処理装置１を機能させるための各種プログラムを記憶する。例えば、記憶部１１は、第１クエリ処理装置１の制御部１２を、後述するクエリ取得部１２１、クエリ計画部１２２、及び出力部１２３として機能させる第１クエリ実行プログラムを記憶する。
【００２６】
また、記憶部１１は、演算実装情報１１１と、利用可能メモリ情報１１２とを記憶する。
演算実装情報１１１は、クエリが示す操作を実行するための複数の演算を示す演算情報と、演算に必要とされるバッファの種類とを関連付けた情報である。操作の種類は、例えば、射影、結合、グループ化等である。バッファの種類は、後述する出力バッファ、制御バッファ、及び共有バッファを示す情報である。
利用可能メモリ情報１１２は、複数の第２クエリ処理装置２のそれぞれにおいて利用可能なメモリ２１１のサイズを示す情報を記憶する。
【００２７】
制御部１２は、例えばＣＰＵ（Central Processing Unit）である。制御部１２は、記憶部１１に記憶されている各種プログラムを実行することにより、第１クエリ処理装置１に係る機能を制御する。制御部１２は、第１クエリ実行プログラムを実行することにより、クエリ取得部１２１、クエリ計画部１２２、及び出力部１２３として機能する。
【００２８】
クエリ取得部１２１は、ユーザ端末４から複数のデータベース３１の少なくともいずれかに対応するクエリを取得する。
クエリ計画部１２２は、取得されたクエリに基づいて複数の第２クエリ処理装置２のそれぞれに実行させる複数の演算を特定し、特定した複数の演算の実行を指示する演算指示情報と、複数の演算の実行順序を示すツリー構造の順序情報と含む実行計画情報を生成する。
【００２９】
具体的には、クエリ計画部１２２は、以下の手順により実行計画情報を生成する。まず、クエリ計画部１２２は、取得されたクエリを解析し、クエリが示す１以上の操作の種類を特定する。クエリ計画部１２２は、特定した操作の種類に対応し、複数の演算の実行を指示する演算指示情報を含むタスクを特定することにより、取得されたクエリに対応する複数のタスクを生成する。ここで、タスクには、複数の演算の実行順序を示す順序情報と、複数の演算の実行を指示する演算指示情報とが含まれている。
【００３０】
クエリ計画部１２２は、生成したタスクの実行を指示するタスク実行指示情報を含む実行計画情報を生成する。クエリ計画部１２２は、タスクを実行する１以上の第２クエリ処理装置２のそれぞれに対応する実行計画情報を生成する。
【００３１】
また、クエリ計画部１２２は、タスクに含まれる複数の演算の内容及び実行順序と、演算実装情報１１１とに基づいて、複数の演算のそれぞれに割り当てられるバッファのサイズを示すバッファ情報をタスクごとに生成する。図３は、本実施形態に係る演算とバッファとの関係の一例を示す図である。
【００３２】
図３において、「ｏｐ」は、タスクＴに含まれている演算を示し、「Ｂ」はバッファを示している。「Ｂ」に対して大括弧で設けられている添え字は、バッファに関連する演算の実行順序に対応している。図３に示すように、バッファは複数の演算のそれぞれに割り当てられる。また、バッファには、出力バッファと、制御バッファと、共有バッファとが含まれている。
【００３３】
出力バッファは、演算の実行結果を示すデータを格納する。出力バッファは、当該演算の上流の演算に実行結果を示すデータを受け渡すために用いられる。
制御バッファは、演算を実行する途中で生成される中間結果を示すデータを格納するバッファである。制御バッファは、他の演算によって参照されないバッファである。また、制御バッファは、演算の種類によっては設けられないことがある。制御バッファの有無は、演算実装情報１１１において演算ごとに規定されている。例えば、結合演算の場合には、第１のテーブルのデータと、第２のテーブルのデータとの突合せを行うため、制御バッファが必要となる。また、射影演算のように、一時的にデータを保存する必要のない演算の場合には、制御バッファは不要となる。
【００３４】
共有バッファは、タスクの実行結果を格納するバッファである。共有バッファは、他のタスク又は第１クエリ処理装置１が参照するバッファである。共有バッファには、タスクの実行結果を共有バッファに格納するＯｕｔｐｕｔ演算によって、データが格納される。Ｏｕｔｐｕｔ演算は、タスクに含まれる複数の演算のうち最上流の演算として指定される。
【００３５】
第２クエリ処理装置２は、複数の演算のそれぞれについて、直前に実行される演算に割り当てられている出力バッファと、自身に割り当てられている制御バッファとからデータを取得して演算を実行する。第２クエリ処理装置２は、当該演算の実行結果を示すデータを、当該演算に割り当てられている出力バッファに格納する。
【００３６】
図３に示す例において、第２クエリ処理装置２は、演算ｏｐ［ｉ］を実行する場合に、直前に実行される演算ｏｐ［ｉ−１］に割り当てられているバッファＢ［ｉ−１］を構成する出力バッファからデータを取得する。第２クエリ処理装置２は、演算ｏｐ［ｉ］が示す演算の内容に基づいて演算を実行する。第２クエリ処理装置２は、演算の途中で発生する中間結果を示すデータを、演算ｏｐ［ｉ］に割り当てられているバッファＢ［ｉ］を構成する制御バッファに格納する。また、第２クエリ処理装置２は、演算ｏｐ［ｉ］の実行結果を示すデータを、バッファＢ［ｉ］を構成する出力バッファに格納する。
【００３７】
また、タスクＴには、データベース３１に格納されているデータ、又は他のタスクの実行結果を示すデータを、他のタスクの共有バッファから取得するための演算としてのＳｃａｎ演算又はＥｘｃｈａｎｇｅ演算が含まれている。Ｓｃａｎ演算は、データベース３１からデータを取得する演算である。Ｅｘｃｈａｎｇｅ演算は、他のタスクの共有バッファからデータを取得する演算である。これらの演算は、タスクに含まれる複数の演算のうち、最下流の演算として指定される。
【００３８】
図４は、本実施形態に係るクエリに対して生成された複数のタスクに含まれる演算とバッファとの関係の一例を示す図である。図４に示す例は、以下のクエリに対応しているものとする。
SELECT a.name, b.value
FROM a, b
WHERE a.id = b.id
【００３９】
タスクＴ［０］は、テーブル「ａ」が格納されているデータベース３１からデータを取得し、当該データを上流のタスクＴ［２］に受け渡すための共有バッファＢ［１］にデータを格納する。タスクＴ［１］は、テーブル「ｂ」が格納されているデータベース３１からデータを取得し、当該データを上流のタスクＴ［２］に受け渡すための共有バッファＢ［３］にデータを格納する。タスクＴ［２］は、タスクＴ［０］、Ｔ［１］のそれぞれの共有バッファＢ［１］、Ｂ［３］からデータを取得し、これらのデータの結合を行う。タスクＴ［２］は、結合結果を示すデータを第１クエリ処理装置１に受け渡すため共有バッファＢ［７］に当該データを格納する。
【００４０】
図２に説明を戻す。クエリ計画部１２２は、複数の第２クエリ処理装置２のそれぞれにおいて実行されるタスクの数を特定する。クエリ計画部１２２は、タスクの数と、利用可能メモリ情報１１２に含まれている第２クエリ処理装置２において利用可能なメモリ２１１のサイズを示す情報とに基づいて、複数のタスクのそれぞれに割り当てるメモリのサイズを特定する。例えば、クエリ計画部１２２は、利用可能なメモリのサイズを、タスクの数で除算することによって、複数のタスクのそれぞれに割り当てるメモリのサイズを特定する。
【００４１】
クエリ計画部１２２は、複数のタスクのそれぞれについて、特定されたメモリのサイズと、タスクに含まれる複数の演算の数とに基づいて、複数の演算のバッファサイズを特定する。クエリ計画部１２２は、演算に出力バッファ及び制御バッファが割り当てられる場合、例えば、演算に対応するバッファサイズの半分のサイズを、当該出力バッファ及び制御バッファのサイズとする。クエリ計画部１２２は、特定したバッファサイズを示す情報を含むバッファ情報を生成する。
【００４２】
ここで、クエリ計画部１２２は、第２クエリ処理装置２において利用可能なバッファのサイズと、第２クエリ処理装置２において実行される演算の数と、当該演算の内容とに基づいて、第２クエリ処理装置２において実行される複数の演算のそれぞれに割り当てるバッファのサイズを特定してもよい。このようにすることで、第１クエリ処理装置１は、第２クエリ処理装置２に、例えば、データの参照量や参照回数が多い演算に対して、相対的に多くのバッファを割り当てさせることができる。
【００４３】
なお、クエリ計画部１２２は、複数のタスクを生成する際に、相対的に処理負荷が大きいデータ操作については、複数のタスクを生成する。そして、クエリ計画部１２２は、複数の第２クエリ処理装置２に当該複数のタスクを並列して実行させることによって、分散処理を行わせる。
【００４４】
図４に示す例では、タスクＴ［２］は、テーブルの結合に係る処理であり、処理負荷が大きいことから、クエリ計画部１２２は、タスクＴ［２］を複数生成し、複数の第２クエリ処理装置２において分散処理させる。クエリ計画部１２２は、バッファ情報を生成した後、複数のタスクのうち、同一の演算を行うタスク群を特定する。クエリ計画部１２２は、生成したバッファ情報に基づいて、当該タスク群に含まれる複数のタスクＴ［２］のそれぞれに割り当てられるバッファのサイズを特定する。クエリ計画部１２２は、特定したサイズに基づいて当該複数のタスクのそれぞれに入力されるデータの比率を特定し、当該データの比率に対応する情報を出力する演算を示す演算指示情報を、当該タスク群にデータを提供するタスクに挿入する。
【００４５】
例えば、第２クエリ処理装置２として、３台の第２クエリ処理装置２（第２クエリ処理装置２Ａ、第２クエリ処理装置２Ｂ、第２クエリ処理装置２Ｃ）が存在し、それぞれにおける利用可能なメモリのサイズが３０ＧＢであるものとする。クエリ計画部１２２は、図４に対応するクエリを実行する場合、第２クエリ処理装置２ＡにタスクＴ［０］とＴ［２］とを実行させ、第２クエリ処理装置２ＢにＴ［１］とＴ［２］とを実行させ、第２クエリ処理装置２Ｃが、Ｔ［２］を実行させるものとする。
【００４６】
さらに、クエリ計画部１２２は、それぞれの第２クエリ処理装置２において利用可能なメモリのサイズを、実行するタスクの数で除算することにより、バッファのサイズを特定する。ここで、クエリ計画部１２２は、第２クエリ処理装置２Ａ、第２クエリ処理装置２Ｂが実行するＴ［２］のバッファのサイズを１５ＧＢ、第２クエリ処理装置２Ｃが実行するＴ［２］のバッファのサイズを３０ＧＢとする。この場合において、バッファのサイズの比率は、１：１：２となる。
【００４７】
Ｔ［０］及びＴ［１］においてハッシュ化するデータが一様に分布すると仮定すると、クエリ計画部１２２は、３台の第２クエリ処理装置２におけるバッファのサイズの比率に対応するようにハッシュ値を生成するハッシュ関数を生成する。例えば、クエリ計画部１２２は、ハッシュ値として０、１、２、３を生成するハッシュ関数を生成し、当該ハッシュ関数をＴ［０］及びＴ［１］におけるＯｕｔｐｕｔ演算に挿入する。タスクＴ［１］、タスクＴ［０］を実行する第２クエリ処理装置２Ａ、２Ｂは、Ｏｕｔｐｕｔ演算において、複数のタスクＴ［２］にデータを振り分けるために、ハッシュ関数によって、取得したデータのハッシュ値を生成する。第２クエリ処理装置２Ａ、２Ｂは、取得したデータとハッシュ値とを関連付けて共有バッファに記憶させる。
【００４８】
そして、クエリ計画部１２２は、第２クエリ処理装置２ＡがタスクＴ［２］を実行する際に、タスクＴ［０］、Ｔ［１］から、ハッシュ値「０」に関連付けられているデータを取得するものとする。また、クエリ計画部１２２は、第２クエリ処理装置２ＢがタスクＴ［２］を実行する際に、タスクＴ［０］、Ｔ［１］から、ハッシュ値「２」に関連付けられているデータを取得するものとする。また、クエリ計画部１２２は、第２クエリ処理装置２ＣがタスクＴ［２］を実行する際に、タスクＴ［０］、Ｔ［１］から、ハッシュ値「１」、［３］に関連付けられているデータを取得するものとする。このようにすることで、第１クエリ処理装置１は、処理負荷が大きいタスクＴ［２］を複数の第２クエリ処理装置２に分散実行させて実行結果を高速に取得することができる。
【００４９】
図２に説明を戻す。クエリ計画部１２２は、生成した実行計画情報と、バッファ情報とを、タスクを実行する１以上の第２クエリ処理装置２に送信する。
出力部１２３は、複数の第２クエリ処理装置２のそれぞれで実行された演算の結果に基づくクエリの実行結果を取得し、当該実行結果をユーザ端末４に出力する。図４に示す例では、出力部１２３は、複数の第２クエリ処理装置２において実行される複数のタスクＴ［２］の共有バッファから実行結果を示すデータを取得し、これらのデータをユーザ端末４に出力する。
【００５０】
［第２クエリ処理装置２の構成例］
第２クエリ処理装置２は、図２に示すように、記憶部２１と、制御部２２とを備える。
記憶部２１は、例えば、ＲＯＭ及びＲＡＭ等である。記憶部２１は、メモリ２１１と、データストレージ２１２とを備える。メモリ２１１は、演算に対応するデータを一時的に記憶する。データストレージ２１２は、例えばハードディスクであり、演算に対応するデータのうち、メモリ２１１の記憶容量の上限を超えるデータを一時的に記憶する。メモリ２１１へのデータの書込速度及び読取速度は、データストレージ２１２へのデータの書込速度及び読取速度に比べて速いものとする。
【００５１】
記憶部２１は、第２クエリ処理装置２を機能させるための各種プログラムを記憶する。例えば、記憶部２１は、第２クエリ処理装置２の制御部２２を、後述するバッファ管理部２２１及び演算実行部２２２として機能させる第２クエリ実行プログラムを記憶する。
【００５２】
制御部２２は、例えばＣＰＵである。制御部２２は、記憶部２１に記憶されている各種プログラムを実行することにより、第２クエリ処理装置２に係る機能を制御する。制御部２２は、第２クエリ実行プログラムを実行することにより、バッファ管理部２２１及び演算実行部２２２として機能する。
【００５３】
バッファ管理部２２１は、第２クエリ処理装置２において実行される複数の演算のそれぞれにバッファを割り当てるとともに、当該バッファの利用状況に基づいて複数の演算のそれぞれに割り当てられているバッファのサイズを動的に更新する。
【００５４】
まず、バッファ管理部２２１は、初期処理として、第１クエリ処理装置１から取得したバッファ情報に基づいて、実行される複数のタスクのそれぞれにバッファを割り当てる。具体的には、バッファ管理部２２１は、第１クエリ処理装置１から取得したバッファ情報を記憶部２１に記憶させる。バッファ管理部２２１は、記憶部２１に記憶されているバッファ情報に基づいて、第２クエリ処理装置２において実行されるタスクに含まれている複数の演算のそれぞれにバッファを割り当てる。
【００５５】
すなわち、バッファ管理部２２１は、第１クエリ処理装置１から取得したバッファ情報に基づいて、第２クエリ処理装置２において実行されるタスクの数と、第２クエリ処理装置２において利用可能なバッファのサイズとに対応する、複数のタスクのそれぞれに割り当てるバッファのサイズを特定する。バッファ管理部２２１は、第２クエリ処理装置２において実行される複数の演算のそれぞれに、タスクに割り当てるバッファのサイズと、当該タスクに含まれる演算の数とに基づいて算出されたサイズのバッファを割り当てる。
【００５６】
また、バッファ管理部２２１は、演算実行部２２２が実行中の演算に割り当てられているバッファの利用状況を特定する。例えば、バッファ管理部２２１は、選択した演算に対応するバッファの利用状況を示す情報を演算実行部２２２から取得する。バッファの利用状況を示す情報には、入力元のバッファのサイズと、当該バッファに格納されているデータのサイズと、出力先のバッファのサイズと、当該バッファに格納されているデータのサイズとを示す情報が含まれている。
【００５７】
バッファ管理部２２１は、入力元のバッファのサイズから、当該バッファに格納されているデータのサイズを減算することにより、入力元のバッファの空き領域のサイズを特定する。ここで、入力元のバッファは、直下の演算に割り当てられている出力バッファ、又は実行中の演算に割り当てられている制御バッファである。また、バッファ管理部２２１は、出力先のバッファのサイズから、当該バッファに格納されているデータのサイズを減算することにより、出力先のバッファの空き領域のサイズを特定する。ここで、出力先のバッファは、実行中の演算の出力バッファ、制御バッファ、又は共有バッファである。バッファ管理部２２１は、空き領域のサイズを特定したことに応じて、実行中の演算と、直下の演算とに対応するバッファのバッファ情報を更新する。
【００５８】
また、バッファ管理部２２１は、タスクに含まれる複数の演算のそれぞれについて、処理が完了しているか否かを示す処理完了フラグ、制御バッファへのデータの格納が完了しているか否かを示す格納完了フラグを取得することにより、タスクに含まれる複数の演算の完了状況を示す情報を更新する。
【００５９】
演算実行部２２２が実行中の演算に割り当てられている複数のバッファのいずれかにおいて全ての領域が利用されており、演算実行部２２２が当該実行中の演算において新たに当該メモリを利用する場合、バッファ管理部２２１は、演算実行部２２２からバッファの増加依頼を受け付ける。
【００６０】
バッファ管理部２２１は、演算実行部２２２が実行中の演算において新たにメモリ領域を利用する場合に、複数の演算に割り当てられているバッファのうち、利用されていないバッファを解放するとともに、当該実行中の演算に対してメモリ領域を新たに割り当てる。例えば、バッファ管理部２２１は、演算の実行順序に基づいて実行中の演算の下位の演算を特定し、当該下位の演算に割り当てられているバッファの利用状況に基づいて、当該下位の演算に割り当てられているバッファを解放するとともに、実行中の演算に対してバッファを新たに割り当てる。バッファ管理部２２１は、演算実行部２２２が当該実行中の演算において新たに当該バッファを利用する場合に、下位の演算のうち、実行が完了している演算に割り当てられているバッファを解放するとともに、当該実行中の演算に対して、解放されたバッファを新たに割り当てる。
【００６１】
図５は、本実施形態に係るバッファの増加依頼を受け付けた場合におけるバッファ管理部２２１の処理の流れを示す図である。なお、以下の説明において、増加依頼に対応するバッファを、増加対象バッファという。
まず、バッファ管理部２２１は、実行中の演算を含んでいるタスクに割り当てられているバッファから空き領域を探索する（Ｓ１０）。バッファ管理部２２１は、複数の演算の完了状況を示す情報に基づいて、演算実行部２２２による処理が完了しているバッファ（出力バッファ、制御バッファ及び共有バッファ）の未使用領域を空き領域として探索する。
【００６２】
例えば、バッファ管理部２２１は、増加対象バッファが出力バッファの場合、実行中の演算に割り当てられている制御バッファの未使用領域を空き領域として探索する。この場合、バッファ管理部２２１は、制御バッファへのデータの格納が完了している場合に、当該制御バッファの未使用領域を空き領域として探索する。
【００６３】
また、バッファ管理部２２１は、増加対象バッファが制御バッファの場合、実行中の演算に割り当てられている出力バッファの未使用領域を空き領域として探索する。この場合、当該出力バッファは、まだ利用される可能性がある。このため、バッファ管理部２２１は、全ての領域を増加対象バッファに割り当てないように、出力バッファのサイズの所定割合のサイズを空き領域のサイズとして算出する。例えば、バッファ管理部２２１は、出力バッファの未使用領域の半分を空き領域として探索する。
【００６４】
また、バッファ管理部２２１は、演算の実行順序に基づいて、実行中の演算の下位の演算に割り当てられ、当該下位の演算によるデータの格納が完了している制御バッファの未使用領域を空き領域として探索する。
【００６５】
また、バッファ管理部２２１は、演算の実行順序に基づいて、実行中の演算の下位の演算に割り当てられているバッファの未使用領域を空き領域として探索する。この場合、当該バッファには新たにデータが格納される可能性がある。このため、バッファ管理部２２１は、当該バッファのサイズの所定割合のサイズを空き領域のサイズとして算出する。例えば、バッファ管理部２２１は、当該バッファの未使用領域の半分を空き領域として探索する。
また、バッファ管理部２２１は、演算実行部２２２による処理が完了しているタスクに対応するバッファを空き領域として探索してもよい。
【００６６】
続いて、バッファ管理部２２１は、空き領域が探索できたか否かを判定する（Ｓ２０）。バッファ管理部２２１は、空き領域が探索できたと判定すると、Ｓ３０に処理を移す。Ｓ３０において、バッファ管理部２２１は、探索された空き領域を解放するとともに、増加対象バッファに対して当該空き領域を割り当てる。
【００６７】
バッファ管理部２２１は、Ｓ２０において空き領域が探索できなかったと判定すると、増加対象バッファが制御バッファであるか否かを判定する（Ｓ４０）。バッファ管理部２２１は、増加対象バッファが制御バッファであると判定すると、Ｓ５０に処理を移す。Ｓ５０において、バッファ管理部２２１は、増加対象バッファに対してデータストレージ２１２の領域を割り当てる。
【００６８】
バッファ管理部２２１は、Ｓ３０又はＳ５０において増加対象バッファに領域を割り当てた後、バッファ情報を更新し、更新後のバッファ情報を演算実行部２２２に通知する（Ｓ６０）。
また、バッファ管理部２２１は、Ｓ４０において、増加対象バッファが制御バッファではなく、出力バッファ又は共有バッファであると判定すると、増加不可を示す情報を演算実行部２２２に通知する（Ｓ７０）。出力バッファと共有バッファとのバッファのサイズを増加させなくても第２クエリ処理装置２における処理が止まることはないため、バッファ管理部２２１は、相対的に読取速度及び書込速度が遅いデータストレージ２１２の領域を付与しない。
【００６９】
図２に説明を戻す。演算実行部２２２は、実行計画情報に含まれるタスク指示情報に基づいて、複数のタスクのそれぞれに含まれる複数の演算を特定する。演算実行部２２２は、タスクに含まれる複数の演算のそれぞれを、当該演算に割り当てられたバッファ上で実行する。
【００７０】
具体的には、演算実行部２２２は、実行計画情報に含まれている１以上のタスク実行指示情報を特定する。そして、演算実行部２２２は、タスク実行指示情報に含まれる順序情報と、演算指示情報と、演算指示情報に対応する演算に対して割り当てられているバッファの利用状況とに基づいて、最上位の演算から順に要求駆動方式に従った演算を実行する。
【００７１】
図６は、本実施形態に係る演算実行部２２２が実行する処理の流れを示すフローチャートである。図６に示すように、演算実行部２２２は、第１クエリ処理装置１から実行計画情報を取得する（Ｓ１１０）。
続いて、演算実行部２２２は、実行計画情報に基づいて、実行対象の複数の演算のうち、最上位の演算を選択する（Ｓ１２０）。ここで、最上位の演算は原則としてＯｕｔｐｕｔ演算である。
続いて、演算実行部２２２は、選択した演算と直下の演算とのバッファ情報を取得する（Ｓ１３０）。なお、演算実行部２２２は、後述するＳ２６０から遷移した結果、Ｓｃａｎ演算を選択した場合には、直下の演算が存在しないことから、直下の演算のバッファ情報を取得しない。
【００７２】
続いて、演算実行部２２２は、取得したバッファ情報に基づいて、選択した演算を実行可能か否かを判定する（Ｓ１４０）。例えば、演算実行部２２２は、出力先の出力バッファ又は共有バッファに格納されているデータのサイズが、これらのバッファのサイズの上限未満の場合に、以下の第１条件から第３条件のいずれかを満たす場合に、選択した演算を実行可能と判定する。第１条件は、入力元の出力バッファにデータが格納されていることである。第２条件は、入力元のデータベース３１に未取得のデータが存在していることである。第３条件は、入力元の他のタスクの共有バッファに未取得のデータが存在していることである。ここで、出力先の出力バッファは、選択した演算に割り当てられているバッファであり、入力元の出力バッファは、選択した演算の直下の演算に割り当てられている出力バッファである。
【００７３】
演算実行部２２２は、選択した演算を実行可能と判定すると、Ｓ１６０に処理を移す。また、演算実行部２２２は、選択した演算を実行不可能と判定すると、Ｓ１５０に処理を移す。演算実行部２２２は、Ｓ１５０において実行対象の演算を直下の演算に移行させ、その後、Ｓ１３０に処理を移す。
【００７４】
Ｓ１６０において、演算実行部２２２は、選択した演算を実行する。具体的には、演算実行部２２２は、演算の種類に対応する処理を実行する。演算実行部２２２は、直下の演算に割り当てられている出力バッファからデータを取得し、演算の種類に対応する処理を実行し、演算結果を、選択した演算に割り当てられている出力バッファに格納する。ここで、選択した演算に制御バッファが割り当てられている場合には、演算を実行する途中で生成される中間結果を示すデータを制御バッファに格納する。演算実行部２２２は、選択した演算に割り当てられている出力バッファに、出力バッファのサイズ分のデータが格納されるか、直下の演算に割り当てられている出力バッファが空になるかのいずれかを満たすまで、演算の実行を継続する。演算実行部２２２は、選択した演算の実行が中断又は終了すると、選択した演算に対応するバッファの利用状況を示す情報をバッファ管理部２２１に通知する。
【００７５】
続いて、演算実行部２２２は、選択した演算の実行後における、選択した演算と直下の演算とのバッファ情報を取得する（Ｓ１７０）。
続いて、演算実行部２２２は、Ｓ１７０において取得したバッファ情報に基づいて、選択した演算の制御バッファのサイズ、選択した演算の出力先の共有バッファのサイズ、直下の演算の出力バッファのサイズとの少なくともいずれかを増加させるか否かを判定する（Ｓ１８０）。
【００７６】
具体的には、演算実行部２２２は、選択した演算に割り当てられている制御バッファに、当該制御バッファのサイズ分のデータが格納されているとともに、直下の演算に割り当てられている出力バッファにデータが格納されている場合に、当該制御バッファのサイズを増加させると判定する。
【００７７】
また、演算実行部２２２は、選択した演算に対応する共有バッファに、当該共有バッファのサイズ分のデータが格納されているとともに、直下の演算に割り当てられている出力バッファにデータが格納されている場合に、当該共有バッファのサイズを増加させると判定する。
【００７８】
また、演算実行部２２２は、選択した演算の出力先のバッファ（出力バッファ、制御バッファ、又は共有バッファ）に、当該バッファのサイズ分のデータが格納されておらず、直下の演算の実行が終了しておらず、入力元が別のタスクの共有バッファではない場合、直下の演算の出力バッファを増量させると判定する。
演算実行部２２２は、バッファのサイズを増加させると判定すると、Ｓ１９０に処理を移し、バッファのサイズを増加させないと判定すると、Ｓ２３０に処理を移す。
【００７９】
演算実行部２２２は、Ｓ１８０において増加すると判定されたバッファについて、バッファ管理部２２１にバッファの増加を依頼し、バッファ管理部２２１から、当該依頼に対応する結果を示す情報を取得する（Ｓ１９０）。依頼に対応する結果を示す情報は、図５のＳ７０に対応する増加不可を示す情報、又は図５のＳ６０に対応するバッファ情報のいずれかである。
【００８０】
続いて、演算実行部２２２は、バッファの増加を依頼した結果、選択した演算に割り当てられている制御バッファが増加したか否かを判定する（Ｓ２００）。バッファ管理部２２１は、制御バッファが増加したと判定すると、Ｓ１６０に処理を移し、選択した演算の実行を行わせる。
【００８１】
Ｓ２１０において、演算実行部２２２は、バッファの増加を依頼した結果、選択した演算に対応する共有バッファ、又は選択した演算の直下の演算に割り当てられている出力バッファのいずれかが増加したか否かを判定する。演算実行部２２２は、共有バッファ又は出力バッファが増加したと判定すると、Ｓ２５０に処理を移し、共有バッファ及び出力バッファが増加していないと判定すると、Ｓ２２０に処理を移す。
演算実行部２２２は、実行対象の演算を直上の演算に移行させ、その後、Ｓ１３０に処理を移す（Ｓ２２０）。
【００８２】
Ｓ２３０において、演算実行部２２２は、選択した演算を終了させるか否かを判定する。具体的には、演算実行部２２２は、選択した演算がデータを取得できず、制御バッファからデータを取得できない場合に、選択した演算を終了させると判定する。ここで、選択した演算がデータを取得できない場合とは、データの取得元となる直下の演算が終了しているとともに直下の演算に割り当てられている出力バッファが空である場合、又はデータの取得元がデータベース３１であるとともに、データベース３１から読み込んでいないデータが存在しない場合のいずれかである。演算実行部２２２は、選択した演算を終了させると判定すると、Ｓ２４０に処理を移し、選択した演算を終了させないと判定すると、Ｓ２５０に処理を移す。
【００８３】
Ｓ２４０において、演算実行部２２２は、最上位の演算、すなわち、Ｏｕｔｐｕｔ演算が終了したか否かを判定する。演算実行部２２２は、最上位の演算が終了したと判定すると、本フローチャートに係る処理を終了し、最上位の演算が終了していないと判定すると、Ｓ２５０に処理を移す。
【００８４】
なお、演算実行部２２２は、選択した演算の直下の演算の処理が完了している場合には、選択した演算の処理が完了したと判定し、選択した演算の処理が完了した旨を示す処理完了フラグをバッファ管理部２２１に通知する。また、演算実行部２２２は、選択した演算に制御バッファが割り当てられている場合において、選択した演算の直下の演算の処理が完了しているとともに制御バッファが空である場合には、制御バッファの利用が完了した旨を示す格納完了フラグをバッファ管理部２２１に通知する。また、演算実行部２２２は、選択した演算がＳｃａｎ演算であり、データベース３１から読み込んでいないデータが存在しない場合には、Ｓｃａｎ演算の処理が完了したと判定し、完了した旨を示す処理完了フラグをバッファ管理部２２１に通知する。
【００８５】
Ｓ２５０において、演算実行部２２２は、直上の演算に移行可能か否かを判定する。演算実行部２２２は、以下の第１条件から第３条件の少なくともいずれかを満たす場合、直上の演算に移行可能と判定する。第１条件は、選択した演算がＥｘｃｈａｎｇｅ演算であることである。第２条件は、選択した演算に割り当てられている出力バッファに格納されているデータのサイズが当該バッファのサイズの上限であることである。第３条件は、直下の演算が終了しているとともに、直下の演算に割り当てられている出力バッファが空であることである。演算実行部２２２は、直上の演算に移行可能と判定すると、Ｓ２２０に処理を移し、実行対象の演算を直上の演算に移行させる。また、演算実行部２２２は、直上の演算に移行可能ではないと判定すると、Ｓ２６０に処理を移し、実行対象の演算を直下の演算に移行させる。
【００８６】
［本実施形態における効果］
以上のとおり、本実施形態に係るクエリ処理システムＳでは、第１クエリ処理装置１が、取得したクエリに基づいて複数の第２クエリ処理装置２のそれぞれに実行させる複数の演算を特定し、当該演算の実行を指示する演算指示情報を含む実行計画情報を生成し、複数の第２クエリ処理装置２のそれぞれが、第２クエリ処理装置２において実行される複数の演算のそれぞれにバッファを割り当て、実行計画情報に含まれる演算指示情報に基づいて、複数の演算のそれぞれを、当該演算に割り当てられたバッファ上で実行し、当該バッファの利用状況に基づいて複数の演算のそれぞれに割り当てられているバッファの量を動的に更新する。
【００８７】
このようにすることで、クエリ処理システムＳは、第２クエリ処理装置２が演算に割り当てられるメモリの量を動的に変更することにより、大規模データを対象とするクエリ処理を高速かつ確実に実行することができる。また、クエリ処理システムＳは、タスクのそれぞれに割り当てるバッファのサイズの比率を変えることにより、分散処理の並列性を向上させて、クエリ処理を高速に実行することができる。
【００８８】
また、第２クエリ処理装置２は、演算に対して割り当てられているバッファの利用状況に基づいて、最上位の演算から順に要求駆動方式に従った演算を実行し、実行中の演算において新たにバッファを利用する場合に、当該演算の下位の演算を特定し、当該下位の演算に割り当てられているバッファの利用状況に基づいて、当該下位の演算に割り当てられているバッファの空き領域を解放するとともに、当該実行中の演算に対して当該バッファの空き領域を新たに割り当てる。このようにすることで、第２クエリ処理装置２は、演算の切替を最小限にすることができる。また、第２クエリ処理装置２は、バッファの再利用を行うことにより、データストレージ２１２の利用を最小限にして、クエリの実行を高速化することができる。
【００８９】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更又は改良を加えることが可能であることが当業者に明らかである。例えば、上述の複数の実施形態を組み合わせてもよい。また、特に、装置の分散・統合の具体的な実施形態は以上に図示するものに限られず、その全部又は一部について、種々の付加等に応じて、又は、機能負荷に応じて、任意の単位で機能的又は物理的に分散・統合して構成することができる。例えば、第１クエリ処理装置１が、バッファ情報を生成することとしたが、これに限らず、バッファ情報を生成するサーバが別途設けられていてもよい。また、本実施形態では、仮想データベースシステムＶＤＳにおいて、クエリ処理システムＳが、記憶装置３に記憶されているデータベース３１からデータを取得して演算を実行し、当該クエリに対応する実行結果をユーザ端末４に出力したが、クエリ処理システムＳを、一般的な分散データベースに適用してもよい。この場合、第２クエリ処理装置２のデータストレージ２１２に、処理対象のデータベース３１が含まれていてもよい。
【符号の説明】
【００９０】
１・・・第１クエリ処理装置、１１・・・記憶部、１２・・・制御部、１２１・・・クエリ取得部、１２２・・・クエリ計画部、１２３・・・出力部、２・・・第２クエリ処理装置、２１・・・記憶部、２２・・・制御部、２２１・・・バッファ管理部、２２２・・・演算実行部、３・・・記憶装置、３１・・・データベース、４・・・ユーザ端末、Ｓ・・・クエリ処理システム、ＶＤＳ・・・仮想データベースシステム
【図１】
2018101280.tif 000003
【図２】
2018101280.tif 000004
【図３】
2018101280.tif 000005
【図４】
2018101280.tif 000006
【図５】
2018101280.tif 000007
【図６】
2018101280.tif 000008