JP3668243B2 - データベース管理システム - Google Patents

Description

本発明は、デ−タベ−ス管理システムに関し、特に、リレ−ショナルデ−タベ−ス管理システムに適した問合せの並列処理に好適なデ−タベ−ス管理システムに関する。

デ−タベ−ス管理システム（以下ＤＢＭＳと略記）、特に、リレ−ショナルＤＢＭＳは、非手続き的な言語で表現された問合せを処理し、内部処理手順を決定し、内部処理手順に従って実行する。このデータベース言語としては、ＳＱＬが用いられる（Database Language SQL ISO 9075:1989）。従来の問合せ処理の主な方法には、予め設定した規則に基づいて単一の内部処理手順を決定するものと、各種統計情報を用いて選定された複数の候補処理手順から、コスト評価により、最適と思われるものを決定するものとがある。前者は、処理手順作成のための負荷は小さいけれども、一律に設定された規則の妥当性に問題があり、選ばれた内部処理手順の最適性にも問題がある。後者は、各種統計情報の管理し、複数の候補処理手順の作成し、それらのコスト評価のための負荷を算出して最適な処理手順を与える。上記両者の組合せ技術としては、例えば、Satoh,K.,et.al."Local and Global Optimization Mechanisms for Relational Database", Proc. VLDB, 1985.がある（非特許文献１）。該従来技術では、問い合わせの条件からデータ量を推定して処理手順を決めている。

また、多くのＤＢＭＳは、問合せ解析処理と問合せ実行処理との２フェーズの処理を経て、問合せ処理が実現される。ホスト言語（ＣＯＢＯＬ、ＰＬ／Ｉ等）に問合せ言語を組み込む場合、当アプリケ−ションプログラム実行前に予め問合せを問合せ解析処理し、実行形式である１つの内部処理手順を作成している。この問合せ表現では、多くの場合、検索条件式にはホスト言語の変数が記述される。この変数に定数が代入されるのは、既に問合せ解析処理された結果の内部処理手順の実行時、すなわち、問合せ実行時である。この場合の問題点としては、変数に代入される値に従って複数の最適な処理手順が考えられることである。この問題を解決するために、問合せ実行処理時に複数の処理手順を作成しておき、問合せ実行時に変数に代入された値に従って処理手順を選択するものがある。コードの技術に関するものとしては、特開平１−１９４０２８号公報（特許文献１）、および、Graefe,G.,et.al."Dynamic Query Evaluation Plans", Proc. ACM-SIGMOD, 1989.（非特許文献２）に記載されている技術がある。

さらに、ＣＰＵ性能、ディスク容量の延びを上回るような、トランザクション量の増大、データベース量の増大に対応して、スケーラブルな並列データベースシステムの提供がユーザから望まれている。データベースシステムに対するユーザの性能要件として、数万を超える同時実行ユーザ数への対応、テラバイト単位の検索トランザクションの出現、表サイズに比例しない応答時間の保証がある。並列データベースシステムは、近年のハードウェアコストの低減と相まって、注目を浴びている。並列データベースシステムについては、DeWitt,D.,et.al.:"Parallel Database Systems: The Future of High Performance Database Systems", CACM, Vol.35, No.6, 1992.（非特許文献３）に記載の技術がある。そのようなシステムでは、密結合あるいは疎結合にプロセッサを接続し、データベース処理を複数のプロセッサに静的／動的に処理を配分し、スケジュールする必要がある。並列度を増せば応答性能は向上するが、過度の並列度は逆にオーバヘッドの増大、他トランザクションの応答時間の延び等の影響がある。そのため、適度な並列度の設定が重要である。

デ−タベ−ス処理において、処理対象となるデ−タは、二次記憶装置上に存在し、各デ−タベ−ス演算に対して大量デ−タの読み出しおよび転送が必要となる。並列デ−タベ−スシステムにおいても、転送するデ−タが大量となる場合、デ−タ転送時間がデ−タベ−スシステムの性能ネックとなる。そこで、二次記憶装置からデ−タを転送する時間を有効活用する方法が考えられる。これは、デ−タの転送時間と当該デ−タに対するデ−タベ−ス処理に要する時間とをオ−バラップさせるものであり、従来技術として良く知られている。この方式は、相互結合ネットワークで接続されるプロセッサ群間のデータ転送にも適用可能である。

特開平１−１９４０２８号公報

Satoh,K.,et.al."Local and Global Optimization Mechanisms for Relational Database", Proc. VLDB, 1985. Graefe,G.,et.al."Dynamic Query Evaluation Plans", Proc. ACM-SIGMOD, 1989. DeWitt,D.,et.al.:"Parallel Database Systems: The Future of High Performance Database Systems", CACM, Vol.35, No.6, 1992.

上記従来技術において、問合せ最適化処理とは、ユ−ザが入力した問合せからデ−タベ−スシステムの各種統計情報を基にし、最も効率の良い処理手順をＤＢＭＳが自動判定するものである。さらに、問合せの選択条件式に変数が埋め込まれている場合には、複数の処理手順を問合せ解析時に展開しておき、問合せ実行時に当変数に代入される値に従って処理手順を選択することによって、最適な処理手順が選択される。

並列データベース処理では、各ノード（プロセッサあるいはプロセッサとディスク装置との対）へデータベース演算が分割され、各ノードで各データベース演算が並列にあるいはパイプライン的に動作する。上記従来技術によれば、この並列処理形態でも、各ノードで処理手順を選択する方法は適用可能である。

しかし、並列に動作する処理では、同時間にそれぞれのノードが並行処理をするが、各ノードで実行するデータベース演算に対応して各ノード数を決定できないという問題がある。すなわち、ノード数を決定する基準が明確でないために、過度の並列化は逆にオーバヘッドの増大等の影響があり、最適に負荷分散することが困難である。

また、パイプライン動作させる処理では各ノードへデータベース演算が分割格納されるが、データの分割にバラツキが存在する場合、各ノードへの均等分割方法が明確でない。

さらに、処理時間の制約があったときなどのように、その時間内で複数の処理を行う場合において、各ノードで実行する各データベース演算をパラメータ化し、期待する処理時間に基づいて時間調整（チューニング）をする方法も明確でない。

本発明の目的は、問合せ処理を高速化する問い合わせ処理方法およびデータベースシステムを提供することにある。

本発明は、上記課題を解決するために、第１のデータベースを分散格納する複数の第１の分配処理部と、第２のデータベースを分散格納する複数の第２の分配処理部と、データのマージ処理を行う複数の結合処理部と、入力された問合せに対するマージ処理を実行する結合処理部を決定する決定処理部と、を有し、前記決定処理部は、処理時間と結合処理部数との対応関係を用いて、前記第１の分配処理部および第２の分配処理部における処理時間に対応する結合処理部数を特定し、前記問合せに対するマージ処理を実行する前記特定した結合処理部数の結合処理部を決定する手段と、前記第１のデータベースおよび第２のデータベースのデータを均等に分割するための結合キーの最適化情報に従い、前記問合せに対するマージ処理を実行する前記特定した結合処理部数の結合処理部各々に割り当てる結合キーの分割範囲が記述されたデータ分配情報を、前記第１の分配処理部および第２の分配処理部に設定する手段と、前記問合せに対するマージ処理を実行する前記特定した結合処理部数の結合処理部各々から受け取ったデータを出力する手段と、を有し、前記第１の分配処理部および第２の分配処理部各々は、自処理部に分散格納されたデータベースからデータを取り出し、該データを、自処理部に設定されているデータ分配情報において当該データの結合キーが属する分割範囲に割り当てられた結合処理部へ分配する手段を有し、前記結合処理部は、前記第１の分配処理部および前記第２の分配処理部から分配された同じ結合キーを持つデータをマージ処理し、その結果を前記決定処理部に出力する手段を有する。

また、本発明は、第１のデータベースを分散格納する複数の第１の分配処理部と、第２のデータベースを分散格納する複数の第２の分配処理部と、データのマージ処理を行う複数の結合処理部と、入力された問合せに対するマージ処理を実行する結合処理部を決定する決定処理部と、を有し、前記決定処理部は、処理時間と結合処理部数との対応関係を用いて、前記第１の分配処理部および第２の分配処理部における処理時間に対応する結合処理部数を特定し、前記問合せに対するマージ処理を実行する前記特定した結合処理部数の結合処理部を決定する手段と、前記問合せに対するマージ処理を実行する前記特定した結合処理部数の結合処理部各々に割当てる、前記第１のデータベースおよび第２のデータベースのデータの結合キーに対するハッシュ値が記述されたデータ分配情報を、前記第１の分配処理部および第２の分配処理部に設定する手段と、前記問合せに対するマージ処理を実行する前記特定した結合処理部数の結合処理部各々から受け取ったデータを出力する手段と、を有し、前記第１の分配処理部および第２の分配処理部各々は、自処理部に分散格納されたデータベースからデータを取り出し、該データを、自処理部に設定されているデータ分配情報において当該データの結合キーに対するハッシュ値に割り当てられた結合処理部へ分配する手段を有し、前記結合処理部は、前記第１の分配処理部および前記第２の分配処理部から分配された同じ結合キーを持つデータをマージ処理し、その結果を前記決定処理部に出力する手段を有する。

実行するデータベース演算に応じて結合処理部の数を決定し、各結合処理部へデータを均等に分割させ、各結合処理部で実行する処理時間を均等化させるので、各結合処理部間で処理時間の偏りがなく、高速な問い合わせ処理を実現することができる。

以下、本発明の実施例を図面に基づいて詳細に説明する。

図２は、本実施例のデ−タベ−スシステムの概念図を示している。図２において、デ−タベ−スシステムは、ユ−ザが作成した、複数のアプリケ−ションプログラム（以下、ＡＰと略記する）１０および１１と、問合せ処理やリソ−ス管理等デ−タベ−スシステム全体の管理を行うＤＢＭＳ２０と、デ−タベ−ス処理において、入出力処理対象となるデ−タの読書きを行い、計算機システム全体の管理を受け持つオペレ−ティングシステム（以下では、オペレ−ティングシステムをＯＳと略記する）３０と、デ−タベ−ス処理対象となるデ−タを格納するデ−タベ−ス４０と、データベースの定義情報を管理するディクショナリ５０とを有する。ＤＢＭＳ２０は、他のデータベース管理システムと接続されている。ディクショナリ５０には、本実施例において使用する結合カラムに関する最適化情報なども記憶されている。

上記ＤＢＭＳ２０は、システム全体の管理、制御に加えて、入出力の管理等を行うシステム制御部２１と、問い合わせに関する論理処理を行う論理処理部２２と、データベースの物理処理を実行する物理処理部２３と、当ＤＢＭＳ２０で処理対象となるデータを格納するデータベースバッファ２４とを備える。また、論理処理部２２は、問合せの構文解析、意味解析を行う問合せ解析２２０、適切な処理手順を生成する静的最適化処理２２１、処理手順に対応したコ−ドの生成を行なうコード生成２２２、静的最適化処理２２１で生成された処理手順候補から最適なものを選択する動的最適化処理２２３、および、当コードの解釈実行を行うコード解釈実行部２２４を備える。また、物理処理部２３は、アクセスしたデ−タの条件判定、編集、レコード追加等を実現するデ−タアクセス処理２３０、データベースレコ−ドの読み書きを制御するデ−タベ−スバッファ制御２３１、入出力対象となるデ−タの格納位置を管理するマッピング処理２３２、および、システムで共用するリソースの排他制御を実現する排他制御２３３を備える。

図３は、本発明が適用されるハードウェア構成の一例を示すものである。具体的には、図３は、プロセッサおよびディスク装置が１ノードを構成し、複数のノードを備える並列プロセッサシステムの適用構成例を示している。図３において、プロセッサ６０〜６５およびディスク装置７０〜７５が相互結合ネットワーク８０で接続される。図３に示すハードウェア構成は、図２に示すデータベースシステムを複数のプロセッサで並列処理するための構成であり、各ノードに対してそれぞれ処理が分散される。

上記各ノードごとに機能分散した場合の構成を図１に示す。図１は、本実施例が適用されたデ−タベ−スシステムの概要図を示している。以下に、並列データベースシステムの処理例を図１を参照して説明する。この例では、データベースに対する検索要求に並列処理を適用する。図１において、各ノードは、データを取り出して分配処理するソート機能と、複数のノードでそれぞれソートされたデータを結合処理するマージ機能とが各ノードごとに割り当てられている。ノードによりソート機能だけを備えるものや、ソート機能とマージ機能とを備えるものがある。デ−タベ−スは、ユ−ザから２次元のテ−ブル形式で見られる表から成るものとし、当該表は行あるいはロウごとにデータが存在するものである。また、ロウは、１つ以上の属性（これを「カラム」という）からなる。図１においては、データベースの表としてＴ１およびＴ２があり、ノード１（９０）からノード４（９１）に表Ｔ１が、ノード５（９２）からノード８（９３）に表Ｔ２が各々格納されており、これらの各ノードが分配ノードであり、分配ノードにおいて格納している表に基づいてデータ取り出し処理およびデータ分配処理が実行される。また、ノード９（９４）からノード１１（９６）は、結合ノードであり、ノード１〜４およびノード５〜８から出力されるデータを受け取り、部分列ソート処理およびマージ処理をして完全列の作成を実行する。さらに、ノード１２（９７）は、問い合わせを受け付け、該問い合わせを解析し、問い合わせに対する処理を実行する分配ノードおよび結合ノードの数を決定する決定ノードである。また、ノード１２（９７）は、ノード９〜１１から出力されたデータを受け取り出力する。これらのノード群は、相互結合ネットワーク８０で接続され、ノード１〜４およびノード５〜８と、ノード９〜１１とが並列に動作し、しかもノード１〜４およびノード５〜８でそれぞれ処理された結果は、すぐにノード９〜１１で処理を行うというようなパイプライン的に動作する（以下、並列パイプライン動作と呼ぶ）。また、ノード９〜１１とノード１２とも同様にパイプライン動作する。以下では、ノード９〜１１における部分列ソート処理をスロットソート処理といい、完全列作成処理をＮウェイマージ処理と呼ぶ。スロットソート処理は、データが格納されるページを対象とするページ内のソート処理を指し、スロット順に読みだせば昇順にロウがアクセス可能とする。Ｎウェイマージ処理は、Ｎウェイのバッファを用いて、各マージ段でＮ本のソート連を入力にして最終的に１本のソート連を作成する。

データベース検索処理のための問合せは、例えば、以下のようになる。

ＳＥＬＥＣＴ Ｔ１．Ｃ３，Ｔ２．Ｃ３
ＦＲＯＭ Ｔ１，Ｔ２
ＷＨＥＲＥ Ｔ１．Ｃ１＝Ｔ２．Ｃ１
ＡＮＤ Ｔ１．Ｃ２＝？
このような問い合わせが、ノード１２において受け付けられると、ノード１２において、最適な分配処理方法が選択され、各ノードに対してネットワークを介して指示される。上記の問い合わせにおいては、ノード１（９０）からノード４（９１）に表Ｔ１が、ノード５（９２）からノード８（９３）に表Ｔ２が各々格納されているので、各ノードにおいてデータ取り出し処理およびデータ分配処理が実行される。また、ノード９（９４）からノード１１（９６）では、ノード１〜４およびノード５〜８から出力されるデータを逐次受け取り、ソート処理および結合処理を実行する。ノード１２（９７）では、ノード９〜１１から出力されたデータを受け取り出力する。これによりデータベース検索は終了する。

つぎに、上記各ノードの処理時間の関係について図４を参照して説明する。図４は、並列パイプライン動作を説明するための概要図を示す。図４において、１００および１０１は、図１におけるノード１（９０）からノード４（９１）と、ノード５（９２）からノード８（９３）とにおける処理に対応し、データ取り出し処理およびデータ配分処理を実行する。１１０および１１１は、ノード９（９４）からノード１１（９６）における処理に対応し、スロットソート処理、Ｎウェイマージ処理、突き合わせ処理が実行される。１２０は、ノード１２（９７）における処理に対応し、要求データ出力処理が実行される。時間軸に沿えば、データ取り出し処理およびデータ配分処理１００および１０１で処理されたデータは、逐次スロットソート処理１１０および１１１に移り、パイプライン的に実行される。データ取り出し処理からスロットソート処理までを取り出しフェーズと呼ぶ。また、Ｎウェイマージ処理１１０および１１１は、それぞれのノードで単に並列に実行される。このＮウェイマージ処理期間をマージフェーズと呼ぶ。さらに、突き合わせ処理の結果は要求データ出力処理１２０に逐次転送されてパイプライン的に実行される。この突き合わせから要求データ出力までを結合フェーズと呼ぶ。図４に示すタイムチャートは、図１に示す問合せ例を適用した場合の処理内容である。取り出しフェーズにおいて、ノード１（９０）からノード４（９１）における処理時間は、Ｔ１データ取り出し／データ分配処理時間１３０として示す。また、ノード５（９２）からノード８（９３）における処理時間は、Ｔ２データ取り出し／データ分配処理時間１３１で示し、相互結合ネットワーク８０における転送時間をデータ分配転送時間１４０で示し、ノード９（９４）からノード１１（９６）における処理時間は、Ｔ１／Ｔ２スロットソート処理時間１５０に示すように、各々実行される。図４において、取り出しフェーズは、スロットソート処理完了待ち合わせ１８０の時点までで終了する。また、マージフェーズにおいて、ノード９（９４）からノード１１（９６）における処理時間は、Ｔ１／Ｔ２Ｎウェイマージ処理時間１５１に示す時間において実行される。このマージフェーズは、Ｔ１／Ｔ２Ｎウェイマージ処理待ち合わせ１８１までで終了する。結合フェーズは、ノード９（９４）からノード１１（９６）における処理時間は、突き合わせ処理時間１５２で示し、相互結合ネットワーク８０における処理時間は、結合結果転送時間１６０で示し、ノード１２（９７）における処理時間は、要求データ出力処理時間１７０で示し、各々その時間内に実行される。

つぎに、図１におけるノード１２の各ノード群への処理の振り分け方法について図５を参照して説明する。図５は、データ分配処理における各ノード群への振り分け方法を示す説明図である。前提として、データ取り出し／データ分配処理をするノード群は、プロセッサ２００〜２３０とディスク装置２０１〜２３１とを備えるノード１〜１０の１０台からなる。また、結合処理をするノード群は、プロセッサ２４０〜２５０とディスク装置２４１〜２５１とを備えるノード１１〜１５の５台からなるとする。ディクショナリ５０には、結合カラムに関する最適化情報５１が格納されていている。該最適化情報５１とは、データベースのデータを均等に分割するための情報であり、例えば、結合カラムに対するデータ件数は通常均一でないので、データ件数が均一になるように結合カラムで分割するようにするものである。図５に示すように、ノード１〜１０に格納されているデータが、ｖ１からｖ１０の各分割範囲で均等にデータ分割可能であることを示す。この場合、ノード１１〜１５に均等にデータ分割するためにはｖ１〜ｖ２、ｖ３〜ｖ４、ｖ５〜ｖ６、ｖ７〜ｖ８、ｖ９〜ｖ１０の５区間にそれぞれノード番号１１、１２、１３、１４、１５を対応付けるような分配処理手段を備えればよい。上記最適化情報が存在しない場合、適当なハッシュ関数を設定してデータ分配を行なえばよい。このようにして、図１におけるノード１２では、分配処理手段を備えることにより、Ｎウェイマージ処理を行う際の各ノード群への処理の振り分けを行う。これにより、上記のような場合には、ノード１１〜１５に均等にデータ分割することができ、処理時間が均等になる。

つぎに、Ｎウェイマージ処理を行う際の結合ノード数の決定方法について図６を参照して説明する。図６は、結合ノード数決定方法を説明するための概要図を示している。

図１における並列結合処理の各フェーズ、各処理の処理時間をグラフ化し、図４に示す並列パイプライン動作概要に合わせてレイアウトしている。図６において、データ取り出し／データ分配処理が、ノード１〜８で実行され、３００〜３０５の処理時間がそれぞれかかるものとする。ここでは、ノード５の処理時間３０４が最大処理時間であるとする。スロットソート処理時間は、結合処理ノード数Ｎと、予め決められたシステム特性（ＣＰＵ性能、ディスク装置性能等）と、データベース演算方法とから導けることができ、スロットソート処理の性能特性は一般的に下記に示すような式で求めることができる。

パイプライン処理を行う際の効果を最大にするために、スロットソート処理の性能特性と最大処理時間３０４との交点となる結合ノード割当て数３５０をノード数として求めることができる。結合ノード割当て数３５０が決まると、Ｎウェイマージ処理時間３２０および突き合わせ処理時間３３０が、Ｎウェイマージ処理の性能特性と突き合わせ処理の性能特性とから同様に推定できる。これらの処理時間の合計が問い合わせに対する全体の処理時間となる。このように結合ノード数を決定し、データ取り出し／データ分配処理において分配されたデータを逐次マージして同時に処理することにより、全体の処理時間（問い合わせをしてから出力されるまでの応答時間）を短縮することができる。

結合ノード数を決定する場合に用いられる性能特性の具体例を以下に示しておく。例えば、ロウ数が表Ｔ１および表Ｔ２とも１０、０００、０００件あり、条件数がＴ１−１コ（全体ロウが１％に絞られる）とし、データ取り出し／データ分配処理をする分配ノード数が表Ｔ１および表Ｔ２ともそれぞれ１６ノードで均等分割され、結合ノード数が８ノードで、プロセッサ性能が５０ＭＩＰＳ（１秒間に５千万命令実行）で、ネットワーク転送レートが２０Ｍバイト／秒であるとする。このような条件で実際のデータベース管理システムに処理させた結果もしくは性能モデルから算出した結果が以下のようになる。

表Ｔ１および表Ｔ２の分配ノードの処理時間がそれぞれ１８０秒、Ｔ１／Ｔ２スロットソート処理時間が８０秒、Ｎウェイマージ処理時間が３８０秒、突き合わせ処理時間が１１０秒、要求データ出力時間が１０秒となる。これらの結果の処理性能に基づいて問い合わせに対する処理時間を推定する。

つぎに、図６に示した結合ノード数決定方法を基にして、応答時間をさらに短縮するための処理時間調整方法（チューニング方法）について、図７、図８および図９を参照して説明する。以下に示す方法は、上記ノード１２の分配処理手段において、各ノード群への処理の振り分けを決定する際にあらかじめ算出されて、その結果より振り分けを決定するものである。

図７は、スロットソート前処理化の概要図を示す。データ取り出し／データ分配処理が、ノード１〜８で実行され、各３００〜３０５の処理時間がそれぞれかかるものとする。ノードごとの処理時間には各表のデータ数によりバラツキが存在する。また、スロットソート処理は、結合処理ノード群で実行されるように設定されている。ノードごとの処理時間でバラツキがある場合には、データ取り出し／データ分配処理ノード群へスロットソート処理を移す処理手順を考える。図７に、スロットソートの前処理化として示すように、データ取り出し／データ分配処理がより早く終了したノードでスロットソート処理を行う。その処理によれば、結合ノード割当て数３５０のノードにおけるスロットソート処理時間が３１０から３１２に削減できる。その処理時間の差３１１においてＮウェイマージ処理を移す。これは、スロットソート処理の連長を延ばすことにほかならない。これによって、Ｎウェイマージ処理時間が削減でき、結果的に応答時間が削減できる。

図８は、スロットソート連長チューニング概要図を示している。例えば処理時間の制約があったときなどのように、その時間内で複数の処理を行う場合において、各ノードで実行する各データベース演算をパラメータ化し、期待する処理時間に基づいて時間調整（チューニング）をする方法について説明する。図６で求まる結合ノード割当て数３５０から最小限だけ結合処理ノードを増やし、応答時間の短縮を図る。この場合の結合ノード割当て数を３５１とする。結合ノード割当て数３５１とすると、スロットソート処理時間は３１０から３１２へ削減される。パイプライン効果を最大にするため、処理時間３１１においてＮウェイマージ処理をスロットソート処理へ移す。これによって、Ｎウェイマージ処理のマージ回数が減り、処理時間が３２０と削減でき、結果的に応答時間が削減できる。

図９は、Ｎウェイマージ回数チューニングの概要図を示す。結合ノード割当て数３５０で決まる突き合わせ処理時間３３０が要求データ出力処理時間３４０より小である場合には、Ｎウェイマージ処理の最終段のマージ処理を突き合わせ処理に移すようにできる。Ｎウェイマージ処理の最終段のマージ処理時間３３１と突き合わせ処理時間３３０との和が要求データ出力処理時間３４０を上回らなければ、当最終段のマージ処理を突き合わせ処理へ移す。これによって、応答時間が削減できる。

つぎに、本実施例におけるデータベース管理システムの動作フローを説明する。図１０、図１１、図１２、図１３、図１４および図１５は、本実施例におけるＤＢＭＳの処理のフロ−チャ−トを示す。図１０において、ＤＢＭＳは、問合せ実行前に行われる問合せの解析処理（ステップ２２０）、静的最適化処理（ステップ２２１）およびコード生成（ステップ２２２）により問い合わせ解析を行う問合せ解析処理４００と、変数に定数を代入し、処理手順を選択する動的最適化処理（ステップ２２３）および問合せのコード解釈実行（ステップ２２４）により問い合わせに対する実行処理を行う問合せ実行処理４１０とを行う。

以下、各処理部の概要について述べる。

（ａ）問合せ解析処理４００
図１０（ａ）および（ｃ）において、問合せ解析（ステップ２２０）では、上記ノード１２においてアプリケーションプログラムにより入力された問合せ文の構文解析、意味解析を実行する（ステップ２２００）。図１０（ａ）において静的最適化処理（ステップ２２１）では、上記ノード１２において問合せで出現する条件式から条件を満足するデ−タの割合を推定し、予め設定している規則を基に、有効なアクセスパス候補（特にインデクスを選出する）を作成し、処理手順の候補を作成する。コード生成（ステップ２２２）では、上記ノード１２において処理手順候補を実行形式に展開する。

（ｂ）問合せ実行処理４１０
図１０（ｂ）において、動的実行時最適化（ステップ２２３）では、上記ノード１２において代入された定数に基づき、各ノード群で実行する処理手順を決定する。コード解釈実行（ステップ２２４）では、それぞれのノードにおいて処理手順を解釈し、実行する。

つぎに、各処理部の詳細な処理フローの説明を行う。

図１０（ｄ）において、動的最適化処理（ステップ２２１）では、問合せに出現する条件式の述語選択率推定し（ステップ２２１０）、インデクス等からなるアクセスパスの剪定をし（ステップ２２１１）、これらアクセスパスを組合せた処理手順候補の生成をする（ステップ２２１２）。

図１０（ｅ）において、述語選択率推定（ステップ２２１０）では、問合せ条件式に変数が出現するか否かチェックする（ステップ２２１０１）。変数が出現すれば、当条件式にカラム値分布情報があるかチェックする（ステップ２２１０４）。存在すれば終了する。存在しなければ、条件式の種別に応じてディフォルト値を設定し（ステップ２２１０５）、終了する。変数が出現しなければ、当条件式にカラム値分布情報があるかチェックする（ステップ２２１０４）。存在しなければ、条件式の種別に応じてディフォルト値を設定し（ステップ２２１０５）、終了する。存在すれば、カラム値分布情報を用いて選択率を算出する（ステップ２２１０３）。

図１１において、アクセスパス剪定２２１２では、問合せ条件式で出現するカラムのインデクスをアクセスパス候補として登録する（ステップ２２１２０）。つぎに、問合せでアクセス対象となる表が複数ノードに分割格納されているかチェックする（ステップ２２１２１）。分割格納されていれば、パラレルテーブルスキャンをアクセスパス候補として登録する（ステップ２２１２３）。分割格納されていなければ、テ−ブルスキャンをアクセスパス候補として登録する（ステップ２２１２３）。各条件式の選択率が既に設定済みか否かチェックする（ステップ２２１２４）。設定済みであれば、各表に関して選択率が最小となる条件式のインデクスをアクセスパスの最優先度とする（ステップ２２１２５）。設定済みでなければ、各条件式の選択率の最大値／最小値を取得する（ステップ２２１２６）。最後に、ＣＰＵ性能、ＩＯ性能等のシステム特性より各アクセスパスの選択基準を算出し（ステップ２２１２７）、単一あるいは複数のインデクスを組合せたアクセスパスでの選択率が上記選択基準を下回るものだけアクセスパス候補として登録する（ステップ２２１２８）。

図１２において、処理手順候補生成２２１３は、問合せでアクセス対象となる表が複数ノードに分割格納されているかチェックする（ステップ２２１３０）。分割格納されていれば、ステップ２２１３５へ移行する。分割格納されていなければ、処理手順候補にソート処理が含まれているか否かをチェックする（ステップ２２１３１）。含まれていれば、ステップ２２１３５へ移行する。含まれていなければ、問合せでアクセス対象となる表のアクセスパスが唯一であるかチェックし（ステップ２２１３２）、唯一であれば単一の処理手順を作成し（ステップ２２１３３）、唯一でなければ複数の処理手順を作成し（ステップ２２１３４）、終了する。ステップ２２１３５では、結合可能な２ウェイ結合へ問合せを分解する。分割格納される表の格納ノード群に対応して、データ読みだし／データ分配処理手順を候補として登録する。また、スロットソート処理手順を候補として登録する（ステップ２２１３６）。結合処理ノード群に対応して、スロットソート処理手順、Ｎウェイマージ処理手順および突き合わせ処理手順を候補として登録し、スロットソート連長およびマージ処理回数をパラメタ化しておく（ステップ２２１３７）。要求データ出力ノードに要求データ出力処理手順を登録する（ステップ２２１３８）。最後に、分解結果に対して評価がすべて終了すれば（ステップ２２１３９）、終了する。

図１３において、コード生成２２２は、処理手順候補が唯一か否かをチェックする（ステップ２２２０）。唯一であれば、ステップ２２２３へ移行する。唯一でなければ、カラム値分布情報等からなる最適化情報を処理手順に埋込み（ステップ２２２１）、問合せ実行時に代入された定数に基づいて処理手順を選択するデータ構造を作成する（ステップ２２２２）。最後に、処理手順を実行形式へ展開する（ステップ２２２３）。

図１４において、動的最適化処理２２３は、作成されている処理手順が単一か否かをチェックする（ステップ２２３００）。単一であれば、終了する。単一でなければ、代入された定数を基に選択率を算出する（ステップ２２３０１）。処理手順候補に並列な処理手順が含まれるか否かチェックする（ステップ２２３０２）。含まれていなければ、アクセスパスの選択基準に従って処理手順を選択し（ステップ２２３１３）、終了する。含まれていれば、ディクショナリから最適化情報（結合カラムのカラム値分布情報、アクセス対象となる表のロウ数、ページ数等）を入力し（ステップ２２３０３）、データ取り出し／データ分配のための処理時間を各システム特性を考慮し、前述したように算出する（ステップ２２３０４）。当処理時間から結合処理に割当てるノード数ｐを決定し、当処理手順ａ１を決定する（ステップ２２３０５）。データ取り出し／データ分配処理時間にバラツキがあるか否かをチェックする（ステップ２２３０６）。バラツキがあれば、データ取り出し／データ分配処理ノード群でスロットソート処理を実行する処理手順ａ２を設定する（ステップ２２３０７）。つぎに、結合ノード割当て数ｐをα台だけ増した処理手順ａ３を設定する（ステップ２２３０８）。要求データ処理時間が突き合わせ処理時間と１回分のＮウェイマージ処理時間との和より大であれば（ステップ２２３０９）、突き合わせ処理へ１回分のＮウェイマージ処理を移した処理手順ａ４を設定する（ステップ２２３１０）。処理手順ａ１〜ａ４で最適な処理手順を応答時間最小、各ノード負荷量最小、他トランザクション応答性能への影響小等の観点で選択する（ステップ２２３１１）。データ分配情報を最適化情報を基にして作成する（ステップ２２３１２）。最適化情報がなければ、ハッシュ関数の結合カラム評価値に従い、データ分配情報を作成する。アクセスパスの選択基準に従って処理手順を選択し（ステップ２２３１３）、終了する。

図１５において、コード解釈実行処理２２４では、設定された各ノードにおいてそれぞれ対応する処理手順にしたがって処理を行う。

まず、各ノードでは、データ取り出し／データ分配処理が設定されているか否かを判断する（ステップ２２４００）。データ取り出し／データ分配処理が設定されていれば、各ノードの記憶装置に格納されているデータベースにアクセスし、条件式を評価する（ステップ２２４０１）。最適化情報を基に作成されたデータ分配情報に基づいて、データを取り出し、各結合ノードのバッファへ逐次データを分配する（ステップ２２４０２）。各結合ノードのバッファが満杯か否かを判定し、満杯であれば、ページ形式で対応する結合ノードへ転送する。問い合わせに対応する全てのデータを取り出して分配すると処理が終了する（ステップ２２４０４）。

また、各ノードでは、スロットソート処理が設定されているか否かを判断する（ステップ２２４０５）。スロットソート処理が設定されていれば、前記データ取り出し／データ分配処理ノードからのページ形式のデータを受信し、（ステップ２２４０６）受信したデータについて順次スロットソート処理を行う（ステップ２２４０７）。処理したスロットソート結果を一時保存しておき、スロットソート処理を終了する（ステップ２２４０８）。

また、Ｎウェイマージ処理が設定されているか否かを判断する（ステップ２２４０９）。Ｎウェイマージ処理が設定されていれば、スロットソート結果に基づいてＮウェイマージ処理を実行し（ステップ２２４１０）、Ｎウェイマージ処理結果をバッファなどに一時保存し（ステップ２２４１１）、Ｎウェイマージ処理を終了する。

また、突き合わせ処理が設定されているか否かを判断する（ステップ２２４１２）。突き合わせ処理が設定されていれば、Ｎウェイマージ処理結果のソートリストを突き合わせ、出力用バッファにデータを設定する（ステップ２２４１３）。出力用バッファが満杯の場合には、ページ形式で要求データ出力ノードへ転送する（ステップ２２４１５）。

また、要求データ出力処理が設定されているか否かを判断する（ステップ２２４１６）。要求データ出力処理が設定されていれば、結合ノードからページ形式のデータの転送があるかないかを判断する（ステップ２２４１７）。ページ形式のデータの転送がある場合には、該ページ形式のデータを受信し（ステップ２２４１８）、アプリケーションプログラムへ問い合わせ処理結果を出力し、ページ形式のデータ転送がない場合にはそのまま問い合わせ処理結果を出力する（ステップ２２４１９）。

また、上記コード解釈実行処理において、処理時間にバラツキがある場合などのときにデータ取り出し／データ分配処理ノード群でスロットソート処理を実行する場合には、データ取り出し／データ分配処理終了後、コード解釈実行処理２２４を再度実行し、スロットソート処理を行うようにする。

さらに、ステップ２２４１３でＮウェイマージ処理結果が完全ソート列でなければ、最終段のマージと突き合わせ処理とを行う。

以上のように処理することによりデータベース管理システムの問い合わせ応答時間を短縮することができる。

図６に示す結合ノード割当て方法と、図７、図８および図９に示すチューニング方法とは、各々独立に適用してもよいし、また任意の組合せで適用してもよい。すなわち、動的最適化処理２２３では、すべての組合せが適用できる場合を想定している。さらに、データ取り出し処理においては、複数ディスク装置からなる並列入出力アクセス方法の適用と、一括入出力方法／先読み入出力方法の適用と、データ分配処理に最適化情報あるいはハッシュ関数によるデータ分配方法の適用と、Ｎウェイマージ処理に並列ソート方法の適用と、突き合わせ処理にノード間での突き合わせ処理方法の適用と、要求データ出力処理に複数のノードを割当て並列受け取り処理方法の適用等も考えられる。上記ステップ２２３０９およびステップ２２３１０では、１回分のＮウェイマージ処理を仮定しているが、一般的にｎ回（ｎ≧１）としてもよい。

図４に示す並列パイプライン動作に関して、上記図６に示した結合ノード割当て方法と、図７、図８および図９に示すチューニング方法とを適用すると、取り出しフェーズ、マージフェーズ、結合フェーズの内、マージフェーズが省略可能となる場合も存在する。すなわち、スロットソート連長の延び、Ｎウェイマージ処理の移動により可能となる。この場合、問合せ実行処理でもマージフェーズの処理を省略する。

本発明の問合せ処理方法は、統計情報を用いた規則とコスト評価との併用に限らず、適当なデ−タベ−ス参照特性情報を与える処理手順が得られるものであれば適用できる。例えば、コスト評価のみ、規則利用のみ、コスト評価と規則利用の併用等の最適化処理を行うＤＢＭＳにも適用できる。

本発明は、密結合／疎結合マルチプロセッサシステム大型計算機のソフトウェアシステムを介して実現することも、また、各処理部のために専用プロセッサが用意された密結合／疎結合複合プロセッサシステムを介して実現することも可能である。また、単一プロセッサシステムでも、各処理手順のために並列なプロセスを割当てていれば、適用可能である。

本実施例によれば、各ノードで実行するデータベース演算に対応して各ノード数を決定し、また、データの分割にバラツキが存在する場合、各ノードへデータを均等に分割させ、各ノードで実行する各データベース演算をパラメタ化し、期待する処理時間均等化させるので、各ノード間で処理時間の偏りがなく、円滑にパイプライン動作させることが可能となり、高速な問合せ処理が実現可能となる。

並列結合処理概要図 データベースシステムの構成図 ハードウェア構成図 並列パイプライン動作の概要図 データ分配処理概要図 結合ノード割当て概要図 スロットソート前処理化概要図 スロットソート連長チューニング概要図 Ｎウェイマージ回数チューニング概要図 データベース管理システムのフローチャート データベース管理システムのフローチャート データベース管理システムのフローチャート データベース管理システムのフローチャート データベース管理システムのフローチャート データベース管理システムのフローチャート

符号の説明

１０、１１…アプリケーションプログラム、２０…データベース管理システム、２２…論理処理部、２２０…問合せ解析、２２１…静的最適化処理、２２２…コード生成、２２３…動的最適化処理、２２４…コード解釈実行、３０…オペレーティングシステム、４０…データベース、５０…ディクショナリ、８０…相互結合ネットワーク、９０、９１、９２、９３、９４、９５、９６、９７…ノード。

Claims (2)

1. 第１のデータベースを分散格納する複数の第１の分配処理部と、
   第２のデータベースを分散格納する複数の第２の分配処理部と、
   データのマージ処理を行う複数の結合処理部と、
   入力された問合せに対するマージ処理を実行する結合処理部を決定する決定処理部と、を有し、
   前記決定処理部は、
   処理時間と結合処理部数との対応関係を用いて、前記第１の分配処理部および第２の分配処理部における処理時間に対応する結合処理部数を特定し、前記問合せに対するマージ処理を実行する前記特定した結合処理部数の結合処理部を決定する手段と、
   前記第１のデータベースおよび第２のデータベースのデータを均等に分割するための結合キーの最適化情報に従い、前記問合せに対するマージ処理を実行する前記特定した結合処理部数の結合処理部各々に割り当てる結合キーの分割範囲が記述されたデータ分配情報を、前記第１の分配処理部および第２の分配処理部に設定する手段と、
   前記問合せに対するマージ処理を実行する前記特定した結合処理部数の結合処理部各々から受け取ったデータを出力する手段と、を有し、
   前記第１の分配処理部および第２の分配処理部各々は、
   自処理部に分散格納されたデータベースからデータを取り出し、該データを、自処理部に設定されているデータ分配情報において当該データの結合キーが属する分割範囲に割り当てられた結合処理部へ分配する手段を有し、
   前記結合処理部は、
   前記第１の分配処理部および前記第２の分配処理部から分配された同じ結合キーを持つデータをマージ処理し、その結果を前記決定処理部に出力する手段を有すること
   を特徴とするデータベース管理システム。
2. 第１のデータベースを分散格納する複数の第１の分配処理部と、
   第２のデータベースを分散格納する複数の第２の分配処理部と、
   データのマージ処理を行う複数の結合処理部と、
   入力された問合せに対するマージ処理を実行する結合処理部を決定する決定処理部と、を有し、
   前記決定処理部は、
   処理時間と結合処理部数との対応関係を用いて、前記第１の分配処理部および第２の分配処理部における処理時間に対応する結合処理部数を特定し、前記問合せに対するマージ処理を実行する前記特定した結合処理部数の結合処理部を決定する手段と、
   前記問合せに対するマージ処理を実行する前記特定した結合処理部数の結合処理部各々に割当てる、前記第１のデータベースおよび第２のデータベースのデータの結合キーに対するハッシュ値が記述されたデータ分配情報を、前記第１の分配処理部および第２の分配処理部に設定する手段と、
   前記問合せに対するマージ処理を実行する前記特定した結合処理部数の結合処理部各々から受け取ったデータを出力する手段と、を有し、
   前記第１の分配処理部および第２の分配処理部各々は、
   自処理部に分散格納されたデータベースからデータを取り出し、該データを、自処理部に設定されているデータ分配情報において当該データの結合キーに対するハッシュ値に割り当てられた結合処理部へ分配する手段を有し、
   前記結合処理部は、
   前記第１の分配処理部および前記第２の分配処理部から分配された同じ結合キーを持つデータをマージ処理し、その結果を前記決定処理部に出力する手段を有すること
   を特徴とするデータベース管理システム。

Images