ストリームデータのランキングクエリ処理方法およびランキングクエリ処理機構を有するストリームデータ処理システム
【課題】 （１）ウィンドウへのストリームデータの挿入に加えて、データの消滅の際にも整合性を保つためのランキング計算機構を実現する。
（２）ストリームデータ処理システムの汎用性を確保するため、アプリケーションにランキング計算結果を渡すための汎用インタフェース、およびそのインタフェースに従った出力機構を実現する。
【解決手段】 （１）ウィンドウへのストリームデータの挿入時、削除時に生成されるストリームタプルの符号を利用して順位情報を管理する機構を提供する。
（２）ランキング計算結果の差分情報のみを生成する機構、要求に応じて順位情報を付加する機構、さらに差分情報からランキング全体情報を生成する出力するインタフェース、ランキング計算結果の全体を生成する機構、およびこれらの機構を利用するためのインタフェースを提供する。
（２）ストリームデータ処理システムの汎用性を確保するため、アプリケーションにランキング計算結果を渡すための汎用インタフェース、およびそのインタフェースに従った出力機構を実現する。
【解決手段】 （１）ウィンドウへのストリームデータの挿入時、削除時に生成されるストリームタプルの符号を利用して順位情報を管理する機構を提供する。
（２）ランキング計算結果の差分情報のみを生成する機構、要求に応じて順位情報を付加する機構、さらに差分情報からランキング全体情報を生成する出力するインタフェース、ランキング計算結果の全体を生成する機構、およびこれらの機構を利用するためのインタフェースを提供する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時々刻々と到来するストリームデータをリアルタイムに処理するストリームデータ処理システムにおける、ランキング計算方法、および該計算方法を有するストリームデータ処理システムに関する。
【背景技術】
【０００２】
従来、企業情報システムのデータ管理の中心にはデータベース管理システム（以下、ＤＢＭＳとする）が位置づけられていた。ＤＢＭＳは、処理対象のデータをストレージに格納し、格納したデータに対してトランザクション処理に代表される高信頼な処理を実現している。これに対して、時々刻々と到着する大量のデータをリアルタイム処理するデータ処理システムに対する要求が高まっている。例えば、株取引を支援するファイナンシャルアプリケーションを考えた場合、株価の変動にいかに迅速に反応できるかがシステムの最重要の課題の一つである。従来のＤＢＭＳのように株式のデータを一旦記憶装置に格納してから、該格納データに関して検索を行うようなシステムでは、データの格納とそれに続く検索処理が株価変動のスピードに追いつくことができず、ビジネスチャンスを逃してしまうことになりかねない。例えば、米国特許５４９５６００号（特許文献１）では、記憶されているクエリが周期的に実行される機構を開示しているが、この機構においても前述の株価のようにデータが入ってきた瞬間にクエリを実行することが重要となる。すなわちクエリの実行周期とデータ処理のタイミングのずれが許容できないので、前記のファイナンシャルアプリケーションに代表されるリアルタイムデータ処理には適用が困難であった。Ｊａｖａ（Ｒ）に代表されるプログラミング言語を用いて、各種のリアルタイムアプリケーションを個別に作りこむアプローチは、開発期間の長期化、開発コストの高騰、該アプリケーションを利用する業務の変化への迅速な対応が難しいなどの問題があり、汎用のリアルタイムデータ処理機構が求められるようになっていた。
【０００３】
このようなリアルタイムデータ処理に好適なデータ処理システムとして、ストリームデータ処理システムが提案されている。例えばＲ． Ｍｏｔｗａｎｉ、 Ｊ． Ｗｉｄｏｍ、 Ａ． Ａｒａｓｕ、 Ｂ． Ｂａｂｃｏｃｋ、 Ｓ． Ｂａｂｕ、 Ｍ． Ｄａｔａｒ、 Ｇ． Ｍａｎｋｕ、 Ｃ． Ｏｌｓｔｏｎ、 Ｊ． Ｒｏｓｅｎｓｔｅｉｎ、 ａｎｄ Ｒ． Ｖａｒｍａ著：“Ｑｕｅｒｙ Ｐｒｏｃｅｓｓｉｎｇ、 Ｒｅｓｏｕｒｃｅ Ｍａｎａｇｅｍｅｎｔ、 ａｎｄ Ａｐｐｒｏｘｉｍａｔｉｏｎ ｉｎ ａ Ｄａｔａ Ｓｔｒｅａｍ Ｍａｎａｇｅｍｅｎｔ Ｓｙｓｔｅｍ”、Ｉｎ Ｐｒｏｃ． ｏｆ ｔｈｅ ２００３ Ｃｏｎｆ． ｏｎ Ｉｎｎｏｖａｔｉｖｅ Ｄａｔａ Ｓｙｓｔｅｍｓ Ｒｅｓｅａｒｃｈ （ＣＩＤＲ）、 Ｊａｎｕａｒｙ ２００３ （非特許文献１）にストリームデータ処理システムＳＴＲＥＡＭが開示されている。
【０００４】
ストリームデータ処理システムでは、従来のＤＢＭＳとは異なり、まずクエリ（問合せ）をシステムに登録し、データの到来と共に該クエリが継続的に実行される。ここでのストリームデータとは、映像ストリームのような論理的に継続する一つの大きなデータではなく、ファイナンシャルアプリケーションにおける株価配信データ、小売業でのＰＯＳデータ、交通情報システムにおけるプローブカーデータ、計算機システム管理におけるエラーログ、センサやＲＦＩＤなどのユビキタスデバイスから発生するセンシングデータなど、比較的小さな論理的には独立した大量の時系列データである。ストリームデータは継続してシステムに到着し続けるため、その終わりを待ってから処理を開始するのでは実時間での処理は不可能である。また、システムに到着したデータは、データ処理の負荷に影響されることなく、その到着順を守って処理する必要がある。前記ＳＴＲＥＡＭでは、システムに到来し続けるストリームデータを、最新１０分間などの時間の幅、もしくは最新１０００件などの個数の幅を指定してストリームデータの一部を切り取りながらリアルタイムの処理を実現するため、スライディングウィンドウ（以下単にウィンドウと呼ぶ）と呼ばれる概念を導入している。ウィンドウ指定を含むクエリの記述言語の好適な例としては非特許文献１に開示されているＣＱＬ（Ｃｏｎｔｉｎｕｏｕｓ Ｑｕｅｒｙ Ｌａｎｇｕａｇｅ）をあげることができる。ＣＱＬは、ＤＢＭＳで広く用いられているＳＱＬ（Ｓｔｒｕｃｔｕｒｅｄ Ｑｕｅｒｙ Ｌａｎｇｕａｇｅ）のＦＲＯＭ句に、ストリーム名に続いて括弧を用いることにより、ウィンドウを指定する拡張が施されている。ＳＱＬに関しては、Ｃ． Ｊ． Ｄａｔｅ、 Ｈｕｇｈ Ｄａｒｗｅｎ著：“Ａ Ｇｕｉｄｅ ｔｏ ＳＱＬ Ｓｔａｎｄａｒｄ （４ｔｈ Ｅｄｉｔｉｏｎ）”、Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ Ｐｒｏｆｅｓｓｉｏｎａｌ； ４ ｅｄｉｔｉｏｎ （Ｎｏｖｅｍｂｅｒ ８、 １９９６）、ＩＳＢＮ： ０２０１９６４２６０（非特許文献２）が詳しい。
【０００５】
図１２のクエリ１２０１は非特許文献１の２．１節に示されているＣＱＬによるクエリの例である。該クエリでは、あるＷｅｂプロキシサーバにおいて、ドメインｓｔａｎｆｏｒｄ．ｅｄｕからの現時点から過去１日分のアクセスの総数を計算する。Ｒｅｑｕｅｓｔsは前記Ｗｅｂプロキシサーバに到来し続けるＷｅｂアクセスデータであり、従来のＤＢＭＳで取り扱うテーブル（表）のような静止化されたデータではなく、切れ目のないストリームデータとなる。そのため、アクセスの総数を計算は、ウィンドウ指定“［Ｒａｎｇｅ １ Ｄａｙ Ｐｒｅｃｅｄｉｎｇ］”による、ストリームデータのどの部分を対象とするかの指定なしでは、不可能となる。ウィンドウによって切り取られたストリームデータはメモリ上に保持され、クエリ処理に使用される。代表的なウィンドウの指定方法には、ウィンドウの幅を時間で指定するＲａｎｇｅウィンドウと、ウィンドウの幅をデータ数で指定するＲｏｗウィンドウがある。例えば、Ｒａｎｇｅウィンドウを用いて、［Ｒａｎｇｅ １０ ｍｉｎｕｔｅｓ］とすると、最新の１０分間分がクエリ処理の対象となり、Ｒｏｗウィンドウを用いて［Ｒｏｗｓ １０］とすると、最新の１０件がクエリ処理の対象となる。
【０００６】
ストリームデータ処理システムは、ファイナンシャルアプリケーション、小売業での売り上げモニタリング、交通情報システム、計算機システム管理に代表される、リアルタイム処理が必要とされる応用に対する適用が期待されている。以下、リアルタイム処理を必要とする応用をリアルタイムアプリケーションと呼ぶ。リアルタイムアプリケーションにおいては、膨大な情報から瞬時に重要度の高い情報を取り出すために、ある瞬間でのランキング計算が必要とされる場合が多い。例えばファイナンシャルアプリケーションでは、株価の値動きや取引量が大きい株に注目するためのランキング情報が重要であり、小売業の売り上げモニタリングでは、店舗別、商品別など様々な角度からの売上高、売上数のランキング情報が注目される。また、交通情報システムでは、渋滞度が高い、通行量が多い地区に注目するためのランキング情報が必要となり、計算機管理においても、重大なエラーの数、アクセス数など、管理対象の優先度をつけるためのランキング情報が必須となる。
【０００７】
ランキング計算対象のデータが静止化されている場合、すなわちランキング付けしようとするデータが変更されない場合には、該データをランキング付けしようとするキー（以下、ランキングキー）でソーティングし、ソーティング結果の順位に従って、データを出力すればよい。例えば、データベースに格納されている株価の売上高の上位１０位のランキング情報を計算する際には、その日の各銘柄別の売上高を集計し、売上高をランキングキーとして集計した結果をソートし、上位の１０件を選択して出力すればよい。ユーザが投入したクエリからランキングキー（前述の例では売上高）を自動的に決定する方法が米国特許７２５１６４８号（特許文献２）で開示されている。米国公開特許ＵＳ２００６／０２５９４５７号（特許文献３）では、ＤＢＭＳのクエリで最初のｎ行のみを出力する指定があった場合に、クエリ処理時に条件を追加することによって余分なデータ処理のコストを削減する方法が開示されている。また、前記ＳＱＬでは銘柄別の分類のためのＧＲＯＵＰ ＢＹ句、売上高の総計を計算するための集計関数ＳＵＭ、集計値に基づいてソーティングを実行するＯＲＤＥＲ ＢＹ句が準備されている。これらを組合せることで、データベースに格納されている一日の株取引データから売上高の高い順（もしくは低い順）のランキング計算結果を生成することができる。
【０００８】
しかしながら、前記リアルタイムアプリケーションにおいては、新しいデータ（ストリームデータ）が次々に到来し続けるため、その静止化は困難である。ＤＢＭＳを用いて、リアルタイムアプリケーション向けのランキング計算を実施しようとする場合、ストリームデータが到来するごとに該データをＤＢＭＳに格納し、ＤＢＭＳで前記の分類、集計、ソーティング処理を行う必要がある。これらの処理では、基本的にデータベース内の大量のデータにアクセスする必要があり、処理コストが高い。そのため、リアルタイムアプリケーションから発生するストリームデータが高速で到来する場合、すなわちストリームデータの到来する時間間隔が短い場合には、該時間間隔内での処理の実行は不可能であり、ＤＢＭＳを用いたリアルタイムアプリケーション向けのランキング計算の実現は困難であった。
【０００９】
前述したように、ストリームデータ処理システムでは、無限に続くストリームデータから、処理の対象を前述のウィンドウで切り取って処理している。処理対象のデータは、ウィンドウ中に存在するデータのみであり、ウィンドウから押し出されたデータはランキング処理の対象から削除する必要がある。ウィンドウからデータが押し出されるタイミングは、ウィンドウの指定方法が時間である（前述のＲａｎｇｅウィンドウ）か、件数である（前述のＲｏｗウィンドウ）かによって異なる。件数指定の場合、処理対象のデータがウィンドウから押し出される時刻は、該データがウィンドウに入った瞬間には決定できず、後続のストリームデータによって決定される。一方、時間指定の場合には、処理対象のデータがウィンドウから押し出される時刻は、該データがウィンドウに入った瞬間に決定できるが、その消去タイミング（ウィンドウから押し出されるタイミング）は、後続のデータとは同期しない。
【００１０】
ランキング計算においては、ウィンドウへのストリームデータの挿入の都度、ランキング計算を実行してランキング情報の整合性を保つ必要がある。それに加えて、ウィンドウからのデータの消滅の際にも同様にランキング情報の整合性を保つことが必要となる。とくにウィンドウが時間指定の場合には、後続のデータ到来とは同期しないウィンドウからのデータの消滅タイミングを考慮してランキング計算を実行する必要がある。
【００１１】
さらに、ランキング計算では、処理の効率化によって、ストリームデータ処理システム利用の重要な目的の一つであるリアルタイム処理の制約を守る必要がある。加えて、ストリームデータ処理システムは汎用のデータ処理基盤であるため、ランキング計算結果の差分情報のみを渡す、ランキング計算結果全体を渡す、ランキング計算結果に順位情報を含めるなど利用するアプリケーションの要求に応えるための汎用のインタフェース、そのインタフェースに従う処理を実現する機構を準備する必要がある。以上の条件を満足するストリームデータ処理システム向けのランキング計算方法はこれまで実現されていなかった。
【００１２】
【特許文献１】米国特許５４９５６００号
【特許文献２】米国特許７２５１６４８号
【特許文献３】米国公開特許ＵＳ２００６／０２５９４５７号
【特許文献４】特開２００６−３３８４３２号
【非特許文献１】Ｒ． Ｍｏｔｗａｎｉ、 Ｊ． Ｗｉｄｏｍ、 Ａ． Ａｒａｓｕ、 Ｂ． Ｂａｂｃｏｃｋ、 Ｓ． Ｂａｂｕ、 Ｍ． Ｄａｔａｒ、 Ｇ． Ｍａｎｋｕ、 Ｃ． Ｏｌｓｔｏｎ、 Ｊ． Ｒｏｓｅｎｓｔｅｉｎ、 ａｎｄ Ｒ． Ｖａｒｍａ著：“Ｑｕｅｒｙ Ｐｒｏｃｅｓｓｉｎｇ、 Ｒｅｓｏｕｒｃｅ Ｍａｎａｇｅｍｅｎｔ、 ａｎｄ Ａｐｐｒｏｘｉｍａｔｉｏｎ ｉｎ ａ Ｄａｔａ Ｓｔｒｅａｍ Ｍａｎａｇｅｍｅｎｔ Ｓｙｓｔｅｍ”、Ｉｎ Ｐｒｏｃ． ｏｆ ｔｈｅ ２００３ Ｃｏｎｆ． ｏｎ Ｉｎｎｏｖａｔｉｖｅ Ｄａｔａ Ｓｙｓｔｅｍｓ Ｒｅｓｅａｒｃｈ （ＣＩＤＲ）、 Ｊａｎｕａｒｙ ２００３
【非特許文献２】Ｃ． Ｊ． Ｄａｔｅ、 Ｈｕｇｈ Ｄａｒｗｅｎ著：“Ａ Ｇｕｉｄｅ ｔｏ ＳＱＬ Ｓｔａｎｄａｒｄ （４ｔｈ Ｅｄｉｔｉｏｎ）”、Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ Ｐｒｏｆｅｓｓｉｏｎａｌ； ４ ｅｄｉｔｉｏｎ （Ｎｏｖｅｍｂｅｒ ８、 １９９６）、ＩＳＢＮ： ０２０１９６４２６０
【発明の開示】
【発明が解決しようとする課題】
【００１３】
リアルタイムアプリケーションで必要となるランキング計算を実現するためにストリームデータ処理システムを用いる場合、ウィンドウへのストリームデータの挿入に加えて、該ストリームデータの消滅の際にも整合性を保つランキング処理の実現が必要となる。また、リアルタイムと呼べるランキング処理結果を得るには、処理対象ウィンドウの内部データの時々刻々の変化の度に実行するランキング更新の処理を高速化する必要がある。
【００１４】
本発明の目的は、処理対象ウィンドウの内部データの時々刻々の変化の度に行なうランキング更新の演算を高速化でき、しかも処理結果の整合性を保つランキング処理方法及びシステムを提供するにある実現することにある。
【課題を解決するための手段】
【００１５】
本願で開示される発明のうち、代表的な発明の概要は以下の通りである。すなわち、代表的実施態様ではウィンドウへのストリームデータの挿入、削除の度毎に、すなわちあるストリームタプルの生存期間の開始、及びあるストリームタプルの生存期間の終了の度毎に、生存期間にあるストリームタプルの範囲内でそれらのランキングを生成・更新し、かつ出力指定された順位の範囲を越えて、生存期間にあるストリームタプルの範囲内でバッファに保存するストリームデータ処理を採用する。
【００１６】
ある時点でのランキング情報の出力だけから言えば、ランキング情報の保存は出力指定された順位のストリームタプルの範囲で行なえば一見充分であるかに思われる。しかしながら、新たなストリームタプルの受け付けに起因して、ウィンドウ内のストリームタプルへの挿入および削除が生じ、その挿入、削除の度にランキングそのものが変動する。したがって、整合性のあるランキング計算を継続して実行するには、その挿入・削除の度毎にランキング情報の更新が必要であり、かつ出力指定された順位の範囲を越えて、生存期間にあるストリームタプルの範囲内のストリームタプル及びそれらのランキング情報を保存する必要がある。
【００１７】
さらに上記代表的実施態様は、受け付けたストリームタプルをランキング計算の処理対象としてウィンドウへ挿入し、該ストリームタプルのウィンドウ内での生存期間を決定し、生存期間の終了時には上記ウィンドウからの削除を行なうウィンドウマネージャと、ランキング計算を行うランキング処理モジュールとの２段階の処理機構を持ち、上記ウィンドウマネージャは、ウィンドウ内のストリームタプル全体の情報ではなく、刻々の変化部分を示すウィンドウ差分情報を上記ランキング処理モジュールに伝達し、上記ランキング処理モジュールは、伝達された上記ウィンドウ差分情報と、過去にランキング計算を行って保存した保存情報とを用いてランキングの更新を行う構成とした点に特徴を有する。具体的には当該ストリームタプルがウィンドウに挿入されたことを示す符号を付加したストリームタプル、および当該ストリームタプルがウィンドウから削除されたことを示す符号を付加したストリームタプルが上記のウィンドウ差分情報としてランキング処理モジュールに伝達され、ランキング処理モジュールでは該差分情報に基づいてランキング情報を更新し、ランキング情報保持バッファに保存するとともに、指定された形式でランキング出力情報を出力する。
【発明の効果】
【００１８】
本発明を用いることにより、時々刻々と到来する大量データをリアルタイム処理するストリームデータ処理システムにおいて、入力されるストリームデータとの整合性を保ち、かつ高速、高効率のランキング計算が実現できる。本ランキング計算方法の適用により、リアルタイムアプリケーションで共通に利用可能なデータ処理基盤が提供できる。
【発明を実施するための最良の形態】
【００１９】
図１および図１６に、本発明のストリームデータ処理システムの好適な実現例を示す。アプリケーション１（１０２）を実行するクライアント計算機１０１、アプリケーション２（１０４）を実行するクライアント計算機１０３は、ネットワーク１０７を介してストリームデータ処理システム１１５に接続されている。ネットワーク１０７は、イーサネット、光ファイバなどで接続されるローカルエリアネットワーク（ＬＡＮ）、もしくはＬＡＮよりも低速なインターネットを含んだワイドエリアネットワーク（ＷＡＮ）でも差し支えない。また、クライアント計算機はパーソナルコンピュータ、ブレード型の計算機システムなどの任意のコンピュータシステムでよい。
【００２０】
本実施例のストリームデータ処理システムが稼動する計算機をストリームデータ処理サーバと呼ぶ。図１６に示すように、ストリームデータ処理サーバ１６０１は、イーサネットアダプタなどの通信インタフェース１６０２、ＣＰＵ１６０３、メモリ１６０４、およびＩ／Ｏインタフェース１６０５を備えた計算機であり、ブレード型計算機システム、ＰＣサーバなどの任意のコンピュータシステムでよい。ストリームデータ処理サーバでは、前記通信インタフェースを介して前記クライアント計算機、後述するデータソースにアクセスする。ストリームデータ処理サーバで、ストリームデータ処理結果、処理の中間結果、システム動作に必要な設定データを不揮発性のストレージに格納する場合には、ストリームデータ処理サーバに接続したストレージ装置１６０６を用いることができる。ストレージ装置１６０６は、ストリームデータ処理サーバのＩ／Ｏインタフェースを介して直接接続されるか、もしくは通信インタフェースを介してネットワーク接続される。
【００２１】
ストリームデータ処理システム１１５は、前記ストリームデータ処理サーバ１６０１の上で動作する。図１にストリームデータ処理システムの主要構成要素を示す。アプリケーションは、まずストリームデータ処理システムにクエリを登録する（１０５）。登録されたクエリはクエリ管理テーブル（１１２）に格納される。クエリ登録の詳細な手順、ストリームデータ処理システム内部のデータの格納方法、格納形式、クエリを受け付けた後の解析方法、最適化方法、システムへの登録方法、ストリームデータ処理システムへのストリームの登録方法、システム内のデータ保持方法については、特開２００６−３３８４３２号「ストリームデータ処理システムのクエリ処理方法」（特許文献４）に、その好適な実施の方法が開示されている。クエリ管理テーブルは、ストリームデータ処理サーバ上のメモリ１６０４に保持するのでも、ストリームデータ処理サーバに接続されているストレージ装置１６０６に格納するのでも差し支えない。
【００２２】
ストリームデータ処理システムには、一つ以上のストリームデータソースであるストリームデータソース１（１２２）〜ストリームデータソースＮ（１２３）からネットワーク１２１を介して時々刻々と大量のデータが到来する。このデータをストリームデータと呼ぶ。ストリームデータの好適な例としては、ファイナンシャルアプリケーションにおける株価配信情報、小売業でのＰＯＳデータ、交通情報システムにおけるプローブカー情報、計算機システム管理におけるエラーログなどが挙げられる。ストリームデータ処理システムでは、通信インタフェース１６０２を介してデータフローマネージャ１１９が受け付けたストリームデータをクエリ処理エンジン１１３にフィードする。
【００２３】
前述したように、継続して到来する比較的小さな論理的には独立した大量の時系列データであるストリームデータを取り扱うために、ストリームデータ処理システムではウィンドウを用いる。図１のウィンドウマネージャ１２６は、到来するストリームデータに対して、クエリで指定されたウィンドウ演算を適用してストリームタプルを生成し、ストリームタプルのシステム内での生存期間を設定する。ストリームデータがウィンドウに挿入された時が生存期間の開始時刻、そしてウィンドウから該ストリームデータが削除される時が生存期間の終了時刻に相当する。
【００２４】
図１５を用いて、ウィンドウマネージャの構成と動作内容を説明する。ウィンドウマネージャ１２６は、ストリームデータ受付インタフェース１５０５、ストリームタプル保持バッファ１５０２、生存期間決定部１５０４、および差分情報生成部１５０６から構成される。ストリームデータ受付インタフェースは、受け付けたストリームデータの構成要素であるストリームタプルを、ストリームタプル保持バッファ１５０２に格納するとともに、生存期間決定部１５０６に格納したことを伝達する。生存期間決定部１５０６は前記ウィンドウ演算により各ストリームタプルの生存期間を決定し、生存期間が終了するストリームプルをストリーム保存バッファ１５０２から消去する。差分情報生成部１５０４は、ストリームタプルが該ストリームタプル保持バッファに格納されたタイミングで、プラスタプルを生成し、差分情報として出力する（１５０８）。同様に、ストリームタプルがストリームタプル保持バッファから消去されるタイミング（ストリームタプルの生存期間が終了するタイミング）でマイナスタプルを生成し、同様に差分情報として出力する（１５０８）。
【００２５】
図１６に示すように、ストリームタプル保持バッファ１５０２は、クエリ処理エンジン１１３内のメモリマネージャ１１７によって割り当てられるメモリ上に配置される。該メモリは、ストリームデータ処理サーバ１６０１上のメモリ１６０４、もしくは要求される性能要件、信頼性要件に応じて、ストリームデータ処理サーバに接続されたストレージ装置１６０６、もしくはストリームデータ処理サーバとネットワークで接続される、ストリームデータ処理サーバと同様の計算機資源を保持するサーバ計算機（図１のブロック１３３）上のメモリを利用してもよい。
【００２６】
次に、図２を用いてランキング処理モジュールの構成を説明する。ランキング処理モジュール１１６はストリームタプル受付インタフェース２０６、順序・順位生成部２０４、ランキング情報保持バッファ２０２、ランキング情報保持テーブル２０３、順位管理インデックス２０８、およびランキング処理結果出力インタフェース２０７から構成される。図１６に示すように、ランキング処理モジュールは、クエリ処理エンジン１１３内のメモリマネージャ１１７によって割り当てられるメモリ上に配置される。該メモリは、ストリームデータ処理サーバ１６０１上のメモリ１６０４、もしくは要求される性能要件、信頼性要件に応じて、ストリームデータ処理サーバに接続されたストレージ装置１６０６、もしくはストリームデータ処理サーバとネットワークで接続される、ストリームデータ処理サーバと同様の計算機資源を保持するサーバ計算機（図１のブロック１３３）上のメモリを利用してもよい。
【００２７】
図１７に本発明のストリームデータ処理における、ランキング情報生成のシーケンスを示す。前記ウィンドウマネージャ１２６は外部データソースから到来するストリームデータを受け付け（１７０１）、差分情報（符号付ストリームタプル）を生成する（１７０２）。ランキング処理モジュール１１６では、ストリームタプル受付インタフェース２０６が、前記ウィンドウマネージャから出力された差分情報（符号付ストリームタプル）を受け取り、順序・順位生成部２０４に転送する。順序・順位生成部では、ランキング情報保持バッファ２０２を参照しながら、受け取った符号付ストリームタプルをランキングバッファの適切な位置に追加、もしくはランキングバッファ内の適切な位置のランキング情報を削除し、前回の出力時とのランキング情報の差分（ランキング差分情報）を生成し（１７０５）、該ランキング差分情報をランキング処理結果出力インタフェース２０７に転送する（１７０６）。ランキング処理結果出力インタフェースでは、前記クエリによって指定されているデータの出力形式に従ってランキング情報を出力する。
【００２８】
以下、具体的なクエリ、ストリームデータに対する、本実施例のランキング計算方法を説明する。図３（ａ）に示すクエリ３０１は、順位出力（順位そのものを出力すること）を指定しないランキング処理を命じるクエリである。１行目のＳＥＬＥＣＴ句はｓ．ｉｄとｓ．ｖａｌの値の組を出力対象とすることを、２行目のＦＲＯＭ句はストリームｓを対象とすることを、同じく２行目のＰａｒｔｉｔｉｏｎ Ｂｙ句はｓ．ｉｄの値でグルーピングしてそれぞれのｓ．ｖａｌの値の最新の１件を保持することを、また３行目のＬＩＭＩＴ句は、ｓ．ｖａｌの値の降順に３件を出力すること意味する。本実施例のストリームデータ処理システムでは、予め入力されるクエリにて、ランキング計算の対象となるカラムと、ランキング付けの方向（昇順／降順）と、ランキング計算結果を出力する個数と、計算結果に順位情報を付与するか否かが指定される。クエリ３０１では、３行目のＬＩＭＩＴ句が、ｓ．ｖａｌの値の降順に３件を出力するランキング指定である。さらに、１行目のＩＤＳＴＲＥＡＭ句は、本クエリは出力として前回の出力時との差分情報のみを出力することを意味している。
【００２９】
図４および図５（ａ）を用いて、クエリ３０１が設定されたストリームデータ処理システムに対して、ストリームデータが到来した際の処理内容を説明する。クエリ３０１がストリームデータ処理システム１１５に登録された場合、例えば特許文献４に示された方法でクエリ解析、クエリ最適化、クエリ生成が実行され、クエリ処理エンジンにクエリの実行形式が登録される。クエリ３０１はランキング計算指定を含むため、実行形式のクエリの実行時には、クエリ処理エンジン１１３内のランキング処理モジュール１１６でランキング計算が実行される。特許文献１で述べられているように、ストリームデータ処理システムでは、クエリは登録された後システム上で動作し続け、一つ一つのストリームデータがシステムに到来するたびに、その状態が変化する。
【００３０】
クエリ３０１が登録されている状況で、図４に示すストリームデータが到来したことを仮定する。図４および図５（ａ）では、時刻の経過を縦軸にとり、時刻の経過と共にシステムに到来したストリームデータが各処理モジュールで処理される様子を模式的に表している。凡例４０２および５０２に示すように、本実施例では到来するストリームデータは｛ｉｄ，ｖａｌ｝の形式と仮定しており、これを楕円で表現している。ｔ１〜ｔ７（４０１）は、４０５〜４１１の各ストリームデータがストリームデータ処理システムに到来する時刻を表している。例えば、ストリームデータ｛ａ，５０｝（４０５）、及びストリームデータ｛ｂ，１０｝（４０６）はそれぞれ、時刻ｔ１、ｔ２にストリームデータ処理システムに到来することを示している。図４の横軸は到来したストリームデータが処理される位置、および生成されるデータを表している。さらに、図４の左側の角丸四角（１５０２）は、システムに到来した前記ストリームデータに対して、前記ウィンドウマネージャ（１２６）でウィンドウ演算“［Ｐａｒｔｉｔｉｏｎ Ｂｙ ｓ．ｉｄ Ｒｏｗｓ １］”（４０３）を適用した結果を格納した、ストリーム保持バッファの各時刻での状態を示している。また、右側の角丸四角（２０２）は、ウィンドウマネージャから到来するストリームタプルに対して、前記ランキング処理モジュール（１１６）内の順序・順位生成部（２０４）における、ランキング計算指定句“ＬＩＭＩＴ ３ Ｂｙ ｓ．ｖａｌ ＤＥＳＣ”（４０４）の適用した結果を格納した、ランキング情報保持バッファの各時刻での状態を示している。
【００３１】
前述したように、ウィンドウマネージャ１２６は、到来するストリームデータに対して、クエリで指定されたウィンドウ演算を適用してストリームタプルを生成し、ストリームタプルのシステム内での生存期間を設定する。図４の例では、生存期間の開始時刻は黒丸（４２６）、終了時刻は白丸４２７で表現されており、該ウィンドウ演算により、ストリームタプル｛ａ，５０｝（４０５）の生存期間は時刻ｔ１に始まり、時刻ｔ７に終わることを示している。本実現例においては、ストリームデータの生存期間の開始時刻には、システム内部で前記のストリームデータに増加分を表す符号を付けたタプル（以下プラスタプル）が生成される。また、ウィンドウからストリームデータが削除された場合、先に出力されたプラスタプルへの参照を持つ、減少分を表す符号を付けたタプル（以下マイナスタプル）が生成される。以上の処理は、前記ウィンドウマネージャで実行される。例えば、図４の場合、時刻ｔ１にはストリームデータ｛ａ，５０｝（４０５）に対応するプラスタプル４３０が生成され、時刻ｔ７に該ストリームデータのマイナスタプル４３１が生成されることとなる。ウィンドウ演算に続く、後段のクエリ処理は、本プラスタプルおよびマイナスタプルが到着したタイミングで該プラスタプルとマイナスタプルに起因して生成される差分情報に関して実行される。なおプラスタプル、マイナスタプルそのものの概念は前述の非特許文献１に紹介されている。
【００３２】
クエリ３０１では、到来するストリームデータはまずウィンドウ演算“［Ｐａｒｔｉｔｉｏｎ Ｂｙ ｓ．ｉｄ Ｒｏｗｓ １］”（４０３）により、ｓ．ｉｄの値毎に最新１個のみが保持される。具体的には、図４で時刻ｔ１にストリームデータ｛ａ，５０｝（４０５）が、時刻ｔ２に｛ｂ，１０｝（４０６）が、時刻ｔ３に｛ｃ，３０｝（４０７）が、時刻ｔ４に｛ｄ，２０｝（４０８）が、そして時刻ｔ５に｛ｅ，４０｝（４０９）がそれぞれ到来する。これら５つのストリームデータはｓ．ｉｄの値が異なるので、それぞれウィンドウに保持される。次に、時刻ｔ６に新たなストリームデータ｛ｅ，１５｝（４１０）が到来すると、それまでウィンドウに保持されていたｓ．ｉｄの値がｅのストリームデータ４０９はウィンドウから押し出される（削除される）。次に時刻ｔ７に｛ａ，４５｝（４１１）が到来すると、同様に｛ａ，５０｝（４０５）がウィンドウから削除される。この様子を図示したのが図４の中央部分４２９である。例えば、ストリームデータ｛ａ，５０｝（４１２）は時刻ｔ１に到来し、時刻ｔ７に｛ａ，４５｝（４１８）が到来するまでウィンドウに保持される。この時、ストリームデータ｛ａ、５０｝の生存期間はｔ１からｔ７（但し時刻ｔ７は含まない）と表現する。図４の例では、生存期間の開始時刻は黒丸（４２６）、終了時刻は白丸（４２７）で、生存期間中は実線で表している。同様にして、｛ｅ，４０｝（４１７）の生存期間はｔ５からｔ６となる。一方、｛ｂ，１０｝（４１３）、｛ｃ，３０｝（４１４）、｛ｄ，２０｝（４１５）、｛ｅ，１５｝（４１７）、および｛ａ，４５｝（４１８）については、時刻ｔ７の時点では終了時刻が決定していないため、実線で表現されている。
【００３３】
以上のように生存期間を持つストリームデータから、どのようにランキング情報を生成するかを、同じく図４を用いて説明する。図４の右側４３２に、ランキング計算指定句“ＬＩＭＩＴ ３ Ｂｙ ｓ．ｖａｌ ＤＥＳＣ”（４０４）による処理結果を示す。前述したように、本ランキング指定句の意味は、ｓ．ｖａｌの値で降順に３件を抽出することである。今、ストリームデータ｛ａ，５０｝（４１９）、｛ｂ，１０｝（４２０）、｛ｃ，３０｝（４２１）がそれぞれ時刻ｔ１、ｔ２、ｔ３に到来する。これら３つのストリームデータは上位３件ランキング情報としてそれぞれ出力される。次に、時刻ｔ４に｛ｄ，２０｝（４２２）が到来すると、そのｓ．ｖａｌの値２０は、これまでに保持されている｛ｂ、１０｝の１０よりも大きいため、｛ｂ，１０｝が上位３件のランキング情報から削除されてその生存期間がｔ４で終了し（４２８）、｛ｄ，２０｝がランキング計算結果として出力される。次に時刻ｔ５に｛ｅ，４０｝（４２３）が到来すると、そのｓ．ｖａｌの値は４０となるため、上位３件に含まれるため、ランキング情報として出力される。そしてこれまで上位３件に保持されていた中で最も値の小さい｛ｄ，２０｝がランキングから削除される。ところが、時刻ｔ６には、前述したように｛ｅ、１５｝（４１７）の到来により｛ｅ，４０｝（４１６）がウィンドウから削除されるため、再び｛ｄ，２０｝（４２４）が上位３件に復活することになり、再びランキング計算結果として出力される。時刻ｔ７には｛ａ，５０｝（４１２）が｛ａ、４５｝（４１８）に置き換わり、｛ａ，４５｝のｓ．ｖａｌの値４５は上位３件に含まれるため、｛ａ，４５｝（４２５）がランキング結果として出力される。
【００３４】
以上のランキング計算の好適な実施方法を図２、図９、図１０、図１８、および図１９を用いて説明する。ランキング処理モジュール１１６のストリームタプル受付インタフェース２０６が差分情報であるストリームタプルを受け取る（９０２）。すると、順序・順位生成部２０４はランキング情報保持バッファ２０２のバッファメンテナンスを実行する（９０３）。バッファメンテナンス処理の処理方法について、図２および図１０を用いて説明する。順序・順位生成部２０４は、ストリームタプルを受け取ると、該ストリームタプルの符号がプラスであるかマイナスであるかをチェックする（１００２）。符号がプラスの場合（１００２でＹｅｓが選択された場合）、ランキング情報保持バッファ２０２のランキング情報保持テーブル２０３に受け取ったストリームタプルを追加し（１００３）、ランキング情報保持バッファメンテナンス処理を終了する。ランキング情報保持バッファへのストリームタプル追加処理の詳細を図１８のフローチャートを用いて説明する。順位・順序生成部では、追加対象のストリームタプル（符号がプラスのストリームタプル）を受け取ると、追加先のランキング情報保持テーブル２０３に順位管理インデックス２０８が付与されているかどうかをチェックする（１８０２）。順位管理インデックスは、順位付けの対象のカラムをキーとしたＢ＋ｔｒｅｅインデックスやハッシュインデックスで差し支えない。順位管理インデックスが存在する場合（ステップ１８０２でＹｅｓが選択された場合）には、順位・順序生成部は該インデックスを利用して追加対象のストリームタプルの、ランキング情報保持テーブルへの挿入位置を決定する（１８０３）。該インデックスが存在しない場合（ステップ１８０２でＮｏが選択された場合）には、順位・順序生成部はランキング情報保持テーブルを検索し、追加対象のストリームタプルの、ランキング情報保持テーブルへの挿入位置を決定する（１８０４）。挿入位置を決定した後、順位・順序生成部は追加対象のストリームタプルをランキング情報保持テーブルに挿入し（１８０５）、順位管理インデックスが存在する場合（ステップ１８０６でＹｅｓが選択された場合）には、該インデックスも更新してランキング情報保持バッファへのストリームタプル追加処理を終了する（１８０８）。
【００３５】
好適なランキング情報保持バッファの実現形態では、追加されたストリームタプルの、ランキング指定されたカラムの値での順序関係が保持される。ストリームタプルの追加時に順序関係を保持しておく理由は、遅延処理により一括して順序関係を作成する方法では、リアルタイム処理アプリケーションの要求である即時の結果出力が困難であるためである。例えば、図３のクエリ３０１の場合には、順序付けの対象となるカラム（前述のランキングキー）はｓ．ｖａｌであるので、図２のランキング情報保持バッファ中のランキング情報保持テーブル（２０３）ではｓ．ｖａｌの降順に順位情報とストリームタプルを保持している。
【００３６】
図１０に戻って、受け取ったストリームタプルの符号がマイナスの場合（図１０の１００２でＮｏが選択された場合）、ランキング情報保持バッファ（２０２）から該ストリームタプルに対応する、符号がプラスのタプルを削除し（１００４）、ランキング情報保持バッファメンテナンス処理を終了する。
【００３７】
ランキング情報保持バッファからのストリームタプル削除処理の詳細を図１９のフローチャートを用いて説明する。順位・順序生成部では、ランキング情報保持テーブル２０３に順位管理インデックス２０８が付与されているかどうかをチェックする（１９０２）。順位管理インデックスが存在する場合（ステップ１９０２でＹｅｓが選択された場合）には、順位・順序生成部は該インデックスを利用して、ランキング情報保持テーブル中の削除対象のストリームタプルを検索する（１９０３）。該インデックスが存在しない場合（ステップ１９０２でＮｏが選択された場合）には、順位・順序生成部はランキング情報保持テーブルを検索し、削除対象のストリームタプルを決定する（１９０４）。削除対象のストリームタプルが決定されると、順位・順序生成部では該ストリームタプルの削除処理を実行する（１９０５）。順位管理インデックスが存在する場合（ステップ１９０６でＹｅｓが選択された場合）には、順位管理インデックスも更新し、ランキング情報保持バッファからのストリームタプル削除処理を終了する。
【００３８】
ここで図１４を用いて、図３（ａ）のクエリを登録したストリームデータ処理システムに対して、図４で示したタイムチャートでストリームが到来する場合の、ランキング情報保持テーブルに保持されるランキング情報の変化の様子を説明する。図１４では、左側のｔ０（１４１６）、ｔ１（１４０４）、…、ｔ７が時刻を、中央の符号付きの楕円（１４０５、１４０７、…）がウィンドウマネージャで生成された差分情報（符号付ストリームタプル）を、そして右側のテーブル（１４１７、１４０６、…、１４１５）がランキング情報保持テーブルに保持されるランキング情報を表す。便宜上時刻ｔ１以前のｔ０にはランキング情報は存在しなかったと仮定する。
【００３９】
時刻ｔ１（１４０４）に、プラスの符号を持つストリームタプル｛ａ，５０｝（１４０５）が到来すると、ランキング情報保持テーブルに該ストリームタプルが登録される（１４０６）。次に、時刻ｔ２（１４１８）にプラスの符号を持つストリームタプル｛ｂ，１０｝（１４０７）が到来すると、その順位付け対象ｓ．ｖａｌの値である１０を、ランキング情報保持テーブルに保持されているストリームタプルのｓ．ｖａｌの値５０と比較し、挿入位置が｛ａ，５０｝（１４０５）の次と決定され、該挿入位置にストリームタプル｛ｂ，１０｝が挿入される（１４０８）。以下同様に、ｔ３、ｔ４、ｔ５にそれぞれ、｛ｃ，３０｝、｛ｄ，２０｝、｛ｅ，４０｝が到来すると、これらのストリームタプルが順位付け対象のｓ．ｖａｌの値の順にソートされて登録される。
【００４０】
図４に示すように、時刻ｔ６において｛ｅ，１５｝（４０８）が到来すると、図３（ａ）に示した１行指定のＲｏｗウィンドウクエリでは｛ｅ、４０｝がウィンドウから削除される（４３３）。そのため、図１４に示すランキング処理モジュール（１１６）のストリームタプル受付インタフェース２０６には、マイナス符号の付いたストリームタプル｛ｅ，４０｝（１４１３）と、プラス符号の付いたストリームタプル｛ｅ，１５｝（１４１４）が到来する。順序・順位生成部２０４では、マイナス符号の付いたストリームタプル｛ｅ，４０｝に対応するプラス符号の付いたストリームタプルを検索、決定し（１４１２の上から２番目）、該ストリームタプルを削除する。そして、プラス符号の付いた新たなストリームタプル｛ｅ，１５｝（１４１４）の挿入位置を決定し（１４１５の上から４番目）、ランキング情報保持テーブルに該ストリームタプルを追加する。時刻ｔ７についても同様である。
【００４１】
本実施例では、ランキング情報保持バッファ内でのデータ構造がテーブルの場合を示したが、ランキング情報保持バッファ内でのデータ構造の他の好適な実現例としては、例えば図１３に示すようなランキングキーをノードとした二分探索木（ｂｉｎａｒｙ ｓｅａｒｃｈ ｔｒｅｅ）を挙げることができる。図１３では、二分探索木のノード（ランキングキー）を四角１３０１で、ノードからポイントされるデータ本体（ストリームタプル）を円と楕円の組１３０２で示した。二分探索木を用いる場合には、ランキングキーをノードとして、あるノードの左側の子およびその全ての子孫ノードのランキングキーの値は、該ノードのランキングキーの値より小さく、右の子およびその全ての子孫ノードの値は該ノードのランキングキーの値と等しいもしくは大きくなるように構成する。図１３の角丸四角１３０３内の二分探索木は、図４の時刻ｔ５の時点でのランキング情報保持バッファが保持するデータの二分探索木での構成の例であり、保持しているデータの内容は図１４のランキング情報保持テーブル１４１２と等しい。二分探索木を用いてランキングキーに基づいた順序を管理することで、前記プラスタプル、および前記マイナスタプル到来時の順序関係の管理を効率化することができる。さらに、ストリームタプルの順序関係を保持して管理するための他の好適なデータ構造としては、多くのＤＢＭＳのデータ管理機構で利用されるＢ＋−Ｔｒｅｅを利用するのでも差し支えない。
【００４２】
ランキング情報保持バッファでは、ユーザに指定されたランキングの出力件数のみでなく、生存期間中のストリームデータに対応する全てのストリームタプルを保持する必要がある。例えば、図３のクエリ３０１では、ユーザからは上位３件のみを出力するように指示されているが、図４に示すストリームデータの系列がシステムに到来する場合、時刻ｔ４で｛ｄ，２０｝（４０８）が到来した際に、前記ランキング情報保持バッファから、順位が４位となったストリームデータ｛ｂ，１０｝（４０６）に対応するストリームタプル４３３を削除してはならない。その理由は、ストリームデータ処理においては、新しいストリームデータがシステムに到来するときに加えて、ストリームデータの生存期間が終了した際にもランキングが変化するため、現在はユーザが指定した範囲外にあるストリームデータが、他のストリームデータの生存期間の終了によって、再びランキング結果として出力する必要が出てくるためである。例えば、図４では時刻ｔ４で到来し、上位３件に含まれたストリームデータ｛ｄ，２０｝（４０８）が時刻ｔ５に到来した｛ｅ，４０｝（４０９）によってランキング外に押し出されてしまっているが、時刻ｔ６に到来した｛ｅ，１５｝（４１０）によって、｛ｅ，４０｝はウィンドウから消去される（４３３）ため、｛ｄ，２０｝は再びランキング計算結果に含まれる（４２４）必要がある。すなわち、ランキング情報保持バッファでは、ユーザに指定されたランキングの出力件数のみでなく、ウィンドウで管理されているストリームデータに対応する全て、すなわち生存期間中のストリームデータに対応する全てのストリームタプルを保持する必要がある。
【００４３】
但し、ストリームタプルが到着した瞬間に上位５０位以内に含まれていない場合には、該ストリームタプルはランキングの対象としないなどのアプリケーションの特別な条件が存在する場合には、該アプリケーションの条件に従ってランキング情報保持バッファで保持するストリームタプルの数を変更することは可能である。
【００４４】
図９に戻って、順序・順位生成部では、受け取ったストリームタプルのバッファメンテナンス処理（９０３）の結果に基づき、該処理結果がランキングに影響するか否かをチェックする（９０４）。処理結果がランキングに影響を及ぼす場合とは、受け取ったストリームタプルに基づいたランキング情報保持バッファのメンテナンスの結果、クエリで指定されている範囲の順序に変更がある場合を指す。例えば、図３のクエリ３０１では、上位３件を出力の範囲に指定しているため、上位３位以内の順序に変更がある場合、処理結果がランキングに影響するか否かの判定（ステップ９０４）はＹｅｓとなる。例えば、図４で示した処理の場合、時刻ｔ４で｛ｄ，２０｝が到来した場合には上位３位以内の順序に変更があるので、Ｙｅｓの例となる。処理結果がランキングに影響する場合（ステップ９０４でＹｅｓが選択された場合）、順序出力指定があるかないかをチェックする（９０５）。順序出力指定がある場合（ステップ９０５でＹｅｓが選択された場合）、処理結果タプルへの順位情報カラムを追加して（９０６）、処理結果タプルを出力し（９０７）、ランキング処理を終了する（９０８）。順位出力の指定がない場合（ステップ９０５でＮｏが選択された場合）、処理結果タプルを出力し（９０７）、ランキング処理を終了する（９０８）。
【００４５】
図３のクエリ３０１の場合には、順位出力の指定はないので、ランキング処理結果出力インタフェースから出力する処理結果タプルは、例えば図５の５２３に示すものであり、順位情報は付加されていない。順位出力の指定がある場合（ステップ９０５でＹｅｓが選択された場合）の例については後述する。
【００４６】
前述したように、リアルタイムアプリケーションのランキング計算では、膨大な情報から瞬時に有用な情報を取り出す必要があるため、処理の効率化が必要となる。そこで、本実施例のストリームデータ処理システムでは、ランキングに変動があった差分だけを出力するインタフェースと、その時点のランキング内の全データを出力するインタフェースを備える。図５（ａ）中央の２０２は、図４で説明したクエリ３０１（図３）のウィンドウ演算“［Ｐａｒｔｉｔｉｏｎ Ｂｙ ｓ．ｉｄ Ｒｏｗｓ １］”、およびランキング計算指定句“ＬＩＭＩＴ ３ Ｂｙ ｓ．ｖａｌ ＤＥＳＣ”の処理結果を格納したランキング情報保持バッファの各時刻での状態を示している。クエリ３０１では、最終的な出力形式として、ＩＤＳＴＲＥＡＭ句が指定されている。ＩＤＳＴＲＥＡＭ句は、ランキング計算の結果、ランキングに追加されたタプルを増加分タプルとして、ランキングから削除されたタプルを減少分タプルとして出力するインタフェースである。図５（ａ）では、ＩＤＳＴＲＥＡＭ句（５０４）によって処理された後のストリームデータを図の右側の角丸四角５２３内に示した。ただし、該ストリームデータの黒丸は増加分、白丸は減少分を表す。以下、ＩＤＳＴＲＥＡＭ句の処理の内容について説明する。時刻ｔ１に｛ａ，５０｝（５０５）がランキングに追加されるので、ＩＤＳＴＲＥＡＭ句では処理結果の増加分ストリームデータとして｛ａ，５０｝（５１２）を出力する。次に時刻ｔ２、ｔ３にそれぞれ｛ｂ，１０｝（５０６）および｛ｃ，３０｝（５０７）がランキングに追加されるので、｛ｂ，１０｝（５１４）および｛ｃ，３０｝（５１５）が増加分として出力される。時刻ｔ４には、｛ｄ，２０｝（５０８）がランキングに挿入されると共に、｛ｂ，１０｝（５０６）がランキングから削除される。この場合、ＩＤＳＴＲＥＡＭ句では、時刻ｔ４に｛ｄ，２０｝（５１６）を増加分として、｛ｂ，１０｝（５１７）を減少分として出力する。増加分と減少分の情報のみを計算し、該情報を利用するクライアント計算機に送信することにより、ストリームデータ処理システムの処理コスト、および通信コストを削減することができる。例えば図５（ａ）の場合、ｔ１からｔ７までの間に、クライアント計算機に対して１１個の処理結果が送信されるが、各タイミングで上位ｎ件の全結果を全て送信する場合にはｎ×７個の処理結果を送信する必要があり、特にｎが大きい場合差分情報のみを送信する本発明の効果は高い。
【００４７】
但し、クライアント計算機側でランキング情報を随時ユーザに提供し続ける必要がある場合には、クライアント計算機側で差分情報から全体のランキング情報を作成し続ける必要がある。本処理では、クライアント計算機側で状態（ステート）を管理する必要があるため、クライアント計算機の状態、リアルタイムアプリケーションの形態によっては実現が難しい場合もある。このような状況でもランキング情報を利用できるようにするために、本出願のストリームデータ処理システムでは、生成した差分ランキング情報から全体のランキング情報を生成し、出力するインタフェースを備える。図３（ｂ）のクエリ３０２は、１行目のＲＳＴＲＥＡＭ句以外はクエリ３０１と同一であり、１行目のＳＥＬＥＣＴ句はｓ．ｉｄとｓ．ｖａｌの値の組を出力対象とすることを、２行目のＦＲＯＭ句はストリームｓを対象とすることを、同じく２行目のＰａｒｔｉｔｉｏｎ Ｂｙ句はｓ．ｉｄの値でグルーピングしてそれぞれのｓ．ｖａｌの値の最新の１件を保持することを、３行目のＬＩＭＩＴ句はｓ．ｖａｌの値の降順に３件を出力することを指定する。クエリ３０１の１行目のＩＤＳＴＲＥＡＭ句が、前回の出力時との差分情報のみを出力するのに対して、クエリ３０２の１行目のＲＳＴＲＥＡＭ句は、出力のタイミング毎に、出力指定範囲内のストリームタプル全てのランキング情報を出力することを意味している。図５（ｂ）に、該インタフェースでのランキング計算出力結果を示す。図５（ｂ）のランキング情報保持バッファ（２０２）の各時刻の状態は図５（ａ）の場合と同じである。ＬＩＭＩＴ句の処理後に、図３（ｂ）に示すクエリ３０２のＲＳＴＲＥＡＭ句を適用した結果が図５（ｂ）の右側の角丸四角５２６内に示すストリームデータとなる。以下図５（ｂ）を用いて、ランキング計算結果の出力形式について説明する。時刻ｔ１に｛ａ，５０｝（５０５）がランキングに追加されるので、ＲＳＴＲＥＡＭ句では｛ａ，５０｝（５２７）を出力する。次に時刻ｔ２に｛ｂ，１０｝（５０６）がランキングに追加されると、ＲＳＴＲＥＡＭ句はランキング全体、すなわち｛ａ，５０｝と｛ｂ，１０｝の２つのストリームデータを出力する（５２８）。次に時刻ｔ３で｛ｃ，３０｝（５０７）がランキングに追加されると、｛ａ，５０｝、｛ｂ，１０｝に加えて｛ｃ，３０｝が出力される（５２９）。次に、時刻ｔ４で｛ｄ，２０｝（５０８）がランキングに挿入されると共に、｛ｂ，１０｝（５０６）がランキングから削除される。この場合、ＲＳＴＲＥＡＭ句では、時刻ｔ４に｛ａ，５０｝、｛ｃ，３０｝、｛ｄ，２０｝を出力する（５３０）。本処理を実現するためには、処理結果出力時にランキング処理結果出力インタフェース（２０７）で前回の出力時の出力内容を保持し、該出力内容と、順序・順位生成部（２０４）で新たに生成されたランキング情報とを組合せて、出力情報を生成すればよい。今回の説明では、ＲＳＴＲＥＡＭ句の出力タイミングは、入力となるストリームデータが到来した瞬間としたが、出力生成の負荷、通信コスト削減のために、例えば１秒毎などの一定間隔、入力タプルｎ個毎、出力タプルｍ個毎などでも差し支えない。
【００４８】
次に、クエリで順位出力指定がある場合（図９のステップ９０５でＹｅｓが選択される場合）の例について、図６のクエリ６０１および６０２を用いて説明する。クエリ６０１では、クエリ３０１で出力したｓ．ｉｄとｓ．ｖａｌに加えて、１行目のＲＡＮＫＩＮＧ ＡＳ ｒａｎｋ指定により、その時点での順位情報も加えて出力することが指定されている。また、クエリ６０１が前回出力した後の差分情報のみを出力するのに対して、クエリ６０２では、出力タイミング毎にランキング情報を全て出力する。
【００４９】
最初に、順位出力指定を含む場合のランキング計算方法について、図７を用いて説明する。図７の左側の角丸四角（１５０２）は、ウィンドウ演算“［Ｐａｒｔｉｔｉｏｎ Ｂｙ ｓ．ｉｄ Ｒｏｗｓ １］”の処理結果を格納したストリームタプル保持バッファの各時刻での状態を示しており、図４と同じである。各時刻の状態に対して、順位出力指定を含むランキング計算の方法を説明する。図７の凡例７０２に示すように、楕円で囲まれた２つの値の組は｛ｉｄ，ｖａｌ｝の形式のストリームデータを表す。また、凡例７０３に示すように、角丸四角形で囲まれた３つの値の組は、｛ｒａｎｋ，ｉｄ，ｖａｌ｝の形式のストリームデータを表す。ここで、ｒａｎｋは出力時のｖａｌの値に基づいた順位である。
【００５０】
時刻ｔ１にストリームデータで｛ａ，５０｝（７０５）が到来すると、本ストリームタプルはランキングに含まれ、かつその順位は１位であるので、ランキング計算結果は｛１，ａ，５０｝（７１２）となる。次に時刻ｔ２にストリームデータ｛ｂ、１０｝（７０６）が到来すると、本ストリームデータもランキングに含まれるので、｛２，ｂ，１０｝（７１３）が出力される。時刻ｔ３に｛ｃ，３０｝（７０７）が到来すると、本ストリームデータもランキングに含まれ、かつそのｖａｌの値３０が｛ｂ，１０｝よりも大きいため順位は２位となり、同時に｛ｂ，１０｝の順位は３位となる。そのため、ランキング計算結果からは、｛２，ｂ，１０｝が削除され、｛３，ｂ，１０｝（７１４）および｛２，ｃ，３０｝（７１５）が追加される。続いて、時刻ｔ４にストリームデータ｛ｄ，２０｝（７０８）が到来すると、そのｖａｌの値２０が｛ｂ，１０｝のｖａｌの値１０よりも大きいので、｛３，ｂ，１０｝がランキング計算結果から削除され、｛３，ｄ，２０｝（７１６）が計算結果に追加される。次に、時刻ｔ５でストリームデータ｛ｅ，４０｝（７０９）が到来すると、そのｖａｌの値４０は現在ランキング計算結果に含まれている｛ｃ，３０｝および｛ｄ，２０｝よりも大きく、順位は２位となるため｛２，ｅ，４０｝（７１８）がランキング計算結果に含まれる。同時に、｛３，ｄ，２０｝がランキング計算結果から削除され、かつ｛ｃ，３０｝の順位が２位から３位に変化するため、｛２，ｃ，３０｝が削除され、｛３，ｃ，３０｝（７１７）が追加される。時刻ｔ６、ｔ７にそれぞれ｛ｅ，１５｝（７１０）および｛ａ，４５｝（７１１）が到来する場合も同様である。これらのランキング計算処理は、図２の順序・順位生成部（２０４）で実行され、各時刻でのランキング計算処理結果はランキング情報保持バッファ（２０２）に格納される。計算の好適な実施方法は、図９のフローチャートでは、ランキング情報保持バッファメンテナンス（９０３）までは共通である。次に、順序出力指定があるかないかをチェックし（９０５）、順序出力指定がある場合（９０５でＹｅｓが選択された場合）には処理結果タプルの順位情報カラム追加処理を実施する（９０６）。順位情報追加処理は、ランキング情報処理バッファ（２０２）を利用する。前述したように、好適な実施例では、ランキング情報保持バッファでは、追加されたストリームタプルを、順序付けが指定されたカラムの値の順序関係を保持しながら管理する。例えば、クエリ６０１の場合には、クエリ３０１の場合と同様に、順序付けの対象となるカラムはｓ．ｖａｌであるので、ランキング情報保持バッファ内でのデータ構造としては、図２の２０３に示すようなテーブル形式や、図１３のｓ．ｖａｌの値をキーにした二分探索木が実施の方法として挙げられる。順位情報の追加処理では、順位情報追加対象のストリームカラムがｓ．ｖａｌをキーにした場合何番目にあるかを計算し、該順位をクエリで指定されたカラムの位置に追加する。例えば、クエリ６０１の場合には、ＳＥＬＥＣＴ句の最初のカラムに“ＲＡＮＫＩＮＧ ＡＳ ｒａｎｋ”指定があるため、一番目のカラムに順位情報を含めて出力する。
【００５１】
クエリ６０１では、最終的な出力形式として、ＩＤＳＴＲＥＡＭ句が指定されている。クエリ３０１を用いて説明したように、ＩＤＳＴＲＥＡＭ句は、ランキング計算の結果、ランキングに追加されたストリームデータを増加分として、ランキングから削除されたストリームデータを減少分として出力するインタフェースである。図８（ａ）では、ＩＤＳＴＲＥＡＭ句（８０４）によって処理された後のストリームデータを図の右側（８１９）に示した。時刻ｔ１に｛ａ，５０｝（８０５）が到来した場合、出力カラムの先頭に前記順序・順位生成部で計算した順位情報をクエリで指定された１番目のカラムに追加して出力する。｛ａ，５０｝が到来したときには、ストリームデータは１つしかなく、その順位は１位となるので、｛１，ａ，５０｝（８１１）を出力する。次に時刻ｔ２に｛ｂ，１０｝（８０６）が到来すると、その順位は２位となるので、｛２，ｂ，１０｝（８１２）を出力する。時刻ｔ３に｛ｃ，３０｝（８０７）が到来すると、そのｖａｌの値３０は｛ａ，５０｝のｖａｌの値５０よりは小さく、｛ｂ，１０｝のｖａｌの値１０よりは大きいため、その順位は２位となる。そのため、時刻ｔ３では、｛３，ｂ，１０｝（８１３）および｛２，ｃ，３０｝（８１４）が増加分として出力されると共に、｛２，ｂ，１０｝（８１５）が減少分として出力される。図５で示したクエリ３０１の例では、｛ｃ，３０｝によりランキング出力に含まれる集合自体は変化しなかったため、増加分として｛ｃ，３０｝のみを出力した（５１５）が、図８のクエリ６０１の例では｛ｃ，３０｝の到来によって順位が変化するため、増加分、減少分を合わせて３つのストリームデータが出力される。同様にして、時刻ｔ５およびｔ６では順位の変化に対応して、それぞれ４個（８２０）、（８２１）となり、クエリ３０１の場合よりも出力するストリームタプル数が増加している。クエリ６０１では、最終的な出力形式として、前記ＩＤＳＴＲＥＡＭ句が指定されているため、増減分のストリームデータを出力しているが、順位出力指定がない場合と同様に、順位出力指定がある場合も各瞬間のランキングの全体を出力する要求もある。クエリ６０２がその例である。クエリ６０１のＩＤＳＴＲＥＡＭのかわりにＲＳＴＲＥＡＭを指定する（８２９）ことによって、出力時点でのランキング計算結果全体を出力する。図８（ｂ）はクエリ６０２の実行結果を示している。時刻ｔ１〜ｔ７のそれぞれの出力を８２２〜８２８に示した。
【００５２】
以上の実施例では、ランキングの指定は降順でその開始順位は１位のみを示したが、ランキングの指定は昇順でも差し支えない。また、ランキング開始順位は任意の整数値での指定が可能である。例えば、図１１のクエリ１１０１はストリームｓから、ｓ．ｉｄとｓ．ｖａｌの値の組を、ｓ．ｉｄの値でグルーピングしてそれぞれのｓ．ｖａｌの値の最新の１件を保持し、開始順位１０位からｓ．ｖａｌの値の昇順に３件を出力することを示している。図３のクエリ３０１との違いは、３行目のＯＦＦＳＥＴ句とＡＳＣ指定であり、前者が開始順位の指定、後者が昇順の指定である。ＯＦＦＳＥＴ指定がある場合には、図９のランキング処理の受け取ったタプルがランキングに影響するか否かのチェック（９０４）は、受け取ったストリームタプルが、ＯＦＦＳＥＴ句で指定された開始順位から、ＬＩＭＩＴ句で指定された出力指定範囲に影響するか否かをチェックすればよい。ランキング情報の保持、管理に関しては、図２に示したランキング処理モジュール（１１６）でＯＦＦＳＥＴ指定なしの場合と同様に処理できる。
さらに、上述の実施例ではランキング付け対象のカラムが明示的にシステム投入されるが、ランキング付け対象のカラムを自動的に決定するシステムにも本発明は適用可能である。
【図面の簡単な説明】
【００５３】
【図１】本発明におけるストリームデータ処理システムの構成を示す図。
【図２】本発明におけるランキング処理モジュールの構成を示す図。
【図３】本発明におけるランキング指定を含むクエリ（順位出力指定含まず）の例。
【図４】本発明におけるランキング計算の計算内容（順位出力指定含まず）を示す図。
【図５】本発明におけるランキング計算結果の出力結果（順位出力指定含まず）を示す図。
【図６】本発明におけるランキング指定を含むクエリ（順位出力指定含む）の例。
【図７】本発明におけるランキング計算の計算内容（順位出力指定含む）を示す図。
【図８】本発明におけるランキング計算結果の出力結果（順位出力指定含む）を示す図。
【図９】本発明におけるランキング処理手順を示すフローチャート。
【図１０】本発明におけるランキング情報保持バッファメンテナンス処理手順を示すフローチャート。
【図１１】本発明におけるランキング指定を含むクエリ（オフセット指定含む）の例。
【図１２】クエリ処理言語ＣＱＬによるクエリ記述例。
【図１３】本発明におけるランキング情報の二分探索木による表現の例。
【図１４】本発明におけるランキング情報保持バッファ内のランキング情報保持テーブルの変化の様子を示す図。
【図１５】本発明におけるウィンドウマネージャの構成を示す図。
【図１６】本発明におけるクエリ処理エンジンの計算機上での実現例を示す図。
【図１７】本発明におけるランキング計算方法を示すシーケンス図。
【図１８】本発明におけるランキング情報保持バッファへのストリームタプル追加処理方法を示すフローチャート。
【図１９】本発明におけるランキング情報保持バッファからのストリームタプル削除処理方法を示すフローチャート。
【符号の説明】
【００５４】
１１５…ストリームデータ処理システム
１０７、１２１…ネットワーク
１１３…クエリ処理エンジン
１１６、…ランキング処理モジュール
２０２…ランキング情報保持バッファ
２０３…ランキング情報保持テーブル
２０４…順序・順位生成部
２０６…ストリームタプル受付インタフェース
２０７…ランキング処理結果出力インタフェース
２０８…順位管理インデックス
１１６…ランキング処理モジュール
１１７…メモリマネージャ
１２６…ウィンドウマネージャ
１５０２…ストリームタプル保持バッファ
１５０４…生存期間決定部
１５０５…ストリームデータ受付インタフェース
１５０６…差分情報生成部
３０１、３０２、６０１、６０２、１１０１、１２０１…クエリ
１６０１…ストリームデータ処理サーバ
１６０２…通信インタフェース
１６０３…ＣＰＵ
１６０４…メモリ
１６０５…Ｉ／Ｏインタフェース
１６０６…ストレージ装置
【技術分野】
【０００１】
本発明は、時々刻々と到来するストリームデータをリアルタイムに処理するストリームデータ処理システムにおける、ランキング計算方法、および該計算方法を有するストリームデータ処理システムに関する。
【背景技術】
【０００２】
従来、企業情報システムのデータ管理の中心にはデータベース管理システム（以下、ＤＢＭＳとする）が位置づけられていた。ＤＢＭＳは、処理対象のデータをストレージに格納し、格納したデータに対してトランザクション処理に代表される高信頼な処理を実現している。これに対して、時々刻々と到着する大量のデータをリアルタイム処理するデータ処理システムに対する要求が高まっている。例えば、株取引を支援するファイナンシャルアプリケーションを考えた場合、株価の変動にいかに迅速に反応できるかがシステムの最重要の課題の一つである。従来のＤＢＭＳのように株式のデータを一旦記憶装置に格納してから、該格納データに関して検索を行うようなシステムでは、データの格納とそれに続く検索処理が株価変動のスピードに追いつくことができず、ビジネスチャンスを逃してしまうことになりかねない。例えば、米国特許５４９５６００号（特許文献１）では、記憶されているクエリが周期的に実行される機構を開示しているが、この機構においても前述の株価のようにデータが入ってきた瞬間にクエリを実行することが重要となる。すなわちクエリの実行周期とデータ処理のタイミングのずれが許容できないので、前記のファイナンシャルアプリケーションに代表されるリアルタイムデータ処理には適用が困難であった。Ｊａｖａ（Ｒ）に代表されるプログラミング言語を用いて、各種のリアルタイムアプリケーションを個別に作りこむアプローチは、開発期間の長期化、開発コストの高騰、該アプリケーションを利用する業務の変化への迅速な対応が難しいなどの問題があり、汎用のリアルタイムデータ処理機構が求められるようになっていた。
【０００３】
このようなリアルタイムデータ処理に好適なデータ処理システムとして、ストリームデータ処理システムが提案されている。例えばＲ． Ｍｏｔｗａｎｉ、 Ｊ． Ｗｉｄｏｍ、 Ａ． Ａｒａｓｕ、 Ｂ． Ｂａｂｃｏｃｋ、 Ｓ． Ｂａｂｕ、 Ｍ． Ｄａｔａｒ、 Ｇ． Ｍａｎｋｕ、 Ｃ． Ｏｌｓｔｏｎ、 Ｊ． Ｒｏｓｅｎｓｔｅｉｎ、 ａｎｄ Ｒ． Ｖａｒｍａ著：“Ｑｕｅｒｙ Ｐｒｏｃｅｓｓｉｎｇ、 Ｒｅｓｏｕｒｃｅ Ｍａｎａｇｅｍｅｎｔ、 ａｎｄ Ａｐｐｒｏｘｉｍａｔｉｏｎ ｉｎ ａ Ｄａｔａ Ｓｔｒｅａｍ Ｍａｎａｇｅｍｅｎｔ Ｓｙｓｔｅｍ”、Ｉｎ Ｐｒｏｃ． ｏｆ ｔｈｅ ２００３ Ｃｏｎｆ． ｏｎ Ｉｎｎｏｖａｔｉｖｅ Ｄａｔａ Ｓｙｓｔｅｍｓ Ｒｅｓｅａｒｃｈ （ＣＩＤＲ）、 Ｊａｎｕａｒｙ ２００３ （非特許文献１）にストリームデータ処理システムＳＴＲＥＡＭが開示されている。
【０００４】
ストリームデータ処理システムでは、従来のＤＢＭＳとは異なり、まずクエリ（問合せ）をシステムに登録し、データの到来と共に該クエリが継続的に実行される。ここでのストリームデータとは、映像ストリームのような論理的に継続する一つの大きなデータではなく、ファイナンシャルアプリケーションにおける株価配信データ、小売業でのＰＯＳデータ、交通情報システムにおけるプローブカーデータ、計算機システム管理におけるエラーログ、センサやＲＦＩＤなどのユビキタスデバイスから発生するセンシングデータなど、比較的小さな論理的には独立した大量の時系列データである。ストリームデータは継続してシステムに到着し続けるため、その終わりを待ってから処理を開始するのでは実時間での処理は不可能である。また、システムに到着したデータは、データ処理の負荷に影響されることなく、その到着順を守って処理する必要がある。前記ＳＴＲＥＡＭでは、システムに到来し続けるストリームデータを、最新１０分間などの時間の幅、もしくは最新１０００件などの個数の幅を指定してストリームデータの一部を切り取りながらリアルタイムの処理を実現するため、スライディングウィンドウ（以下単にウィンドウと呼ぶ）と呼ばれる概念を導入している。ウィンドウ指定を含むクエリの記述言語の好適な例としては非特許文献１に開示されているＣＱＬ（Ｃｏｎｔｉｎｕｏｕｓ Ｑｕｅｒｙ Ｌａｎｇｕａｇｅ）をあげることができる。ＣＱＬは、ＤＢＭＳで広く用いられているＳＱＬ（Ｓｔｒｕｃｔｕｒｅｄ Ｑｕｅｒｙ Ｌａｎｇｕａｇｅ）のＦＲＯＭ句に、ストリーム名に続いて括弧を用いることにより、ウィンドウを指定する拡張が施されている。ＳＱＬに関しては、Ｃ． Ｊ． Ｄａｔｅ、 Ｈｕｇｈ Ｄａｒｗｅｎ著：“Ａ Ｇｕｉｄｅ ｔｏ ＳＱＬ Ｓｔａｎｄａｒｄ （４ｔｈ Ｅｄｉｔｉｏｎ）”、Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ Ｐｒｏｆｅｓｓｉｏｎａｌ； ４ ｅｄｉｔｉｏｎ （Ｎｏｖｅｍｂｅｒ ８、 １９９６）、ＩＳＢＮ： ０２０１９６４２６０（非特許文献２）が詳しい。
【０００５】
図１２のクエリ１２０１は非特許文献１の２．１節に示されているＣＱＬによるクエリの例である。該クエリでは、あるＷｅｂプロキシサーバにおいて、ドメインｓｔａｎｆｏｒｄ．ｅｄｕからの現時点から過去１日分のアクセスの総数を計算する。Ｒｅｑｕｅｓｔsは前記Ｗｅｂプロキシサーバに到来し続けるＷｅｂアクセスデータであり、従来のＤＢＭＳで取り扱うテーブル（表）のような静止化されたデータではなく、切れ目のないストリームデータとなる。そのため、アクセスの総数を計算は、ウィンドウ指定“［Ｒａｎｇｅ １ Ｄａｙ Ｐｒｅｃｅｄｉｎｇ］”による、ストリームデータのどの部分を対象とするかの指定なしでは、不可能となる。ウィンドウによって切り取られたストリームデータはメモリ上に保持され、クエリ処理に使用される。代表的なウィンドウの指定方法には、ウィンドウの幅を時間で指定するＲａｎｇｅウィンドウと、ウィンドウの幅をデータ数で指定するＲｏｗウィンドウがある。例えば、Ｒａｎｇｅウィンドウを用いて、［Ｒａｎｇｅ １０ ｍｉｎｕｔｅｓ］とすると、最新の１０分間分がクエリ処理の対象となり、Ｒｏｗウィンドウを用いて［Ｒｏｗｓ １０］とすると、最新の１０件がクエリ処理の対象となる。
【０００６】
ストリームデータ処理システムは、ファイナンシャルアプリケーション、小売業での売り上げモニタリング、交通情報システム、計算機システム管理に代表される、リアルタイム処理が必要とされる応用に対する適用が期待されている。以下、リアルタイム処理を必要とする応用をリアルタイムアプリケーションと呼ぶ。リアルタイムアプリケーションにおいては、膨大な情報から瞬時に重要度の高い情報を取り出すために、ある瞬間でのランキング計算が必要とされる場合が多い。例えばファイナンシャルアプリケーションでは、株価の値動きや取引量が大きい株に注目するためのランキング情報が重要であり、小売業の売り上げモニタリングでは、店舗別、商品別など様々な角度からの売上高、売上数のランキング情報が注目される。また、交通情報システムでは、渋滞度が高い、通行量が多い地区に注目するためのランキング情報が必要となり、計算機管理においても、重大なエラーの数、アクセス数など、管理対象の優先度をつけるためのランキング情報が必須となる。
【０００７】
ランキング計算対象のデータが静止化されている場合、すなわちランキング付けしようとするデータが変更されない場合には、該データをランキング付けしようとするキー（以下、ランキングキー）でソーティングし、ソーティング結果の順位に従って、データを出力すればよい。例えば、データベースに格納されている株価の売上高の上位１０位のランキング情報を計算する際には、その日の各銘柄別の売上高を集計し、売上高をランキングキーとして集計した結果をソートし、上位の１０件を選択して出力すればよい。ユーザが投入したクエリからランキングキー（前述の例では売上高）を自動的に決定する方法が米国特許７２５１６４８号（特許文献２）で開示されている。米国公開特許ＵＳ２００６／０２５９４５７号（特許文献３）では、ＤＢＭＳのクエリで最初のｎ行のみを出力する指定があった場合に、クエリ処理時に条件を追加することによって余分なデータ処理のコストを削減する方法が開示されている。また、前記ＳＱＬでは銘柄別の分類のためのＧＲＯＵＰ ＢＹ句、売上高の総計を計算するための集計関数ＳＵＭ、集計値に基づいてソーティングを実行するＯＲＤＥＲ ＢＹ句が準備されている。これらを組合せることで、データベースに格納されている一日の株取引データから売上高の高い順（もしくは低い順）のランキング計算結果を生成することができる。
【０００８】
しかしながら、前記リアルタイムアプリケーションにおいては、新しいデータ（ストリームデータ）が次々に到来し続けるため、その静止化は困難である。ＤＢＭＳを用いて、リアルタイムアプリケーション向けのランキング計算を実施しようとする場合、ストリームデータが到来するごとに該データをＤＢＭＳに格納し、ＤＢＭＳで前記の分類、集計、ソーティング処理を行う必要がある。これらの処理では、基本的にデータベース内の大量のデータにアクセスする必要があり、処理コストが高い。そのため、リアルタイムアプリケーションから発生するストリームデータが高速で到来する場合、すなわちストリームデータの到来する時間間隔が短い場合には、該時間間隔内での処理の実行は不可能であり、ＤＢＭＳを用いたリアルタイムアプリケーション向けのランキング計算の実現は困難であった。
【０００９】
前述したように、ストリームデータ処理システムでは、無限に続くストリームデータから、処理の対象を前述のウィンドウで切り取って処理している。処理対象のデータは、ウィンドウ中に存在するデータのみであり、ウィンドウから押し出されたデータはランキング処理の対象から削除する必要がある。ウィンドウからデータが押し出されるタイミングは、ウィンドウの指定方法が時間である（前述のＲａｎｇｅウィンドウ）か、件数である（前述のＲｏｗウィンドウ）かによって異なる。件数指定の場合、処理対象のデータがウィンドウから押し出される時刻は、該データがウィンドウに入った瞬間には決定できず、後続のストリームデータによって決定される。一方、時間指定の場合には、処理対象のデータがウィンドウから押し出される時刻は、該データがウィンドウに入った瞬間に決定できるが、その消去タイミング（ウィンドウから押し出されるタイミング）は、後続のデータとは同期しない。
【００１０】
ランキング計算においては、ウィンドウへのストリームデータの挿入の都度、ランキング計算を実行してランキング情報の整合性を保つ必要がある。それに加えて、ウィンドウからのデータの消滅の際にも同様にランキング情報の整合性を保つことが必要となる。とくにウィンドウが時間指定の場合には、後続のデータ到来とは同期しないウィンドウからのデータの消滅タイミングを考慮してランキング計算を実行する必要がある。
【００１１】
さらに、ランキング計算では、処理の効率化によって、ストリームデータ処理システム利用の重要な目的の一つであるリアルタイム処理の制約を守る必要がある。加えて、ストリームデータ処理システムは汎用のデータ処理基盤であるため、ランキング計算結果の差分情報のみを渡す、ランキング計算結果全体を渡す、ランキング計算結果に順位情報を含めるなど利用するアプリケーションの要求に応えるための汎用のインタフェース、そのインタフェースに従う処理を実現する機構を準備する必要がある。以上の条件を満足するストリームデータ処理システム向けのランキング計算方法はこれまで実現されていなかった。
【００１２】
【特許文献１】米国特許５４９５６００号
【特許文献２】米国特許７２５１６４８号
【特許文献３】米国公開特許ＵＳ２００６／０２５９４５７号
【特許文献４】特開２００６−３３８４３２号
【非特許文献１】Ｒ． Ｍｏｔｗａｎｉ、 Ｊ． Ｗｉｄｏｍ、 Ａ． Ａｒａｓｕ、 Ｂ． Ｂａｂｃｏｃｋ、 Ｓ． Ｂａｂｕ、 Ｍ． Ｄａｔａｒ、 Ｇ． Ｍａｎｋｕ、 Ｃ． Ｏｌｓｔｏｎ、 Ｊ． Ｒｏｓｅｎｓｔｅｉｎ、 ａｎｄ Ｒ． Ｖａｒｍａ著：“Ｑｕｅｒｙ Ｐｒｏｃｅｓｓｉｎｇ、 Ｒｅｓｏｕｒｃｅ Ｍａｎａｇｅｍｅｎｔ、 ａｎｄ Ａｐｐｒｏｘｉｍａｔｉｏｎ ｉｎ ａ Ｄａｔａ Ｓｔｒｅａｍ Ｍａｎａｇｅｍｅｎｔ Ｓｙｓｔｅｍ”、Ｉｎ Ｐｒｏｃ． ｏｆ ｔｈｅ ２００３ Ｃｏｎｆ． ｏｎ Ｉｎｎｏｖａｔｉｖｅ Ｄａｔａ Ｓｙｓｔｅｍｓ Ｒｅｓｅａｒｃｈ （ＣＩＤＲ）、 Ｊａｎｕａｒｙ ２００３
【非特許文献２】Ｃ． Ｊ． Ｄａｔｅ、 Ｈｕｇｈ Ｄａｒｗｅｎ著：“Ａ Ｇｕｉｄｅ ｔｏ ＳＱＬ Ｓｔａｎｄａｒｄ （４ｔｈ Ｅｄｉｔｉｏｎ）”、Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ Ｐｒｏｆｅｓｓｉｏｎａｌ； ４ ｅｄｉｔｉｏｎ （Ｎｏｖｅｍｂｅｒ ８、 １９９６）、ＩＳＢＮ： ０２０１９６４２６０
【発明の開示】
【発明が解決しようとする課題】
【００１３】
リアルタイムアプリケーションで必要となるランキング計算を実現するためにストリームデータ処理システムを用いる場合、ウィンドウへのストリームデータの挿入に加えて、該ストリームデータの消滅の際にも整合性を保つランキング処理の実現が必要となる。また、リアルタイムと呼べるランキング処理結果を得るには、処理対象ウィンドウの内部データの時々刻々の変化の度に実行するランキング更新の処理を高速化する必要がある。
【００１４】
本発明の目的は、処理対象ウィンドウの内部データの時々刻々の変化の度に行なうランキング更新の演算を高速化でき、しかも処理結果の整合性を保つランキング処理方法及びシステムを提供するにある実現することにある。
【課題を解決するための手段】
【００１５】
本願で開示される発明のうち、代表的な発明の概要は以下の通りである。すなわち、代表的実施態様ではウィンドウへのストリームデータの挿入、削除の度毎に、すなわちあるストリームタプルの生存期間の開始、及びあるストリームタプルの生存期間の終了の度毎に、生存期間にあるストリームタプルの範囲内でそれらのランキングを生成・更新し、かつ出力指定された順位の範囲を越えて、生存期間にあるストリームタプルの範囲内でバッファに保存するストリームデータ処理を採用する。
【００１６】
ある時点でのランキング情報の出力だけから言えば、ランキング情報の保存は出力指定された順位のストリームタプルの範囲で行なえば一見充分であるかに思われる。しかしながら、新たなストリームタプルの受け付けに起因して、ウィンドウ内のストリームタプルへの挿入および削除が生じ、その挿入、削除の度にランキングそのものが変動する。したがって、整合性のあるランキング計算を継続して実行するには、その挿入・削除の度毎にランキング情報の更新が必要であり、かつ出力指定された順位の範囲を越えて、生存期間にあるストリームタプルの範囲内のストリームタプル及びそれらのランキング情報を保存する必要がある。
【００１７】
さらに上記代表的実施態様は、受け付けたストリームタプルをランキング計算の処理対象としてウィンドウへ挿入し、該ストリームタプルのウィンドウ内での生存期間を決定し、生存期間の終了時には上記ウィンドウからの削除を行なうウィンドウマネージャと、ランキング計算を行うランキング処理モジュールとの２段階の処理機構を持ち、上記ウィンドウマネージャは、ウィンドウ内のストリームタプル全体の情報ではなく、刻々の変化部分を示すウィンドウ差分情報を上記ランキング処理モジュールに伝達し、上記ランキング処理モジュールは、伝達された上記ウィンドウ差分情報と、過去にランキング計算を行って保存した保存情報とを用いてランキングの更新を行う構成とした点に特徴を有する。具体的には当該ストリームタプルがウィンドウに挿入されたことを示す符号を付加したストリームタプル、および当該ストリームタプルがウィンドウから削除されたことを示す符号を付加したストリームタプルが上記のウィンドウ差分情報としてランキング処理モジュールに伝達され、ランキング処理モジュールでは該差分情報に基づいてランキング情報を更新し、ランキング情報保持バッファに保存するとともに、指定された形式でランキング出力情報を出力する。
【発明の効果】
【００１８】
本発明を用いることにより、時々刻々と到来する大量データをリアルタイム処理するストリームデータ処理システムにおいて、入力されるストリームデータとの整合性を保ち、かつ高速、高効率のランキング計算が実現できる。本ランキング計算方法の適用により、リアルタイムアプリケーションで共通に利用可能なデータ処理基盤が提供できる。
【発明を実施するための最良の形態】
【００１９】
図１および図１６に、本発明のストリームデータ処理システムの好適な実現例を示す。アプリケーション１（１０２）を実行するクライアント計算機１０１、アプリケーション２（１０４）を実行するクライアント計算機１０３は、ネットワーク１０７を介してストリームデータ処理システム１１５に接続されている。ネットワーク１０７は、イーサネット、光ファイバなどで接続されるローカルエリアネットワーク（ＬＡＮ）、もしくはＬＡＮよりも低速なインターネットを含んだワイドエリアネットワーク（ＷＡＮ）でも差し支えない。また、クライアント計算機はパーソナルコンピュータ、ブレード型の計算機システムなどの任意のコンピュータシステムでよい。
【００２０】
本実施例のストリームデータ処理システムが稼動する計算機をストリームデータ処理サーバと呼ぶ。図１６に示すように、ストリームデータ処理サーバ１６０１は、イーサネットアダプタなどの通信インタフェース１６０２、ＣＰＵ１６０３、メモリ１６０４、およびＩ／Ｏインタフェース１６０５を備えた計算機であり、ブレード型計算機システム、ＰＣサーバなどの任意のコンピュータシステムでよい。ストリームデータ処理サーバでは、前記通信インタフェースを介して前記クライアント計算機、後述するデータソースにアクセスする。ストリームデータ処理サーバで、ストリームデータ処理結果、処理の中間結果、システム動作に必要な設定データを不揮発性のストレージに格納する場合には、ストリームデータ処理サーバに接続したストレージ装置１６０６を用いることができる。ストレージ装置１６０６は、ストリームデータ処理サーバのＩ／Ｏインタフェースを介して直接接続されるか、もしくは通信インタフェースを介してネットワーク接続される。
【００２１】
ストリームデータ処理システム１１５は、前記ストリームデータ処理サーバ１６０１の上で動作する。図１にストリームデータ処理システムの主要構成要素を示す。アプリケーションは、まずストリームデータ処理システムにクエリを登録する（１０５）。登録されたクエリはクエリ管理テーブル（１１２）に格納される。クエリ登録の詳細な手順、ストリームデータ処理システム内部のデータの格納方法、格納形式、クエリを受け付けた後の解析方法、最適化方法、システムへの登録方法、ストリームデータ処理システムへのストリームの登録方法、システム内のデータ保持方法については、特開２００６−３３８４３２号「ストリームデータ処理システムのクエリ処理方法」（特許文献４）に、その好適な実施の方法が開示されている。クエリ管理テーブルは、ストリームデータ処理サーバ上のメモリ１６０４に保持するのでも、ストリームデータ処理サーバに接続されているストレージ装置１６０６に格納するのでも差し支えない。
【００２２】
ストリームデータ処理システムには、一つ以上のストリームデータソースであるストリームデータソース１（１２２）〜ストリームデータソースＮ（１２３）からネットワーク１２１を介して時々刻々と大量のデータが到来する。このデータをストリームデータと呼ぶ。ストリームデータの好適な例としては、ファイナンシャルアプリケーションにおける株価配信情報、小売業でのＰＯＳデータ、交通情報システムにおけるプローブカー情報、計算機システム管理におけるエラーログなどが挙げられる。ストリームデータ処理システムでは、通信インタフェース１６０２を介してデータフローマネージャ１１９が受け付けたストリームデータをクエリ処理エンジン１１３にフィードする。
【００２３】
前述したように、継続して到来する比較的小さな論理的には独立した大量の時系列データであるストリームデータを取り扱うために、ストリームデータ処理システムではウィンドウを用いる。図１のウィンドウマネージャ１２６は、到来するストリームデータに対して、クエリで指定されたウィンドウ演算を適用してストリームタプルを生成し、ストリームタプルのシステム内での生存期間を設定する。ストリームデータがウィンドウに挿入された時が生存期間の開始時刻、そしてウィンドウから該ストリームデータが削除される時が生存期間の終了時刻に相当する。
【００２４】
図１５を用いて、ウィンドウマネージャの構成と動作内容を説明する。ウィンドウマネージャ１２６は、ストリームデータ受付インタフェース１５０５、ストリームタプル保持バッファ１５０２、生存期間決定部１５０４、および差分情報生成部１５０６から構成される。ストリームデータ受付インタフェースは、受け付けたストリームデータの構成要素であるストリームタプルを、ストリームタプル保持バッファ１５０２に格納するとともに、生存期間決定部１５０６に格納したことを伝達する。生存期間決定部１５０６は前記ウィンドウ演算により各ストリームタプルの生存期間を決定し、生存期間が終了するストリームプルをストリーム保存バッファ１５０２から消去する。差分情報生成部１５０４は、ストリームタプルが該ストリームタプル保持バッファに格納されたタイミングで、プラスタプルを生成し、差分情報として出力する（１５０８）。同様に、ストリームタプルがストリームタプル保持バッファから消去されるタイミング（ストリームタプルの生存期間が終了するタイミング）でマイナスタプルを生成し、同様に差分情報として出力する（１５０８）。
【００２５】
図１６に示すように、ストリームタプル保持バッファ１５０２は、クエリ処理エンジン１１３内のメモリマネージャ１１７によって割り当てられるメモリ上に配置される。該メモリは、ストリームデータ処理サーバ１６０１上のメモリ１６０４、もしくは要求される性能要件、信頼性要件に応じて、ストリームデータ処理サーバに接続されたストレージ装置１６０６、もしくはストリームデータ処理サーバとネットワークで接続される、ストリームデータ処理サーバと同様の計算機資源を保持するサーバ計算機（図１のブロック１３３）上のメモリを利用してもよい。
【００２６】
次に、図２を用いてランキング処理モジュールの構成を説明する。ランキング処理モジュール１１６はストリームタプル受付インタフェース２０６、順序・順位生成部２０４、ランキング情報保持バッファ２０２、ランキング情報保持テーブル２０３、順位管理インデックス２０８、およびランキング処理結果出力インタフェース２０７から構成される。図１６に示すように、ランキング処理モジュールは、クエリ処理エンジン１１３内のメモリマネージャ１１７によって割り当てられるメモリ上に配置される。該メモリは、ストリームデータ処理サーバ１６０１上のメモリ１６０４、もしくは要求される性能要件、信頼性要件に応じて、ストリームデータ処理サーバに接続されたストレージ装置１６０６、もしくはストリームデータ処理サーバとネットワークで接続される、ストリームデータ処理サーバと同様の計算機資源を保持するサーバ計算機（図１のブロック１３３）上のメモリを利用してもよい。
【００２７】
図１７に本発明のストリームデータ処理における、ランキング情報生成のシーケンスを示す。前記ウィンドウマネージャ１２６は外部データソースから到来するストリームデータを受け付け（１７０１）、差分情報（符号付ストリームタプル）を生成する（１７０２）。ランキング処理モジュール１１６では、ストリームタプル受付インタフェース２０６が、前記ウィンドウマネージャから出力された差分情報（符号付ストリームタプル）を受け取り、順序・順位生成部２０４に転送する。順序・順位生成部では、ランキング情報保持バッファ２０２を参照しながら、受け取った符号付ストリームタプルをランキングバッファの適切な位置に追加、もしくはランキングバッファ内の適切な位置のランキング情報を削除し、前回の出力時とのランキング情報の差分（ランキング差分情報）を生成し（１７０５）、該ランキング差分情報をランキング処理結果出力インタフェース２０７に転送する（１７０６）。ランキング処理結果出力インタフェースでは、前記クエリによって指定されているデータの出力形式に従ってランキング情報を出力する。
【００２８】
以下、具体的なクエリ、ストリームデータに対する、本実施例のランキング計算方法を説明する。図３（ａ）に示すクエリ３０１は、順位出力（順位そのものを出力すること）を指定しないランキング処理を命じるクエリである。１行目のＳＥＬＥＣＴ句はｓ．ｉｄとｓ．ｖａｌの値の組を出力対象とすることを、２行目のＦＲＯＭ句はストリームｓを対象とすることを、同じく２行目のＰａｒｔｉｔｉｏｎ Ｂｙ句はｓ．ｉｄの値でグルーピングしてそれぞれのｓ．ｖａｌの値の最新の１件を保持することを、また３行目のＬＩＭＩＴ句は、ｓ．ｖａｌの値の降順に３件を出力すること意味する。本実施例のストリームデータ処理システムでは、予め入力されるクエリにて、ランキング計算の対象となるカラムと、ランキング付けの方向（昇順／降順）と、ランキング計算結果を出力する個数と、計算結果に順位情報を付与するか否かが指定される。クエリ３０１では、３行目のＬＩＭＩＴ句が、ｓ．ｖａｌの値の降順に３件を出力するランキング指定である。さらに、１行目のＩＤＳＴＲＥＡＭ句は、本クエリは出力として前回の出力時との差分情報のみを出力することを意味している。
【００２９】
図４および図５（ａ）を用いて、クエリ３０１が設定されたストリームデータ処理システムに対して、ストリームデータが到来した際の処理内容を説明する。クエリ３０１がストリームデータ処理システム１１５に登録された場合、例えば特許文献４に示された方法でクエリ解析、クエリ最適化、クエリ生成が実行され、クエリ処理エンジンにクエリの実行形式が登録される。クエリ３０１はランキング計算指定を含むため、実行形式のクエリの実行時には、クエリ処理エンジン１１３内のランキング処理モジュール１１６でランキング計算が実行される。特許文献１で述べられているように、ストリームデータ処理システムでは、クエリは登録された後システム上で動作し続け、一つ一つのストリームデータがシステムに到来するたびに、その状態が変化する。
【００３０】
クエリ３０１が登録されている状況で、図４に示すストリームデータが到来したことを仮定する。図４および図５（ａ）では、時刻の経過を縦軸にとり、時刻の経過と共にシステムに到来したストリームデータが各処理モジュールで処理される様子を模式的に表している。凡例４０２および５０２に示すように、本実施例では到来するストリームデータは｛ｉｄ，ｖａｌ｝の形式と仮定しており、これを楕円で表現している。ｔ１〜ｔ７（４０１）は、４０５〜４１１の各ストリームデータがストリームデータ処理システムに到来する時刻を表している。例えば、ストリームデータ｛ａ，５０｝（４０５）、及びストリームデータ｛ｂ，１０｝（４０６）はそれぞれ、時刻ｔ１、ｔ２にストリームデータ処理システムに到来することを示している。図４の横軸は到来したストリームデータが処理される位置、および生成されるデータを表している。さらに、図４の左側の角丸四角（１５０２）は、システムに到来した前記ストリームデータに対して、前記ウィンドウマネージャ（１２６）でウィンドウ演算“［Ｐａｒｔｉｔｉｏｎ Ｂｙ ｓ．ｉｄ Ｒｏｗｓ １］”（４０３）を適用した結果を格納した、ストリーム保持バッファの各時刻での状態を示している。また、右側の角丸四角（２０２）は、ウィンドウマネージャから到来するストリームタプルに対して、前記ランキング処理モジュール（１１６）内の順序・順位生成部（２０４）における、ランキング計算指定句“ＬＩＭＩＴ ３ Ｂｙ ｓ．ｖａｌ ＤＥＳＣ”（４０４）の適用した結果を格納した、ランキング情報保持バッファの各時刻での状態を示している。
【００３１】
前述したように、ウィンドウマネージャ１２６は、到来するストリームデータに対して、クエリで指定されたウィンドウ演算を適用してストリームタプルを生成し、ストリームタプルのシステム内での生存期間を設定する。図４の例では、生存期間の開始時刻は黒丸（４２６）、終了時刻は白丸４２７で表現されており、該ウィンドウ演算により、ストリームタプル｛ａ，５０｝（４０５）の生存期間は時刻ｔ１に始まり、時刻ｔ７に終わることを示している。本実現例においては、ストリームデータの生存期間の開始時刻には、システム内部で前記のストリームデータに増加分を表す符号を付けたタプル（以下プラスタプル）が生成される。また、ウィンドウからストリームデータが削除された場合、先に出力されたプラスタプルへの参照を持つ、減少分を表す符号を付けたタプル（以下マイナスタプル）が生成される。以上の処理は、前記ウィンドウマネージャで実行される。例えば、図４の場合、時刻ｔ１にはストリームデータ｛ａ，５０｝（４０５）に対応するプラスタプル４３０が生成され、時刻ｔ７に該ストリームデータのマイナスタプル４３１が生成されることとなる。ウィンドウ演算に続く、後段のクエリ処理は、本プラスタプルおよびマイナスタプルが到着したタイミングで該プラスタプルとマイナスタプルに起因して生成される差分情報に関して実行される。なおプラスタプル、マイナスタプルそのものの概念は前述の非特許文献１に紹介されている。
【００３２】
クエリ３０１では、到来するストリームデータはまずウィンドウ演算“［Ｐａｒｔｉｔｉｏｎ Ｂｙ ｓ．ｉｄ Ｒｏｗｓ １］”（４０３）により、ｓ．ｉｄの値毎に最新１個のみが保持される。具体的には、図４で時刻ｔ１にストリームデータ｛ａ，５０｝（４０５）が、時刻ｔ２に｛ｂ，１０｝（４０６）が、時刻ｔ３に｛ｃ，３０｝（４０７）が、時刻ｔ４に｛ｄ，２０｝（４０８）が、そして時刻ｔ５に｛ｅ，４０｝（４０９）がそれぞれ到来する。これら５つのストリームデータはｓ．ｉｄの値が異なるので、それぞれウィンドウに保持される。次に、時刻ｔ６に新たなストリームデータ｛ｅ，１５｝（４１０）が到来すると、それまでウィンドウに保持されていたｓ．ｉｄの値がｅのストリームデータ４０９はウィンドウから押し出される（削除される）。次に時刻ｔ７に｛ａ，４５｝（４１１）が到来すると、同様に｛ａ，５０｝（４０５）がウィンドウから削除される。この様子を図示したのが図４の中央部分４２９である。例えば、ストリームデータ｛ａ，５０｝（４１２）は時刻ｔ１に到来し、時刻ｔ７に｛ａ，４５｝（４１８）が到来するまでウィンドウに保持される。この時、ストリームデータ｛ａ、５０｝の生存期間はｔ１からｔ７（但し時刻ｔ７は含まない）と表現する。図４の例では、生存期間の開始時刻は黒丸（４２６）、終了時刻は白丸（４２７）で、生存期間中は実線で表している。同様にして、｛ｅ，４０｝（４１７）の生存期間はｔ５からｔ６となる。一方、｛ｂ，１０｝（４１３）、｛ｃ，３０｝（４１４）、｛ｄ，２０｝（４１５）、｛ｅ，１５｝（４１７）、および｛ａ，４５｝（４１８）については、時刻ｔ７の時点では終了時刻が決定していないため、実線で表現されている。
【００３３】
以上のように生存期間を持つストリームデータから、どのようにランキング情報を生成するかを、同じく図４を用いて説明する。図４の右側４３２に、ランキング計算指定句“ＬＩＭＩＴ ３ Ｂｙ ｓ．ｖａｌ ＤＥＳＣ”（４０４）による処理結果を示す。前述したように、本ランキング指定句の意味は、ｓ．ｖａｌの値で降順に３件を抽出することである。今、ストリームデータ｛ａ，５０｝（４１９）、｛ｂ，１０｝（４２０）、｛ｃ，３０｝（４２１）がそれぞれ時刻ｔ１、ｔ２、ｔ３に到来する。これら３つのストリームデータは上位３件ランキング情報としてそれぞれ出力される。次に、時刻ｔ４に｛ｄ，２０｝（４２２）が到来すると、そのｓ．ｖａｌの値２０は、これまでに保持されている｛ｂ、１０｝の１０よりも大きいため、｛ｂ，１０｝が上位３件のランキング情報から削除されてその生存期間がｔ４で終了し（４２８）、｛ｄ，２０｝がランキング計算結果として出力される。次に時刻ｔ５に｛ｅ，４０｝（４２３）が到来すると、そのｓ．ｖａｌの値は４０となるため、上位３件に含まれるため、ランキング情報として出力される。そしてこれまで上位３件に保持されていた中で最も値の小さい｛ｄ，２０｝がランキングから削除される。ところが、時刻ｔ６には、前述したように｛ｅ、１５｝（４１７）の到来により｛ｅ，４０｝（４１６）がウィンドウから削除されるため、再び｛ｄ，２０｝（４２４）が上位３件に復活することになり、再びランキング計算結果として出力される。時刻ｔ７には｛ａ，５０｝（４１２）が｛ａ、４５｝（４１８）に置き換わり、｛ａ，４５｝のｓ．ｖａｌの値４５は上位３件に含まれるため、｛ａ，４５｝（４２５）がランキング結果として出力される。
【００３４】
以上のランキング計算の好適な実施方法を図２、図９、図１０、図１８、および図１９を用いて説明する。ランキング処理モジュール１１６のストリームタプル受付インタフェース２０６が差分情報であるストリームタプルを受け取る（９０２）。すると、順序・順位生成部２０４はランキング情報保持バッファ２０２のバッファメンテナンスを実行する（９０３）。バッファメンテナンス処理の処理方法について、図２および図１０を用いて説明する。順序・順位生成部２０４は、ストリームタプルを受け取ると、該ストリームタプルの符号がプラスであるかマイナスであるかをチェックする（１００２）。符号がプラスの場合（１００２でＹｅｓが選択された場合）、ランキング情報保持バッファ２０２のランキング情報保持テーブル２０３に受け取ったストリームタプルを追加し（１００３）、ランキング情報保持バッファメンテナンス処理を終了する。ランキング情報保持バッファへのストリームタプル追加処理の詳細を図１８のフローチャートを用いて説明する。順位・順序生成部では、追加対象のストリームタプル（符号がプラスのストリームタプル）を受け取ると、追加先のランキング情報保持テーブル２０３に順位管理インデックス２０８が付与されているかどうかをチェックする（１８０２）。順位管理インデックスは、順位付けの対象のカラムをキーとしたＢ＋ｔｒｅｅインデックスやハッシュインデックスで差し支えない。順位管理インデックスが存在する場合（ステップ１８０２でＹｅｓが選択された場合）には、順位・順序生成部は該インデックスを利用して追加対象のストリームタプルの、ランキング情報保持テーブルへの挿入位置を決定する（１８０３）。該インデックスが存在しない場合（ステップ１８０２でＮｏが選択された場合）には、順位・順序生成部はランキング情報保持テーブルを検索し、追加対象のストリームタプルの、ランキング情報保持テーブルへの挿入位置を決定する（１８０４）。挿入位置を決定した後、順位・順序生成部は追加対象のストリームタプルをランキング情報保持テーブルに挿入し（１８０５）、順位管理インデックスが存在する場合（ステップ１８０６でＹｅｓが選択された場合）には、該インデックスも更新してランキング情報保持バッファへのストリームタプル追加処理を終了する（１８０８）。
【００３５】
好適なランキング情報保持バッファの実現形態では、追加されたストリームタプルの、ランキング指定されたカラムの値での順序関係が保持される。ストリームタプルの追加時に順序関係を保持しておく理由は、遅延処理により一括して順序関係を作成する方法では、リアルタイム処理アプリケーションの要求である即時の結果出力が困難であるためである。例えば、図３のクエリ３０１の場合には、順序付けの対象となるカラム（前述のランキングキー）はｓ．ｖａｌであるので、図２のランキング情報保持バッファ中のランキング情報保持テーブル（２０３）ではｓ．ｖａｌの降順に順位情報とストリームタプルを保持している。
【００３６】
図１０に戻って、受け取ったストリームタプルの符号がマイナスの場合（図１０の１００２でＮｏが選択された場合）、ランキング情報保持バッファ（２０２）から該ストリームタプルに対応する、符号がプラスのタプルを削除し（１００４）、ランキング情報保持バッファメンテナンス処理を終了する。
【００３７】
ランキング情報保持バッファからのストリームタプル削除処理の詳細を図１９のフローチャートを用いて説明する。順位・順序生成部では、ランキング情報保持テーブル２０３に順位管理インデックス２０８が付与されているかどうかをチェックする（１９０２）。順位管理インデックスが存在する場合（ステップ１９０２でＹｅｓが選択された場合）には、順位・順序生成部は該インデックスを利用して、ランキング情報保持テーブル中の削除対象のストリームタプルを検索する（１９０３）。該インデックスが存在しない場合（ステップ１９０２でＮｏが選択された場合）には、順位・順序生成部はランキング情報保持テーブルを検索し、削除対象のストリームタプルを決定する（１９０４）。削除対象のストリームタプルが決定されると、順位・順序生成部では該ストリームタプルの削除処理を実行する（１９０５）。順位管理インデックスが存在する場合（ステップ１９０６でＹｅｓが選択された場合）には、順位管理インデックスも更新し、ランキング情報保持バッファからのストリームタプル削除処理を終了する。
【００３８】
ここで図１４を用いて、図３（ａ）のクエリを登録したストリームデータ処理システムに対して、図４で示したタイムチャートでストリームが到来する場合の、ランキング情報保持テーブルに保持されるランキング情報の変化の様子を説明する。図１４では、左側のｔ０（１４１６）、ｔ１（１４０４）、…、ｔ７が時刻を、中央の符号付きの楕円（１４０５、１４０７、…）がウィンドウマネージャで生成された差分情報（符号付ストリームタプル）を、そして右側のテーブル（１４１７、１４０６、…、１４１５）がランキング情報保持テーブルに保持されるランキング情報を表す。便宜上時刻ｔ１以前のｔ０にはランキング情報は存在しなかったと仮定する。
【００３９】
時刻ｔ１（１４０４）に、プラスの符号を持つストリームタプル｛ａ，５０｝（１４０５）が到来すると、ランキング情報保持テーブルに該ストリームタプルが登録される（１４０６）。次に、時刻ｔ２（１４１８）にプラスの符号を持つストリームタプル｛ｂ，１０｝（１４０７）が到来すると、その順位付け対象ｓ．ｖａｌの値である１０を、ランキング情報保持テーブルに保持されているストリームタプルのｓ．ｖａｌの値５０と比較し、挿入位置が｛ａ，５０｝（１４０５）の次と決定され、該挿入位置にストリームタプル｛ｂ，１０｝が挿入される（１４０８）。以下同様に、ｔ３、ｔ４、ｔ５にそれぞれ、｛ｃ，３０｝、｛ｄ，２０｝、｛ｅ，４０｝が到来すると、これらのストリームタプルが順位付け対象のｓ．ｖａｌの値の順にソートされて登録される。
【００４０】
図４に示すように、時刻ｔ６において｛ｅ，１５｝（４０８）が到来すると、図３（ａ）に示した１行指定のＲｏｗウィンドウクエリでは｛ｅ、４０｝がウィンドウから削除される（４３３）。そのため、図１４に示すランキング処理モジュール（１１６）のストリームタプル受付インタフェース２０６には、マイナス符号の付いたストリームタプル｛ｅ，４０｝（１４１３）と、プラス符号の付いたストリームタプル｛ｅ，１５｝（１４１４）が到来する。順序・順位生成部２０４では、マイナス符号の付いたストリームタプル｛ｅ，４０｝に対応するプラス符号の付いたストリームタプルを検索、決定し（１４１２の上から２番目）、該ストリームタプルを削除する。そして、プラス符号の付いた新たなストリームタプル｛ｅ，１５｝（１４１４）の挿入位置を決定し（１４１５の上から４番目）、ランキング情報保持テーブルに該ストリームタプルを追加する。時刻ｔ７についても同様である。
【００４１】
本実施例では、ランキング情報保持バッファ内でのデータ構造がテーブルの場合を示したが、ランキング情報保持バッファ内でのデータ構造の他の好適な実現例としては、例えば図１３に示すようなランキングキーをノードとした二分探索木（ｂｉｎａｒｙ ｓｅａｒｃｈ ｔｒｅｅ）を挙げることができる。図１３では、二分探索木のノード（ランキングキー）を四角１３０１で、ノードからポイントされるデータ本体（ストリームタプル）を円と楕円の組１３０２で示した。二分探索木を用いる場合には、ランキングキーをノードとして、あるノードの左側の子およびその全ての子孫ノードのランキングキーの値は、該ノードのランキングキーの値より小さく、右の子およびその全ての子孫ノードの値は該ノードのランキングキーの値と等しいもしくは大きくなるように構成する。図１３の角丸四角１３０３内の二分探索木は、図４の時刻ｔ５の時点でのランキング情報保持バッファが保持するデータの二分探索木での構成の例であり、保持しているデータの内容は図１４のランキング情報保持テーブル１４１２と等しい。二分探索木を用いてランキングキーに基づいた順序を管理することで、前記プラスタプル、および前記マイナスタプル到来時の順序関係の管理を効率化することができる。さらに、ストリームタプルの順序関係を保持して管理するための他の好適なデータ構造としては、多くのＤＢＭＳのデータ管理機構で利用されるＢ＋−Ｔｒｅｅを利用するのでも差し支えない。
【００４２】
ランキング情報保持バッファでは、ユーザに指定されたランキングの出力件数のみでなく、生存期間中のストリームデータに対応する全てのストリームタプルを保持する必要がある。例えば、図３のクエリ３０１では、ユーザからは上位３件のみを出力するように指示されているが、図４に示すストリームデータの系列がシステムに到来する場合、時刻ｔ４で｛ｄ，２０｝（４０８）が到来した際に、前記ランキング情報保持バッファから、順位が４位となったストリームデータ｛ｂ，１０｝（４０６）に対応するストリームタプル４３３を削除してはならない。その理由は、ストリームデータ処理においては、新しいストリームデータがシステムに到来するときに加えて、ストリームデータの生存期間が終了した際にもランキングが変化するため、現在はユーザが指定した範囲外にあるストリームデータが、他のストリームデータの生存期間の終了によって、再びランキング結果として出力する必要が出てくるためである。例えば、図４では時刻ｔ４で到来し、上位３件に含まれたストリームデータ｛ｄ，２０｝（４０８）が時刻ｔ５に到来した｛ｅ，４０｝（４０９）によってランキング外に押し出されてしまっているが、時刻ｔ６に到来した｛ｅ，１５｝（４１０）によって、｛ｅ，４０｝はウィンドウから消去される（４３３）ため、｛ｄ，２０｝は再びランキング計算結果に含まれる（４２４）必要がある。すなわち、ランキング情報保持バッファでは、ユーザに指定されたランキングの出力件数のみでなく、ウィンドウで管理されているストリームデータに対応する全て、すなわち生存期間中のストリームデータに対応する全てのストリームタプルを保持する必要がある。
【００４３】
但し、ストリームタプルが到着した瞬間に上位５０位以内に含まれていない場合には、該ストリームタプルはランキングの対象としないなどのアプリケーションの特別な条件が存在する場合には、該アプリケーションの条件に従ってランキング情報保持バッファで保持するストリームタプルの数を変更することは可能である。
【００４４】
図９に戻って、順序・順位生成部では、受け取ったストリームタプルのバッファメンテナンス処理（９０３）の結果に基づき、該処理結果がランキングに影響するか否かをチェックする（９０４）。処理結果がランキングに影響を及ぼす場合とは、受け取ったストリームタプルに基づいたランキング情報保持バッファのメンテナンスの結果、クエリで指定されている範囲の順序に変更がある場合を指す。例えば、図３のクエリ３０１では、上位３件を出力の範囲に指定しているため、上位３位以内の順序に変更がある場合、処理結果がランキングに影響するか否かの判定（ステップ９０４）はＹｅｓとなる。例えば、図４で示した処理の場合、時刻ｔ４で｛ｄ，２０｝が到来した場合には上位３位以内の順序に変更があるので、Ｙｅｓの例となる。処理結果がランキングに影響する場合（ステップ９０４でＹｅｓが選択された場合）、順序出力指定があるかないかをチェックする（９０５）。順序出力指定がある場合（ステップ９０５でＹｅｓが選択された場合）、処理結果タプルへの順位情報カラムを追加して（９０６）、処理結果タプルを出力し（９０７）、ランキング処理を終了する（９０８）。順位出力の指定がない場合（ステップ９０５でＮｏが選択された場合）、処理結果タプルを出力し（９０７）、ランキング処理を終了する（９０８）。
【００４５】
図３のクエリ３０１の場合には、順位出力の指定はないので、ランキング処理結果出力インタフェースから出力する処理結果タプルは、例えば図５の５２３に示すものであり、順位情報は付加されていない。順位出力の指定がある場合（ステップ９０５でＹｅｓが選択された場合）の例については後述する。
【００４６】
前述したように、リアルタイムアプリケーションのランキング計算では、膨大な情報から瞬時に有用な情報を取り出す必要があるため、処理の効率化が必要となる。そこで、本実施例のストリームデータ処理システムでは、ランキングに変動があった差分だけを出力するインタフェースと、その時点のランキング内の全データを出力するインタフェースを備える。図５（ａ）中央の２０２は、図４で説明したクエリ３０１（図３）のウィンドウ演算“［Ｐａｒｔｉｔｉｏｎ Ｂｙ ｓ．ｉｄ Ｒｏｗｓ １］”、およびランキング計算指定句“ＬＩＭＩＴ ３ Ｂｙ ｓ．ｖａｌ ＤＥＳＣ”の処理結果を格納したランキング情報保持バッファの各時刻での状態を示している。クエリ３０１では、最終的な出力形式として、ＩＤＳＴＲＥＡＭ句が指定されている。ＩＤＳＴＲＥＡＭ句は、ランキング計算の結果、ランキングに追加されたタプルを増加分タプルとして、ランキングから削除されたタプルを減少分タプルとして出力するインタフェースである。図５（ａ）では、ＩＤＳＴＲＥＡＭ句（５０４）によって処理された後のストリームデータを図の右側の角丸四角５２３内に示した。ただし、該ストリームデータの黒丸は増加分、白丸は減少分を表す。以下、ＩＤＳＴＲＥＡＭ句の処理の内容について説明する。時刻ｔ１に｛ａ，５０｝（５０５）がランキングに追加されるので、ＩＤＳＴＲＥＡＭ句では処理結果の増加分ストリームデータとして｛ａ，５０｝（５１２）を出力する。次に時刻ｔ２、ｔ３にそれぞれ｛ｂ，１０｝（５０６）および｛ｃ，３０｝（５０７）がランキングに追加されるので、｛ｂ，１０｝（５１４）および｛ｃ，３０｝（５１５）が増加分として出力される。時刻ｔ４には、｛ｄ，２０｝（５０８）がランキングに挿入されると共に、｛ｂ，１０｝（５０６）がランキングから削除される。この場合、ＩＤＳＴＲＥＡＭ句では、時刻ｔ４に｛ｄ，２０｝（５１６）を増加分として、｛ｂ，１０｝（５１７）を減少分として出力する。増加分と減少分の情報のみを計算し、該情報を利用するクライアント計算機に送信することにより、ストリームデータ処理システムの処理コスト、および通信コストを削減することができる。例えば図５（ａ）の場合、ｔ１からｔ７までの間に、クライアント計算機に対して１１個の処理結果が送信されるが、各タイミングで上位ｎ件の全結果を全て送信する場合にはｎ×７個の処理結果を送信する必要があり、特にｎが大きい場合差分情報のみを送信する本発明の効果は高い。
【００４７】
但し、クライアント計算機側でランキング情報を随時ユーザに提供し続ける必要がある場合には、クライアント計算機側で差分情報から全体のランキング情報を作成し続ける必要がある。本処理では、クライアント計算機側で状態（ステート）を管理する必要があるため、クライアント計算機の状態、リアルタイムアプリケーションの形態によっては実現が難しい場合もある。このような状況でもランキング情報を利用できるようにするために、本出願のストリームデータ処理システムでは、生成した差分ランキング情報から全体のランキング情報を生成し、出力するインタフェースを備える。図３（ｂ）のクエリ３０２は、１行目のＲＳＴＲＥＡＭ句以外はクエリ３０１と同一であり、１行目のＳＥＬＥＣＴ句はｓ．ｉｄとｓ．ｖａｌの値の組を出力対象とすることを、２行目のＦＲＯＭ句はストリームｓを対象とすることを、同じく２行目のＰａｒｔｉｔｉｏｎ Ｂｙ句はｓ．ｉｄの値でグルーピングしてそれぞれのｓ．ｖａｌの値の最新の１件を保持することを、３行目のＬＩＭＩＴ句はｓ．ｖａｌの値の降順に３件を出力することを指定する。クエリ３０１の１行目のＩＤＳＴＲＥＡＭ句が、前回の出力時との差分情報のみを出力するのに対して、クエリ３０２の１行目のＲＳＴＲＥＡＭ句は、出力のタイミング毎に、出力指定範囲内のストリームタプル全てのランキング情報を出力することを意味している。図５（ｂ）に、該インタフェースでのランキング計算出力結果を示す。図５（ｂ）のランキング情報保持バッファ（２０２）の各時刻の状態は図５（ａ）の場合と同じである。ＬＩＭＩＴ句の処理後に、図３（ｂ）に示すクエリ３０２のＲＳＴＲＥＡＭ句を適用した結果が図５（ｂ）の右側の角丸四角５２６内に示すストリームデータとなる。以下図５（ｂ）を用いて、ランキング計算結果の出力形式について説明する。時刻ｔ１に｛ａ，５０｝（５０５）がランキングに追加されるので、ＲＳＴＲＥＡＭ句では｛ａ，５０｝（５２７）を出力する。次に時刻ｔ２に｛ｂ，１０｝（５０６）がランキングに追加されると、ＲＳＴＲＥＡＭ句はランキング全体、すなわち｛ａ，５０｝と｛ｂ，１０｝の２つのストリームデータを出力する（５２８）。次に時刻ｔ３で｛ｃ，３０｝（５０７）がランキングに追加されると、｛ａ，５０｝、｛ｂ，１０｝に加えて｛ｃ，３０｝が出力される（５２９）。次に、時刻ｔ４で｛ｄ，２０｝（５０８）がランキングに挿入されると共に、｛ｂ，１０｝（５０６）がランキングから削除される。この場合、ＲＳＴＲＥＡＭ句では、時刻ｔ４に｛ａ，５０｝、｛ｃ，３０｝、｛ｄ，２０｝を出力する（５３０）。本処理を実現するためには、処理結果出力時にランキング処理結果出力インタフェース（２０７）で前回の出力時の出力内容を保持し、該出力内容と、順序・順位生成部（２０４）で新たに生成されたランキング情報とを組合せて、出力情報を生成すればよい。今回の説明では、ＲＳＴＲＥＡＭ句の出力タイミングは、入力となるストリームデータが到来した瞬間としたが、出力生成の負荷、通信コスト削減のために、例えば１秒毎などの一定間隔、入力タプルｎ個毎、出力タプルｍ個毎などでも差し支えない。
【００４８】
次に、クエリで順位出力指定がある場合（図９のステップ９０５でＹｅｓが選択される場合）の例について、図６のクエリ６０１および６０２を用いて説明する。クエリ６０１では、クエリ３０１で出力したｓ．ｉｄとｓ．ｖａｌに加えて、１行目のＲＡＮＫＩＮＧ ＡＳ ｒａｎｋ指定により、その時点での順位情報も加えて出力することが指定されている。また、クエリ６０１が前回出力した後の差分情報のみを出力するのに対して、クエリ６０２では、出力タイミング毎にランキング情報を全て出力する。
【００４９】
最初に、順位出力指定を含む場合のランキング計算方法について、図７を用いて説明する。図７の左側の角丸四角（１５０２）は、ウィンドウ演算“［Ｐａｒｔｉｔｉｏｎ Ｂｙ ｓ．ｉｄ Ｒｏｗｓ １］”の処理結果を格納したストリームタプル保持バッファの各時刻での状態を示しており、図４と同じである。各時刻の状態に対して、順位出力指定を含むランキング計算の方法を説明する。図７の凡例７０２に示すように、楕円で囲まれた２つの値の組は｛ｉｄ，ｖａｌ｝の形式のストリームデータを表す。また、凡例７０３に示すように、角丸四角形で囲まれた３つの値の組は、｛ｒａｎｋ，ｉｄ，ｖａｌ｝の形式のストリームデータを表す。ここで、ｒａｎｋは出力時のｖａｌの値に基づいた順位である。
【００５０】
時刻ｔ１にストリームデータで｛ａ，５０｝（７０５）が到来すると、本ストリームタプルはランキングに含まれ、かつその順位は１位であるので、ランキング計算結果は｛１，ａ，５０｝（７１２）となる。次に時刻ｔ２にストリームデータ｛ｂ、１０｝（７０６）が到来すると、本ストリームデータもランキングに含まれるので、｛２，ｂ，１０｝（７１３）が出力される。時刻ｔ３に｛ｃ，３０｝（７０７）が到来すると、本ストリームデータもランキングに含まれ、かつそのｖａｌの値３０が｛ｂ，１０｝よりも大きいため順位は２位となり、同時に｛ｂ，１０｝の順位は３位となる。そのため、ランキング計算結果からは、｛２，ｂ，１０｝が削除され、｛３，ｂ，１０｝（７１４）および｛２，ｃ，３０｝（７１５）が追加される。続いて、時刻ｔ４にストリームデータ｛ｄ，２０｝（７０８）が到来すると、そのｖａｌの値２０が｛ｂ，１０｝のｖａｌの値１０よりも大きいので、｛３，ｂ，１０｝がランキング計算結果から削除され、｛３，ｄ，２０｝（７１６）が計算結果に追加される。次に、時刻ｔ５でストリームデータ｛ｅ，４０｝（７０９）が到来すると、そのｖａｌの値４０は現在ランキング計算結果に含まれている｛ｃ，３０｝および｛ｄ，２０｝よりも大きく、順位は２位となるため｛２，ｅ，４０｝（７１８）がランキング計算結果に含まれる。同時に、｛３，ｄ，２０｝がランキング計算結果から削除され、かつ｛ｃ，３０｝の順位が２位から３位に変化するため、｛２，ｃ，３０｝が削除され、｛３，ｃ，３０｝（７１７）が追加される。時刻ｔ６、ｔ７にそれぞれ｛ｅ，１５｝（７１０）および｛ａ，４５｝（７１１）が到来する場合も同様である。これらのランキング計算処理は、図２の順序・順位生成部（２０４）で実行され、各時刻でのランキング計算処理結果はランキング情報保持バッファ（２０２）に格納される。計算の好適な実施方法は、図９のフローチャートでは、ランキング情報保持バッファメンテナンス（９０３）までは共通である。次に、順序出力指定があるかないかをチェックし（９０５）、順序出力指定がある場合（９０５でＹｅｓが選択された場合）には処理結果タプルの順位情報カラム追加処理を実施する（９０６）。順位情報追加処理は、ランキング情報処理バッファ（２０２）を利用する。前述したように、好適な実施例では、ランキング情報保持バッファでは、追加されたストリームタプルを、順序付けが指定されたカラムの値の順序関係を保持しながら管理する。例えば、クエリ６０１の場合には、クエリ３０１の場合と同様に、順序付けの対象となるカラムはｓ．ｖａｌであるので、ランキング情報保持バッファ内でのデータ構造としては、図２の２０３に示すようなテーブル形式や、図１３のｓ．ｖａｌの値をキーにした二分探索木が実施の方法として挙げられる。順位情報の追加処理では、順位情報追加対象のストリームカラムがｓ．ｖａｌをキーにした場合何番目にあるかを計算し、該順位をクエリで指定されたカラムの位置に追加する。例えば、クエリ６０１の場合には、ＳＥＬＥＣＴ句の最初のカラムに“ＲＡＮＫＩＮＧ ＡＳ ｒａｎｋ”指定があるため、一番目のカラムに順位情報を含めて出力する。
【００５１】
クエリ６０１では、最終的な出力形式として、ＩＤＳＴＲＥＡＭ句が指定されている。クエリ３０１を用いて説明したように、ＩＤＳＴＲＥＡＭ句は、ランキング計算の結果、ランキングに追加されたストリームデータを増加分として、ランキングから削除されたストリームデータを減少分として出力するインタフェースである。図８（ａ）では、ＩＤＳＴＲＥＡＭ句（８０４）によって処理された後のストリームデータを図の右側（８１９）に示した。時刻ｔ１に｛ａ，５０｝（８０５）が到来した場合、出力カラムの先頭に前記順序・順位生成部で計算した順位情報をクエリで指定された１番目のカラムに追加して出力する。｛ａ，５０｝が到来したときには、ストリームデータは１つしかなく、その順位は１位となるので、｛１，ａ，５０｝（８１１）を出力する。次に時刻ｔ２に｛ｂ，１０｝（８０６）が到来すると、その順位は２位となるので、｛２，ｂ，１０｝（８１２）を出力する。時刻ｔ３に｛ｃ，３０｝（８０７）が到来すると、そのｖａｌの値３０は｛ａ，５０｝のｖａｌの値５０よりは小さく、｛ｂ，１０｝のｖａｌの値１０よりは大きいため、その順位は２位となる。そのため、時刻ｔ３では、｛３，ｂ，１０｝（８１３）および｛２，ｃ，３０｝（８１４）が増加分として出力されると共に、｛２，ｂ，１０｝（８１５）が減少分として出力される。図５で示したクエリ３０１の例では、｛ｃ，３０｝によりランキング出力に含まれる集合自体は変化しなかったため、増加分として｛ｃ，３０｝のみを出力した（５１５）が、図８のクエリ６０１の例では｛ｃ，３０｝の到来によって順位が変化するため、増加分、減少分を合わせて３つのストリームデータが出力される。同様にして、時刻ｔ５およびｔ６では順位の変化に対応して、それぞれ４個（８２０）、（８２１）となり、クエリ３０１の場合よりも出力するストリームタプル数が増加している。クエリ６０１では、最終的な出力形式として、前記ＩＤＳＴＲＥＡＭ句が指定されているため、増減分のストリームデータを出力しているが、順位出力指定がない場合と同様に、順位出力指定がある場合も各瞬間のランキングの全体を出力する要求もある。クエリ６０２がその例である。クエリ６０１のＩＤＳＴＲＥＡＭのかわりにＲＳＴＲＥＡＭを指定する（８２９）ことによって、出力時点でのランキング計算結果全体を出力する。図８（ｂ）はクエリ６０２の実行結果を示している。時刻ｔ１〜ｔ７のそれぞれの出力を８２２〜８２８に示した。
【００５２】
以上の実施例では、ランキングの指定は降順でその開始順位は１位のみを示したが、ランキングの指定は昇順でも差し支えない。また、ランキング開始順位は任意の整数値での指定が可能である。例えば、図１１のクエリ１１０１はストリームｓから、ｓ．ｉｄとｓ．ｖａｌの値の組を、ｓ．ｉｄの値でグルーピングしてそれぞれのｓ．ｖａｌの値の最新の１件を保持し、開始順位１０位からｓ．ｖａｌの値の昇順に３件を出力することを示している。図３のクエリ３０１との違いは、３行目のＯＦＦＳＥＴ句とＡＳＣ指定であり、前者が開始順位の指定、後者が昇順の指定である。ＯＦＦＳＥＴ指定がある場合には、図９のランキング処理の受け取ったタプルがランキングに影響するか否かのチェック（９０４）は、受け取ったストリームタプルが、ＯＦＦＳＥＴ句で指定された開始順位から、ＬＩＭＩＴ句で指定された出力指定範囲に影響するか否かをチェックすればよい。ランキング情報の保持、管理に関しては、図２に示したランキング処理モジュール（１１６）でＯＦＦＳＥＴ指定なしの場合と同様に処理できる。
さらに、上述の実施例ではランキング付け対象のカラムが明示的にシステム投入されるが、ランキング付け対象のカラムを自動的に決定するシステムにも本発明は適用可能である。
【図面の簡単な説明】
【００５３】
【図１】本発明におけるストリームデータ処理システムの構成を示す図。
【図２】本発明におけるランキング処理モジュールの構成を示す図。
【図３】本発明におけるランキング指定を含むクエリ（順位出力指定含まず）の例。
【図４】本発明におけるランキング計算の計算内容（順位出力指定含まず）を示す図。
【図５】本発明におけるランキング計算結果の出力結果（順位出力指定含まず）を示す図。
【図６】本発明におけるランキング指定を含むクエリ（順位出力指定含む）の例。
【図７】本発明におけるランキング計算の計算内容（順位出力指定含む）を示す図。
【図８】本発明におけるランキング計算結果の出力結果（順位出力指定含む）を示す図。
【図９】本発明におけるランキング処理手順を示すフローチャート。
【図１０】本発明におけるランキング情報保持バッファメンテナンス処理手順を示すフローチャート。
【図１１】本発明におけるランキング指定を含むクエリ（オフセット指定含む）の例。
【図１２】クエリ処理言語ＣＱＬによるクエリ記述例。
【図１３】本発明におけるランキング情報の二分探索木による表現の例。
【図１４】本発明におけるランキング情報保持バッファ内のランキング情報保持テーブルの変化の様子を示す図。
【図１５】本発明におけるウィンドウマネージャの構成を示す図。
【図１６】本発明におけるクエリ処理エンジンの計算機上での実現例を示す図。
【図１７】本発明におけるランキング計算方法を示すシーケンス図。
【図１８】本発明におけるランキング情報保持バッファへのストリームタプル追加処理方法を示すフローチャート。
【図１９】本発明におけるランキング情報保持バッファからのストリームタプル削除処理方法を示すフローチャート。
【符号の説明】
【００５４】
１１５…ストリームデータ処理システム
１０７、１２１…ネットワーク
１１３…クエリ処理エンジン
１１６、…ランキング処理モジュール
２０２…ランキング情報保持バッファ
２０３…ランキング情報保持テーブル
２０４…順序・順位生成部
２０６…ストリームタプル受付インタフェース
２０７…ランキング処理結果出力インタフェース
２０８…順位管理インデックス
１１６…ランキング処理モジュール
１１７…メモリマネージャ
１２６…ウィンドウマネージャ
１５０２…ストリームタプル保持バッファ
１５０４…生存期間決定部
１５０５…ストリームデータ受付インタフェース
１５０６…差分情報生成部
３０１、３０２、６０１、６０２、１１０１、１２０１…クエリ
１６０１…ストリームデータ処理サーバ
１６０２…通信インタフェース
１６０３…ＣＰＵ
１６０４…メモリ
１６０５…Ｉ／Ｏインタフェース
１６０６…ストレージ装置
【特許請求の範囲】
【請求項１】
継続的に到来する、タイムスタンプが付与された複数のストリームタプルで構成されるストリームデータを受け付け、予め登録されたクエリにより前記ストリームデータにクエリ処理を継続実行するストリームデータのランキングクエリ処理方法であって、
前記クエリにより指定するウィンドウ指定に従い、各ストリームタプルの到着に対応して、該ストリームタプルのウィンドウ中の生存期間、もしくはそれに加えて過去に到着したストリームタプルのウィンドウ中の生存期間の終了を決定し、
前記クエリにより指定するランキング処理に従い、あるストリームタプルの生存期間が開始するタイミング、及びあるストリームタプルの生存期間が終了するタイミング毎に、ストリームタプル間の順序付け対象項目に関するランキングを算出してそのランキング情報を更新し、
前記順序付け対象項目のランキングが前記クエリで指定する出力指定範囲に含まれるストリームタプルの集合を出力するとともに、該出力指定範囲を越えて生存期間内にあるストリームタプルの更新されたランキング情報を保存することを特徴とするストリームデータのランキングクエリ処理方法。
【請求項２】
前記ランキング情報の保存は、生存期間内にある全てのストリームタプルに亘って行うことを特徴とする請求項１のストリームデータのランキングクエリ処理方法。
【請求項３】
前記ランキング情報は、バッフア内に各ストリームタプルと順位を対応させた表として保存することを特徴とする請求項１のストリームデータのランキングクエリ処理方法。
【請求項４】
請求項１のストリームデータのランキングクエリ処理方法であって、前記クエリで順位出力の指定があった場合に、前記順序出力指定範囲に含まれるストリームタプルの各々に対して、該ストリームタプルの順位を付加し、ランキング情報として出力することを特徴とするストリームデータのランキングクエリ処理方法。
【請求項５】
請求項１のストリームデータのランキングクエリ処理方法であって、前記ランキング情報の出力の際に、前回の出力との差分情報を生成することを特徴とするストリームデータのランキングクエリ処理方法。
【請求項６】
請求項１のストリームデータのランキングクエリ処理方法であって、前記ランキング情報の出力の際に、ランキング全体情報を出力することを特徴とする、ストリームデータのランキングクエリ処理方法。
【請求項７】
ストリームタプルが到来した時、該ストリームタプルに生存期間の開始を示す符号を付加し、ストリームタプルの生存期間の終了が決定した時に該ストリームタプルにその生存期間の終了を示す別の符号を付加する段階を更に有し、符号が付加されたストリームタプルを用いて前記ランキング情報の更新が成されることを特徴とする請求項１のスとリームデータのランキングクエリ処理方法。
【請求項８】
継続的に到来する、タイムスタンプが付与された複数のストリームタプルで構成されるストリームデータを受け付け、予め登録されたクエリにより前記ストリームデータにクエリ処理を継続実行するストリームデータ処理システムであり、
到来するストリームタプルに対してクエリで指定されたウィンドウ演算を実行し、各ストリームタプルのウィンドウ中の生存期間を決定するウィンドウマネージャと、
該クエリで指定されたランキング処理を行い、該クエリで指定された出力指定範囲に含まれるストリームタプルの集合を出力するランキング処理モジュールとを有し、
前記ウィンドウマネージャは、各時点での前記ウィンドウへのストリームタプルの挿入、及び前記ウィンドウからのストリームタプルの削除を示すウィンドウ差分情報を生成して前記ランキング処理モジュールに伝達する差分情報生成部を備え、
前記ランキング処理モジュールには、前記ウィンドウマネージャの差分情報生成部から伝達されるウィンドウ差分情報と、保存した情報とから前記ウィンドウ中での生存期間にあるストリームタプルの範囲内でそれらのランキング情報を生成・更新する順序・順位生成部と、
前記ウィンドウ中の生存期間にあるストリームタプルの範囲内で該順序・順位制製部で更新したランキング情報を保存するランキング情報保持バッファを含むことを特徴とするストリームデータ処理システム。
【請求項９】
前記ランキング情報保持バッファは、各ストリームタプルとその順位を対応させた表として前記ランキング情報を保持することを特徴とするストリームデータ処理システム。
【請求項１０】
前記差分情報生成部は、ストリームタプルが到来した時、該ストリームタプルに前記ウィンドウへの挿入を示す符号を付加し、決定したストリームタプルの生存期間の終了の時点で前記ウィンドウからの該ストリームタプルの削除を示す別の符号を付加し、それぞれ前記ウィンドウ差分情報として前記ランキング処理モジュールに伝達することを特徴とする請求項９のストリームデータ処理システム。
【請求項１】
継続的に到来する、タイムスタンプが付与された複数のストリームタプルで構成されるストリームデータを受け付け、予め登録されたクエリにより前記ストリームデータにクエリ処理を継続実行するストリームデータのランキングクエリ処理方法であって、
前記クエリにより指定するウィンドウ指定に従い、各ストリームタプルの到着に対応して、該ストリームタプルのウィンドウ中の生存期間、もしくはそれに加えて過去に到着したストリームタプルのウィンドウ中の生存期間の終了を決定し、
前記クエリにより指定するランキング処理に従い、あるストリームタプルの生存期間が開始するタイミング、及びあるストリームタプルの生存期間が終了するタイミング毎に、ストリームタプル間の順序付け対象項目に関するランキングを算出してそのランキング情報を更新し、
前記順序付け対象項目のランキングが前記クエリで指定する出力指定範囲に含まれるストリームタプルの集合を出力するとともに、該出力指定範囲を越えて生存期間内にあるストリームタプルの更新されたランキング情報を保存することを特徴とするストリームデータのランキングクエリ処理方法。
【請求項２】
前記ランキング情報の保存は、生存期間内にある全てのストリームタプルに亘って行うことを特徴とする請求項１のストリームデータのランキングクエリ処理方法。
【請求項３】
前記ランキング情報は、バッフア内に各ストリームタプルと順位を対応させた表として保存することを特徴とする請求項１のストリームデータのランキングクエリ処理方法。
【請求項４】
請求項１のストリームデータのランキングクエリ処理方法であって、前記クエリで順位出力の指定があった場合に、前記順序出力指定範囲に含まれるストリームタプルの各々に対して、該ストリームタプルの順位を付加し、ランキング情報として出力することを特徴とするストリームデータのランキングクエリ処理方法。
【請求項５】
請求項１のストリームデータのランキングクエリ処理方法であって、前記ランキング情報の出力の際に、前回の出力との差分情報を生成することを特徴とするストリームデータのランキングクエリ処理方法。
【請求項６】
請求項１のストリームデータのランキングクエリ処理方法であって、前記ランキング情報の出力の際に、ランキング全体情報を出力することを特徴とする、ストリームデータのランキングクエリ処理方法。
【請求項７】
ストリームタプルが到来した時、該ストリームタプルに生存期間の開始を示す符号を付加し、ストリームタプルの生存期間の終了が決定した時に該ストリームタプルにその生存期間の終了を示す別の符号を付加する段階を更に有し、符号が付加されたストリームタプルを用いて前記ランキング情報の更新が成されることを特徴とする請求項１のスとリームデータのランキングクエリ処理方法。
【請求項８】
継続的に到来する、タイムスタンプが付与された複数のストリームタプルで構成されるストリームデータを受け付け、予め登録されたクエリにより前記ストリームデータにクエリ処理を継続実行するストリームデータ処理システムであり、
到来するストリームタプルに対してクエリで指定されたウィンドウ演算を実行し、各ストリームタプルのウィンドウ中の生存期間を決定するウィンドウマネージャと、
該クエリで指定されたランキング処理を行い、該クエリで指定された出力指定範囲に含まれるストリームタプルの集合を出力するランキング処理モジュールとを有し、
前記ウィンドウマネージャは、各時点での前記ウィンドウへのストリームタプルの挿入、及び前記ウィンドウからのストリームタプルの削除を示すウィンドウ差分情報を生成して前記ランキング処理モジュールに伝達する差分情報生成部を備え、
前記ランキング処理モジュールには、前記ウィンドウマネージャの差分情報生成部から伝達されるウィンドウ差分情報と、保存した情報とから前記ウィンドウ中での生存期間にあるストリームタプルの範囲内でそれらのランキング情報を生成・更新する順序・順位生成部と、
前記ウィンドウ中の生存期間にあるストリームタプルの範囲内で該順序・順位制製部で更新したランキング情報を保存するランキング情報保持バッファを含むことを特徴とするストリームデータ処理システム。
【請求項９】
前記ランキング情報保持バッファは、各ストリームタプルとその順位を対応させた表として前記ランキング情報を保持することを特徴とするストリームデータ処理システム。
【請求項１０】
前記差分情報生成部は、ストリームタプルが到来した時、該ストリームタプルに前記ウィンドウへの挿入を示す符号を付加し、決定したストリームタプルの生存期間の終了の時点で前記ウィンドウからの該ストリームタプルの削除を示す別の符号を付加し、それぞれ前記ウィンドウ差分情報として前記ランキング処理モジュールに伝達することを特徴とする請求項９のストリームデータ処理システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【公開番号】特開２００９−１３４６８９（Ｐ２００９−１３４６８９Ａ）
【公開日】平成２１年６月１８日（２００９．６．１８）
【国際特許分類】
【出願番号】特願２００８−１７４０８６（Ｐ２００８−１７４０８６）
【出願日】平成２０年７月３日（２００８．７．３）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成２１年６月１８日（２００９．６．１８）
【国際特許分類】
【出願日】平成２０年７月３日（２００８．７．３）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．イーサネット
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]