(57)【特許請求の範囲】
【請求項１】
複数の検索処理を含む１つの検索要求、もしくは複数の検索処理を一括化した検索要求を実行するデータベースの検索処理方法であって、
入力した検索要求が１つのテーブルに対する複数の検索処理を含む場合に、
前記１つのテーブルの１回のスキャン処理で読み込んだデータを、前記１つのテーブルに対する複数の検索処理の個別の検索条件の論理和を検索条件としてヒット判定する第１のステップと、
前記ヒット判定によりヒットしたデータを、前記１つのテーブルに対する複数の検索処理の個別の検索条件でそれぞれヒット判定し、それぞれの検索処理に対応する複数の出力バッファにそれぞれセットする第２のステップと、
該セットされたデータをそれぞれ後続の処理ステップに渡す第３のステップとを含むことを特徴とするデータベース検索処理方法。
【請求項２】
前記検索要求を実行するために、入力した検索要求の検索実行グラフを生成するコンパイル処理として、
前記入力した検索要求を解析して該検索要求に含まれる検索処理毎の検索実行木を生成するステップ、
前記生成した検索処理毎の検索実行木からスキャン対象のテーブルが共通な共通部分木を抽出するステップと、
前記共通部分木を一括スキャン処理ノードに変換することで前記生成した検索実行木で構成される検索実行グラフを変換するステップ、
該変換された検索実行グラフを解析して実行時にデッドロック状態になる可能性があるかを検出するステップ、及び
デッドロック状態になる可能性が検出された場合には、前記変換された検索実行グラフを再変換してデッドロック状態を回避する検索実行グラフを生成し、前記第１乃至第３のステップの実行に供するステップ、
を含むコンパイル処理の手順をさらに有する請求項１記載のデータベース処理方法。
【請求項３】
前記デッドロック状態になる可能性を検出するステップは、
前記生成した検索処理毎の検索実行木からなる検索実行グラフの各ノードを、複数のノードにデータを出力する一括スキャン処理ノードと、複数のノードからデータを入力し互いに同期を取りながら処理を行う同期処理ノードと、入力データを全て読み込むまで出力データを出力しないブロック処理ノードと、それ以外のパイプライン処理ノードとに識別するステップと、
パイプライン処理ノードは入力と出力を短絡することにより除去し、複数の連続するブロック処理ノードは一つのブロック処理ノードにまとめることにより検索実行グラフを簡素化するステップと、
一括スキャン処理ノードから同期処理ノードに至る経路を、前記２つのノード間を直接接続するパイプラインストリームと、前記２つのノードをブロック処理ノードを介して接続するブロッキングストリームに識別するステップと、
検索実行グラフを表す有向グラフにおいて、前記パイプラインストリームまたはブロッキングストリームのいずれか一方を表現する有向線分の矢印の向きを反転するステップと、
前記矢印の向きを反転した検索実行グラフにおいてループを検出するステップを有する請求項２記載のデータベース検索処理方法。
【請求項４】
前記デッドロックを回避する検索実行グラフの生成するステップは、
前記デッドロック状態になる可能性を検出するステップにより検出された検索実行グラフのループに属する一括スキャン処理ノードの一つを選択するステップと、
該選択された一括スキャン処理の複製を作り、該選択された一括スキャン処理ノードから出力されるパイプラインストリームとブロッキングストリーム毎にまとめて各々別々のスキャン処理ノードに割り当てるステップと、
該割り当てられたスキャン処理ノードから出力されるストリームが１つである場合には該一括スキャン処理ノードをシングルスキャン処理ノードに変換するステップと、
上記変換により生成された新たな検索実行グラフに対して前記デッドロックを検出するステップを施すステップと、
前記デッドロックを検出するステップによりデッドロックのループが検出されたときには、上記一括スキャン処理ノードを一つ選択するするステップに戻り、デッドロックのループが検出されなかった場合には前記デッドロックを回避するステップを終了するステップとを有する請求項３記載のデータベース検索処理方法。
【請求項５】
前記一括スキャン処理ノードを一つ選択するステップは、複数の一括スキャン処理ノードが存在する場合には、よりデータの流れの上流にあたる一括スキャン処理ノードを選択することを特徴とする請求項４記載のデータベース検索処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はテーブルの参照を行うデータベースシステムに係り、特に複数の検索処理を同時に実行する検索処理方法に関する。
【０００２】
【従来の技術】
商業用応用並列サーバ市場の拡大に伴って実用化されつつあるデータウェアハウスは、一般的には、膨大なデータを蓄積する企業データウェアハウスと部門毎に抽出されたデータを格納する部門データウェアハウスと多数のクライアント端末からなる３階層の企業情報システムである。
【０００３】
このデータウェアハウスでは、生データを保持するテーブルを様々な角度から分析する多次元解析が頻繁に行われる。そのため、一つのテーブルに対して種々の条件で検索が繰り返し実行される。データベースシステムでは、これらの検索を別々に実行していた。データウェアハウスが保持する生データはＴＢ規模の膨大な量でありデータを全件スキャンするだけでも多くの時間を要する。そのため、種々の条件で検索を繰り返し実行した場合、生データの全件スキャンを何度も繰り返す必要があり、膨大な処理時間が必要であるという問題点があった。
【０００４】
図３は複数の検索処理を含む検索要求のＳＱＬ文の例である。図３は、ＷＩＴＨ句で指示される２つの検索処理Ｑ１およびＱ２を含む。検索処理Ｑ１はテーブルＴ１とＤ３列が１００未満のテーブルＴ２をＣ１列をキーとしてジョインし、Ｃ１列とＣ２列でグループ化し、Ｄ１列とＤ２列のグループ毎の合計を求める。検索処理Ｑ２はＤ４列が１００未満のテーブルＴ２とテーブルＴ３をＣ３列をキーとしてジョインし、Ｃ２列とＣ３列でグループ化し、Ｄ１列とＤ２列のグループ毎の合計を求める。図３のＳＱＬでは、上記のＱ１及びＱ２の処理をＵＮＩＯＮ  ＡＬＬで一つの検索結果としてまとめる。この際、取り出した結果がＱ１の検索処理の結果かＱ２の検索処理の結果かが分かるように先頭に識別子“Ｑ１”および“Ｑ２”の識別子をそれぞれ負荷してまとめる。本ＳＱＬでは、テーブルＴ１とＴ２を結合してグループ化する処理と、テーブルＴ２とＴ３を結合してグループ化する処理を含んでいる。本検索要求を従来方式で実行すると、テーブルＴ２が２回スキャンされる。このときの処理の流れを図２に示す。
【０００５】
図２は、複数の２次記憶装置２８〜３０に格納されているテーブルＴ１、Ｔ２、Ｔ３をスキャンバックエンドサーバ（Ｓｃａｎ  ＢＥＳ）６で読み込み、ジョインバックエンドサーバ（Ｊｏｉｎ  ＢＥＳ）４及び５に転送して処理する様子を示している。スキャンバックエンドサーバ６は、２次記憶から読み込んだデータを主記憶上にキャッシングするためのデータベースバッファ１７を有し、テーブルＴ１とＴ２を結合するためのテーブルスキャン処理１４及び３１と、テーブルＴ２とＴ３を結合するためのテーブルスキャン処理３２と１６の合計４つのテーブルスキャン処理を独立に実行する。
【０００６】
図２の処理では、テーブルＴ２のスキャン処理が２回重複して実行されるため、データベースバッファからテーブルスキャン処理がデータを取ってくる処理を２回重複して行わなければならず、さらに、Ｔ２のスキャン処理３１と３２の処理速度に差がある場合には、データベースバッファ１７上にそれぞれのスキャン処理が参照すべきテーブルＴ２のキャッシュ効果がなくなり、最悪の場合、２次記憶に対するＩ／Ｏ処理を２回発行する事になってしまう。
【０００７】
これらの問題を解決するために、従来の技術では特願平６−１３５４６４号公報に記載されているように複数の検索処理間で同一のデータをアクセスする場合には、同時実行制御を行うことにより、１回のＩ／Ｏでデータベースバッファに取り込まれたデータを複数の検索処理で利用可能にする技術が提案されてきた。
【０００８】
【発明が解決しようとする課題】
従来の複数の検索処理の同時実行制御方式では、データベースバッファのヒット率を高めるために各検索処理間で同期制御を行う必要があった。しかしながら、各検索要求はデータベースシステムに非同期に投入されるため、その同期制御を行うためのオーバヘッドが大きかった。さらに、各検索処理間でデータをスキャンする速度に差が生じる場合には、頻繁に同期制御を行わないとデータベースバッファに保持されているデータを共有できないという問題点があった。
【０００９】
また、従来の方式では、２次記憶からデータベースバッファにデータを読み出す処理は共通化されていたが、データベースバッファから各検索処理のローカルバッファにデータを読み出す処理を各検索処理毎に行っていたため、十分な処理の共通化が行えなかった。
【００１０】
複数の検索処理を一連の検索要求として一括化して発行する手段としてＳＱＬのストアドプロシジャやＳＱＬ３で標準化されるＷＩＴＨ句が提供されている。データウェアハウスの多次元解析では、複数の検索処理が同時に発行されるため、これらのストアドプロシジャやＷＩＴＨ句を用いた手段で１回の検索要求にまとめることができる。
【００１１】
複数の検索処理を一括化した一連の検索要求を発行する手段としては、上記以外にもたとえば、データベースシステムの問い合わせ受け付けサーバで複数のＳＱＬ文をバッファリングして一括化して発行する手段等も考えられる。
【００１２】
本発明は、上記のような一連の検索要求の中に内在する複数の検索処理を効率良く実行する方法を提供することを目的とする。
【００１３】
本発明は、複数の検索処理で構成される一連の検索要求をコンパイルして検索実行グラフを生成する方法を提供することを目的とする。
【００１４】
さらに、本発明は、複数の検索処理を同時に実行する時に発生しうるデッドロック状態をコンパイル時に検出し、それを回避する方法を提供することを目的とする。
【００１５】
【課題を解決するための手段】
本発明の実施例では、一つのテーブルに対して複数の検索処理を実行するときに、該複数の検索処理で共通な部分検索処理を一つにまとめて複数の検索処理間で共有する処理方法を提供する。この処理方法は、複数の検索処理を含む一つの検索要求を解析して検索処理の実行グラフを生成するステップと、前記生成された実行グラフに従い検索処理を実行するステップとで構成される。
【００１６】
検索要求を解析して検索処理の実行グラフを生成するステップは、該検索要求に含まれる複数の検索処理を解析して各検索処理毎の実行木を作成するステップと、各検索処理の実行木の間で共通な部分を切り出して、該共通な部分を共有した実行グラフに変換するステップと、該変換された実行グラフを解析して実行時にデッドロック状態になる可能性があるかどうかを検出してデッドロック状態になりうる場合には共通な部分グラフの一部を非共有化してデッドロックフリーな実行グラフに変換するステップとで構成される。
【００１７】
検索処理を実行するステップは、同一テーブルに対する複数の検索処理を実行する一括スキャン処理ステップを有し、一括スキャン処理ステップは、入力バッファに読み込まれた一つのデータを複数の検索条件に共通な条件で予め絞り込むステップと、該共通条件に適合したデータをさらに各検索条件に複数回照合して該検索条件に適合した全ての検索処理に対応する複数の出力バッファにそれぞれ出力するステップとで構成される。
【００１８】
【発明の実施の形態】
図１は本発明を実施するデータベースにおける複数の検索処理を同時に実行する方法を示した図である。端末１が図３で示される検索要求をデータベースシステム２に対して発行すると、検索要求受付サーバ（フロントエンドサーバ）３が該検索要求を受け付け、これをコンパイルする。今、コンパイルの結果、図４で示す様な検索処理の実行グラフを生成したとする。以下、図４で示される検索処理を実行するものとして説明する。コンパイル後、次に検索処理を実行するのに必要な各種バックエンドサーバを起動し、検索処理の実行を指示する。図４に示す検索実行グラフは２つの結合演算と３つのテーブルスキャン処理を含んでいるので、ジョインバックエンドサーバ４及び５とスキャンバックエンドサーバ６が起動される。
【００１９】
ジョインバックエンドサーバでは、ハッシュジョインとグループ化を行う処理が実行される。
【００２０】
テーブルＴ１またはＴ３をスキャンするスキャンバックエンドサーバでは、一つの条件でヒット判定を行い、ヒットしたデータを出力先（ジョインバックエンドサーバ）に出力するシングルスキャン処理１４、１６が実行される。
【００２１】
一方、テーブルＴ２をするスキャンバックエンドサーバでは、複数の条件でヒット判定を行いヒットした条件に対応する出力先（ジョインバックエンドサーバ）にデータを出力する一括スキャン処理１５が実行される。この一括スキャン処理では、１回のスキャン処理で読み込んだデータを複数の検索処理の検索条件でヒット判定する。
【００２２】
テーブルＴ１のシングルスキャン処理１４は、２次記憶からＤＢバッファ１７内にテーブルＴ１のデータを読み込み、更にそのデータをシングルスキャン処理のバッファ内に取り込み、当該処理済みのデータをジョインバックエンドサーバに出力する。
【００２３】
テーブルＴ３のシングルスキャン処理１６は、シングルスキャン処理１４と同様に、２次記憶からＤＢバッファ１７内にテーブルＴ３のデータを読み込み、更にそのデータをシングルスキャン処理のバッファ内に取り込み、当該処理済みのデータをジョインバックエンドサーバに出力する。
【００２４】
テーブルＴ２の一括スキャン処理１５は、２次記憶からＤＢバッファ内にテーブルＴ２のデータを読み込みさらにそのデータを一括スキャン処理のバッファ内に取り込み、それぞれの結合演算に対応する条件で取り込んだデータを複数回判定する（２２）。各条件に適合したデータは一括スキャン処理によって対応する出力バッファに格納され、それぞれのジョインバックエンドサーバに出力される。
【００２５】
各スキャン処理が出力したデータは、２次記憶装置に格納されることなくジョインバックエンドサーバで順次処理される。さらにジョインバックエンドサーバで求められた演算結果はフロントエンドサーバ３に順次出力され、最終的に検索要求を発行した端末１に出力される。このように本方式では各サーバ間のデータの受け渡しに２次記憶を用意する必要がないため、各処理を独立した制御装置で実行した場合には処理がパイプライン的に実行できる。
【００２６】
本実施例では各処理において出力したデータが次の処理の入力に転送されるように記述しているが、入出力のバッファを共有することによりデータの転送を省略することももちろん可能である。
【００２７】
また、本実施例では一つの端末からあらかじめ複数の検索処理を含む検索要求が発行されている例を示しているが、検索要求受け付けサーバで複数の検索処理をまとめることも可能であり、そのような場合でも本発明による検索処理の同時実行方式が適用できることは明らかである。
【００２８】
図５は一括スキャン処理の詳細な方法を示す図である。一括スキャン処理１５は、一括スキャン処理ノード（Ｍ−ＳＣＡＮ  Ｐｒｏｃ）６４をルートとする木を実行する。Ｍ−ＳＣＡＮ  Ｐｒｏｃノードは、左の部分木として出力先ノード（ＤＳＴ）を複数持つことができる（６５及び６６）。一括スキャン処理のＤＳＴノードは、出力を識別する情報である出力識別子と各ＤＳＴ毎の検索条件を示す個別検索条件式が記載された出力先情報（６６及び６７）を有する。
【００２９】
本実施例では、ＤＳＴノード６５では出力識別子が２（ジョインバックエンドサーバ４に対する出力）で個別検索条件がＴ２．Ｄ３＜１００となっており、ＤＳＴノード６６では出力識別子が３（ジョインバックエンドサーバ５に対する出力）で個別検索条件がＴ２．Ｄ４＜１００となっている。個別検索条件に適合したデータは各ＤＳＴノードが持つ出力バッファ１９及び２０にそれぞれ出力され、次の処理の入力データとして消費される。
【００３０】
Ｍ−ＳＣＡＮ  Ｐｒｏｃノードの右の部分木には該Ｍ−ＳＣＡＮ  Ｐｒｏｃで共通化した処理が記述される。本実施例ではテーブルＴ２の全件スキャン処理を共通化したので、その実行を指示する部分木がＳＣＡＮノード６３及びＯＢＪノード６２で表現されている。ＯＢＪノードには入力識別子及び共通検索条件が記述される（６１）。
【００３１】
入力識別子には入力元がデータベースのテーブルか他のサーバの出力バッファか等の、入力元を識別特定するための情報が記述され、例えば、入力元がテーブルの場合にはテーブルを示す識別子が、入力元が出力バッファの場合には出力バッファを示す出力識別子が記述される。本実施例では、入力元はテーブルでテーブル識別子がＴ２となっている。一方、ＯＢＪノードの共通検索条件には、本一括スキャン処理で絞り込むデータの共通部分（各個別条件の論理和）が記述される。
【００３２】
なお、ＤＳＴノードで指定される個別検索条件は共通検索条件で絞り込めなかった以外の条件を記述する。例えば、出力先が２つで、それぞれの検索条件が「１００≦Ｄ１＜２００」と「２００≦Ｄ１＜３００」の時には共通条件は「１００≦Ｄ１＜３００となり、各個別条件が、ぞれぞれＤ１＜２００と２００≦Ｄ１となる。本実施例では、共通検索条件がテーブルの全データとなるので共通条件は記載されない。
【００３３】
次に一括スキャン処理のデータの流れについて説明する。一括スキャン処理は、まずＯＢＪノードに記述されている入力識別子に従ってデータを読み込み、共通条件に適合するデータを入力バッファ６０に取り込む。入力バッファに取り込まれたデータは、ＤＳＴノード６５の出力先情報６６に記載されている個別検索条件と照合され、検索条件に合致した場合には出力バッファ２０に出力される。さらに次のＤＳＴノード６６でも同様の処理を行い、個別検索条件に合致したデータが出力バッファ１９に出力される。本発明では１回のデータ入力に対して複数の出力先にデータを出力するため、データの入力処理が１回で済み、オーバヘッドが削減される。
【００３４】
図６は、シングルスキャン処理の詳細な方法を示す。シングルスキャン処理１４は、シングルスキャン処理ノード（Ｓ−ＳＣＡＮ  Ｐｒｏｃ）７４をルートとする木を実行する。Ｓ−ＳＣＡＮ  Ｐｒｏｃノード７４は、左の部分木として出力先ノード（ＤＳＴ）を一つだけ持つことができる（７６）。シングルスキャン処理のＤＳＴノードは、出力識別子が記載された出力先情報７５を有する。本実施例では出力先ノード７５の出力識別子が１となっている。一括スキャン処理では出力先情報に個別検索条件式が記載されていたが、シングルスキャン処理では、出力先は唯一つであるため、検索条件はＯＢＪノード７２に記載される（７１）。
【００３５】
Ｓ−ＳＣＡＮ  Ｐｒｏｃノードの右の部分木にはスキャンするデータの入力元や検索条件等が記述される。図６の例ではテーブルＴ１の無条件全件スキャン処理の実行を指示する木がＳＣＡＮノード７４及びＯＢＪノード７２で表現されている。ＯＢＪノードには入力識別子及び検索条件が記述される（７１）。入力識別子には入力元がデータベースのテーブルか他のサーバの出力バッファか等を識別するための情報が記述され、テーブルの場合にはテーブル識別子が、出力バッファの場合には出力識別子が記述される。図６の例では、入力元はテーブルでテーブル識別子がＴ１となっている。ＯＢＪノードの検索条件には何も記述されず全件スキャンを指示している。
【００３６】
同一テーブルに対する複数のスキャンを従来のようにシングルスキャン処理ノード（Ｓ−ＳＣＡＮ  Ｐｒｏｃ）のみで行った場合の処理コストは、ＤＢバッファへのページ単位の入力処理コストをＤ＿ＩＮ、ＤＢバッファから１行毎にスキャン処理にデータを持ってきて選択条件で絞り込む処理コストをＤ＿ＦＥＴＣＨ、出力バッファにヒットしたデータを書き込む処理コストをＤ＿ＳＥＴ、出力バッファのデータをページ単位で出力する処理コストをＤ＿ＯＵＴとし、テーブルスキャンの多重度、即ち一括処理する検索処理の数をＮとしたとき、従来の方法では、
（Ｄ＿ＩＮ×（テーブルページ数）＋Ｄ＿ＦＥＴＣＨ×（テーブル行数））×Ｎ
＋（Ｄ＿ＳＥＴ×（ヒット件数）＋Ｄ＿ＯＵＴ×（スキャン結果のデータのページ数））×Ｎ
となる。
【００３７】
一方、本実施例の方法では前半の処理が共通化されるため、テーブルスキャンコストが
（Ｄ＿ＩＮ×（テーブルページ数）＋Ｄ＿ＦＥＴＣＨ×（テーブル行数））×１
＋（Ｄ＿ＳＥＴ×（ヒット件数）＋Ｄ＿ＯＵＴ×（スキャン結果のデータのページ数））×Ｎ
となる。
【００３８】
いま、Ｄ＿ＩＮ、Ｄ＿ＦＥＴＣＨ、Ｄ＿ＳＥＴ、Ｄ＿ＯＵＴの処理コストの比を５：２：１：５とし、テーブルのレコード長を５１２Ｂｙｔｅ、レコード数を十万行、スキャン結果のレコード長を５０Ｂｙｔｅ、各スキャン条件の選択率を５０％、ページサイズを４０９６Ｂｙｔｅとすると、図７に示すような結果となり処理コストを削減する効果があることがわかる。
【００３９】
一般に大規模な生データを保持するテーブルを多次元解析する場合には、膨大な生データに対して種々の角度から検索要求が出ることが多い。本実施例の方法を適用することによりこのような大規模なデータのスキャン処理を削減することができる。
【００４０】
この結果から全ての場合について共有可能なテーブルスキャン処理を一括スキャン処理で共有化する方式が考えられるが、実際にはテーブルスキャンを共有化すると検索処理のデッドロックが発生するような問い合わせ要求が存在する。
【００４１】
図８は、テーブルスキャンの共有化によりデッドロックを発生する問い合わせ要求の一例である。いま、８９で示すような検索要求が発行されたとする。本検索要求はテーブルＴ４（８５）をＣ１列でグループ化して各グループ毎のＤの平均値を求めその中間結果をＱ１（８４）とする。次に、テーブルＴ４と中間結果Ｑ１をＣ１列をキーとしてジョインし、ＤとＤの平均（ＤＡＶＧ）の差分を求める（８２）。
【００４２】
本検索処理ではＱ１を生成する時と、結合演算を実行するときにテーブルＴ４のスキャンを行う。そこで、Ｍ−ＳＣＡＮ  Ｐｒｏｃ８０によりテーブルＴ４のスキャン処理を共通化したとする。Ｍ−ＳＣＡＮ  Ｐｒｏｃ８０はグループ化をして平均を求める処理ノード８１とジョイン演算をするノード８２に結果を出力する（８６及び８８）。また、グループ化して平均を求める処理ノードはジョイン演算をするノード８２に結果を出力する（８７）。
【００４３】
グループ化を行い平均を求めるノード８１はテーブルＴ４の全データのスキャンが完了するまで結果を出力することはできない。このように入力データの終端（エンドオブデータ）を受け取らないと結果が出力されないノードをブロック処理ノード（Ｂｌｏｃｋ  Ｐｒｏｃ）と呼ぶ。
【００４４】
ジョインを行うノード８２は２つの入力データ一方が到着しないと他方の入力を抑止する。この例の場合、ノード８１からＱ１のデータを受信しない間はノード８０からのデータの入力を抑止する。このように、複数の入力データを持つノードで、一方のデータの入力状況が他方のデータの入力を抑止するノードを同期処理ノード（Ｓｙｎｃ  Ｐｒｏｃ）と呼ぶ。
【００４５】
一括スキャン処理ノードとブロック処理ノード、同期処理ノードが図８で示すような関係で結合されている場合には検索処理全体がデッドロックする。
【００４６】
図９は、図８で示した検索処理がデッドロック状態に遷移する過程を説明する図である。図９の（ａ）は、検索処理開始直後の様子を示している。一括スキャン処理ノード８０の入力バッファ９０にはテーブルＴ４のデータが読み込まれ、次の処理ノードへの出力バッファ９１及び９２に蓄積されていく。
【００４７】
図９の（ｂ）では、出力バッファ９１及び９２から次の処理ノード８２及び８１にデータが出力され、それぞれの入力バッファ９６及び９３に蓄積されている。
【００４８】
図９の（ｃ）では、グループ化及び平均値を求める処理として入力バッファ９３に到着したデータをワークバッファ領域９４上に足し込んでいく処理を行っている。しかし、全ての入力データが到着するまで出力バッファ９５にデータは出力されない。従って、ジョインを行うノード８２の入力バッファ９７にはデータが到着しない。
【００４９】
すると、図９の（ｄ）で示すような待ち状態となり、デッドロックが発生する。即ち、ジョインノード８２の入力バッファ９６に到着したデータは、ハッシュテーブル９８が未完成のためバッファ内で待たされる。ハッシュテーブル９８は入力バッファ９７にＱ１のデータが到着しないため作成できない。Ｑ１のデータはテーブルＴ４のデータがノード８１の入力バッファ９３に全て到着していないため、集計処理が完了せず出力ノード９５に出力することができない。テーブルＴ４のデータは一括スキャン処理ノード８０の出力ノード９１が満杯のため読み込むことができない。出力ノード９１は次のジョインを実行するノード８２の入力バッファ９６が満杯のためデータを送信することができない、というように全てが互いに他を待ち続ける状況となる。
【００５０】
このような状態を避けるためには、あらかじめ検索処理の実行グラフを作成したときにデッドロックが起きうるかどうかを検出して、デッドロックが起きる可能性があるときには、一括スキャン処理の一部を非共有化する必要がある。
【００５１】
図１０は、検索要求の実行グラフを作成する方法を示す流れ図である。検索要求のコンパイル処理では、まず検索要求に含まれる各検索毎の実行木を生成する。次に、各検索の実行木の共通部分（即ち共通部分グラフ）を切り出す。共通部分グラフは、複数の検索木間及び同一の検索実行木内の全ての場合について、実行木から取り出される。共通部分グラフの抽出には、単純なマッチングアルゴリズムのほかグラフ構造の変換を伴うあらゆる方式が適用可能である。なお共通部分グラフの抽出時には、テーブルの検索絞り込み条件の違いは無視して抽出する。
【００５２】
次に、抽出した共通部分グラフを一括スキャン処理ノードに変換する。この際、絞り込み条件が異なる検索処理に対しては、一括スキャン処理ノードの共通検索条件と個別検索条件とで当該検索処理を共通化する。最後に、共通部分木を一括スキャン処理ノードに変換した検索実行グラフに対して、デッドロック検出処理をおこない、デッドロック状態が検出された場合には一部の一括スキャン処理ノードの複製を作ることによりデッドロック状態の回避処理を行う。
【００５３】
図１１の（ａ）は、デッドロック状態を検出する方法を説明するのに使用する記号を説明する図である。符号１０５で示される図形は複数の入力間で同期処理を行う同期処理ノード（Ｓｙｎｃ  Ｐｒｏｃ）を示し、符号１０６で示される図形は一括スキャン処理ノード（Ｍ−ＳＣＡＮ  Ｐｒｏｃ）を示し、符号１０７で示される図形は入力側のデータを全て読み込むまでデータを出力しないブロック処理ノード（Ｂｌｏｃｋ  Ｐｒｏｃ）を示す。またパイプライン的に処理できる通常のパイプライン処理ノードは符号１０８で示す図形で示す。
【００５４】
検索実行グラフにはデータの流れに沿って有向線分が記されている。本発明では、検索実行グラフにおいて一括スキャン処理ノードから同期処理ノードに至るデータの流れをパイプラインストリーム１０９とブロッキングストリーム１１０の２種類に識別してデッドロック状態を検出することを特徴とする。パイプラインストリームは一括スキャン処理ノードから同期処理ノードに至る経路で途中にブロック処理ノードがないデータストリームであり、ブロッキングストリームは一括スキャン処理ノードから同期処理ノードに至る経路で途中にブロック処理ノードがあるデータストリームである。
【００５５】
図１１の（ｂ）、（ｃ）はパイプラインストリーム並びにブロッキングストリームを見つけるために検索グラフを簡素なものに変換する方法を示している。図１１の（ｂ）は、通常の処理ノードを除去し、入力と出力を短絡する変換処理１を示す。図１１の（ｃ）は、複数の連続するブロック処理ノードを一つにまとめる変換処理２を示している。これらの変換を検索実行グラフに適用することにより、一括スキャン処理ノードから同期処理ノードに至る全ての経路は、直接結合されているか、または、ブロック処理ノードを一つ含むかのいずれかに分類される。このとき直接接続されている経路をパイプラインストリーム、ブロック処理ノードを介して接続されている経路をブロックストリームとする。図１１（ｃ）では、説明を解かりやすくするためにブロッキングストリームを点線の有向線分で示している。
【００５６】
図１１の（ｄ）は、デッドロック状態を検出するためにブロックストリームの矢印の向きを反転させてブロック処理ノードを除去する処理を示している。本発明では、検索実行グラフのデッドロック状態の検出を、ブロックストリームの有向線分の向きを反転させてループの検出を行うことにより、実行することを特徴とする。
【００５７】
図１２は、一括スキャン処理ノードへの変換により生成された検索実行グラフがデッドロック状態を有する簡単な例を示している。図１２の（ａ）は最も簡単なデッドロック状態を示すグラフである。本グラフは図８で示した検索処理を実行する際に作成される検索実行グラフである。符号１２０が図８のＳｙｎｃ  Ｐｒｏｃ８２に、符号１２１が図８のＭ−ＳＣＡＮ  Ｐｒｏｃ８０に、符号１２２が図８のＢｌｏｃｋ  Ｐｒｏｃ８１にそれぞれ対応する。
【００５８】
図１２の（ｃ）は、このグラフがデッドロック状態を有するかどうかを検出するために、図１１の（ｄ）で示したデッドロック検出手続きにより、ブロッキングストリームの矢印の向きを反転させたグラフである。このようにすると、ノード１２０及び１２１と有向線分１２３と１２４でループが形成されていることわかる。本発明によるデッドロックの検出方法は変換した検索実行グラフにループがあるかどうかを検出することによって行われる。グラフに内在するループの検出方法についてはグラフ理論等で提示されている任意の方法を適用することができる。
【００５９】
図１２の（ｂ）は、複数の検索処理間でのデッドロックの状態を示す図である。この例では、ノード１２５または１２６をルートとする検索実行グラフは単独ではデッドロックに陥らないが、ノード１２７及び１２８の一括スキャン処理を共有するとデッドロック状態に陥る。なぜなら、ブロックストリーム１３０及び１３１の影響でパイプラインストリーム１２９及び１３２が、ブロックされ一括スキャン処理ノード１２７及び１２８がブロックされるためである。このような複数の検索処理間のデッドロックも本発明で示したデッドロック検出手続きを適用すると容易に検出可能である。即ち、図１２の（ｄ）に示すようにブロッキングストリームの矢印の向きを反転させれば、有向線分１２９〜１３１〜１３２〜１３０で示される横８の字型のループが形成されるため、グラフのループ検出処理により容易にデッドロック状態が検出できる。
【００６０】
図１３はより複雑な検索要求の検索実行グラフを示した図である。本図は、図１１の（ｂ）及び（ｃ）の変換処理を施した後の検索実行グラフを示す。本検索実行グラフは一括スキャン処理ノードを３つ（１４６、１４５、１４３）と同期処理ノードを４つ（１４０、１４１、１４２、１４４）含み、さらに４つのブロック処理ノードを含む。
【００６１】
図１４は図１３の検索実行処理のデッドロック状態を検出する手続きを示した図である。図１４の（ａ）は、検索実行グラフに図１１の（ｄ）で示したブロッキングストリームの矢印の反転処理を施した後の状態を示す図である。この処理によりブロッキングストリーム１５０、１５１、１５２、１５６の矢印の向きが反転される。次にこのグラフに対してループ検出処理を適用すると図１４の（ｂ）で示すような２つのループが検出される。即ち、有向線分１５１〜１５５〜１５４〜１５２〜１５３で示される第一のループと、有向線分１５２〜１５６〜１５５〜１５４で示される第二のループが検出される。従って本検索実行グラフはデッドロック状態を有することが解かる。
【００６２】
図１５は、本検索実行グラフのデッドロック状態を回避する手段を示した図である。デッドロック状態を回避するためには、デッドロックループを切断すればよい。そのためにはループ内に含まれる一括スキャン処理ノードの一部を複製して、該一括スキャン処理ノードから出力されるパイプラインストリームとブロッキングストリームを各々別のスキャン処理ノードで実行するようにする。本実施例では、一括スキャン処理ノード１４５を複製してスキャンノード１４７を作成し、一括スキャン処理１４５から出力されていた全てのブロッキングストリーム（本実施例では１５１と１５６）を割り当てる。複製元の一括スキャン処理ノード１４５には残りの全てのパイプラインストリームを割り当てる。デッドロックの回避処理では、検索実行グラフの全てのループが切断されるまでこの一括スキャン処理ノードの複製によるループの切断を行う。本実施例では、一括スキャン処理ノード１４５を複製すれば前記の第一のループ及び第二のループは同時に解消するため、これ以上の複製は行わない。
【００６３】
本実施例ではデッドロックの状態に陥っている一括スキャン処理ノードとしてはノード１４５の他にノード１４３がある。図１６にノード１４３の複製を行うことによりループの切断を試みた場合を示す。一括スキャン処理ノード１４３はブロッキングストリーム１５２とパイプラインストリーム１５３をそれぞれ１つずつしか持たないため、複製を作成すると共にシングルスキャン処理ノード１４８及び１４９となる。すると前記第一のループは一時的に解消されるものの、ノード１４２〜１４９〜１４５〜１４４で形成される前記第二のループは切断されずに残る。このように一括スキャン処理ノードを複製したばあい、選択した一括スキャン処理ノードによりループが切断できる場合とできない場合がある。このように１回の一括スキャン処理ノードの複製によりループを切断できない場合には他の一括スキャン処理ノードをさらに複製し、これを繰り返すことでデッドロック状態のループを切断することができる。
【００６４】
しかしながら、検索実行時の処理性能を考慮すると、なるべく少ない一括スキャン処理ノードの複製でデッドロック状態のループを解消できることが望ましい。本発明では、以下のように、より少ない複製処理でループを切断しうる一括スキャンノードの候補を選択する方法を提供することも特徴とする。
【００６５】
検索実行グラフのループの切断するために複製する一括スキャンノードの候補としては、デッドロック状態のループに陥っているノードのなかでストリームのより上流になっている一括スキャン処理ノードを一つ選択する。本実施例ではデッドロック状態のループに陥っている一括スキャン処理ノードはノード１４３とノード１４５があったのであるが、ノード１４５の出力がノード１４３に入力されているため、ノード１４５がより上流ノードにあたる。従ってノード１４５の複製処理をおこないデッドロック状態を回避する処理を行う。そして、この回避処理を検索実行グラフのループが解消されるまで繰り返し適用する。
【００６６】
上記デッドロック状態の回避処理は、少なくとも検索実行グラフの全ての一括スキャン処理ノードを複製すればループが無くなる。検索じっうグラフの中に含まれる一括スキャン処理ノードの数は有限であるため、本デッドロック回避方法は有限回で停止することが保証される。
【００６７】
なお、本実施例ではデッドロックの検出／回避処理をブロッキングストリームの有向線分の矢印の向きを反転させて行っていたが、本質的にはデッドロックループの検出並びにループ切断が行えればよいので、パイプラインストリームの有向線分の向きを反転させても全く同様のデッドロック検出／回避処理ができることは明かである。
【００６８】
以上の実施例では、一つの検索要求に複数の検索処理が含まれる場合について説明を行なった。しかし、本発明は、複数のクライアント端末から同一データに対する検索要求が発行される場合においても適用可能である。図１７は、複数のクライアント端末１７１・１７２から複数の検索要求Ｑ１・Ｑ２が発行された場合に本発明を適用する例を説明する図である。端末１７１から発行される検索処理Ｑ１はテーブルＴ１とＤ３列が１００未満のテーブルＴ２のをＣ１列をキーとしてジョインし、Ｃ１列とＣ２列でグループ化し、Ｄ１列とＤ２列のグループ毎の合計を求める。端末１７２から発行される検索処理Ｑ２はＤ４列が１００未満のテーブルＴ２とテーブルＴ３をＣ３列をキーとしてジョインし、Ｃ２列とＣ３列でグループ化し、Ｄ１列とＤ２列のグループ毎の合計を求める。本実施例では、それぞれの端末が発行した検索要求はクエリスケジューラ（Ｑｕｅｒｙ  Ｓｃｈｅｄｕｌｅｒ：ＱＳＣＤ）１７５に送られ、該スケジューラが有する検索要求バッファ１７６にバッファリングされる。クエリスケジューラはバッファリングされた各問い合わせをコンパイルし、共通部分の切り出しを行ない、共通部分がある問い合わせを一括化した検索実行グラフを生成し、実行グラフの各部分木を各サーバに割り当てる。共通部分がある問い合わせを一括化した検索実行グラフの生成法は先に述べた実施例と同様の方法が適用可能である。
【００６９】
本実施例では、クエリスケジューラで生成された検索実行グラフの各部分木は、フロントエンドサーバ１７８及び１７９、ジョインバックエンドサーバ４及び５、スキャンバックエンドサーバ６にそれぞれ割り当てられる（１７７）。先の実施例では、検索要求を発行した端末が一つであったため、フロントエンドサーバは一つであったが、本実施例では、複数の端末からの検索要求を一括して実行するため、各検索要求毎に異なるフロントエンドサーバが割り当てられる。そして、各検索処理の結果は対応するフロントエンドサーバから、検索要求を発行した端末にそれぞれ返される（１８０、１８１）。本実施例では、クエリスケジューラ１７５が検索要求のバッファリング機能を持つことにより複数の検索要求に存在する共通処理を一括化することを可能としている。バッファリングされた検索要求を一括化するタイミングとしては、一定時間毎やデータベースの負荷状態に応じて決める等、種々の方法が適用できる。
【００７０】
【発明の効果】
本発明の検索処理の共通化によりデータベースシステムにおける複数の検索処理の同時実行が可能となる。
【００７１】
また、本発明ではかかる検索処理の共通化に伴い問題となるデッドロック状態をあらかじめ検出し回避する手段を提供することで検索実行時にデッドロックの検出を行う必要がないという効果がある。
【００７２】
更に、デッドロックの回避では、より少ない一括スキャンノードの複製によりデッドロック状態を回避する方法を提供することにより検索実行時間を短縮する。
【図面の簡単な説明】
【図１】複数の検索処理を同時に実行する方法を示す図である。
【図２】従来方式における処理概要図である。
【図３】複数の検索処理を含むＳＱＬ文の例を示す図である。
【図４】検索要求の検索実行グラフの例を示す図である。
【図５】一括スキャン処理の詳細な流れを示す図である。
【図６】シングルスキャン処理の詳細な流れを示す図である。
【図７】本発明と従来方法との処理コストの差を示す図である。
【図８】一括スキャン処理を用いたときにデッドロックが起こる場合の例を示す図である。
【図９】デッドロックに陥る状態の遷移を示す図である。
【図１０】検索処理要求をコンパイルして検索実行グラフを作成する処理の流れ図である。
【図１１】検索実行グラフのデッドロック検出手段の説明をする図である。
【図１２】簡単なデッドロック検出手順を示す図である。
【図１３】複雑な検索実行グラフを示す図である。
【図１４】複雑な検索実行グラフのデッドロック検出手段を説明する図である。
【図１５】複雑な検索実行グラフのデッドロック回避処理を説明する図である。
【図１６】一括スキャン処理ノードの複製によりループが解消できない場合を説明する図である。
【図１７】複数の検索処理を同時に実行する方法の他の例を示す図である。
【符号の説明】
１  端末
２  データベースシステム
３  フロントエンドサーバ
４、５  ジョインバックエンドサーバ
６  スキャンバックエンドサーバ
７  データベース２次記憶装置
１４、１６  シングルスキャン処理手段
１５  一括スキャン処理手段
１７  データベースバッファ
１８、１９、２０、２１  出力バッファ
２２  多重選択手段。
【図１】
0003620203.tif 000002
【図２】
0003620203.tif 000003
【図３】
0003620203.tif 000004
【図４】
0003620203.tif 000005
【図５】
0003620203.tif 000006
【図６】
0003620203.tif 000007
【図７】
0003620203.tif 000008
【図８】
0003620203.tif 000009
【図９】
0003620203.tif 000010
【図１０】
0003620203.tif 000011
【図１１】
0003620203.tif 000012
【図１２】
0003620203.tif 000013
【図１３】
0003620203.tif 000014
【図１４】
0003620203.tif 000015
【図１５】
0003620203.tif 000016
【図１６】
0003620203.tif 000017
【図１７】
0003620203.tif 000018