(57)【要約】【課題】再帰的処理を含む一般のデータ処理を低レイテンシで実現できるストリームデータ処理方法及びシステムを提供する。【解決手段】ストリームデータ処理システム９００は、複数のクエリの実行木から単一のオペレータグラフ９３１を構築し、ストリーム化演算の実行が、入力から出力に向かって一方通行で進むように、オペレータの実行順序を決定し、システム外部のデータを入力する外部発火オペレータと時限的にデータを生成する内部発火オペレータの発火時刻を監視し、オペレータ実行制御部９１６は、最も早い発火時刻のオペレータを起点として、決定したオペレータ実行順序に従って、当該時刻のオペレータグラフ９３１における処理を完結させる処理を繰り返す。【選択図】図９
2010108152.tif 000002
【特許請求の範囲】
【請求項１】
タイムスタンプが付与され、前記タイムスタンプの昇順に到来する時系列データの流れであるストリームを処理するストリームデータ処理方法であって、
複数のクエリの連携によって定義されたデータ処理を、前記クエリ個々に対して、基本データ処理単位であるオペレータをノードとする実行木を一つずつ作成し、作成した複数の前記実行木から単一のオペレータグラフを構築し、
前記オペレータグラフ上の全ての前記オペレータに対して、前記オペレータ間の入出力関係に基づいて、出力側オペレータに付与された実行順序が入力側オペレータの実行順序よりも大となるよう、オペレータ実行順序を付与し、
前記オペレータグラフから、前記オペレータグラフの外部からデータを受取る外部発火オペレータと、保持するタプルを時限的に出力する内部発火オペレータを抽出して、発火オペレータリストを構成し、
前記クエリの実行時点において、
前記発火オペレータリストに属する前記オペレータの発火時刻が、最も早いものからなる前記オペレータの集合を抽出して実行オペレータリストを作成し、
前記実行オペレータリストに属する前記オペレータの中で、前記オペレータに付与された前記オペレータ実行順序が最小である前記オペレータを実行することを特徴とするストリームデータ処理方法。
【請求項２】
請求項１に記載のストリームデータ処理方法であって、
前記オペレータの実行によって、結果タプルが生成された場合は、前記オペレータの出力先の前記オペレータを、前記実行オペレータリストに追加し、
再び、前記実行オペレータリストに属する前記オペレータの中で、付与された前記オペレータ実行順序が最小である前記オペレータを実行する処理を、前記実行オペレータリストが空になるまで継続する、
ことを特徴とするストリームデータ処理方法。
【請求項３】
請求項２に記載のストリームデータ処理方法であって、
前記実行オペレータリストが空になった時点で、
前記発火オペレータリストに属する前記オペレータで、前記オペレータの発火時刻が、最も早いものからなる前記オペレータの集合を抽出する繰り返し処理を継続する、
ことを特徴とするストリームデータ処理方法。
【請求項４】
タイムスタンプが付与され、前記タイムスタンプの昇順に到来する時系列データの流れであるストリームを処理するストリームデータの処理方法であって、
複数のクエリの連携によって定義されたデータ処理を、前記クエリ個々に対して、基本データ処理単位であるオペレータをノードとする実行木を作成し、作成した複数の前記実行木から単一のオペレータグラフを構築し、
前記オペレータグラフ上の全ての前記オペレータに対してオペレータ実行順序を付与する際、前記オペレータグラフを、前記オペレータの入出力関係に基づいて、入力側オペレータから出力側オペレータに向かう有向辺を持つ有向グラフに見立て、前記有向グラフを強連結成分の集合に分解し、前記強連結成分の集合に属する成分間の入出力関係に基づいて、出力側成分を構成する全ての前記オペレータに付与された前記オペレータ実行順序が、入力側成分を構成する全ての前記オペレータに付与された前記オペレータ実行順序よりも、大となるように決定し、
前記オペレータグラフから、前記オペレータグラフの外部からデータを受取る外部発火オペレータと、保持するタプルを時限的に出力する内部発火オペレータを抽出して、発火オペレータリストを構成し、
前記クエリの実行時点において、
前記発火オペレータリストに属する前記オペレータの発火時刻が、最も早いものからなる前記オペレータの集合を抽出して実行オペレータリストを作成し、前記実行オペレータリストに属する前記オペレータの中で、前記オペレータに付与された前記オペレータ実行順序が最小であるオペレータを実行する、
ことを特徴とするストリームデータ処理方法。
【請求項５】
請求項４に記載のストリームデータ処理方法であって、
前記強連結成分の集合のうち、複数の前記オペレータから構成される成分について、複数の前記オペレータのうちの任意の一つを選択して展開点オペレータとし、
前記強連結成分の集合から、前記展開点オペレータに向かう有向辺を全て削除した有向グラフについて、前記強連結成分の集合に分解し、前記強連結成分の集合に属する成分間の入出力関係に基づいて、出力側成分を構成する全ての前記オペレータに付与された前記オペレータ実行順序が、入力側成分を構成する如何なる前記オペレータに付与された前記オペレータ実行順序よりも大となるように決定し、
前記強連結成分の集合の要素が全て単一のオペレータとなるまで、再帰的に同様の方法で前記オペレータ実行順序を決定する、
ことを特徴とするストリームデータ処理方法。
【請求項６】
請求項５に記載のストリームデータ処理方法であって、
前記強連結成分における前記展開点オペレータとして、データソースから到来する前記ストリーム、またはストリーム化演算の出力であるストリームの各データのタイムスタンプを、未来に指定時間だけずらす遅延演算を選択する、
ことを特徴とするストリームデータ処理方法。
【請求項７】
請求項６記載のストリームデータ処理方法であって、
前記強連結成分において、複数の前記オペレータの中に遅延演算が存在しない場合は、前記ストリーム化演算の出力先に、遅延演算を挿入する、
ことを特徴とするストリームデータ処理方法。
【請求項８】
請求項６に記載のストリームデータ処理方法であって、
前記強連結成分において、前記複数のオペレータの中に遅延演算が存在しない場合は、クエリ定義エラーをユーザに通知する、
ことを特徴とするストリームデータ処理方法。
【請求項９】
請求項６に記載のストリームデータ処理方法であって、
前記強連結成分において、前記遅延演算はデータ処理上の仮想的な微小時間だけ、前記ストリームの各データの前記タイムスタンプを未来にずらす、
ことを特徴とするストリームデータ処理方法。
【請求項１０】
タイムスタンプが付与され、前記タイムスタンプの昇順に到来する時系列データであるストリームを処理するストリームデータ処理システムであって、
前記ストリームが入力されるネットワークインタフェースと、前記ストリームを処理する処理部とを備え、
前記処理部は、
個々のクエリに対して、基本データ処理単位であるオペレータをノードとする実行木を一つずつ作成し、作成した複数の前記実行木から単一のオペレータグラフを構築し、
前記オペレータグラフ上の全ての前記オペレータに対して、前記オペレータ間の入出力関係に基づいて、出力側オペレータに付与された実行順序が、入力側オペレータの実行順序よりも大となるよう、オペレータ実行順序を付与する、
ことを特徴とするストリームデータ処理システム。
【請求項１１】
請求項１０に記載のストリームデータ処理システムであって、
前記処理部は、
前記オペレータグラフから、前記オペレータグラフの外部からデータを受取る外部発火オペレータと、保持するタプルを時限的に出力する内部発火オペレータを抽出して、発火オペレータリストを構成し、
前記クエリの実行時点において、
前記発火オペレータリストに属する前記オペレータの発火時刻が、最も早いものからなる前記オペレータの集合を抽出して実行オペレータリストを作成し、
前記実行オペレータリストに属する前記オペレータの中で、前記オペレータに付与された前記オペレータ実行順序が最小であるオペレータを実行する、
ことを特徴とするストリームデータ処理システム。
【請求項１２】
請求項１１に記載のストリームデータ処理システムであって、
前記処理部は、
前記オペレータの実行によって結果タプルが生成された場合に、前記オペレータの出力先の前記オペレータを、前記実行オペレータリストに追加し、
再び、前記実行オペレータリストに属する前記オペレータの中で、付与された前記オペレータ実行順序が最小である前記オペレータを実行する処理を、前記実行オペレータリストが空になるまで継続し、
前記実行オペレータリストが空になった時点で、
前記発火オペレータリストに属する前記オペレータで、前記オペレータの前記発火時刻が、最も早いものからなる前記オペレータの集合を抽出する繰り返し処理を継続する、
ことを特徴とするストリームデータ処理システム。
【請求項１３】
請求項１１に記載のストリームデータ処理システムであって、
前記処理部は、
前記オペレータ実行順序を決定する際に、
前記オペレータグラフを、前記オペレータの入出力関係に基づいて、入力側オペレータから出力側オペレータに向かう有向辺を持つ有向グラフに見立てて、前記有向グラフを、強連結成分の集合に分解し、前記強連結成分の集合に属する成分間の入出力関係に基づいて、出力側成分を構成する全ての前記オペレータに付与された前記オペレータ実行順序が、入力側成分を構成する如何なる前記オペレータに付与された前記オペレータ実行順序よりも大となるように決定する、
ことを特徴とするストリームデータ処理システム。
【請求項１４】
請求項１３に記載のストリームデータ処理システムであって、
前記処理部は、
前記強連結成分における前記展開点オペレータとして、データソースから到来する前記ストリーム、またはストリーム化演算の出力であるストリームの各データのタイムスタンプを、未来に指定時間だけずらす遅延演算を選択する、
ことを特徴とするストリームデータ処理システム。
【請求項１５】
請求項１４記載のストリームデータ処理システムであって、
前記強連結成分において、複数の前記オペレータの中に遅延演算が存在しない場合は、前記ストリーム化演算の出力先に遅延演算を挿入する、
ことを特徴とするストリームデータ処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、継続的に生成される時系列データを処理する技術に関し、特に、ストリームデータ処理における、再帰的処理を含む一般のデータ処理を、安定した低レイテンシで高レートで継続的にリアルタイムに実行する技術に関する。
【背景技術】
【０００２】
株取引の自動化、交通情報処理の高度化、クリックストリームの解析といった、高いレートで継続的に発生する情報をリアルタイムに解析し、瞬時にアクションを起こす技術の進展を背景に、高レートデータのリアルタイム処理を実現する、ストリームデータ処理が注目されている。ストリームデータ処理は、様々なデータ処理に適用可能な汎用ミドルウェア技術であるため、個別案件ごとにシステムを構築するのでは間に合わないようなビジネス環境の急激な変化にも応えつつ、実世界のデータをリアルタイムにビジネスに反映することを可能とする。このストリームデータ処理の原理、実現方式は非特許文献１に開示されている。
【０００３】
ストリームデータ処理では、時間軸上における点のデータの系列であるストリームを入力し、ウィンドウ演算によって生存期間を持つデータの集合であるリレーションに変換する。リレーション上の関係演算を実施し、その結果リレーションをストリーム化演算によってストリームに戻し、出力する。リレーションはストリームデータ処理における中間状態である。ストリーム上の個々のデータをストリームタプルと呼ぶ。ストリームタプルは関係データベースのレコードと同様に、複数のカラムの組合せを値とする他に、タイムスタンプを属性として持つことが特徴となっている。ストリーム上のストリームタプルは、タイムスタンプの昇順でストリームデータ処理に入力される。
【０００４】
例として、時刻ｔ１〜ｔ６のタイムスタンプが付いた６個のストリームタプルの系列を考える。各タプルの値は文字列ｉｄと整数値ｖａｌの２つのカラムからなり、それぞれ（ａ，１），（ａ，２），（ｂ，１），（ａ，１），（ａ，２），（ｂ，３）を値としている。これに対し、ウィンドウ演算として、最大同時生存数を制限する個数ウィンドウを適用するとする。ここでは、同時生存数を３個に制限する。このとき、例えば１個目のタプルは、時刻ｔ１を始点、４個目のタプルが到着するｔ４を終点とする期間生存するデータに変換される。なお終点丁度は生存期間に含めない。その他のウィンドウ演算には、生存期間を定数時間とする時間ウィンドウ、および、特定のカラムの値が同一のストリームタプルをグループ化し、各グループ別に最大同時生存数を制限するパーティションウィンドウが存在する。
【０００５】
上記のように生存期間を定めたデータの集合であるリレーションに対する関係演算として、カラムｖａｌに対する集計演算ＳＵＭを適用する例を考える。ストリームデータ処理における関係演算では、演算に対する入力と結果のリレーションを時間軸上のある時刻で切った際の交点の集合が、従来の関係データベースの演算における入力と結果の関係と、同一になる。例えば、該例のリレーションを時刻ｔ４で切った交点のデータ値は｛（ａ，２），（ｂ，１），（ａ，１）｝となるので、その結果であるリレーションを同時刻で切った交点のデータ値は｛（４）｝となる。前者のデータ値集合を、従来の関係データベースの集計演算ＳＵＭ（ｖａｌ）で処理した結果が、後者のデータ値集合になっている。同様の関係がどの時刻においても成り立つ。
【０００６】
ある２つのリレーションについて、全ての時刻で交点のデータ値の集合が同じ場合、両リレーションは互いに合同であるという。合同なリレーションに対する関係演算の結果は、やはり合同になる。
【０００７】
上記のような関係演算の結果に対し、ストリーム化演算として、ＩＳｔｒｅａｍという演算を適用する例を考える。ストリーム化演算は、ある時刻においてリレーションの交点のデータ値集合に増減があった場合に、該時刻をタイムスタンプにして、該増減のあったデータ値をストリームタプルとして出力する。ＩＳｔｒｅａｍは増加したデータ値を出力する。その他のストリーム化演算には、減少したデータ値を出力するＤＳｔｒｅａｍ、および、定数時間毎に、生存するデータ値を出力するＲＳｔｒｅａｍが存在する。本例における演算適用の結果は、時刻ｔ１、ｔ２、ｔ３、およびｔ６に、それぞれ｛（１）｝、｛（３）｝、｛（４）｝、および｛（６）｝のストリームタプルが出力されることになる。ここで、時刻ｔ４、およびｔ５においては、ストリームタプルは出力されない。これは、関係演算の結果リレーションの時刻ｔ３〜ｔ６における時刻で切った交点は、常に｛（４）｝、即ち唯一の要素を持つ集合で、その値に変化が無いためである。このように、ストリーム化演算はデータ値の増減に基づいて処理しているので、合同なリレーションからは同一のストリームが生成されることを保証できる。但し、ある時刻におけるリレーションの全ての増減が確定するまで待たないと、該時刻における結果タプルを出力することができないという制限がある。
【０００８】
次に、ストリームデータ処理におけるクエリのデータ処理の定義方法、および、一般的な実行制御方法を説明する。ここでの記法はＣＱＬ（Ｃｏｎｔｉｎｕｏｕｓ  Ｑｕｅｒｙ  Ｌａｎｇｕａｇｅ）という宣言型言語に準ずる。ＣＱＬの文法は、関係データベースにおいて標準的に利用される、関係代数に基づくクエリ言語ＳＱＬに、ウィンドウ演算、およびストリーム化演算の記法を追加した形式をとる。ＣＱＬは非特許文献４に開示されている。
【０００９】
次は、クエリ定義の例である。
ＲＥＧＩＳＴＥＲ ＳＴＲＥＡＭ ｓ１(ｉｄ ＶＡＲＣＨＡＲ(３０)， ｖａｌ ＩＮＴ)；
ＲＥＧＩＳＴＥＲ ＳＴＲＥＡＭ ｓ２(ｉｄ ＶＡＲＣＨＡＲ(３０)， ｖａｌ ＩＮＴ)；
ＲＥＧＩＳＴＥＲ ＱＵＥＲＹ ｑ
ＲＳＴＲＥＡＭ[３０ ＳＥＣＯＮＤ](
ＳＥＬＥＣＴ ｓ１．ｉｄ ＡＳ ｉｄ１， ｓ２．ｉｄ ＡＳ ｉｄ２， ｓ１．ｖａｌ
ＦＲＯＭ ｓ１[ＲＡＮＧＥ ５ ＭＩＮＵＴＥ]， ｓ２[ＲＯＷＳ １]
ＷＨＥＲＥ ｓ１．ｖａｌ ＝ ｓ２．ｖａｌ
)；
ここで、「ＲＥＧＩＳＴＥＲ  ＳＴＲＥＡＭ」で始まる２つのコマンドは、データソースからのストリームを受け付ける入力を定義するコマンドである。
【００１０】
一番目のコマンドはｓ１という名前の入力ストリームを定義している。また、該入力ストリームで受取るデータが、ｉｄおよびｖａｌという名称のカラムを持ち、その型がそれぞれ文字列型と整数型であることを定義している。二番目のコマンドはｓ２という名前の入力ストリームを定義している。カラムの定義は入力ストリームｓ１と同じである。３番目のコマンドはクエリを定義するコマンドである。該コマンドはｑという名前のクエリを定義している。括弧“（”と“）”で囲まれた部分では、関係データベースにおけるデータ処理言語ＳＱＬと同じ文法でリレーション上の関係演算を定義する。この例では、ストリームｓ１とｓ２を、カラムｖａｌの値の一致でジョインすることを指定している。ＦＲＯＭ句には、前記入力ストリーム名、あるいは、他で定義されたクエリの名前を指定する。ストリーム名、あるいはクエリ名に続く“［”と“］”で囲まれた部分はウィンドウ演算を指定する記法である。例中の記述“ｓ１［ＲＡＮＧＥ  ５  ＭＩＮＵＴＥ］”は、入力ストリームｓ１のストリームタプルを、時間ウィンドウによって生存時間５分のデータに変換することを指定している。一方、“ｓ２［ＲＯＷＳ  １］”は、入力ストリームｓ２のストリームタプルを、個数ウィンドウによって同時生存データを最新の１個に制限することを指定している。この他に、パーティションウィンドウを指定する記法である“［ＰＡＲＴＩＴＩＯＮ  ＢＹ  カラム名リスト  ＲＯＷＳ  個数］”、および、生存期間を実時間未満の論理的な微小時間、即ち瞬間だけに制限する記法“［ＮＯＷ］”が存在する。括弧“（”と“）”で囲まれた部分の前に位置するのは、ストリーム化演算を指定する記法である。例中の記述“ＲＳＴＲＥＡＭ［３０  ＳＥＣＯＮＤ］”は、ＲＳｔｒｅａｍの使用を指定しており、３０秒ごとに生存するリレーションのデータ値をストリームタプルとして出力する。この他に、ＩＳｔｒｅａｍを指定する記法“ＩＳＴＲＥＡＭ”および、ＤＳｔｒｅａｍを指定する記法“ＤＳＴＲＥＡＭ”が存在する。
【００１１】
ストリームデータ処理では、上記のような記法で定義されたクエリを、実行木と呼ばれるデータ構造に変換して処理する。実行木は、要素データ処理を実施するオペレータの間をデータキューで連結した木構造であり、オペレータ間でパイプライン的にデータを送受することで処理を実現する。リレーション上のデータは生存期間を持つので、１データにつき生存開始と生存終了を表す２つのタプルが送受される。前者をプラスタプル、後者をマイナスタプルと呼ぶ。
【００１２】
実行木の処理においては、データ処理の順番をタイムスタンプ通りに厳守するための時刻順保証制御を実施する。例えば、前記クエリ例におけるジョインのように、２つのリレーションを対象とする演算は、実行木上では二入力のオペレータとなる。このようなオペレータは左右のキューに入力されたタプルのタイムスタンプを比較し、早い方のタプルを先に処理しなければならない。一方、２つのデータソースのうち片一方からのデータの到来が滞ると、この比較ができず、もう一方のデータの処理も停滞してしまうことになる。このような現象をストールと呼ぶ。ストールを回避するために、データソースからデータが来ない間も、時刻が進んだことを知らせるためのハートビートタプルを、実行木の葉（入力）となるオペレータから送信するのが、ストリームデータ処理において広く認知されている方法である。ハートビートを利用した実行制御方法は、非特許文献２で開示されている。
【００１３】
二項演算のみでなく、時間ウィンドウ、あるいはＲＳｔｒｅａｍといった時限発火でタプルを出力するオペレータにおいても、ハートビートタプルが必要となる。例えば、前記クエリ例における、入力ストリームｓ１に対する時間ウィンドウオペレータが、９：０３’１０にプラスタプルを受取ると、その５分後の９：０８’１０の時刻に、マイナスタプルを出力する必要がある。もし、該入力ストリームｓ１に対するデータが滞ると、このマイナスタプルを出力することができない。ハートビートタプルがこれを解決する。仮に、ハートビートタプルの送信間隔を１分とすると、該マイナスタプルは、９：０９’００のハートビートタプルによって、出力することができる。前記クエリ例におけるＲＳｔｒｅａｍについても同様である。３０秒毎にタプルを出力する指定なので、例えば９：０２’３０のストリームタプルは、９：０３’００のハートビートタプルが到来することで出力される。この時点では、９：０３’００のストリームタプルを出力することはできない。先に述べたように、ストリーム化演算は、ある時刻（この場合９：０３’００）のタプルが全て到来しないと結果を出力できないという制限があることを鑑みると、ハートビートタプルの後に続いて、さらに９：０３’００の何らかのタプルが来る可能性があるため、この時点での出力は不可となっている。
【００１４】
ストリームデータ処理では、単純に一つの入力から受取ったタプルを処理して次に流すデータフィルタ的な処理のみでなく、二項演算オペレータ、および時間ウィンドウ、ＲＳｔｒｅａｍのような精密な時刻制御を必要とする処理が存在する。ハートビートタプルは、このようなオペレータに対して、どこまでの時刻の処理を実行してよいか、即ち、実行可能時刻を通知する役割を持つ。
【００１５】
非特許文献３には、時刻情報に基づき実行木中から実行可能なオペレータを探索するアルゴリズムとして、単なるラウンドロビンや、実行可能なうち最早のタプルを出力するオペレータの実行を優先する技術が開示されている。
【００１６】
【非特許文献１】Ｂ．Ｂａｂｃｏｃｋ、Ｓ．Ｂａｂｕ、Ｍ．Ｄａｔａｒ、Ｒ．Ｍｏｔｗａｎｉ  ａｎｄ  Ｊ．Ｗｉｄｏｍ、“Ｍｏｄｅｌｓ  ａｎｄ  ｉｓｓｕｅｓ  ｉｎ  ｄａｔａ  ｓｔｒｅａｍ  ｓｙｓｔｅｍｓ”、Ｉｎ  Ｐｒｏｃ．  ｏｆ  ＰＯＤＳ  ２００２、  ｐｐ．１−１６．（２００２）
【非特許文献２】Ｔ．Ｊｏｈｏｎｓｏｎ、Ｓ．Ｍｕｔｈｕｋｒｉｓｈｎａｎ、Ｖ．Ｓｈｋａｐｅｎｙｕｋ  ａｎｄ  Ｏ．Ｓｐａｔｓｃｈｅｃｋ、“Ａ  Ｈｅａｒｔｂｅａｔ  Ｍｅｃｈａｎｉｓｍ  ａｎｄ  ｉｔｓ  Ａｐｐｌｉｃａｔｉｏｎ  ｉｎ  Ｇｉｇａｓｃｏｐｅ”、Ｉｎ  Ｐｒｏｃ．  ｏｆ  ＶＬＤＢ  ２００５、  ｐｐ．１０７９−１０８８．（２００５）
【非特許文献３】Ｂ． Ｂａｂｃｏｃｋ， Ｓ． Ｂａｂｕ， Ｍ． Ｄａｔａｒ， Ｒ． Ｍｏｔｗａｎｉ， ａｎｄ Ｄ． Ｔｈｏｍａｓ． “Ｏｐｅｒａｔｏｒ Ｓｃｈｅｄｕｌｉｎｇ ｉｎ Ｄａｔａ Ｓｔｒｅａｍ Ｓｙｓｔｅｍｓ”、（２００５）
【非特許文献４】Ａ． Ａｒａｓｕ， Ｓ． Ｂａｂｕ  ａｎｄ Ｊ． Ｗｉｄｏｍ. “Ｔｈｅ ＣＱＬ Ｃｏｎｔｉｎｕｏｕｓ Ｑｕｅｒｙ Ｌａｎｇｕａｇｅ： Sｅｍａｎｔｉｃ Ｆｏｕｎｄａｔｉｏｎｓ  ａｎｄ Ｑｕｅｒｙ Ｅｘｅｃｕｔｉｏｎ”、（２００５）
【発明の開示】
【発明が解決しようとする課題】
【００１７】
ストリームデータ処理を、今後重要となる低レイテンシ処理に適用する際に、従来のハートビートタプルによる実行方式では課題があることを、図３、および図４を用いて示す。
【００１８】
図３は、株取引クエリの単純化した例である。コマンド３０１で登録される入力ストリームｍａｒｋｅｔは株価情報を表し、カラムｓｔｏｃｋ＿ｉｄは銘柄ＩＤ、ｐｒｉｃｅは株価を表す。コマンド３０２で登録される入力ストリームｒｅｓｏｕｒｃｅ＿ｓｔｒｅａｍは資金を表し、カラムｖａｌは額面を表す。コマンド３０３で登録される入力ストリームｓｔｏｃｋ＿ｓｔｒｅａｍは保有株を表し、カラムｉｄは銘柄ＩＤ、ｎｕｍは株数、ｐｒｉｃｅは買値を表す。クエリ３１１は、ストリームｒｅｓｏｕｒｃｅ＿ｓｔｒｅａｍをリレーション化し、最新の資金額を保持する。クエリ３１４は、ストリームｓｔｏｃｋ＿ｓｔｒｅａｍをリレーション化し、銘柄毎に最新の保有株情報を保持する。クエリ３１０は、株価が一定水準を下回った銘柄があった場合、もし保有しておらず、購入資金があれば、買い注文を出す。クエリ３１３は、５分間の移動平均が買値より値を上げている保有株があれば、売り注文を出す。クエリ３１６は、買い注文と売り注文をマージし、３０秒間隔のタイミングで発注する。
【００１９】
図４は、図３に示したクエリの実行木を示す。実行木４７０，４７１，４７３，４７４，４７６は、それぞれオペレータ４００〜４０７，４１０〜４１１，４３０〜４３７，４４０〜４４１，４６０〜４６３より構成され、それぞれクエリ３１０，３１１，３１３，３１４，３１６に対応している。オペレータ間の太線はストリームを送受するキュー、細線はリレーションを送受するキューである。また、図ではデータが下から上に向かって流れることを想定している。
【００２０】
オペレータ４００，４１０，４３０，４４０はｓｃａｎオペレータであり、これらから１分間隔でハートビートタプルを送信する。図の時点で、ストリームデータ処理が持つ時計であるシステムタイムは９：１５’００であり、各ｓｃａｎオペレータからは、該時刻までのハートビートタプルが送信されている。
【００２１】
ハートビートタプルを利用する第１の問題は、データタプルの処理タイミングが、ハートビートタプルの送信間隔に律速される点である。例えば、プラスタプル４９０の５分後の９：１４’２４のタイムスタンプで時間ウィンドウオペレータ４３１から出力されるマイナスタプル４９１は、９：１５’００のハートビートタプルが到来するまで待たされることになるため、３６秒の処理タイミングの遅れとなっている。これは、クエリ３１３の売り注文を出すタイミングの遅れを意味する。一方、ＲＳｔｒｅａｍオペレータ４６３においても、ストリームタプル４９５，４９６の出力タイミングは、ハートビートタプル４９７が到来するまで待たされる。タプル４９５，４９６それぞれに関して６０秒，３０秒の処理タイミングの遅れとなっている。また、３０秒間隔で出力されるべきタプルが、１分間隔で同時に２個出力される動作になっている。これは、クエリ３１６の売り買い両注文を出すタイミングの不正を意味する。以上のように、平均してハートビートタプル送信間隔の半分の時間が、レイテンシとして現れてしまう。
【００２２】
第２の問題は、オペレータ間で処理タイミングの齟齬が発生する点である。例えば、二項オペレータ４６２の右側の入力は、データタプル４９３のタイムスタンプである９：１３’３０まで進んでいる一方、左側の入力は、データタプル４９０のタイムスタンプである９：０９’２４までしか進んでいない。該二つのタイムスタンプのずれは、タプル４９０の処理の遅れが少なくとも両時刻の差である４分６秒溜まっていることを意味している。また、左側の入力の処理が進むまで、タプル４９３の処理が停滞する。このようなオペレータ間の処理タイミングのズレも、やはりレイテンシとして現れてしまう。
【００２３】
第３の問題は、ハートビートタプルの処理コストのオーバヘッドである。データタプルと異なり、ハートビートタプルは実データではないため、その処理は本来無駄なコストである。特に、第１の問題を解決するためにハートビートの送信間隔を狭めると、ＣＰＵ負荷の増大やスループットの低下を招く可能性もある。
【００２４】
したがって、ハートビートタプルを用いずに、上記問題を解決しようとすると、あるオペレータが処理完了するたびにどのオペレータが次実行するべきかを特定しなければならない。
【００２５】
非特許文献３は、また、ストリームデータの分析結果をリアルタイムにビジネスに活用するためには、外部からの入力などの変化に対するアクションのみでなく、それに伴うストリームデータ処理システム内のデータ処理結果を含む内部状況の変化を迅速に反映して、次のアクションを決定する必要がある。このような処理を、従来のハートビートタプルによる実行方式で実現することが困難であることを、図５、および図６を用いて示す。
【００２６】
図５は、図３のクエリにおいて、購買に伴う資金の変化を反映するクエリを示す。図３のクエリと異なるのは、クエリ５１２で買い注文に伴う費用を資金から減じ、クエリ３１１に入力して最新の資金額として反映する点である。また、コマンド５０２では初期資金を入力するストリームｉｎｉｔｉａｌ＿ｒｅｓｏｕｒｃｅを定義し、クエリ５１２で資金変化とマージしている。以上により、買い注文に必要な資金額の情報を、当の買い注文の結果に基づいて変化させている。こういった、あるクエリの結果を生成するために、そのクエリ自身の結果を利用するクエリは、再帰クエリと呼ばれる。
【００２７】
図６は，このクエリの実行木を示す。実行木６７０，６７１，６７２，６７４は、それぞれオペレータ６００〜６０７，６１０，６２０〜６２６，６４０〜６４１より構成され、それぞれクエリ３１０，３１１，５１２，３１４に対応している。該実行木におけるｓｃａｎオペレータ６００，６２０，６４０からは、データタプルやハートビートタプルが出力される。しかし、これらのタプルは、それぞれ二項オペレータ６０５，６２５，６０４によって停滞する。原因は、これらのオペレータにおける他方の入力が、オペレータ６１０−６０４−６０５−６０６−６０７−６２２−６２３−６２４−６２５−６２６−６１０で形成される閉ループのパス上にあり、該ループ上を一切タプルが流れないことにある。
【００２８】
再帰クエリの実行木はこのように必ずループを持つことになる。ハートビートタプルを利用する従来の実行制御方法では、二項演算においては両入力のタプルが揃って、両タプルのタイムスタンプを比較してからでないと処理を進めることができないため、再帰クエリは実行できないことになる。
【００２９】
また、先に述べたように、ストリーム化演算はある時刻のタプルが全て到来しないと結果を出力できないという制限があるため、このような再帰クエリは、そのままでは実行不可能である。この問題を、図７を用いて示す。
【００３０】
図７は、図５のクエリを実行する際の、タプルの値、タイムスタンプ、生存期間を示している。なお、オペレータ６０２，６０４，６２５の処理については、煩雑になるため本図には含めていない。時刻ｔ０においてｒｅｓｏｕｒｃｅ＿ｓｔｒｅａｍに３００００００の値を持つストリームタプルが入力されると、個数ウィンドウオペレータ６１０によって、最新の資金額を表すｒｅｓｏｕｒｃｅリレーションに変換される。ここで、時刻ｔ１において、入力ストリームｍａｒｋｅｔにストリームタプルが入力されると、ウィンドウオペレータ６０１によって、論理的な微小時間の生存期間を持つリレーションに変換される。これと、リレーションｒｅｓｏｕｒｃｅがジョインオペレータ６０５によって結合され、射影オペレータ６０６，ストリーム化演算６０７を介して、買い注文を表すストリームｂｕｙ＿ｅｖｅｎｔのタプルとして出力される。該タプルは、オペレータ６２２，６２３，６２４を介してリレーションｒｅｓｏｕｒｃｅと結合され、買い注文を反映した新たな資金額２５２００００を表すリレーションとして出力される。該リレーションはストリーム化演算６２６によって、時刻ｔ１のタプルとしてストリームｒｅｓｏｕｒｃｅ＿ｓｔｒｅａｍに追加される。
【００３１】
しかし、実際には以上の説明のようには動作せず、処理がデッドロックする。理由は、ストリーム化演算６０７の出力が自分自身の入力に戻っているためである。ストリーム化演算６２６についても同様である。但し、もしこのデッドロックが発生しないとすると、２５２００００という値が時刻ｔ１における新たな資金額となり、再びストリームｍａｒｋｅｔとジョインされ、処理を再び一周し、その過程で全く同じ買い注文を出して、今度は２０４００００という資金額に更新される。そして、再びストリームｍａｒｋｅｔとジョインする、というように、買い注文および資金の減少が過剰に発生することになる。
【００３２】
以上のように，再帰的なクエリは，ハートビートタプルによる実行制御方法の問題，およびストリーム化演算の制限によって実行できない。
【００３３】
本発明の目的は，従来の実行制御方法におけるレイテンシに関する課題を解決する実行制御方式を用いたストリームデータ処理方法、及びそのシステムを提供することにある。
【００３４】
本発明の他の目的は，従来の実行制御方法における再帰クエリを実現できないという課題を解決し、更にはストリーム化演算の制限を回避する実行制御方式を用いたストリームデータ処理方法、及びそのシステムを提供することにある。
【課題を解決するための手段】
【００３５】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、次の通りである。
【００３６】
クエリ実行の前段階において，複数のクエリの実行木を連結した単一のオペレータグラフを形成し，このオペレータグラフの外部からタプルを入力する外部発火オペレータ，および，時間ウィンドウ, ＲＳｔｒｅａｍ といった内部発火オペレータを抽出する。本明細書では、外部発火オペレータと内部発火オペレータの両者を合わせて発火オペレータと呼ぶ。
【００３７】
そして，オペレータグラフに属する全オペレータ集合上に全順序を定める。この順序は，オペレータ間の入出力関係における出力側のオペレータが入力側のオペレータより大となるような順序付けとする。そして、本明細書においては、この順序をオペレータ実行順序と呼ぶ。
【００３８】
また、クエリ実行においては，各発火オペレータが次回実行された際に出力するタプルのタイムスタンプを，発火オペレータの発火時刻と呼ぶ。
【００３９】
このとき，本発明においては、以下のような処理のループによって，クエリの実行を制御する。
（１）発火オペレータ群において，最も早い発火時刻のオペレータを選択する。選択されたオペレータを実行オペレータと呼ぶ。また，その発火時刻を実行時刻と呼ぶ。
（２）（１）で選択した実行オペレータを起点として，オペレータ実行順序の昇順に，オペレータグラフの出口までオペレータを順次実行する。
（３）この実行時刻をタイムスタンプとするタプルの処理を全て実行し，オペレータグラフ上から該当する発火時刻のタプルが無くなったら（１）に戻る。
【００４０】
また、本発明においては、オペレータグラフがループを含む場合には，オペレータ実行順序を定めることができないので，グラフを強連結成分に分解する。強連結成分とは、有向グラフにおいて、互いに到達し合う関係にあるノードの集合である。これにより成分間にはループが存在しなくなるので，成分間の実行順序を決定することができる。さらに，成分内のオペレータ実行順序を決定するアルゴリズムを提供する。
【発明の効果】
【００４１】
本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下のとおりである。
【００４２】
全オペレータの処理を実行時刻ごとに完結しつつ実行を進めるため，処理の各ループにおいて各オペレータの実行可能時刻が自ずと決まるので，ハートビートが不要である。従って，従来の実行制御方法における，レイテンシに関する課題を解決する。即ち，
（１）レイテンシを律速する要因はない。
（２）オペレータ間で処理タイミングにズレがないため，オペレータの実行順の非決定性によるレイテンシが発生しない。
（３）データタプル以外の無駄なタプルを処理するオーバヘッドは存在しない。
【００４３】
また，再帰クエリの実行可能性に関して，実行木がループを持つため，従来のハートビートを利用する実行制御では実現不可であったが，本発明ではハートビートが不要となったことで実行が可能となる。
【発明を実施するための最良の形態】
【００４４】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において、同一の部材には原則として同一の符号を付し、その繰り返しの説明は省略する。
【００４５】
まず、図８Ａ、８Ｂ、８Ｃを用いて、本発明の基本原理を説明する。図８Ａは、図４の実行木中の各オペレータに対して、四角枠で囲む数字を付与している。この値は、後で詳述するオペレータの実行順を表している。図４と異なり、クエリの別を無視して単一の大きなオペレータグラフと捉え、該グラフ上での実行順を定めている。該実行順は自然数で、出力側のオペレータに付けられる値が入力側に付けられる値より大になるという条件を満たしている。
【００４６】
図８Ｂは、システムタイムが９：１３’３０になった際の実行の様子を示している。丁度このとき、ｓｃａｎオペレータ４４０にストリームタプル４９３が到来すると、そのタイムスタンプは９：１３’３０と付けられる。同時に、時間ウィンドウ４３１には、タイムスタンプ９：１４’２４のデータタプル４９１が、ストリーム化演算４６３には、タイムスタンプ９：１３’３０のデータタプル８００が保持されている。オペレータ４４０は外部発火オペレータであり、発火時刻は９：１３’３０となる。オペレータ４３１、および４６３は内部発火オペレータであり、それぞれの発火時刻は９：１４’２４、および９：１３’３０となる。これら発火時刻の中で最早の値が実行時刻となるので、この場合は９：１３’３０となり、該時刻と同刻の発火時刻をもつ発火オペレータ４４０、および４６３が実行オペレータとなる。該オペレータ群を起点として、四角枠内のオペレータ実行順序に従って実行していく。この例では、オペレータ４４０を起点として太曲線の矢印のパスに沿って処理が進む。ここでは、オペレータ４３５でデータがフィルタされ、オペレータ４３６，４３７，４６１の処理が実行されないと想定している。
【００４７】
実行オペレータ４４０を起点とする処理の過程で、もう一つの実行オペレータである４６３も含まれるので、該オペレータ４６３を起点とする処理が別途実行されることは無い。ここで、実行オペレータ４４０を起点とする処理に先んじて、実行オペレータ４６３を起点とする処理を実行することはできない。理由は、オペレータ４６３がストリーム化演算であり、実行時刻である９：１３’３０の全オペレータが入力に揃わないとタプルを出力することができないためである。このような、ストリーム化演算の制限を保証するために、オペレータ実行順序を、前記条件を満たすように決定する必要がある。
【００４８】
図８Ｃは、システムタイムが９：１４’２６になった際の実行の様子を示している。ｓｃａｎオペレータ４１０には、タイムスタンプ９：１４’２５のストリームタプル４９８が到来している。このとき、外部発火オペレータ４１０の発火時刻が９：１４’２５、内部発火オペレータ４３１の発火時刻が９：１４’２４となるので、その中で最早である９：１４’２４が実行時刻、オペレータ４３１が実行オペレータとなって、該オペレータを起点として太曲線の矢印のパスに沿って処理が進む。
【００４９】
以上のように、システムタイムの変化と同時に、該時刻で実行すべきオペレータの処理を全て完結する。
【００５０】
次に、図１および図２を用いて、本発明を実現するためのストリームデータ処理システムの基本構成を説明する。
【００５１】
図１に示すように、ネットワーク１０６にストリームデータ処理サーバ１００と計算機１０７、１０９、１１０が接続されている。ストリームデータ処理サーバ１００は、図２に示すように、記憶部であるメモリ１０１、処理部である中央処理部（ＣＰＵ）１０２、ネットワークＩ／Ｆ１０３、記憶部であるストレージ１０４、およびそれらを結合するバス１０５によって構成される計算機である。メモリ１０１上に、ストリームデータ処理の論理動作を定義するストリームデータ処理システム９００を配置する。ストリームデータ処理システム９００は、後で詳述するようにＣＰＵ１０２によって解釈実行可能な実行イメージである。ストリームデータ処理サーバ１００は、ネットワークＩ／Ｆ１０３を介して外部のネットワーク１０６に接続される。
【００５２】
ネットワーク１０６に接続された計算機１０７上で動作するクエリ登録コマンド実行インタフェース１０８を介して、ユーザによって定義されたクエリ９５０、およびクエリグループ定義９５１を、ストリームデータ処理サーバ１００が受取ると、ストリームデータ処理システム９００は、この定義に従ってストリームデータ処理を実行可能な実行木を自身の内部に構成する。この後、ネットワーク１０６に接続された計算機１０９上で動作するデータソース９５２によって送信されるデータを、ストリームデータ処理サーバ１００が受取ると、この実行木に従って処理し、結果データを生成する。この結果データは、ネットワーク１０６に接続された計算機１１０上で動作する結果利用アプリケーション９５３に送信する。ストレージ１０４は、ストリームデータ処理システム９００の他、一度受取ったクエリ９５０、およびクエリグループ定義９５１を保存する。ストリームデータ処理システム９００は、起動時にストレージ１０４からこの定義をロードし、実行木を構成することも可能である。
【実施例１】
【００５３】
続いて、第一の実施例のストリームデータ処理システムを図９〜図１８に従い説明する。
【００５４】
図９に第一の実施例のストリームデータ処理システム９００の詳細を示す。このストリームデータ処理システム９００は、図２に示したＣＰＵ１０２によって解釈実行される。ストリームデータ処理システム９００中、クエリ定義保存部９０２、クエリグループ定義保存部９０３、クエリ実行木保存部９０５、オペレータグラフ保存部９０７、実行制御情報保存部９０９、実行時刻保存部９１４、実行オペレータリスト９１５、実行オペレ−タフラグ配列９１７、クエリ実行ワークエリア９１９は、記憶部であるメモリ１０１やストレージ１０４上に適宜形成される。クエリ構文・意味解析部９０４、オペレータグラフ構築部９０６、オペレータグラフ解析部９０８、実行オペレータ抽出部９１３、オペレータ実行制御部９１６、クエリグループ実行木構築部９１８の各機能は、ＣＰＵ１０２で実行される。コマンド受付インタフェース９０１、ストリームタプル入力インタフェース９２０、ストリームタプル出力インタフェース９２１は、ネットワークＩ／Ｆ１０３に対応する。
【００５５】
さて、ストリームデータ処理システム９００は、コマンド受付インタフェース９０１を介して、ユーザによって定義されたクエリ９５０を受取る。この情報は、クエリ定義保存部９０２に保持される。一方、クエリ９５０のうちどのクエリを、本システムの実行制御方法の対象とするか定義する、クエリグループ定義９５１もユーザによって与えられる。この定義は、クエリグループ定義保存部９０３に保持される。なお、クエリグループ定義は、明示的にユーザが与えるのではなく、別形態で定義することも可能である。例えば、同一ファイル中に定義された複数クエリの集合を暗黙でクエリグループとする、再帰クエリを成す複数のクエリをクエリグループとする、実行スレッドが分かれるクエリを互いに疎なクエリグループとする、クエリ定義においてアノテーションで囲った部分をクエリグループとする、といったバリエーションをとることもできる。
【００５６】
個々のクエリ定義は、クエリ構文・意味解析部９０４によって実行木９０３に変換後、クエリ実行木保存部９０５に格納される。オペレータグラフ構築部９０６は、クエリグループ定義保存部９０３に保存されたクエリグループ定義９５１を参照し、一つのグループを成すクエリ群の実行木から、該実行木群を連結した単一のオペレータグラフ９３１を形成し、オペレータグラフ保存部９０７に格納する。
【００５７】
オペレータグラフ解析部９０８は、オペレータグラフ９３１におけるオペレータ間の入出力関係、およびオペレータの種別に基づき、外部発火オペレータリスト９１０、内部発火オペレータリスト９１１、オペレータ実行順表９１２を作成し、実行制御情報保存部９０９に格納する。クエリグループ実行木構築部９１８は、該クエリグループに属する実行木群とオペレータグラフに基づき、該クエリグループに属するオペレータ全てを要素とする単一の実行木である、クエリグループ実行木９３２を構築し、クエリ実行ワークエリア９１９に格納する。
【００５８】
クエリ実行時は、実行オペレータ抽出部９１３が、発火オペレータリストを構成する外部発火オペレータリスト９１０および内部発火オペレータリスト９１１を参照し、クエリグループ実行木９３２中の発火オペレータの発火時刻から、実行時刻と実行オペレータ群を求め、それぞれ実行時刻保存部９１４、および実行オペレータリスト９１５に格納する。それに続き、オペレータ実行制御部９１６が、実行時刻保存部９１４、実行オペレータリスト９１５、およびオペレータ実行順表９１２を参照し、ワークエリアとして実行オペレータフラグ配列９１７を使用し、クエリグループ実行木９３２のオペレータの実行を制御する。このように、実行オペレータ抽出部９１３と、オペレータ実行制御部９１６の処理を交互に実施することで、クエリを実行する。
【００５９】
ストリームデータ処理システム９００の外部のデータソース９５２からのデータは、ストリームタプル入力インタフェース９２０で受取り、クエリ実行ワークエリア９１９に渡す。一方、クエリの実行結果は、クエリ実行ワークエリア９１９から、ストリームタプル出力インタフェース９２１を介して、ストリームデータ処理システム９００の外部の結果利用アプリケーション９５３に送出する。
【００６０】
次に、図８Ａ、Ｂ、Ｃの実行木を例にし、図１０〜１４を用いて本実施例におけるオペレータ実行順序の決定方法を説明する。
【００６１】
図１０に示したオペレータ間入出力関係表１０００は、図８Ａ、Ｂ、Ｃに示した実行木における、各オペレータと、その出力先となるオペレータ（複数の場合もある）の対応を表している。オペレータグラフ保存部９０７のオペレータグラフ９３１から得られる。
【００６２】
図１１は、図８Ａ、Ｂ、Ｃに示した実行木における、発火オペレータのＩＤをリストで表している。１１００は外部発火オペレータリスト、１１０１は内部発火オペレータリストである。
【００６３】
本実施形態では、オペレータのうち、処理の実行契機となり得る発火オペレータは、以下のものがある。一つ目は、Ｓｃａｎオペレータで、Ｓｃａｎオペレータが、入力データタプルが到着したかを監視する。ストリームデータ処理システム９００は、入力データタプルが到着していない場合、実施例１で示すように、実行順序で定義された次の発火オペレータの監視処理を行う。
【００６４】
二つ目の発火オペレータは、DelayStreamである。DelayStreamオペレータは、再帰クエリの入力遅延が設定されたかを監視する。ＤｅｌａｙＳｔｒｅａｍオペレータは、入力タプルに対して実行時刻に対応する入力遅延を設定し、保持する。実行時刻が入力遅延設定後の時刻を経過を監視し、経過した場合、ＤｅｌａｙＳｔｒｅａｍオペレータが、保持していた入力タプルを後続のオペレータに排出し、実行順序で定義された複数のオペレータの処理を行う。入力タプルは、クエリ実行ワークエリア９１９に保持される。
【００６５】
三つ目の発火オペレータは、ＲａｎｇｅＷｉｎｄｏｗオペレータである。ＲａｎｇｅＷｉｎｄｏｗオペレターは、ウィンドウオペレータが持つテンポラリバッファに保持されるストリームデータ（データタプル）の生存期間を監視するオペレータである。このオペレーターは、ストリームデータの生存期間を監視し、生存期間を経過した時点で、実行順序で定義された複数のオペレーターの処理を開始するために、消滅を知らせるタプル（マイナスタプル）を後続オペレータに排出する。なお、テンポラリバッファは、クエリ実行ワークエリアに構成されていてもよい。
【００６６】
四つ目の発火オペレータは、ストリーム化オペレータで、ストリーム化演算する契機を監視する。
【００６７】
ストリーム化オペレータとは，CQL文で定義された関係演算の実行結果に対して，ストリーム化演算をするオペレータである。ストリーム化演算では，ストリームの生存期間から決定されるタイムスタンプを設定したタプルを生成する。ストリーム化オペレータには，IStream(出現時刻をタイムスタンプとするタプルを生成)，DStream(消滅時刻をタイムスタンプとするタプルを生成)，RStream(一定時間間隔毎に，その時刻に生存するデータについて，その時刻をタイムスタンプとしてタプルを生成)がある。
【００６８】
ストリーム化演算において，リレーションの結果は該当時刻を経過した時に初めて確定する。そのため，ストリーム化オペレータは該当時刻のタプルが確定するまでテンポラリストアに全タプルを保持する。また，該当時刻が経過したかどうかを監視し，経過した時点で発火オペレータの処理を開始すし、後続オペレータの処理が続く。
【００６９】
図１２は，オペレータグラフ解析部９０８で、オペレータ実行順序を決定するアルゴリズムのフローチャートである。また、図１３Ａは、該フローチャートにおいて使用するデータ構造である。
【００７０】
まず、図１２の処理１２０１にて、オペレータ番号を１に初期化する。この値は、オペレータ番号保存領域１３１０に格納する。フローの処理中にオペレータグラフをトラバースする過程で、オペレータの実行順が決まる度にインクリメントする。続く処理１２０２にて、全ての外部発火オペレータを、トラバーススタック１３４０にプッシュする。図８Ａ、Ｂ、Ｃの実行木に対するトラバーススタック１３４０は、外部発火オペレータリスト１１００を参照することで、図１３Ａのように初期化される。続く処理１２０３にて、オペレータ間入出力関係表よりトラバース未達入力数表を初期化する。図８Ａ、Ｂ、Ｃの実行木に対する未達入力数表は、オペレータ間入出力関係表１０００の出力先オペレータＩＤの列に、各オペレータが登場する回数として求めることができる。結果として表１３３０のように初期化される。フローの処理中にオペレータをトラバースする過程で、あるオペレータの入力となるオペレータに達すると、前者のオペレータの未達入力数をデクリメントする。
【００７１】
続く処理１２０４のループを、トラバーススタック１３４０が空になるまで繰り返す。まず、処理１２０５にて、トラバーススタック１３４０より一つのオペレータをポップする。続く処理１２０６にて、該オペレータの実行順を、その時点でオペレータ番号保存領域１３１０に格納されている値に定め、オペレータ実行順表９１２に格納する。オペレータ番号１３１０はインクリメントし、オペレータ番号保存領域１３１０に再保存する。続く処理１２０９にて、該ポップしたオペレータの出力先となるオペレータを、図１０のオペレータ間入出力関係表１０００から引き、トラバース未達入力数表１３３０における、全ての該出力先オペレータの未達入力数をデクリメントする。このとき、未達入力数が０になったオペレータがあれば、続く処理１２１０にてトラバーススタックにプッシュする。以上の処理を、トラバーススタックが空になるまで繰り返す。
【００７２】
図１３Ｂ、および図１３Ｃは、図１２のフロー処理におけるデータ構造の状態遷移を示している。図１３Ｂの状態１３５０は、トラバーススタック１３４０からオペレータ４３０をポップしてから、オペレータ４３１までトラバースし、該オペレータの出力先であるオペレータ４３３の未達入力数をデクリメントする１２０９までを処理した状態を表している。該処理１２０９において、出力先４３３の未達入力数は０にならなかったので、トラバーススタックには積まれない。オペレータ実行順表１４００は、オペレータ４３０，４３１の実行順を決定した状態となる。オペレータ番号は３までインクリメントされている。
【００７３】
同図の状態１３５１は、トラバーススタック１３４０からオペレータ４４０をポップしてから、オペレータ４３２までトラバースし、該オペレータの出力先であるオペレータ４３３の未達入力数をデクリメントし、該値が０になったのでトラバーススタック１３４０に積む１２１０までを処理した状態を表している。この過程で、オペレータ４０３の未達入力数も０になっているので、トラバーススタック１３４０に積まれている。オペレータ実行順表１４００は、実行順５まで決定し、オペレータ番号は６までインクリメントされている。
【００７４】
図１３Ｃの状態１３５２は、トラバーススタック１３４０からオペレータ４３３をポップしてから、オペレータ４６１までトラバースし、該オペレータの出力先であるオペレータ４６２の未達入力数をデクリメントする１２０９までを処理した状態を表している。オペレータ実行順表１４００は、実行順１１まで決定されている。
【００７５】
同図の状態１３５３は、トラバーススタック１３４０からオペレータ４０３をポップし、該オペレータの出力先であるオペレータ４０４の未達入力数が０にならないので、続いて、トラバーススタック１３４０からオペレータ４００をポップしてから、オペレータ４０２までトラバースし、該オペレータの出力先であるオペレータ４０５の未達入力数をデクリメントする１２０９までを処理した状態を表している。オペレータ実行順表１４００は、実行順１５まで決定されている。この状態において、トラバーススタック１３４０に残っているオペレータ４１０をポップしてからの処理では、トラバース未達入力数表１３３０の未達入力数が全て１なので、連続してトラバースされる。
【００７６】
図１４の表１４００は、図８Ａ、Ｂ、Ｃに示した実行木の例に対して、該アルゴリズムで最終的に決定されるオペレータ実行順表（図９の表９１２に
対応）あり、実行順は図８Ａ、Ｂ、Ｃ中の四角枠で囲む数字と同一である。
【００７７】
次に、図１５は、図９の実行オペレータ抽出部９１３の動作を説明するフローチャートである。まず、処理１５０１にて、実行時刻をシステムタイムに初期化する。続く処理１５０２のループを、外部発火オペレータリスト９１０、および内部発火オペレータリスト９１１の各オペレータを対象に繰り返し、全発火オペレータを処理する。
【００７８】
まず、処理１５０３にて、そのループにおける対象オペレータが、出力すべきタプルを保持しているかをチェックする。保持していない場合は、該対象オペレータに関する処理を終了する。保持している場合は、該出力すべきタプルのタイムスタンプを発火時刻とし、続く処理１５０４，１５０５にて、その時点における実行時刻と前後を比較する。該発火時刻の方が実行時刻より遅い場合は、該対象オペレータに関する処理を終了する。該発火時刻と実行時刻が同時である場合には、処理１５０７にて、その時点における実行オペレータリスト９１５に該対象オペレータを加える。該発火時刻の方が実行時刻より早い場合は、処理１５０６にて、該発火時刻を新たな実行時刻とし、その時点における実行オペレータリスト９１５を空にして、処理１５０７にて、該対象オペレータのみを実行オペレータリスト９１５に入れる。
【００７９】
図１６は、図１５のフローに従った処理における状態遷移の様子を示す。
【００８０】
状態１６１０は、図８Ｂに示すシステムタイム９：１３’３０の実行木において、処理１５０１を実行した状態である。状態１６１１は、外部発火オペレータリスト９１０について、フロー実施後の状態である。出力すべきタプルを保持し、実行時刻９：１３’３０と同じ発火時刻を持つオペレータ４４０が実行オペレータリスト１６０１（図９のリスト９１５に対応）に格納される。状態１６１２は、内部発火オペレータリスト９１１について、フロー実施後の状態である。出力すべきタプルを保持するが、発火時刻が実行時刻より遅いオペレータ４３１は実行オペレータリスト１６０１に入らず、発火時刻と実行時刻が同時刻であるオペレータ４６３は入る。
【００８１】
状態１６１３は、図８Ｃに示すシステムタイム９：１４’２６の実行木において、処理１５０１を実行した状態である。状態１６１４は、外部発火オペレータリスト９１０について、フロー実施後の状態である。出力すべきタプルを保持し、元の実行時刻９：１４’２６より早い発火時刻９：１４’２５を持つオペレータ４１０が実行オペレータリスト１６０１に格納される。実行時刻は該発火時刻に更新されている。状態１６１２は、内部発火オペレータリスト９１１について、フロー実施後の状態である。オペレータ４３１を処理１５０２のループで処理すると、出力すべきタプルを保持し、元の実行時刻９：１４’２５より早い発火時刻９：１４’２４を持つので、処理１５０３，１５０４は共にＹｅｓと判定され、処理１５０６にてその時点の実行オペレータリスト１６０１がクリアされ、実行時刻が９：１４’２４に更新され、処理１５０７にて、該オペレータ４３１のみが実行オペレータリスト１６０１に残ることになる。
【００８２】
続いて、図１７は、図９のオペレータ実行制御部９１６の動作を説明するフローチャートである。オペレータ実行制御部９１６が実行時に利用するワークエリアである、実行オペレータフラグ配列９１７は、オペレータグラフ上のオペレータ数と同じ要素数を持つ、真理値の配列である。なおインデクスの開始は１からとする。まず、初期化処理１７０１にて、実行オペレータ抽出部９１３の処理の結果、実行オペレータリスト１６０１に格納されているオペレータの、オペレータ実行順序をインデクスとする配列要素をＴｒｕｅ、それ以外の配列要素を全てＦａｌｓｅに初期化する。その後、処理１７０２のループを、インデクスをインクリメントしつつ全ての配列要素について繰り返す。まず、処理１７０３にて、配列要素がＴｒｕｅか否かを判定する。Ｆａｌｓｅである場合は、そのインデクスに関する処理を終了する。Ｔｒｕｅの場合は、処理１７０４にて、該インデクスの値を実行順序とするオペレータのＩＤを、オペレータ実行順表から取得し、該オペレータの処理を実行する。該オペレータの処理の結果、出力結果が生成されたか否かを、処理１７０５にて判定する。出力結果が無い場合は、該インデクスに関する処理を終了する。出力結果がある場合は、処理１７０６にて、出力先のオペレータに付与されたオペレータ実行順序をインデクスとする、実行オペレータフラグ配列９１７の配列要素をＴｒｕｅにする。
【００８３】
図１８は、図１７のフローに従った処理における状態遷移の様子を示す。
【００８４】
状態１８１０は、図８Ｂに示すシステムタイム９：１３’３０の実行木において、処理１７０１を実施した状態である。実行オペレータリスト１６０１には、オペレータ４４０、よび４６３が格納され、オペレータ実行順表１４００より、それぞれのオペレータ実行順序は３、および２４であることが分かるので、実行オペレータフラグ配列１８００の３番目と２４番目の要素のみをＴｒｕｅとする。状態１８１１は、処理１７０２のループにおけるインデクス４の処理１７０４にて、該インデクスをオペレータ実行順序に持つオペレータ４４１の処理を実行し、出力結果があったため、処理１７０６を実施した状態である。オペレータ４４１の出力先である、オペレータ４３２、および４０３それぞれのオペレータ実行順序である、５、および１２番目の配列要素がＴｒｕｅとなる。
【００８５】
状態１８１２は、処理１７０２のループにおけるインデクス８の処理１７０４にて、該インデクスをオペレータ実行順序に持つオペレータ４３５の処理を実行したところ、出力が無かった状態である。処理１７０２のループにおけるインデクス９，１０，１１の処理は、処理１７０３でＮｏと判定されるので何も実施されない。状態１８１３は、その後のインデクス１２の処理の結果である。状態１８１４は、処理１７０２のループを全て終了した状態である。
【００８６】
複数のクエリを一つのクエリとみなして、実行木を構築し、データタプルの時刻情報が所定の条件を満たす場合に、実行される所定のオペレータの処理を契機として、入力タプルを構築された実行木を順に実行し、処理を完了する。
【００８７】
所定のオペレータ（発火オペレータ）を含む複数のオペレータ間の実行順序をあらかじめ特定し、発火オペレータの処理実行開始可否を制御し、全体の実行木の処理を管理する。ある所定の条件を満たしているか監視し、所定の条件を満たした場合は、発火オペレータが処理を開始する。開始した場合は、そのオペレータが、開始時刻に対応するタプルについて処理を行い、処理が完了後、後続のオペレータも開始時刻に対応するタプルの処理を順次開始する。それによって、実行木内のオペレータが処理する対象のデータの時刻が一致するため、障害時のトレースが容易にできる。
【００８８】
また、本実行制御方法で構築される実行木は、登録されている複数のクエリがそれぞれＳｃａｎオペレータを先頭に有し、Ｓｔｏｒｅオペレータを末尾に有するクエリである場合、それらのクエリ間で接続される場合、前のクエリの末尾のＳｔｏｒｅオペレータと後のクエリのＳｃａｎオペレータを削除し、一つのクエリとして実行木を再構築してもよい。この場合、元のクエリ間のキューを削減でき、キュー排他による性能への影響を軽減する。
【００８９】
以上示したように、図１７のフローは配列を用いた実行制御方法である。本実施例に限らずオペレータ実行順序を守る実行制御方法として、例えば、オペレータを実行する度に、その出力先に位置するオペレータを全て記憶し、その中で最小の実行順序を持つオペレータを実行することを繰り返す方法、オペレータ実行順序を付与する対象をストリーム化演算だけに絞り、実行制御を柔軟化する方法がある。。
【実施例２】
【００９０】
以下では，第二の実施例として、再帰クエリの実行制御を行うストリームデータ処理システムについて説明する。
【００９１】
図１９は、図７において、ストリーム化オペレータ６２６の後に、ストリームタプルのタイムスタンプを未来にずらす、遅延オペレータである遅延演算１９００を挿入した様子を示している。時刻の遅延が挟まることで、ストリーム化演算の出力は、自分自身の入力に時間がずれて戻ることになるため、時刻ｔ１におけるリレーションの増減に対し、該ストリーム化演算自身の出力が影響を持つことは無くなる。このように、再帰クエリの途中に遅延演算を挟むことによって、ストリーム化演算のデッドロックを回避し、再帰クエリを実現することが可能となる。
【００９２】
遅延演算１９００により、最後の出力タプルのタイムスタンプが、ｔ１より微小時間εだけ未来にずれてストリームｒｅｓｏｕｒｃｅ＿ｓｔｒｅａｍに戻る。該微小時間は、ウィンドウ演算ＮＯＷで定める生存期間と同じとする。個数オペレータ６１０の結果であるリレーションｒｅｓｏｕｒｃｅにおいて、資金額の変化を反映したリレーション２５２００００は、時刻ｔ１＋εから始まる。ストリームｍａｒｋｅｔに対して、ウィンドウオペレータ６０１で与えられる生存期間は、丁度ｔ１＋εで終了するため、該リレーションとの結合は起こらず、過剰な買い注文は発生しない。
【００９３】
クエリに対する遅延演算の挿入は、自動であっても構わないし、明示的にクエリ定義の一部として挿入しても構わない。図２０は、明示的に遅延演算を挿入したクエリの例である。クエリ２０１２の最後に加えた“＜”と“＞”で囲まれた“ＮＯＷ”が、図５のクエリ５１２との差分であり、ストリーム化演算ＩＳｔｒｅａｍの結果を微小時間未来にずらすことを指定している。ずらす時間の幅は、１秒、１分などの具体値であっても構わない。このように、遅延演算は、時限発火のタプルを保持するオペレータであるので、時間ウィンドウやＲＳｔｒｅａｍに次ぐ、第三の内部発火オペレータである。
【００９４】
図２１は，図２０のクエリの実行木であり、オペレータ２１２７として遅延演算を含んでいる。この実行木はループを含んでおり、オペレータ間の入出力関係が相互再帰になっているため、図１０〜１４を用いて説明したアルゴリズムでは、オペレータ実行順序を定めることができない。図２１の四角枠内に示すオペレータ実行順序は、ループ上に位置しないオペレータである２１００，２１０１，２１０２，２１２０，２１２１，２１４０，２１４１，２１０３の８個については定まるが、それ以外は定義できないことを示している。
【００９５】
この問題に対し、本実施例では、ループ中に存在する遅延演算を利用して、オペレータ実行順を定める方法を提供する。該方法の基本的な考え方を、図２２Ａ、Ｂを用いて説明する。遅延演算は、ある実行時刻における処理の終点と捉えることが可能である。理由は、該実行時刻のタイムスタンプが付いたタプルが遅延演算で処理されて出力されると、該実行時刻より未来になるため、該実行時刻における処理対象から外れるからである。このことを利用し、ループ中に含まれる遅延演算を、オペレータ実行順序の起点、および終点とすることで、ループ上での同時刻タプルの処理が実現可能となる。
【００９６】
図２２Ａの実行木２２０１は、図２１の実行木において、遅延演算２１２７を、仮想的な遅延演算２２００と分離している。２１２７は遅延演算からの出力、２２００は該遅延演算への入力のみを持つオペレータである。実行木２２０１のグラフは、実行木２２０２のグラフと同型であるが、遅延演算を分離することで実行木がループを含まなくなることをより直感的に示している。ループが無くなることで、オペレータ実行順序を定義することが可能となる。最終的に、図２２Ｂの四角枠で囲む数字で示すオペレータ実行順序が定まる。以上のように、一つの遅延演算を分離してループを持たない実行木に変換することを、遅延演算でのループの展開と呼ぶ。
【００９７】
なお、図２１において、ストリーム化演算は２つあるため、どちらの先に遅延演算を入れても、あるいは両方に入れても構わない。但し、オペレータ２１０７の先だけに入ると、オペレータ２１２３〜２１２７と２１１０により構成されるループ中に遅延演算が存在しないことになってしまうので、オペレータ２１２６の後には必須である。遅延オペレータの挿入数を最小化するように、挿入位置を最適化してもよい。
【実施例３】
【００９８】
続いて、第三の実施例として、より複雑なループを持つ実行木の例を、図２３Ａ、Ｂ〜図３２を用いて説明する。
【００９９】
図２３Ａ、Ｂは、図２０のクエリにおいて、売り注文処理も再帰クエリで定義した例である。クエリ２３１５は、買い注文と売り注文による保有株情報の変化をマージする。これにより、注文による保有株情報の変化を、投資行動に迅速に反映することができる。遅延演算はクエリにおいて明示的に定義している。
【０１００】
図２４は、同クエリの実行木を示している。二つの遅延演算２４２７、および２４５７が存在する。この実行木は、オペレータ２４００，２４０１，２４０２，２４２０，２４２１，２４３０，２４３１，２４５０，２４５１の９個のオペレータを除いて巨大なループを形成している。有向グラフにおいて、このように互いに到達し合う関係にあるノードの集合を強連結成分と呼ぶ。
【０１０１】
図２５Ａは、該強連結成分に含まれない９個のオペレータについてオペレータ実行順を付与している。具体的には、１番目がオペレータ２４３０，２番目がオペレータ２４３１，３番目がオペレータ２４５０，４番目が、オペレータ２４５１、５番目がオペレータ２４００，６番目がオペレータ２４０１，７番目がオペレータ２４０２，８番目がオペレータ２４２０，９番目がオペレータ２４２１である。各オペレータの右下の四角で囲まれた数字が、それぞれのオペレータの実行順番を示す。
【０１０２】
図２５Ｂは、遅延演算２４５７で強連結成分を展開した実行木を示している。但し、破線２５０１に囲まれた１１個のオペレータは、なお強連結成分を形成している。該強連結成分を一つの仮想的なオペレータと捉えると、オペレータ実行順序１０〜２０、および３２〜３４については、定めることが可能である。破線２５０１内のオペレータには２１〜３１の実行順序が付く。図２５Ｃは、該強連結成分を遅延演算２４２７で展開し、２１〜３１の実行順序を定めた様子を示している。  最終的には、実行木に属する全オペレータの実行順序が、図２６の四角枠で囲む数字で示すように定まる。クエリ実行時において、オペレータ２４２７が実行オペレータとなった場合、該オペレータを起点とするオペレータの実行は、太曲線矢印のパスに沿って進行することになる。
【０１０３】
図２７Ａ、Ｂを用いて、より複雑なオペレータグラフにおいても同様に実行順序が定まることを示す。オペレータグラフ２７００は、ａ〜ｎの１４個のオペレータからなり、太丸は遅延演算を表す。まず、オペレータａでグラフ２７００を展開することで、ネストした強連結成分２７０１、および２７０２が抽出される。該成分をそれぞれ一つの仮想的なオペレータと捉えると、オペレータａ，ｂ，ｌ，ｎについて、オペレータ実行順序１，６，１３，１４が定まる。オペレータｅで強連結成分２７０１を展開することで、オペレータｅ，ｃ，ｍ，ｄについて、オペレータ実行順序２，３，４，５が定まる。オペレータｇで強連結成分２７０２を展開することで、ネストした強連結成分２７０３が抽出される。該成分を一つの仮想的なオペレータと捉えると、オペレータｇ，ｈ，ｆについて、オペレータ実行順序７，８，１２が定まる。オペレータｉで強連結成分２７０３を展開することで、オペレータｉ，ｊ，ｋについて、オペレータ実行順序９，１０，１１が定まる。最終的に、１４個全オペレータの実行順序が定まる。
【０１０４】
以上の処理において、各強連結成分を展開するために選択する遅延演算は任意で構わない。もし、各強連結成分が遅延演算を含まない場合は、クエリ定義のエラーとする、あるいは警告を出す、あるいは自動で挿入する、その何れであっても構わない。自動で挿入する場合には、遅延オペレータの挿入数を最小化するように、挿入位置、あるいは各強連結成分の分解における遅延演算の選択を最適化してもよい。
【０１０５】
図２８Ａ、Ｂを用いて、オペレータ実行順序を定める図１２のアルゴリズムを、ループを含む一般のオペレータグラフに適用できるよう拡張したアルゴリズムの、フローチャートを示す。
【０１０６】
まず、処理２８０１にて、実行順序０番が付くダミーオペレータを一つ作成し、対象となるオペレータグラフのオペレータ間入出力関係表に、該ダミーオペレータの出力先オペレータとして全ての外部発火オペレータを登録する。また、オペレータ番号を０に初期化する。
【０１０７】
続く処理２８０２にて、サブルーチン２８１０を呼び出す。該サブルーチンには、該ダミーオペレータを含む全てのオペレータを要素とするリストを成分オペレータリストの引数に、該ダミーオペレータをスタートノードの引数に与える。
【０１０８】
次に、サブルーチン２８１０の処理を示す。まず処理２８１１にて、引数に与えられた成分オペレータリストの要素のみからなる、部分グラフのオペレータ間入出力関係表を作成する。該表は、実行木全体のオペレータ間入出力関係表において、該成分オペレータリストの要素に関する登録のみを抽出し、該抽出した登録の出力先オペレータ列に該リストの要素以外が登場している場合はそれを削除することで、作成することができる。続く処理２８１２にて、該部分グラフのオペレータ間入出力関係表の出力先に、スタートノードが登場している場合は、全て削除する。
【０１０９】
続く処理２８１３にて、該部分グラフを強連結成分に分解し、成分間の入出力関係表を作成する。任意の有向グラフを互いに疎な強連結成分に分解する方法は、Tarjan によって考案された古典的アルゴリズムなどを利用して実現可能である。成分間入出力関係表には、ある強連結成分に属する一つ以上のオペレータから、別の強連結成分に属する一つ以上のオペレータに向かって入出力関係がある場合に、該前者成分の出力先成分として該後者成分を登録する。続く処理２８１４にて、サブルーチン２８２０を呼び出す。該サブルーチンには、該成分間入出力関係を成分間入出力関係表の引数に、該スタートノードをスタートノードの引数に与える。
【０１１０】
次に、サブルーチン２８２０の処理を示す。サブルーチン２８２０のフローは、図１２に示したフローと類似している。トラバースするグラフにおける個々のノードが、単一のオペレータのみでなく、複数のオペレータから構成される強連結成分である点が異なる。特に、単一のオペレータも強連結成分の一種である。
【０１１１】
まず、処理２８２１にて、スタートノードを、トラバーススタックにプッシュする。続く処理２８２２にて、引数に与えられた成分間入出力関係表よりトラバース未達入力数表を初期化する。フローの処理中に成分をトラバースする過程で、ある成分の入力となる成分に達すると、前者の成分の未達入力数をデクリメントする。
【０１１２】
続く処理２８２３のループを、トラバーススタックが空になるまで繰り返す。まず、処理２８２４にて、トラバーススタックより一つの成分をポップする。続く処理２８２５にて、該ポップした成分が単一のオペレータである場合は、処理２８２６にて、該オペレータの実行順を、その時点のオペレータ番号の値に定め、オペレータ実行順表に格納する。オペレータ番号はインクリメントする。処理２８２５にて、該ポップした成分が複数のオペレータからなる強連結成分である場合は、処理２８２７にて、該成分に属するオペレータのうち遅延演算を一つ選択し、続く処理２８２８にて、サブルーチン２８１０を呼び出す。該サブルーチンには、該成分に属する全オペレータのリストを成分オペレータリストの引数に、処理２８２７にて選択した該遅延演算をスタートノードの引数に与える。続く処理２８２９にて、該ポップした成分の出力先となる成分を、成分間入出力関係表から引き、トラバース未達入力数表における、全ての該出力先成分の未達入力数をデクリメントする。このとき、未達入力数が０になった成分があれば、続く処理２８３０にてトラバーススタックにプッシュする。以上の処理を、トラバーススタックが空になるまで繰り返す。
【０１１３】
つまり、（３−１）ストリームデータ処理システム９００は、複数のオペレータで構成されるオペレータグラフをそれぞれノードに展開し、tree構造から一以上のオペレータにより閉路（再帰）になっている箇所をコンポーネント化する。図２５や図２６中の強連結成分や部分グラフが、コンポーネントやサブコンポーネントに対応し、仮想的なオペレータである。（３−２）次に、ストリームデータ処理システム９００は、生成したコンポーネント単位で、コンポーネント間の入出力関係を特定する。（３−３）ストリームデータ処理システム９００は、特定された入出力関係で、コンポーネントごとの実行順序を定義する。（３−４）ストリームデータ処理システム９００は、各コンポーネントに対してオペレータが複数含むかを判断し、複数含む場合は、データタプルの入力遅延を設定するＤｅｌａyStreamを構成するオペレータを閉路に追加する。（３−５）さらにストリームデータ処理システム９００は、各コンポーネント内（閉路部分）のノードを新たなサブコンポーネントとして再展開し、同様の（３−２）ないし（３−４）の処理を繰り返す。
【０１１４】
次に、図２９〜３２を用いて、図２４のオペレータグラフを図２８のフローで処理した場合の動作を例示する。
【０１１５】
図２９の表２９００は、図２４のオペレータグラフにおけるオペレータ間入出力関係表である。処理２８０１によってダミーオペレータも登録されている。
【０１１６】
図３０Ａ〜Ｇは，図２８に示したアルゴリズムの処理における、データ構造の状態遷移を表している。
【０１１７】
図３０Ａは、サブルーチン２８２０の初回の呼び出しにおいて、処理２８２３のループに入る前の状態を示している。表３０２０は、引数に与えられる成分間入出力関係表である。成分ＩＤ３０００は、リスト３００１に示したオペレータから構成される強連結成分である。それ以外は、単一のオペレータであり、成分ＩＤはオペレータＩＤと一致する。成分（オペレータ）２４０２，２４２１，２４３１，２４５１については、それぞれの出力先オペレータ２４０５，２４２５，２４３３，２４５３が、リスト３００１に含まれているので、該表における出力先成分は３０００となる。
【０１１８】
表３０３０は、処理２８２２によって作成されるトラバース未達入力数表である。ある成分ＩＤの未達入力数は、表３０２０の出力先成分に該成分ＩＤが登場する回数となる。オペレータ番号保存領域３０１０に格納されたオペレータ番号は、この時点では処理２８０１にて０に初期化されたままである。トラバーススタック３０４０には、処理２８２１にて、スタートノード引数に与えられたダミーオペレータがプッシュされる。
【０１１９】
図３０Ｂは、サブルーチン２８２０の初回の呼び出しにおいて、処理２８２３のループ処理中の状態遷移を示している。
【０１２０】
状態３０５０は、処理２８２４にてダミーオペレータをトラバーススタック３０４０からポップし、続く処理２８２５にてオペレータと判断され、続く処理２８２６にて、オペレータ番号０を該ダミーオペレータに付与してオペレータ実行順表３１００に格納し、オペレータ番号をインクリメントし、続く処理２８２９にて、成分間入出力関係表３０２０において出力先成分に登録されている成分２４００，２４２０，２４３０，２４５０について、トラバース未達入力数表３０３０の値をデクリメントし、続く処理２８３０にて、該表３０３０の未達入力数が０になった成分２４００，２４２０，２４３０，２４５０をトラバーススタックにプッシュした状態を示している。
【０１２１】
状態３０５１は、トラバーススタック３０４０から成分２４３０をポップしてから、成分２４３１までトラバースし、該成分の出力先である成分３０００の未達入力数をデクリメントする２８２９までを処理した状態を表している。該処理２８２９において、出力先３０００の未達入力数は０にならなかったので、トラバーススタックには積まれない。オペレータ実行順表３１００は、オペレータ２４３０，２４３１の実行順を決定した状態となる。オペレータ番号は３までインクリメントされている。
【０１２２】
状態３０５２は、トラバーススタック３０４０に積まれている全ての成分２４５０，２４００，２４２０について処理が終了し、成分３０００の未達入力数が０になったので、トラバーススタックにプッシュされた状態を表している。オペレータ実行順序は９まで決定し、オペレータ実行順表３１００に格納され、オペレータ番号は１０までインクリメントされている。
【０１２３】
この後、続く処理２８２３のループでは、処理２８２４にて成分３０００をトラバーススタック３０４０からポップし、続く処理２８２５にて該成分がＮｏと判断され、続く処理２８２７にて成分３０００に属するオペレータから一つの遅延演算２４５７を選択し、続く処理２８２８にて、成分３０００に属するオペレータのリスト３００１を成分オペレータリストの引数に、該遅延演算２４５７をスタートノードの引数に与えて、サブルーチン２８１０を呼ぶ。
【０１２４】
該サブルーチン呼び出しの処理では、処理２８１１にて、引数に与えられた成分オペレータリスト(この場合、リスト３００１)の要素であるオペレータのみで構成される、部分グラフのオペレータ間入出力関係表を作成する。
【０１２５】
図３０Ｃに示す表２９０１が、該作成された表である。続く処理２８１２にて、引数に与えられたスタートノードである遅延演算２４５７が、表２９０１においてオペレータ２４５６の出力先に含まれているので、削除する。続く処理２８１３にて、図３０Ｄに示す成分間入出力関係表３０２１を作成する。続く処理２８１４にて、該表を成分間入出力関係表の引数に、遅延演算２４５７をスタートノードの引数に与えて、サブルーチン２８２０を呼び出す。
【０１２６】
図３０Ｄは、該サブルーチン呼び出しにおいて、処理２８２２までを実行した状態を表す。図３０Ｅに示す状態３０５３は、トラバーススタック３０４１から成分２４５７をポップし、成分２４５３までトラバースし、該オペレータの出力先であるオペレータ２４５５の未達入力数をデクリメントした状態を表している。この過程で、オペレータ２４０３の未達入力数も０になっているので、トラバーススタック３０４１に積まれている。オペレータ実行順表３１００は、実行順１９まで決定している。
【０１２７】
状態３０５４は、トラバーススタック３０４１から成分２４０３をポップし、処理２８２６まで処理し、処理２８２９にて該成分の出力先である成分３００２の未達入力数をデクリメントし、該値が０になったので、処理２８３０にて成分３００２をトラバーススタック３０４１にプッシュした状態を表している。
【０１２８】
この後、続く処理２８２３のループでは、処理２８２４にて成分３００２をトラバーススタック３０４１からポップし、続く処理２８２５にて該成分がＮｏと判断され、続く処理２８２７にて成分３００２に属するオペレータから一つの遅延演算２４２７を選択し、続く処理２８２８にて、成分３００２に属するオペレータのリスト３００３を成分オペレータリストの引数に、該遅延演算２４２７をスタートノードの引数に与えて、サブルーチン２８１０を呼ぶ。
【０１２９】
該サブルーチン呼び出しの処理では、処理２８１１にて、引数に与えられた成分オペレータリスト(この場合、リスト３００３)の要素であるオペレータのみで構成される、部分グラフのオペレータ間入出力関係表を作成する。図３０Ｆに示す表２９０２が、該作成された表である。続く処理２８１２にて、引数に与えられたスタートノードである遅延演算２４２７が、表２９０２においてオペレータ２４２６の出力先に含まれているので、削除する。続く処理２８１３にて、成分間入出力関係表３０２２を作成する。続く処理２８１４にて、該表を成分間入出力関係表の引数に、遅延演算２４２７をスタートノードの引数に与えて、サブルーチン２８２０を呼び出す。
【０１３０】
図３０Ｆは、該サブルーチン呼び出しにおいて、処理２８２２までを実行した状態を表す。状態３０５５は、トラバーススタック３０４２から成分２４２７をポップして、成分２４２６までトラバースし、全ての成分のオペレータ実行順序が決定され、トラバーススタック３０４２が空になった状態を表す。オペレータ実行順表３１００は、実行順３１まで決定している。
【０１３１】
サブルーチン２８２０の処理は以上で終了し、呼び出し元の処理２８１４に返る。サブルーチン２８１０の処理は以上で終了し、呼び出し元の処理２８２８に返る。続く処理２８２９にて、成分３００２の出力先である成分２４５４の未達入力数をデクリメントすると０になるので、続く処理２８３０にて該成分をトラバーススタック３０４１にプッシュする。図３０Ｇに示す状態３０５６は、ここまでの処理が完了した状態を表す。
【０１３２】
状態３０５７は、トラバーススタック３０４１から成分２４５４をポップして、成分２４５６までトラバースし、全ての成分のオペレータ実行順序が決定され、トラバーススタック３０４１が空になった状態を表す。
【０１３３】
サブルーチン２８２０の処理は以上で終了し、呼び出し元の処理２８１４に返る。サブルーチン２８１０の処理は以上で終了し、呼び出し元の処理２８２８に返る。成分間入出力関係表３０２０において、成分３０００の出力先成分は存在しないので、続く処理２８２９，２８３０は何も実行されない。この時点で、トラバーススタック３０４０は空になる。
【０１３４】
サブルーチン２８２０の処理は以上で終了し、呼び出し元の処理２８１４に返る。サブルーチン２８１０の処理は以上で終了し、呼び出し元の処理２８０２に返る。続く処理２８０３にて、オペレータ間入出力関係表、およびオペレータ実行順表から、ダミーオペレータについての登録を削除する。以上で、該フローチャートの処理が完了する。
【０１３５】
図３１の表３１００は、図２４に示した実行木の例に対して、該アルゴリズムで最終的に決定されるオペレータ実行順表である。
【０１３６】
また、図３２は、図２４に示した実行木における、発火オペレータのＩＤをリストで表している。３２００は外部発火オペレータリスト、３２０１は内部発火オペレータリストである。内部発火オペレータリストには、遅延演算である２４２７、および２４５７が含まれる。
【０１３７】
以上説明した、ループを含むオペレータグラフに対するオペレータ実行順序の決定アルゴリズムは、ループを含まないオペレータグラフにも適用できることは明らかである。図２８のフローチャートで示したアルゴリズムは、図１２のフローチャートで示したアルゴリズムの一般化である。
【０１３８】
なお、クエリ実行時に動作する図１５、および図１７に示したフローチャートは、再帰クエリと非再帰のクエリに共通して適用可能である。
【０１３９】
以上詳述した本発明のストリームデータ処理におけるオペレータ実行制御方法により、低レイテンシのデータ処理を実現することが可能である。特に、再帰クエリを含む一般のクエリに適用可能である。また、数々の実施例に基づき具体的に説明したが、本発明はこれらの実施例に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【０１４０】
本発明は、自動株取引、交通情報解析、製造機器の制御、クリックストリーム解析といった、安定した低レイテンシでのデータ解析が必要となる技術において、株取引における株価、あるいは交通情報処理における車間距離といった外部情報のみならず、資金額の変化、車両位置の変化といった、内部状態の変化も、解析処理の対象として迅速に反映する必要がある場合の、データ解析技術に適している。
【図面の簡単な説明】
【０１４１】
【図１】ストリームデータ処理サーバが動作する計算機環境の一例を示す図である。
【図２】ストリームデータ処理サーバの構成の一例を示す図である。
【図３】ストリームデータ処理におけるデータ処理定義の一例を示す図である。
【図４】図３のデータ処理定義の従来技術での実現方法を示す説明図である。
【図５】ストリームデータ処理におけるデータ処理定義の一例を示す図である。
【図６】図５のデータ処理定義の実現の課題を示す説明図である。
【図７】図５のデータ処理定義の実現の課題を示す説明図である。
【図８Ａ】本発明における図３のデータ処理定義の実現方法の説明図である。
【図８Ｂ】本発明における図３のデータ処理定義の実現方法の説明図である。
【図８Ｃ】本発明における図３のデータ処理定義の実現方法の説明図である。
【図９】第一の実施例に係わる、ストリームデータ処理システムの構成例を示すブロック図である。
【図１０】第一の実施例に係わる、オペレータ実行順序の決定のために利用するデータ構造の説明図である。
【図１１】第一の実施例に係わる、オペレータ実行順序の決定のために利用するデータ構造の説明図である。
【図１２】第一の実施例に係わる、オペレータ実行順序の決定のフローチャートを示す図である。
【図１３Ａ】図１２のフローチャートで利用するデータ構造の説明図である。
【図１３Ｂ】図１２のフローチャートで利用するデータ構造の説明図である。
【図１３Ｃ】図１２のフローチャートで利用するデータ構造の説明図である。
【図１４】第一の実施例で決定されるオペレータ実行順序を示す表である。
【図１５】第一の実施例に係わる、オペレータ実行制御のフローチャートを示す図である。
【図１６】図１５のフローチャートで利用するデータ構造の説明図である。
【図１７】第一の実施例に係わる、オペレータ実行制御のフローチャートを示す図である。
【図１８】図１７のフローチャートで利用するデータ構造の説明図である。
【図１９】第二の実施例による図７の課題の解決方法の説明図である。
【図２０】第二の実施例に係わる、ストリームデータ処理におけるデータ処理定義の例を示す図である。
【図２１】図２０のデータ処理定義の実現方法の説明図である。
【図２２Ａ】図２０のデータ処理定義の実現方法の説明図である。
【図２２Ｂ】図２０のデータ処理定義の実現方法の説明図である。
【図２３Ａ】第三の実施例に係わる、ストリームデータ処理におけるデータ処理定義の例である。
【図２３Ｂ】第三の実施例に係わる、ストリームデータ処理におけるデータ処理定義の例である。
【図２４】図２３Ａ、Ｂのデータ処理定義の実現方法の説明図である。
【図２５Ａ】図２３Ａ、Ｂのデータ処理定義の実現方法の説明図である。
【図２５Ｂ】図２３Ａ、Ｂのデータ処理定義の実現方法の説明図である。
【図２５Ｃ】図２３Ａ、Ｂのデータ処理定義の実現方法の説明図である。
【図２６】図２３Ａ、Ｂのデータ処理定義の実現方法の説明図である。
【図２７Ａ】第三の実施例におけるオペレータ実行順序の決定方法の説明図である。
【図２７Ｂ】第三の実施例におけるオペレータ実行順序の決定方法の説明図である。
【図２８Ａ】第三の実施例におけるオペレータ実行順序の決定のフローチャートを示す図である。
【図２８Ｂ】第三の実施例におけるオペレータ実行順序の決定のフローチャートを示す図である。
【図２９】図２８Ａ、Ｂのフローチャートで利用するデータ構造の説明図である。
【図３０Ａ】図２８Ａ、Ｂのフローチャートで利用するデータ構造の説明図である。
【図３０Ｂ】図２８Ａ、Ｂのフローチャートで利用するデータ構造の説明図である。
【図３０Ｃ】図２８Ａ、Ｂのフローチャートで利用するデータ構造の説明図である。
【図３０Ｄ】図２８Ａ、Ｂのフローチャートで利用するデータ構造の説明図である。
【図３０Ｅ】図２８Ａ、Ｂのフローチャートで利用するデータ構造の説明図である。
【図３０Ｆ】図２８Ａ、Ｂのフローチャートで利用するデータ構造の説明図である。
【図３０Ｇ】図２８Ａ、Ｂのフローチャートで利用するデータ構造の説明図である。
【図３１】第三の実施例において決定されるオペレータ実行順序を示す表である。
【図３２】図２８Ａ、Ｂのフローチャートで利用するデータ構造の説明図である。
【符号の説明】
【０１４２】
４００〜４６３，６００〜６４１，２１００〜２１２７，２４００〜２４５７…オペレータ
３０１〜３１６，５０２，５１２，２０１２，２３０３，２３１５…クエリ登録コマンド
９００…ストリームデータ処理システム
９０８…オペレータグラフ解析部
９０９…実行制御情報保存部
９１３…実行オペレータ抽出部
９１６…オペレータ実行制御部
９３１…オペレータグラフ
１１００，３２００…外部発火オペレータリスト
１１０１，３２０１…内部発火オペレータリスト
１０００，２９００…オペレータ間入出力関係表
１４００，３１００…オペレータ実行順表。
【図１】
2010108152.tif 000003
【図２】
2010108152.tif 000004
【図３】
2010108152.tif 000005
【図４】
2010108152.tif 000006
【図５】
2010108152.tif 000007
【図６】
2010108152.tif 000008
【図７】
2010108152.tif 000009
【図８Ａ】
2010108152.tif 000010
【図８Ｂ】
2010108152.tif 000011
【図８Ｃ】
2010108152.tif 000012
【図９】
2010108152.tif 000013
【図１０】
2010108152.tif 000014
【図１１】
2010108152.tif 000015
【図１２】
2010108152.tif 000016
【図１３Ａ】
2010108152.tif 000017
【図１３Ｂ】
2010108152.tif 000018
【図１３Ｃ】
2010108152.tif 000019
【図１４】
2010108152.tif 000020
【図１５】
2010108152.tif 000021
【図１６】
2010108152.tif 000022
【図１７】
2010108152.tif 000023
【図１８】
2010108152.tif 000024
【図１９】
2010108152.tif 000025
【図２０】
2010108152.tif 000026
【図２１】
2010108152.tif 000027
【図２２Ａ】
2010108152.tif 000028
【図２２Ｂ】
2010108152.tif 000029
【図２３Ａ】
2010108152.tif 000030
【図２３Ｂ】
2010108152.tif 000031
【図２４】
2010108152.tif 000032
【図２５Ａ】
2010108152.tif 000033
【図２５Ｂ】
2010108152.tif 000034
【図２５Ｃ】
2010108152.tif 000035
【図２６】
2010108152.tif 000036
【図２７Ａ】
2010108152.tif 000037
【図２７Ｂ】
2010108152.tif 000038
【図２８Ａ】
2010108152.tif 000039
【図２８Ｂ】
2010108152.tif 000040
【図２９】
2010108152.tif 000041
【図３０Ａ】
2010108152.tif 000042
【図３０Ｂ】
2010108152.tif 000043
【図３０Ｃ】
2010108152.tif 000044
【図３０Ｄ】
2010108152.tif 000045
【図３０Ｅ】
2010108152.tif 000046
【図３０Ｆ】
2010108152.tif 000047
【図３０Ｇ】
2010108152.tif 000048
【図３１】
2010108152.tif 000049
【図３２】
2010108152.tif 000050