(57)【要約】【課題】ユーザが簡便に任意階層を定義しかつそれに対してクエリを行うことを可能にするデータモデルおよびSQL構造体を提供する。【解決手段】本明細書内で取り組まれるのは、データベーステーブルとして表される階層に対する演算を表現および評価する問題である。そのような演算のためのエンジンサポートは、今日、非常に限られているため、それらは通常、ストアドプロシージャまたはクライアントコードにアウトソースされる。有用な演算のクラスを表現する簡潔なシンタックスを提供するために、構造グループ化が関係代数に適用される。利用可能なインデックス作成スキームを利用することによってそのような構造グループ化を効率的に評価するために、アルゴリズムも提供される。関連装置、システム、技術、および物品についても説明される。【選択図】図７
2018014096.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも1つのコンピューティングデバイスの一部を形成する1つまたは複数のデータプロセッサによる実装のための方法であって、
データベースによって、各行がノードの階層の異なるノードに関連しているテーブルの形態でデータを要求するクエリを受信するステップであって、前記クエリが、階層ウィンドウ句および前記階層ウィンドウ句によって指定される階層ウィンドウに対するウィンドウ関数を含む少なくとも1つの表現を指定する、ステップと、
前記階層ウィンドウ句に基づいて、ウィンドウ表示テーブル内の行の少なくとも一部分の有向非巡回グラフを構築するステップと、
前記クエリによって指定される表現に基づいて、前記有向非巡回グラフのエッジにわたって前記行からデータを蓄積することによって前記クエリに応答した結果を得るステップと、
得られた前記結果の少なくとも一部分を含むデータを提供するステップと
を含む方法。
【請求項２】
前記有向非巡回グラフが明示的に構築される、請求項1に記載の方法。
【請求項３】
前記有向非巡回グラフが明示的に構築されない、請求項1に記載の方法。
【請求項４】
前記階層ウィンドウ句が、内容がノードの階層内の前記行の位置を表す行フィールドを指定し、
前記有向非巡回グラフの構造が、前記ノードの階層の構造に由来する、請求項1に記載の方法。
【請求項５】
前記階層ウィンドウ句が、構築された前記有向非巡回グラフにわたる所望のデータフローの方向をさらに指定する、請求項4に記載の方法。
【請求項６】
前記所望のデータフローの方向が、前記ノードの階層のエッジの方向に従う、請求項5に記載の方法。
【請求項７】
前記所望のデータフローの方向が、前記ノードの階層の反対のエッジの方向に従う、請求項5に記載の方法。
【請求項８】
前記有向非巡回グラフにわたるデータフローが、前記ノードの階層の少なくとも1つの中間ノードをバイパスする、請求項3に記載の方法。
【請求項９】
データを提供するステップが、
前記得られた結果の少なくとも一部分を保持するステップ、
前記得られた結果の少なくとも一部分をメモリに読み込むステップ、
前記得られた結果の少なくとも一部分をリモートコンピューティングシステムに送信するステップ、または
前記得られた結果の少なくとも一部分を電子視覚表示装置に表示するステップ
のうちの少なくとも1つを含む、請求項1に記載の方法。
【請求項１０】
前記クエリが、ウィンドウパーティション句をさらに指定し、
前記ノードの階層に記憶される前記データが、前記ウィンドウパーティション句に従って区切られ、
前記ノードの階層の構築された前記有向非巡回グラフが、区切られた前記データに基づく、請求項1に記載の方法。
【請求項１１】
前記クエリが、構造化問い合わせ言語(SQL)で定式化される、請求項1に記載の方法。
【請求項１２】
前記クエリが、前記階層ウィンドウに対する少なくとも1つのウィンドウ関数を有する少なくとも1つの表現をラップするRECURSIVEキーワードを含む、請求項1に記載の方法。
【請求項１３】
前記データベースが、メインメモリリレーショナルデータベース管理システムである、請求項1に記載の方法。
【請求項１４】
前記データベースが、列指向インメモリデータベースである、請求項11に記載の方法。
【請求項１５】
前記データベースが、データが複数のコンピューティングシステムにわたって記憶される分散データベースである、請求項1に記載の方法。
【請求項１６】
少なくとも1つのデータプロセッサと、
命令を記憶するメモリと
を備え、
前記命令が、前記少なくとも1つのデータプロセッサによって実行されるとき、
データベースによって、各行がノードの階層の異なるノードに関連しているテーブルの形態でデータを要求するクエリを受信するステップであって、前記クエリが、階層ウィンドウ句および前記階層ウィンドウ句によって指定される階層ウィンドウに対するウィンドウ関数を含む少なくとも1つの表現を指定する、ステップと、
前記階層ウィンドウ句に基づいて、ウィンドウ表示テーブル内の行の少なくとも一部分の有向非巡回グラフを構築するステップと、
前記クエリによって指定される表現に基づいて、前記有向非巡回グラフのエッジにわたって前記行からデータを蓄積することによって前記クエリに応答した結果を得るステップと、
得られた前記結果の少なくとも一部分を含むデータを提供するステップと
を含む動作をもたらす、システム。
【請求項１７】
前記有向非巡回グラフが明示的に構築される、請求項16に記載のシステム。
【請求項１８】
前記有向非巡回グラフが明示的に構築されない、請求項16に記載のシステム。
【請求項１９】
前記階層ウィンドウ句が、内容がノードの階層内の前記行の位置を表す行フィールドを指定し、
前記有向非巡回グラフの構造が、前記ノードの階層の構造に由来する、請求項16に記載のシステム。
【請求項２０】
命令を含むコンピュータプログラムであって、
前記命令が、少なくとも1つのコンピューティングシステムの一部を形成する少なくとも1つのデータプロセッサによって実行されるとき、
データベースによって、各行がノードの階層の異なるノードに関連しているテーブルの形態でデータを要求するクエリを受信するステップであって、前記クエリが、階層ウィンドウ句および前記階層ウィンドウ句によって指定される階層ウィンドウに対するウィンドウ関数を含む少なくとも1つの表現を指定する、ステップと、
前記階層ウィンドウ句に基づいて、ウィンドウ表示テーブル内の行の少なくとも一部分の有向非巡回グラフを構築するステップと、
前記クエリによって指定される表現に基づいて、前記有向非巡回グラフのエッジにわたって前記行からデータを蓄積することによって前記クエリに応答した結果を得るステップと、
得られた前記結果の少なくとも一部分を含むデータを提供するステップと
を含む動作をもたらす、コンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、2016年7月18日に出願した表題「Index-Assisted Hierarchical Computations in Main Memory Relational Databases」の米国特許出願第62/363,730号の優先権を主張するものであり、その内容は参照により本明細書に完全に組み込まれる。
【背景技術】
【０００２】
ビジネスおよび科学用途において、階層は多くのシナリオに登場する:例えば、組織または財務データは、典型的には階層的に整理される一方、科学は、分類学において、例えば、動物種について、階層を日常的に使用する。根本となるリレーショナルデータベース管理システム(RDBMS)において、それらは、リレーショナルツリーエンコーディングを使用して階層テーブル内に表される。特に分析用途での典型的なクエリを見てみると、階層は主に2つの目的を果たすことが分かる。1つ目は、構造パターンマッチング、即ち、行を階層内のそれらの位置に基づいてフィルタリングおよびマッチングすることである。2つ目は、階層演算、つまり階層ディメンションに並行して、評価基準を伝搬し、かつ集約のような演算を実施することである。RDBMSレベルで両方の目的に取り組むためには、2つの課題、即ち(1)ユーザがどのように目の前のタスクを直観的かつ簡潔にSQLで表現することができるのか?(表現性)、および(2)エンジンがどのようにこれらのSQLクエリを効率的に処理することができるのか?(効率性)が解決される必要がある。
【０００３】
パターンマッチングクエリに関しては、両方とも結局は、「is-descendant」などの階層軸上での簡単なフィルタおよび構造結合ということになり、適切なインデックスおよび結合演算子に関する技法が十分に研究されているため、それらは共に的確に解決されると見なされ得る。階層演算については同じことが言えない。演算の目的のため、階層ノードのサブセットは、伝搬または集約、およびおそらくはフィルタリングされる値と動的に関連付けられる。分析用途において、これは常にルーチンタスクである:ディメンション階層は、典型的には、都市-州-国-大陸などの非正規化レベルのテーブルによってモデル化される。次いで、特定の演算が、SQLの基本的なグループ化機構(具体的には、ROLLUP)を使用して表現され得る。しかしながら、これは、特に階層がレベルに整理されていないが、一レベルのノードが異なる種類のものであり得る不規則構造および任意の深さを呈するとき、単純なロールアップ以上の演算には不十分である。図1の図100内の階層について検討する。葉に付属したいくつかの値の加重和を計算したいとすると、エッジ重みを組み込んだロールアップ式をどのように記述することができるだろうか?これは、SQLでは極めて難しいとすぐに分かる。思い浮かぶ1つのツールは、再帰的共通テーブル表現(RCTE)である。しかしながら、より複雑な集約のような演算は、入り組んだ本質的に非効率的なステートメントをもたらす傾向がある。RDBMSサポートがないため、今日、ユーザは、回避策としてストアドプロシージャまたはクライアントコードに頼っている。これらは、表現性に関して不十分なだけでなく、既知の階層構造を無視しており、故に効率性の観点からも不利である。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許出願第１４／６１４８５９号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本主題は、RDBMSバックエンドを向上させることによって、任意の不規則階層に対する複雑な演算に関する表現性および効率性の問題に取り組む。現在のアプローチの根幹は、ユーザが簡便に任意階層を定義しかつそれに対してクエリを行うことを可能にするデータモデルおよびSQL構造体である。この仕組みが新しい機会を開く:バックエンドは、階層構造を認識し、クエリ処理のための強力なインデックス作成スキームに依存することができる。以下に、関係代数内で構造グループ化動作に翻訳され得る、階層演算および対応するSQL構造体の概念が紹介される。構造グループ化の効率的な評価は、インデックスを使用した物理的な代数演算子を必要とし得る。
【課題を解決するための手段】
【０００６】
一態様において、クエリは、各行がノードの階層の異なるノードに関連しているテーブルの形態でデータを要求するデータベースによって受信され、クエリが、階層ウィンドウ句および階層ウィンドウ句によって指定される階層ウィンドウに対するウィンドウ関数を含む少なくとも1つの表現を指定する。その後、ウィンドウ表示テーブル内の行の少なくとも一部分の有向非巡回グラフが、階層ウィンドウ句に基づいて構築される。その後、クエリによって指定される表現に基づいて、有向非巡回グラフのエッジにわたって行からデータを蓄積することによってクエリに応答した結果が得られる。次いで、得られた結果の少なくとも一部分を含むデータが提供され得る。
【０００７】
有向非巡回グラフは、明示的に構築されるか、明示的に構築されないかのいずれかであり得る。
【０００８】
階層ウィンドウ句は、内容がノードの階層内の行の位置を表す行フィールドを指定することができ、そのような仕組みでは、有向非巡回グラフの構造は、ノードの階層の構造に由来し得る。階層ウィンドウ句は、構築された有向非巡回グラフにわたる所望のデータフローの方向をさらに指定することができる。所望のデータフローの方向は、ノードの階層のエッジの方向に従い得る。所望のデータフローの方向は、ノードの階層の反対のエッジの方向に従い得る。
【０００９】
有向非巡回グラフにわたるデータフローは、ノードの階層の少なくとも1つの中間ノードをバイパスし得る。
【００１０】
データを提供するステップは、得られた結果の少なくとも一部分を保持するステップ、得られた結果の少なくとも一部分をメモリに読み込むステップ、得られた結果の少なくとも一部分をリモートコンピューティングシステムに送信するステップ、または得られた結果の少なくとも一部分を電子視覚表示装置に表示するステップのうちの1つまたは複数を含み得る。
【００１１】
クエリは、ウィンドウパーティション句をさらに指定し得、ノードの階層に記憶されるデータは、ウィンドウパーティション句に従って区切られる。そのような仕組みでは、ノードの階層の生成された有向非巡回グラフは、区切られたデータに基づき得る。
【００１２】
クエリは、構造化問い合わせ言語(Structured Query Language、SQL)を含む異なる言語/プロトコルで定式化され得る。
【００１３】
クエリは、階層ウィンドウに対する少なくとも1つのウィンドウ関数を有する少なくとも1つの表現をラップするRECURSIVEキーワードを含み得る。
【００１４】
データベースは、メインメモリリレーショナルデータベース管理システムおよび/または列指向インメモリデータベースを含むがこれらに限定されない、多くの異なる形態をとり得る。さらに、データベースは、データが複数のコンピューティングシステムにわたって記憶される分散データベースであり得る。
【００１５】
命令を記憶する非一時的コンピュータプログラム製品(即ち、物理的に具現化されたコンピュータプログラム製品)であって、命令が、1つまたは複数のコンピューティングシステムの1つまたは複数のデータプロセッサによって実行されるとき、少なくとも1つのデータプロセッサに本明細書内の動作を実行させる、非一時的コンピュータプログラム製品も説明される。同様に、1つまたは複数のデータプロセッサ、および1つまたは複数のデータプロセッサに連結されたメモリを含み得るコンピュータシステムも説明される。メモリは、少なくとも1つのプロセッサに本明細書に説明される動作のうちの1つまたは複数を実施させる命令を一時的または永続的に記憶し得る。加えて、方法は、単一のコンピューティングシステム内の1つもしくは複数のデータプロセッサか、または2つ以上のコンピューティングシステム間に分散される1つもしくは複数のデータプロセッサのいずれかによって実装され得る。そのようなコンピューティングシステムは、ネットワーク(例えば、インターネット、無線広域ネットワーク、ローカルエリアネットワーク、広域ネットワーク、有線ネットワークなど)を通じた接続、複数のコンピューティングシステムのうちの1つまたは複数間の直接接続などを含むがこれらに限定されない1つまたは複数の接続を介して接続され得、データおよび/またはコマンドもしくは他の命令などを交換することができる。
【００１６】
本明細書に提供される主題は、多くの技術的利点を提供する。例えば、本主題は、従来の技術よりも速い、またより少ない計算資源を使用する、階層データにクエリを行うための技術を提供する。
【００１７】
本明細書に説明される主題の1つまたは複数の変形形態の詳細は、添付の図面および以下の説明において明らかにされる。本明細書に説明される主題の他の特徴および利点は、説明および図面、ならびに請求項から明白である。
【図面の簡単な説明】
【００１８】
【図１】サンプルテーブルHTを例証する図である。
【図２】(a)二項グループ化のための入力/出力ノードおよび(b)単項グループ化のためのテーブルHT1およびInp1の組み合わせを例証する図である。
【図３】ボトムアップ階層ウィンドウを例証する図である。
【図４】単項演算のためのSQL例を例証する図である。
【図５】図4の例に対応する構造集約関数の定義を例証する図である。
【図６】実験結果を例証する図である。
【図７】階層データに対するデータベースクエリの実行を例証するプロセスフロー図である。
【発明を実施するための形態】
【００１９】
本主題は、例えば、メインメモリRDMBSおよび/またはSAP HANAプラットフォームなどの列指向インメモリデータベースを含むがこれらに限定されないリレーショナルデータベース管理システム(RDBMS)などのデータベースに記憶される階層データのクエリを対象にする。はじめに、階層データはリレーショナルテーブルにて表され得る。より具体的には、1つのテーブルタプル(行)が1つの階層ノードを表すように、好適なスキームを使用して、順序付き木、根付き木、ラベル付き木の森をエンコードするテーブルを仮定することができる。ノードのラベルは、関連した行のフィールドである。木には、ノードとその入ってくるエッジとの間の1:1関連がなされ得るため、各フィールド値は、ノードまたはエッジのいずれかに対するラベルと解釈され得る。図1の例テーブルHTにおいては、重みはエッジラベルとして見られる。順序付けプロパティは、兄弟が定義された順序を有することを意味する。それは、すべてのノードが、全ノードの前順または後順シーケンスにおいてはっきり定義されたランクを有することを暗示し、例えば、図のB1は、前ランク2および後ランク3を有する。使用する実際のツリーエンコーディングに関して多くの選択肢が存在することが理解され得る一方、階層演算の本議論は、エンコーディング非依存である。階層テーブルモデルは、抽象データ型NODEによってエンコーディング詳細を簡便に隠蔽する(階層テーブルモデルは、にさらに詳細に説明される。本主題は、2015年2月5日出願の表題「Hierarchy Modeling and Query」の米国特許出願第14/614,859号に説明および例証されるシステム、方法、およびコンピュータプログラム製品に関し、その内容は参照により本明細書に完全に組み込まれる)。
【００２０】
HTのノードの属性は、行の位置を識別し、森構造をカプセル化する階層インデックスHによって裏付けられる。インデックスは、
【数１】
2018014096.tif 000003
において、最小の2つの基本プリミティブ、is-before-preおよびis-before-postでサポートすると仮定することができる。一対のノード値(v1,v2)を考えると、それらは、階層の前順および後順走査に関してv1がv2の前方にあるかどうかテストする。これは、主階層軸に対してノードの対をテストすることを可能にする:
前方(preceding):  is-before-pre(v1,v2)∧is-before-post(v1,v2)
子孫(descendant):  is-before-pre(v2,v1)∧is-before-post(v1,v2)
後方(following):  is-before-pre(v2,v1)∧is-before-post(v2,v1)
祖先(ancestor):  is-before-pre(v1,v2)∧is-before-post(v2,v1)
自己(self):  v1=v2
【００２１】
HTでは、C3は、B1/C1/C2の後に続き、A2/C4/D3に先行する。祖先/子孫および前方/後方軸は対称である。疑似コードでは、例えば、軸に対する「H.is-descendant(v1,v2)」は、「v1はv2の子孫である」をチェックし、時に、明白な意味を有する“-or-self"の変形を使用することを意味し得る。特定のインデックス実装は、これらおよび他の軸ならびにさらなるプリミティブ(例えば、is-child、レベル)を元々サポートするが、本アルゴリズムは、is-before-pre/postにのみ依存する。実装例は、単純なPPPLラベリングスキームである。ここでは、ノードは、前/後ランク、親の前ランク、およびノードのレベルを記憶する4-タプルである。加えて、階層テーブルは、2つの単純なルックアップテーブルを使用して前/後ランクにインデックスされる。PPPLでは、インデックスプリミティブは、明らかに、結局はノードに対する非常に安価な
【数２】
2018014096.tif 000004
算術ということになるため、これは階層インデックスが到達し得る限りの速度である。しかしながら、ある程度の更新サポートが必要とされる場合、より高度なインデックス生成スキームが選択されなければならない。提示を容易にするためにNODE抽象に依存することができる一方で、本明細書内の概念およびアルゴリズムは、前記プリミティブを供給するいかなる特定の「ハードコードされた」エンコーディングにも適合され得ることに再度留意されたい。
【００２２】
階層演算は、階層エッジに沿って、データ(通常は数値)を伝搬および蓄積する。データフローは、根に向かう方向(ボトムアップ)または根から離れる方向(トップダウン、エッジの自然の方向に一致する)のいずれかで発生し得る。ベーステーブル自体と共に記憶される「静的」ラベル(例えば、HTではIDおよび重み)とは異なり、演算入力は、一般的に、いくつかの階層ノードを図2AのテーブルInp1などの入力値と関連付ける任意のサブクエリの結果である。
【００２３】
分析シナリオにおいて、HTは、製品(葉)を製品グループ(内部ノード)に配置するいわゆるディメンション階層であり得、ファクトテーブルSalesは、各販売項目を特定の製品、即ち、HTの葉と関連付け得る:
Sales: {[Sale, Item, Customer, Product, Date, Amount]}
【００２４】
ここでは、演算入力は、結合によって製品の葉のうちのいくつかに付属される、Salesからの量である。ロールアップとして知られるそのようなシナリオにおける標準的タスクは、階層ボトムアップに沿って特定の製品(「タイプA」とする)の収益を合計し、ユーザインターフェースにおいて見ることができる特定の製品グループ(上位3つのレベルとする)についてこれらの合計をレポートすることである。以下のSQLステートメントI-aは、IS_DESCENDANT_OR_SELFおよびLEVEL構造体を使用して、ロールアップを計算する(米国特許出願第14/614,859号に記載される)。
【００２５】
【数３】
2018014096.tif 000005
【００２６】
これは、2つの特定の特徴を有する階層演算のタイプを表す:第一に、ノードのサブセットのみが入力値を持っており(例にあるように、多くの場合は葉のみ)、これらの入力ノードを呼び出すことができる。第二に、入力ノードのセットが、大部分は、演算後に目的とされ得る結果を持つ出力ノードから離れている。したがって、入力および出力ノードは、別個のサブクエリによって決定され、クエリは、join-group-aggregateパターンに従う。このスキームは、二項構造グループ化と称され得る。ここでの「構造」は、階層構造がタプルのグループを形成することにおいて担う役割を示唆する。クエリプランは、典型的には、
【数４】
2018014096.tif 000006
の変形である。ここでは、
【数５】
2018014096.tif 000007
は、標準の左外部結合動作を意味する。
【数６】
2018014096.tif 000008
は、この場合はその入力タプルをt.*でグループ化し、関数fを各グループに適用し、結果として生じる集約値を持つ属性xを各グループに付属させる単項グループ化を意味する。<は、タプル間の入力/出力関係を反映する。例の入力Inp1に基づいてロールアップを計算することを希望し、図2AのOut1によって与えられる3つの出力ノードに興味があるとする。そうするために、e1=Out1、e2=Inp1を使用し、H.is-descendant-or-self(u.Node,t.Node)としての<述語および
【数７】
2018014096.tif 000009
Valueを定義することができる。これが、A1、B1、およびC1それぞれについて、合計6310、310、および100を産出する。
【００２７】
そのようなクエリプランは、fが計算するのに低コストであり、出力ノードのセットがある程度小さいときに満足に機能する。しかしながら、大きな効率性の問題が存在する:各e1タプルでは、演算fはe2からのすべてのマッチング入力値を単刀直入に合計するが、理想的には、以前に処理されたe1タプルからの結果を再使用することができる。例では、A1について合計を計算するために、B1の合計を再使用し、単にD1/D2/D3の入力値を追加することによっていくつかの算術動作を節約することができる。<に関しては、出力ノードB1が、出力ノードA1によってカバーされており、したがって再使用可能な結果を持つということが言える。そのような再使用を有効にするために、本明細書に提供される二項グループ化アルゴリズムは、<順でe1タプルを処理し、この後のe1タプルに関係し得る任意の結果を記憶する。それにより、それらは言及した非効率性を克服する。
【００２８】
表現性の観点から、広く知られているjoin-group-aggregateステートメントは、大半のSQL使用者によってはかなり直観的であるが、十分に満足のいくものではない:それらは、概念的に<対のテーブルがグループ化の前に手動でアセンブルされなければならず、トップダウンまたはボトムアップ階層演算が行われているという事実がいくらか偽装されることから、簡単さを欠く。それらは、以下のように、出力および入力ノードが大きく重複するか、あるいは同一であるときは特に、冗長になる。
【００２９】
【数８】
2018014096.tif 000010
【００３０】
本明細書内で提供されるSQLのウィンドウ表示テーブルへの提案された拡張は、以下のように、等価的に書き込むことを可能にする。
【００３１】
【数９】
2018014096.tif 000011
【００３２】
これより演算は単一のテーブル上で働くため、このスキームを単項構造グループ化と称することができる。それは本質的に、すべてのタプルについて結果を産出し、即ち、すべてのノードが入力ノードおよび出力ノードの両方として機能する。二項グループ化クエリは、通常、マージされた「e1∪e2」テーブルに対して働き、事後的に出力ノードをフィルタリングすることによって、単項グループ化に書き換えられ得る。例えば、図2bのInp2は、HTおよびInp1の組み合わせを示し、ここでNULLは、有意義な値を持たないノードに中立値として割り当てられる。二項を単項演算に書き換えることは、多くの場合、より簡潔かつ直観的なステートメントをもたらす。入力ノードと出力ノードとの間に明白な区別が存在しないときは特に、単項グループ化が最も自然なアプローチである。
【００３３】
単項構造グループ化機構は、別の魅力的な言語機会:構造再帰へのサポートを提供する。構造的に再帰した表現を使用して、さらに別の方法でStmt.II-aおよびII-b内にロールアップを記述することができる:
【００３４】
【数１０】
2018014096.tif 000012
【００３５】
xのためのこの表現は、現在のタプルによってカバーされるすべてのタプルの容易に計算された合計xを合計する。二項グループ化とは異なり、構造再帰を有する単項グループ化は、前の結果の再使用を明示的にし、故に、効率的な評価アプローチに本質的に変わる。さらには、それは、はるかに複雑な演算を極めて簡潔に記述することを可能にする。例えば、ここでは、ロールアップにおいてInp2からのエッジ重みを簡単に考慮することができる:
【００３６】
【数１１】
2018014096.tif 000013
【００３７】
実際に再帰を実施するのではなく、本演算子は、それらの二項相当物のように<ソート後の入力テーブルを活用して、ボトムアップ式で単項グループ化を評価する。
【００３８】
以下に説明されるように、様々な演算がSQLで表現され得る。二項グループ化とは異なり、単項構造グループ化はSQLに対する新規の概念である。以下に提供されるのは、単項グループ化のための拡張の様々な新しいシンタックスおよびセマンティクスに関する詳細である。
【００３９】
ウィンドウ表示テーブルは、これがなければ扱いにくい相関サブクエリを必要とする単一テーブルに対する集約および統計演算のための簡便かつ強力な手段である。それらの暗黙的な自己結合の性質が、それらを構造グループ化へ自然に適合させる。したがって、この機構を階層ウィンドウによって拡張することができる。
【００４０】
標準のウィンドウ指定は、ウィンドウパーティション句、ウィンドウ順序付け句、およびウィンドウフレーム句を含み得る。どのようにして経時的に動作する顧客ごとの販売額合計からSalesテーブルに注釈をつけ得るかを検討する:
【００４１】
【数１２】
2018014096.tif 000014
【００４２】
フレーム句「RANGE...NO OTHERS」は、暗黙のデフォルトであり、省略され得る。簡単に言うと、クエリは、概念的に以下のように評価される:(1)SalesがCustomerによって区切られ、(2)各パーティションがDateでソートされ、(3)ソートされた各パーティション内で、各タプルtが、tに関係するタプルのグループ、フレーム句によって決定されるそのウィンドウフレーム、この場合はtまでのすべてのsalesと関連付けられ、(4)ウィンドウ関数(SUM)が、そのグループおよびtに付加されるその結果について評価される。フレームは常に、本順序付けパーティションのサブシーケンスである。タプルは、ORDER BYフィールドに関して区別可能である必要はないことに留意されたい。これらのフィールド内で一致するtのフレーム内のタプルは、ピアまたはTIESと呼ばれる。
【００４３】
単項構造グループ化では、ウィンドウ表示テーブルは、ノードのいくつかの集まり(例えば、Inp1)であり、即ち、値が階層ベーステーブル(例えば、HT)から導出されるNODEフィールドが存在する。階層ウィンドウを指定する新しいHIERARCHIZE BY句で標準のウィンドウ指定を拡張することができる。この句は、パーティション句の後ろの順序付け句に取って代わり得る。即ち、パーティショニングが通常通り最初に起こり、階層化が順序付けと置き換わる。ウィンドウ順序付けは、パーティションを部分的に順序付けされたシーケンスへと変える一方、階層化はそれを階層に由来する有向非巡回グラフに変える。パーティショニングおよびフレーム句を省略する(そのため上のデフォルトが適用する)最小の階層ウィンドウ指定について議論を始めることができる:
【００４４】
【数１３】
2018014096.tif 000015
【００４５】
句は、NODEフィールドv、その根本となる階層インデックスH、および意図されるデータフローの方向(デフォルトではボトムアップ)を決定して、パーティションに対する適切な<述語を定義するのに必要とされるすべての情報を与える:
【００４６】
【数１４】
2018014096.tif 000016
【００４７】
上に略式で使用されるカバーされた要素の概念も必要とされる。要素uは、別の要素tとの間に3つ目の要素がない場合に、要素tによってカバーされると言われる:
【００４８】
【数１５】
2018014096.tif 000017
【００４９】
<:を使用して、現在のパーティション内のタプルtのすぐ傍の<の近隣(子孫/先祖)を識別することができる。すべての階層ノードが現在のパーティションに含まれる場合、「タプルuがtによってカバーされる」関係は、「ノードu.vがt.vの子/親である」と同等であることに留意されたい。しかしながら、現在のパーティションはノードのサブセットのみをうまく含み得るため、一般的な<:の観念が必要とされる。<:述語は、中間ノードが入力において欠けているときにさえも、タプル間でデータフローを確立するのに役立つ。
【００５０】
現在のパーティションからのタプルuは、4つの関連方法で現在のタプルtに関連し得る:
【００５１】
【数１６】
2018014096.tif 000018
【００５２】
標準のウィンドウフレーム句のシンタックスをいかなる修正もなしに再使用するために、3つの概念をそれに応じて再解釈する必要があり得る:PRECEDINGタプルはカテゴリ(a)のものであり、FOLLOWINGタプルはカテゴリ(b)のものであり、TIESはカテゴリ(c)のタプルである。ボトムアップの場合、PRECEDINGタプルは子孫に、およびFOLLOWINGタプルはt.vの祖先に対応する。これらの用語は、前方および後方階層軸と混同されないものとする。それらの軸上のタプル、ならびにvがNULLであるタプルは、カテゴリ(d)に入り、常にフレームからは除外される。デフォルトフレーム句は、カテゴリ(a)、(c)、および現在の行自身を含む。(c)タプルの処理は、EXCLUDE句によって独立して制御され得る。
【００５３】
ボトムアップ階層ウィンドウをテーブルInp3に適用し、上のStmt.II-b内のように(ここに再現される:
【００５４】
【数１７】
2018014096.tif 000019
【００５５】
) x=SUM(Value)を計算することができる図3について検討する。行列はタプルの関係を示す。現在のウィンドウはデフォルトフレーム句を使用するため、フレームは、まさに<、<:、および
【数１８】
2018014096.tif 000020
タプルを含む。それらを合計すると、右に示されるx値を産出する。Inp3は中間ノードB1/C3/C4を含まないが、右のデータフローグラフによって例証されるように、C1/C2の入力値は依然としてA1へと合計され、D1/D3およびB2タプルについても同様であることに留意されたい。述べたように、単項グループ化は、入力内に存在するすべての中間ノードを必要としない。そこでは、それは、IS_DESCENDANT_OR_SELF結合(Stmt.II-a)に基づいた代替の二項アプローチのように厳密に機能する。階層演算の間違いなく最も一般的な種類である基本のロールアップでは、暗黙のウィンドウフレーム句は、<およびPRECEDING/FOLLOWING概念の定義のおかげで、まさに「正しいこと」を行い、それらをSQLで表現するさらに簡潔かつ可読性の高い方法は想像しにくい。
【００５６】
再帰的表現。これまでのところ、階層ウィンドウは単に省略表現にすぎず、それらは、join-group-aggregateステートメントによって等価に表現され得る。しかしながら、構造再帰は、それらの表現力を著しく拡張する。再帰的表現を可能にするために、SQLキーワードRECURSIVEを再利用し、それを1つまたは複数のウィンドウ関数を含む表現にラップすることを可能にすることができる:
【００５７】
【数１９】
2018014096.tif 000021
【００５８】
これが、タイプ
【数２０】
2018014096.tif 000022
のフィールドcをいかなる含まれたウィンドウ関数内でもアクセス可能にし、故に、ウィンドウフレーム内のいかなるタプルの計算されたexpr値をも参照する方法を提供する。cがexpr内のどこかで使用される場合、
【数２１】
2018014096.tif 000023
は、明示的に指定されなければならず、
【数２２】
2018014096.tif 000024
への暗黙的CASTがexprに適用される。特定のケースにおける自動タイプ推定は将来的に可能な拡張であるが、それは一般的には不確定性なしでは不可能である。以下の追加ルールが適用される:第一に、exprが「expri OVER wi」の1つまたは複数のウィンドウ関数表現を含む場合、使用されるすべての階層ウィンドウwiは、等しくなければならない(同じパーティショニングおよびHIERARCHIZE句、即ち、NODEフィールドおよび方向)。第二に、各ウィンドウwiのフレームは、以下のように制限される:カバーされたタプルのみ(「RANGE 1 PRECEDING」)が、フレーム内に含まれる可能性があり得、特に、EXCLUDE GROUPが施行される。即ち、expr内のすべてのウィンドウ関数のフレーム句は、効果的に以下になる:
【００５９】
【数２３】
2018014096.tif 000025
【００６０】
これは特に、ウィンドウフレームが、CURRENT ROW、いかなるTIES、またはいかなるFOLLOWINGタプルも含まないことを確実にする。それらのうちのいずれかがフレーム内に含まれていた場合、expr内のフィールドcへのいかなるアクセスも循環参照を生み出すことになる。第三に、フィールドcは、ウィンドウ関数表現expriのうちの1つの中にのみ、例えば、集約関数AGGと組み合わせて、登場し得る:
【００６１】
【数２４】
2018014096.tif 000026
【００６２】
ウィンドウ関数外のcについて言及することは、現在のタプルに暗黙的にアクセスし、それは禁止されているが、SQLのルールに従ってexpr'内のcについて言及することは、フレーム行(FRAME_ROW)に暗黙的にアクセスし、それは制限的なウィンドウフレームのおかげで、c値が利用可能であるカバーされたタプルのみであり得る。この標準動作は、通常意図されるものであり、かつ極めて簡便でありながら、SQLは、暗黙的なフレーム行アクセスをオーバーライドする方法を有する。例えば、いわゆる入れ子ウィンドウ関数を使用することによってAGG内の現在のタプルさえも参照することができる:
【００６３】
【数２５】
2018014096.tif 000027
【００６４】
これはcには禁止されているが、それはいかなる他のフィールドにも許可される。
【００６５】
図3の図300に戻ると、これより、Stmt.II-c, x=RECURSIVE INT(Value+SUM(x) OVER w) AS xの再帰的ロールアップ表現をInp3に等価に適用することができる。これより、ウィンドウフレームはカバーされた<:タプルに制限される。Inp3は、ボトムアップ評価、即ち、後順のためにすでに好適に順序付けされているため、単一パスでx結果列を埋め、常にフレーム行のx値を手元に有することができる。
【００６６】
非再帰的表現を用いる場合さえも、階層ウィンドウはすでに、冗長なjoin-group-aggregateステートメントの魅力的な代替案である。上の(および下に再現される)オープニングクエリI-aについて検討する。
【００６７】
【数２６】
2018014096.tif 000028
【００６８】
SQLは、集約がFILTERによって制限されることを可能にする。この便利な特徴は、このクエリを以下のように記述することを可能にする:
【００６９】
【数２７】
2018014096.tif 000029
【００７０】
これが、Stmt.I-aにわたる1つの結合を節約する。外部結合はAmountがNULLであるタプルを産出し得るが、これらは、SUMによって簡便に無視されることに留意されたい。WHERE条件を追加することができるポイントは、全部で3つ存在する:事前(ウィンドウが形成される前)、FILTERとして(演算入力を制限するが、テーブルに影響を与えない)、および事後(出力を制限する)。最後の1つについては、現在のところSQLがウィンドウ表示テーブルに相当するHAVINGを有しないため、2つの選択肢を入れ子にしなければならない。
【００７１】
図4は、可能であればそれぞれがInp2におけるボトムアップまたはトップダウン階層ウィンドウのいずれかに基づいた、非再帰的な変異形を含む、さらなる有意義な表現を示す:
【００７２】
【数２８】
2018014096.tif 000030
【００７３】
図4の(1)は、よく知られたロールアップである。SUM以外にも、図1の(1a)内の動作は、例えば、AVG、MIN、MAX、COUNT(例7を参照)、EVERY、ANY、または単純にアレイ内のすべての値を集めるためのARRAY_AGGであり得る。SQLのDISTINCTおよびFILTER構造体は、さらなる表現性を追加する。例えば、部品表においては、各部品を構成する、特定の製造業者の異なる種類の子部品を計数し得る:
【００７４】
【数２９】
2018014096.tif 000031
【００７５】
図4の(2)は、(1)と対になるトップダウンであり、それは、ルートパス上のすべてのタプルにわたって乗算することにより効果的な重みを産出する。(2a)は、奇妙にも標準SQLには欠けている仮想のPRODUCT集約関数を使用し、(2b)は、FIRST_VALUEをうまく活用して、再帰を介してそれをワークアラウンドする。例を理解するために、トップダウン再帰的演算では、ウィンドウフレームは、空であり得る(FIRST_VALUEにNULLを産出させる)か、または1つのカバーされた祖先を含み得るということに留意されたい。部品表において、重みは、部品の、そのスーパー部品内での多重度(「どれくらいの頻度か?」)であり得、ここでは、製品は、部品が組立て品中に全体でしばしば登場することを伝える。
【００７６】
(3)は、カバーされたタプルのみにわたって合計する(1)の変異形である。(3b)では、Valueにのみアクセスできるが、実際の表現結果にはアクセスできず(故に、そのタイプ
【数３０】
2018014096.tif 000032
は自動推定され得る)、依然として、セマンティクスは再帰的評価のものである。Inp2がすべてのHTノードを含むような場合、カバー関係式<:は、先に述べたようにIS_CHILD述語と等価になるため、join-group-aggregateを介して同じことが同様に達成され得る。
【００７７】
(4)は、重み付けされたロールアップの変異形である。(4d)は、ほとんど(4b)と等価であるが、(4b)を、入れ子ウィンドウ関数を使用して現在の行のWeightにアクセスする(4c)に類似した形態にする。一般に、そのような重み付けされたロールアップは、(構造)再帰なしでは実施することができない。しかしながら、時に動作する非再帰的ワークアラウンドは、分配法則に従って表現を「掛け合わせて展開」し、2つの別個の演算:第一に各タプルの絶対重みwを産出する(2a)、次いでSUM(w *Value)ボトムアップを使用することである。
【００７８】
(5)は、(2)と同じ技術を使用して階層のパスベースのデューイ表現を構築する:それは、例えばC1の場合は'/A1/B1/C1'など、ルートパス上のID値から文字列を築く。
【００７９】
(6〜9)は、入力テーブルにわたってデータフローグラフのプロパティを計算する。Inp2はHTのすべてのノードを含むため、それらは、ノードの(6)レベル、(7)部分木のサイズ、(8)部分木の高さ、および(9)子総数に等しい。一般に、(7)は、ウィンドウフレームのサイズおよび(9)カバーされたタプルの数を提供する。
【００８０】
最後に(10)では、SQLの集約関数および表現言語の能力を超越する必要がある場合、ARRAY_AGGを使用して、カバーされたタプルからデータを収集し、それをユーザ定義された関数に渡すことができる。このようにして任意に複雑な演算が差し込まれ得る。
【００８１】
構造グループ化演算子。本明細書に提供されるのは、階層演算クエリを評価するための2つの論理演算子であり、1つは単項構造グループ化用、および1つは二項構造グループ化用である。
【００８２】
二項グループ化。二項構造グループ化クエリは、典型的に、IS_DESCENDANTなどの階層軸上の内部または左外部結合、および外部側のその後のグループ化を特徴づける。それらは、最初、好適な階層述語θを有する形式
【数３１】
2018014096.tif 000033
のプランに翻訳される。上に記される効率性の問題に起因して、このパターンを単一の複合演算子に書き換えるためのクエリオプティマイザ。
【００８３】
二項グループ化演算子
【数３２】
2018014096.tif 000034
は、表現e1およびe2によって提供される2つの入力関係式
【数３３】
2018014096.tif 000035
を実行し、式中、{ }bは、バッグを意味し、
【数３４】
2018014096.tif 000036
はタプルのタイプである。θを結合述語とすると、xは新しい属性名であり、fは、何らかのタイプ
【数３５】
2018014096.tif 000037
についてのスカラ集約関数
【数３６】
2018014096.tif 000038
である。次いで、
【数３７】
2018014096.tif 000039
は、
【数３８】
2018014096.tif 000040
と定義され、式中、
【数３９】
2018014096.tif 000041
である。それは、タプルtについての関連入力値を含むバッグ
【数４０】
2018014096.tif 000042
に関数fを適用することによって値が得られる
【数４１】
2018014096.tif 000043
のx属性によって各タプル
【数４２】
2018014096.tif 000044
を拡張する。
【００８４】
例として、上のプラン
【数４３】
2018014096.tif 000045
は、fおよび<の同じ定義を使用して、Out1
【数４４】
2018014096.tif 000046
Inp1に書き変えられ得る。
【数４５】
2018014096.tif 000047
プランを最適化する以外に、
【数４６】
2018014096.tif 000048
を使用して、非RECURSIVE表現を有する階層ウィンドウを評価することもできる。それらは、ボトムアップではθ=is-descendant-or-self、およびトップダウンの場合はθ=is-ancestor-or-selfで二項自己グループ化
【数４７】
2018014096.tif 000049
に翻訳される(フレーム句およびEXCLUDEの詳細を処理するモジュロ)。さらなる最適化がそこから可能である。計算された合計xに依存しない出力に対する条件
【数４８】
2018014096.tif 000050
を有するStmt.I-bについて検討する。この種の選択演算子
【数４９】
2018014096.tif 000051
は、典型的には、
【数５０】
2018014096.tif 000052
の左入力へプッシュダウンされ得る。FILTERψは、fによって処理されるか、または右入力へプッシュダウンされ得る。
【数５１】
2018014096.tif 000053
へのそのような書き換えは、常に効果をもたらすが、選択がさらに深くプッシュダウンされ得るときには特にそうである。
【００８５】
単項構造グループ化。階層ウィンドウ上で再帰的表現を評価するために、新しい演算子、単項構造グループ化が本明細書内に提供される。概念それ自体が階層ウィンドウの域を越えて有用であり得るため、データフローを駆動するその入力関係式のタプル上の抽象<比較述語に関してそれを定義することができる。それは、厳密な半順序:非反射的、推移的、および非対称的であることが必要とされる。演算子は、その入力を、エッジがカバーされたタプル<:の観念によって提供される(上の等式1を参照されたい)有向非巡回グラフ内にに配置する。その構造上で、それは、現在のタプルtおよびカバーされたタプルの対応するバッグにおいて、集約のような演算を実施する構造集約関数fを評価する。言い換えれば、変数即ち疑似再帰的表現fは、<によって予め設定された再帰木上で評価される。
【００８６】
表現eに何らかのタプルタイプτについての関係式{τ}bを生成させ、<を、eのタプルの厳密な半順序、新しい属性名x、および何らかのスカラタイプ
【数５２】
2018014096.tif 000054
についての構造集約関数
【数５３】
2018014096.tif 000055
fを提供するτ要素のための比較演算子とする。<、x、およびfと関連付けられる単項構造グループ化演算子
【数５４】
2018014096.tif 000056
は、
【数５５】
2018014096.tif 000057
と定義される。
【００８７】
一般的な単項グループ化の記号Γを
【数５６】
2018014096.tif 000058
に再使用することができる。両方とも、それらが入力タプルのグループを形成するという点で類似しているが、
【数５７】
2018014096.tif 000059
は、タプルを「折りたたむ」ことはない。代わりに、それは、e内の各タプルtを新しい属性xによって拡張し、fをtおよびそのカバーされたタプルuのバッグに適用する「rec」の結果にそれを割り当てる。バッグ内の各タプルuはすでにx値を持つというのが仕掛けであり、x値は今度はrecをuに適用することによって再帰的方式で計算されている。故に、f自体は再帰的ではないが、構造的に再帰的な演算が
【数５８】
2018014096.tif 000060
の定義にカプセル化される。<が厳密な半順序であるため、再帰は、終了することが保証される。
【００８８】
階層ウィンドウでは、実際に非反射的、推移的、および非対称的であるH.is-descendantに関して、<を上のように定義することができる。これより上の2つのステートメントII-cおよびIIIを
【数５９】
2018014096.tif 000061
に基づいたプランに翻訳することができる:
【００８９】
【数６０】
2018014096.tif 000062
【００９０】
図5は、図4のSQL表現に対応するfの定義を示す。例が証明するように、RECURSIVE表現は、ほぼ文字通りに好適なf(t,X)式に換算される。
【００９１】
単項グループ化対二項グループ化。理論上、
【数６１】
2018014096.tif 000063
の関数fに対しては制限がほとんどなく、実用限界は、どのSQLの表現言語が書き込みを可能にするかである。しかしながら、
【数６２】
2018014096.tif 000064
と二項自己グループ化
【数６３】
2018014096.tif 000065
との対応を確立することができる一般的で「単純な」関数のクラスを区別するのが有用である。
【数６４】
2018014096.tif 000066
と一緒に使用するための集約関数
【数６５】
2018014096.tif 000067
は、それが形式
【数６６】
2018014096.tif 000068
のものであれば単純であり、式中、関数
【数６７】
2018014096.tif 000069
は、各タプルから値を抽出または計算し、
【数６８】
2018014096.tif 000070
は、
【数６９】
2018014096.tif 000071
値を組み合わせるための可換の結合演算子である。これは、SQLが形式AGG(expr)で表現することを可能にするものに広く対応し、ここでAGGは、SUM、MIN、MAX、EVERY、またはDISTINCT設定数量詞のないANYなどの基本的な集約関数である。(任意のFILTER(WHERE
【数７０】
2018014096.tif 000072
)条件へのさらなる拡張が可能である。)
【００９２】
構造相当物を以下のように定義することができる:
【数７１】
2018014096.tif 000073
と一緒に使用するための構造集約関数
【数７２】
2018014096.tif 000074
は、それが形式
【数７３】
2018014096.tif 000075
のものであれば単純である。
【００９３】
図5では、関数1b、2b、6b、および7bは、実際に単純である。
【００９４】
対応を得るために、
【数７４】
2018014096.tif 000076
を考える。e上の<によって定められた非巡回有向グラフが木である、即ち、無向閉路が存在しない場合、以下がすべてのt∈Rに対して成り立つ:
【００９５】
【数７５】
2018014096.tif 000077
【００９６】
式中、
【数７６】
2018014096.tif 000078
である。集約関数の単純な形式は、<述語によって再帰を「隠し」、元の入力eに基づいてt.xのための表現の閉形式を得ることを可能にする。故に以下の対応を記述することができる:
【００９７】
【数７７】
2018014096.tif 000079
【００９８】
この等価は、入力e内の2つのタプルu<tを接続する複数のチェーンu<:...<:tが存在する場合には成り立たないことに留意されたい。この状況では、
【数７８】
2018014096.tif 000080
は、uを複数回tの結果に非直接的に算入するが、
【数７９】
2018014096.tif 000081
はそうしない。これは、単にx値を<:チェーンに沿って伝搬する構造再帰の特定のセマンティクスに起因するものである。
【数８０】
2018014096.tif 000082
が階層ウィンドウ設定において適用されるとき、現在のウィンドウパーティション内に重複するv値が存在しないことがさらに確かめられる場合、<:はHの非巡回木構造に由来するために等価が成り立つ。次いで、対応は両方の方向において有用であり、大幅な最適化を可能にする:多くの典型的な非再帰的階層ウィンドウ演算(および時にはjoin-group-aggregateクエリさえ)は、accの形式に適合するため、それらの最初の翻訳
【数８１】
2018014096.tif 000083
に書き換えることができる。本明細書内の他の場所で分析されるように、eが単なるテーブルスキャンであるときさえ、現在の
【数８２】
2018014096.tif 000084
アルゴリズムは、それらのより単純な論理(eが2回評価される必要がない)および効果的なパイプラインに起因して、
【数８３】
2018014096.tif 000085
よりも優れている。逆に、所与のRECURSIVE表現をstr-accの形式に代数的に変換することができる場合、
【数８４】
2018014096.tif 000086
が、
【数８５】
2018014096.tif 000087
の代替案である。出力に対するWHERE条件φまたはFILTER条件ψが適用される場合、すでに上に述べたように、
【数８６】
2018014096.tif 000088
は、通常、
【数８７】
2018014096.tif 000089
に勝る。最後に、1つの結合が節約される、Stmt.I-aのI-bへの現在の手動書き換えは、
【数８８】
2018014096.tif 000090
からΓへの高度な最適化を示す:2つの入力値をe12に「マージすること」によって、(細部に立ち入ることなく)
【数８９】
2018014096.tif 000091
、および次いでΓ(e12)を書き換えることができ、それは、e12がさらに単純化され得る場合、例えば、e1およびe2が最初の段階で非常に類似していたとき、効果をもたらす。
【００９９】
【数９０】
2018014096.tif 000092
のための効率的なアルゴリズムがこれより説明される。
【０１００】
【数９１】
2018014096.tif 000093
の一般的なアプローチは、θを半順序プロパティを有する不明瞭な結合述語として扱うこと、一般的なソートベースのjoin-group-aggregate技術に忠実であることである:入力e1およびe2の両方をθに従ってソートし、次いでソートベースの左外部結合
【数９２】
2018014096.tif 000094
を使用し、次いでソートベースの単項グループ化
【数９３】
2018014096.tif 000095
を使用して結果を計算することである。これは、θによっていくつかのタプルが比較不能であり得るという事実に正しく対処し、e1の順序を保持する非等結合演算子を必要とする。e1およびe2に対してはさらなる仮定が置かれないため、基本的なネステッドループ結合が使用され得、ルーチンの複雑性を非魅力的な
【数９４】
2018014096.tif 000096
にする。インデックスベースのネステッドループ結合は、所与の入力に一般的にはインデックスが存在しない(階層ベーステーブルHTのみがインデックス生成される)ため、使用することができない。このアプローチは、
【数９５】
2018014096.tif 000097
によって参照され得る。それは通常、上のPPPLなどのエンコーディングが、さらなるエンジンサポートなしにRDBMSに手動で実装されるとき、唯一の選択肢である。
【０１０１】
【数９６】
2018014096.tif 000098
が階層演算に使用され、θおよび<がNODEフィールド上で動作するとき、根本となる階層インデックスHが活用され得る、および活用されるべきである。
【数９７】
2018014096.tif 000099
に対する大きな改善は、階層マージ結合、
【数９８】
2018014096.tif 000100
の時間および空間の複雑性を有するソートベースの構造結合演算子を使用することである。前順入力を実行し、子孫軸上で結合し、e1またはe2のいずれかの順序を出力内に保持する階層マージ結合アルゴリズムが提供され得る:それは、ネイティブな
【数９９】
2018014096.tif 000101
アルゴリズムのための最先端かつ自然のベースラインと考えられ得る。より高度な結合技術がXMLの世界では研究されているが、大半は、ベーステーブルHTではなく任意入力に作用する現在の設定には適用できないことに留意されたい。
【０１０２】
【数１００】
2018014096.tif 000102
言及したアプローチは、既存の演算子を再使用することによって実装の労力を低く保つことができる一方、それらは
【数１０１】
2018014096.tif 000103
の構造再帰を評価することができず、それらは上記の効率性の問題を抱えている:単に<:対ではなくすべての<結合対が、クエリ評価中に具体化および処理され、カバーされたタプルからの結果は再使用されない。本明細書に提供されるのは、
【数１０２】
2018014096.tif 000104
であり、それぞれがトップダウンおよびボトムアップ変異形にある4つの専用の演算子である。トップダウン変異形は、入力が前順でソートされることを必要とし、ボトムアップ変異形は後順であり、この順序は出力において保持される。それらの疑似コードが以下に提示される。提示を容易にするため、関係代数レベルからの概念が直接使用される:抽象データ型Aggregateは、タプルバッグXを表し、自明の動作である消去()、追加(u)、およびマージ(X')をサポートする。
【数１０３】
2018014096.tif 000105
の実行中、タプル
【数１０４】
2018014096.tif 000106
ごとに1つのAggregateインスタンスXを作成し、その中に適切な入力タプルをアセンブルし、それを集約関数f(X)またはf(t,X)に供給してt.xを得ることができる。Aggregateの実際のクエリ別の実装およびその動作において、大幅な最適化がf次第で可能であり得る。
【０１０３】
単項階層グループ化。アルゴリズム1は、
【数１０５】
2018014096.tif 000107
の2つの変異形を示す。
【０１０４】
【数１０６】
2018014096.tif 000108
【０１０５】
入力eを介した単一パスでは、それらは事実上、各タプルtに対して以下のコールシーケンスを発行する:
【０１０６】
【数１０７】
2018014096.tif 000109
【０１０７】
式中、「yield」は結果タプルを出力する。スタックS(ライン1)は、以前に処理したタプルuおよびそれらの演算状態、即ち、u.x、および再使用の可能性のための対応する集約Xを管理する。それぞれ
【数１０８】
2018014096.tif 000110
である。アルゴリズムは、まず、t.vが前のノードに一致するかをチェックすることができ、この場合は、アルゴリズムは、Xをそのまま再使用することができる。(このステップは、vが重複なしであることが分かっている場合は省略され得る。)そうでない場合、「collect input」ブロック(ライン8)がSを維持し、tによってカバーされるタプルXを収集する。次いで、アルゴリズムは、f(t,X)を計算し、出力タプルを構築および産出し、後の再使用のためにそれをXと一緒にS上に置くことができる。
【０１０８】
「collect input」に関して、まずボトムアップの場合(後順入力)を検討する:S上の以前に処理されたタプルは、それがある場合、後順先行処理であり、またそれゆえ、t.vに対して子孫および前方軸上に、スタックの先頭から見たときにその順序で、存在する(一方、この後のeタプルは祖先または後方軸上にある)。したがって、tに必要とされるカバーされたタプルXは、Sの上方部分に簡便に置かれる。whileループ(ライン11)は、それらがもはや必要とされないため、それらを収集および削除する。いかなる残りのSエントリも前方であり、tとは無関係であるが、後で実行され得る。トップダウンの場合(前順入力)、Sは、先頭から見たとき、使われなくなった前方タプル、次いでXに追加すべき関連するカバーされた祖先タプル、次いでさらに将来のイテレーションに依然として必要とされ得る非直接の祖先を含み得る。whileループ(ライン14)はまず、前方タプルを却下する。Sの上に残っているエントリがある場合(ライン16)、それはカバーされた祖先u<:tであり、forループ(ライン17)がそれと下のさらなるタプルとをイコールvを用いて収集する(eが別個でない場合)。木構造のデータフローに起因して、いかなるさらなるカバーされたタプルも存在し得ない。ボトムアップの場合とは異なり、カバーされたエントリがこの後の後方タプル(例えば、vの兄弟)に依然として必要とされ得るため、アルゴリズムは、それらをポップすることはできない。
【０１０９】
このアルゴリズムにおいては明示的チェックは<:に必要とされず、カバーされたタプルは暗黙的に識別されることに留意されたい。また、ライン13および18では、u.xに対応する完全なXu状態がadd()動作に利用可能である。この状態は、u.xが単独では十分な情報を提供しない重要な演算に必要とされ得る。それが必要とされない場合、XをS上に維持する必要は全くない。同様に、fによって実際にアクセスされるuのフィールドのみをS上に含んでメモリ消費を最小限にし得る。
【０１１０】
二項階層グループ化。アルゴリズム2は、
【数１０９】
2018014096.tif 000111
を示す。
【０１１１】
【数１１０】
2018014096.tif 000112
【０１１２】
左外部結合セマンティクスでは、ボトムアップ変異形(後順入力)はθ=is-descendant-or-selfに対して結合し、トップダウン変異形(前順入力)はθ=is-ancestor-or-selfに対して結合する。他の軸(子/親および非「自己」変異形)ならびに内部結合は、小さな適合で処理され得る。両方の入力は、連続してアクセスされる:外部ループ(ライン5)はe1を通過する一方、e2はイテレータpを介してアクセスされる。S2は、結合相手として依然として関連し得る処理されたe2タプルをスタッシュする。S1は、処理されたノードv1を、再使用のためにθ-マッチしたe2タプルの対応する集約Xを有するe1から収集する。iは、S2の位置を指し、トップダウンの場合に必要とされる。
【０１１３】
各
【数１１１】
2018014096.tif 000113
(ライン5)について、出力タプルを生成しS1上にXを記憶する前に、ここでも、以前の等しいノード(ライン6〜9)からXを再使用するか、または「collect input」を介してXをアセンブルすることができる。
【０１１４】
ボトムアップ(後順入力)の場合、「collect input」はまず(ライン14)、すべてのカバーされた子孫エントリをS1から除去し、それらの集約をXにマージする。この動作は、上に動機づけられるように部分的な結果を効果的に再使用するための鍵である。次のループ(ライン17)は、descendant-or-self軸上の関連θマッチをS2からXへ移動させ、最終ループ(ライン23)は、右入力e2をv1の最初の後順後続処理まで進める。いかなる遭遇したt2も、後順先行処理、またはv2=v1のいずれかであり、t2も前順後続処理である場合は、それは子孫である。θマッチは、Xに直接追加され(ライン28)、前方タプルはS2上でスタッシュされる(ライン30)。
【０１１５】
トップダウン(前順入力)の場合は、より込み入っている:S1およびS2エントリは、複数回消費され得、したがってスタックからすぐにポップされ得ない。S1およびS2は、それらがv1に対してe1およびe2からの祖先タプルの全チェーンを含むような方式で維持される。S1上のフィールドiは、S2に対する関係を確立する:S1エントリ[v,X,i]では、バッグXは、S2範囲[0,i[(即ち、排他的に、下から位置iまで)に応じて、vについてすべてのθマッチを組み込む。下に別のS1エントリ
【数１１２】
2018014096.tif 000114
がある場合、
【数１１３】
2018014096.tif 000115
は、vのカバーされた祖先であり、Xは、まさに
【数１１４】
2018014096.tif 000116
と位置
【数１１５】
2018014096.tif 000117
にあるS2タプルとからなる。これらの不変量を維持するには4つのステップを要する:第一に(ライン32)、使われなくなった前方エントリをS1からポップすることができる。第二に(ライン35)、S1上に残っているいかなるエントリも祖先であるため、その
【数１１６】
2018014096.tif 000118
を再使用することができる。第三に(ライン38)、
【数１１７】
2018014096.tif 000119
(位置jから始まる)にはすでに存在していなかった任意の追加の祖先t2をXに追加することができる。その時、位置jから先頭までの残りのS2タプルは前方であり、したがって使われなくなっている(ライン41)。最後に(ライン42)、ancestor-or-selfタプルをXおよびS2に追加するが前方タプルを無視して、e2をv1の第1の前順後続処理まで進めることができる。
【０１１６】
【数１１８】
2018014096.tif 000120
より上からのリコールは、階層ウィンドウおよび非再帰的表現のための
【数１１９】
2018014096.tif 000121
に対するRECURSIVE表現、ならびにjoin-group-aggregateステートメントの特定のクラスに使用される。階層ウィンドウの詳細―即ち、フレームの異なる変異形およびEXCLUDE句―を処理することは、アルゴリズム1および2へのさらなる追加を必要とし、特に、イコールv値を有するタプルは、グループとして識別および処理されなければならない。
【０１１７】
インライン演算。以下の最適化は、
【数１２０】
2018014096.tif 000122
の実用性能に極めて重要である:アルゴリズム1および2の疑似コードは、なんらかのバッグXにタプルを明示的に収集するが、fをオンザフライで評価することによってこのバッファリングを完全に回避することができることが多い。このために、クエリコンパイラは、Aggregate動作のために適切な場所に特定のコードを生成しなければならない:
【０１１８】
【数１２１】
2018014096.tif 000123
【０１１９】
図5のExpr.1bを検討する:Xの実際の状態は、部分合計x:
【数１２２】
2018014096.tif 000124
であり、動作は、
【数１２３】
2018014096.tif 000125
ということになる。これは、
【数１２４】
2018014096.tif 000126
の両方と機能する。
【０１２０】
【数１２５】
2018014096.tif 000127
を用いた構造的に再帰的な例として、Expr.4cを検討する:ここでは、状態は同じままであるが、
【数１２６】
2018014096.tif 000128
になる。
【０１２１】
このようにXを除去することは、スカラx値自体または
【数１２７】
2018014096.tif 000129
有界サイズのいくつかの他のデータのいずれかが、サブ演算の必要とされる情報を適切に表すことができるときはいつでも機能する。これは、おおまかに、分配(例えば、COUNT、MIN、MAX、およびSUM)および代数集約関数(例えば、AVG、標準偏差、および「k番目の最大値/最小値」)のクラスに対応する。しかしまた一方では、XまたはサイズΘ(|X|)のなんらかの状態を実際に維持しなければならない場合のあるARRAY_AGGまたはDISTINCT集約などのSQL表現が存在する。COUNT(DISTINCT Weight)を検討する:これを
【数１２８】
2018014096.tif 000130
のいずれかを使用して評価するために、Aggregateは別個のWeight値のセットを維持しなければならない。依然として、サブ演算を再使用するための現在の機構は、特定の最適化機会、例えば、動作
【数１２９】
2018014096.tif 000131
のための効率的な和集合アルゴリズムを使用すること、を提供する。
【０１２２】
複雑性。これを踏まえて、ランタイムおよび空間複雑性を検討する。is-beforeプリミティブは、大半の静的インデックスについては
【数１３０】
2018014096.tif 000132
および共通の動的インデックスについては
【数１３１】
2018014096.tif 000133
内にあると仮定することができ(|HT|は階層サイズである)、どちらにせよ、それらは
【数１３２】
2018014096.tif 000134
の入力サイズによって影響を受けない。さらには、演算が説明されるようにインラインで行われる場合、|X|およびXに対するすべての動作は、実際に
【数１３３】
2018014096.tif 000135
内である。この仮定の下、時間および空間複雑性は、
【数１３４】
2018014096.tif 000136
であり、および
【数１３５】
2018014096.tif 000137
である。演算をインラインで行うことができない場合、それぞれの入力タプルをXバッグに実際に収集することに戻ることができ、これは、現在のアルゴリズムが平易な階層マージ結合アルゴリズムに退化し、ならびにそれらの時間および空間複雑性が
【数１３６】
2018014096.tif 000138
になることを意味する。これらの結果を得るために、償却解析は、アルゴリズムの内部ループが全体的な複雑性に寄与しないことを示すことが必要とされる:
【数１３７】
2018014096.tif 000139
に関して、外部forループが各eタプルを1回S上にプッシュする(つまり|S|≦|e|)一方で、内部whileループがイテレーションごとに1つのSエントリを除去し、故に、それらのボディはそれぞれのプッシュへと償却され得る。
【数１３８】
2018014096.tif 000140
に関して、ライン23およびライン42のループボディは、外部ループに関係なく合計で|e2|回実行され、最大で|e1|および|e2|のタプルがS1およびS2上へそれぞれプッシュされ、他のループがS1またはS2エントリのいずれかを各イテレーション内でポップするため、同様の論法が適用される。
【０１２３】
評価。上のアルゴリズムは、単に外部forループを省くことにより、プッシュベースの物理的代数を特徴とする実行モデルに意図的に適合する。そういった現代のエンジンは、パイプライン内に目に見える演算子境界なしにこれらの代数表現を効率的な機械コードに翻訳することができ、故に、代数による摩擦損失は最小限であり、効果的なパイプラインを有する。
【０１２４】
階層テーブルHTについては、各タプルが独自のCHAR(8)IDおよび小さいドメイン[1,100]から無作為に導出されるTINYINT Weightを有する図1の図表が使用された。テーブルサイズ|HT|は、L3キャッシュ容量をはるかに超える負荷もカバーするために103〜106まで様々であった:106では、HTおよびそのインデックスは≒218MBを使用する。階層インデックスについては、2つの代替案を比較することができる:[静的]は、更新をサポートしないが、非常に速く、故に限定読出分析シナリオにおいて魅力的である上記の単純なPPPLラベリングスキームを指す。[動的]は、各ノードが動的B+木構造内の2つのエントリにリンクされるBO木インデックス生成スキームを指す。混合したブロックサイズおよびギャップバックリンクを有する提案された構成が使用された。それは動的OLTPシナリオにぴったり合うが、更新のサポートは、演算的に重要なΟ(log|HT|)クエリプリミティブおよび増加したメモリトラフィックの犠牲を伴う。他の動的インデックス生成スキームは、当然ながら、異なる特徴を示し、依然として、動的対静的を比較することが、外部の動的インデックス構造にアクセスすることから予期するオーバーヘッドの良い手掛かりを提供する。すべての実験は、生成された森構造Regular<k>を使用し、ここで各木は、m=104ノードを与えられ、各内部ノードはちょうどk個の子を与えられる。|HT|を増加させるこの方法は、合計の高さhに影響を与えない。階層形状の影響を分析するために、非常に深い(k=2,h≒13.2)木を非常に浅い(k=32,h≒3.6)木と比較した。
【０１２５】
階層ウィンドウ。階層ウィンドウのそのままの性能を分析するために、Stmt.IVが、図4の図400の様々な表現を使用して、事前に具体化されたテーブルInpに対して実行され得る。クエリQ1およびQ2は、Expr.1aをそれぞれボトムアップおよびトップダウンで計算し、非再帰的演算を表す。Q3はExpr.(4c)を計算し、構造的に再帰的な演算を表す。Q4は、COUNT(DISTINCT Weight)をボトムアップで計算し、比較的高コストの重複除去を特徴とする。各クエリについて、代替プランを測定することができる。すべてのプランは同じ入力Inpで機能し、それは以下のように事前に準備される:HTの中身を選択し(故に、|Inp|=|HT|)、無作為に集められたINT値フィールドを追加し、必要とされるフィールドを予測し、それぞれのプランによって必要とされる場合にデータを前順または後順のいずれかでソートすることができる。故に、測定値は、いかなる前処理または後処理もなし、特にソートなしであるが、クエリ結果の具体化を含む、それぞれの演算子のそのままの性能を示す。適切な場合、以下のプランを比較することができる:(a)
【数１３９】
2018014096.tif 000141
への直接翻訳、(b)
【数１４０】
2018014096.tif 000142
にわたるオーバーヘッドを分析するために、
【数１４１】
2018014096.tif 000143
、(c)前順ベースの階層マージ結合を用いた上の
【数１４２】
2018014096.tif 000144
アプローチ、(d)ネステッドループ結合を用いた
【数１４３】
2018014096.tif 000145
アプローチ。上に説明されるように、(c)は自然のベースラインである一方、(d)が、多くの場合、手動実装のエンコーディングでの唯一の選択肢となる。さらに、SQLの再帰的CTEを模倣するセミナイーブな最小不動点演算子に基づいて2つのプランを検討することができる:(e)イテレーティブは繰り返されたIS_CHILD階層マージ結合を使用して、まずすべての<対をボトムアップ(Q1)またはトップダウン(Q2)で計算し、次いでソートベースのグループ化を使用して実際の演算を実施する。(f)イテレーティブ*は、さらに、ソートベースの「早期グループ化」を各イテレーション内で適用する。これが、非常に良好に最適化されたRCTEから、または手製のイテレーティブストアドプロシージャから予期する性能の手掛かりを提供する。そのようなプロシージャは、自明な親/子テーブルに依然として依存する実際のアプリケーションにおいて共通して見ることができる(隣接リストモデルとして知られる)。しかしながら、(e)および(f)は、一般的な解決策ではなく、それらは、ただすべてのHTノードがInpに存在するという理由から、セットアップにおいて機能する。また、プラン(b)(f)が非再帰的演算の場合のみ機能することに留意されたい。
【０１２６】
図6は、処理された要素|Inp|に対して正規化された結果を示す図600である。赤線は、事前に計算された結果テーブルを物理的上限(≒37.6M/s)としてコピーするタプルごとの速度を示す。静的でのQ1〜3において、
【数１４４】
2018014096.tif 000146
は、この境界に著しく近い(≒25.4M/s、または67%)。
【数１４５】
2018014096.tif 000147
を使用した非再帰的演算(Q1)が、再帰的演算(Q3)より遅くないということは、アルゴリズムが同一であることから驚くに値しない。
【数１４６】
2018014096.tif 000148
の両方については、トップダウンアルゴリズム(Q2)はボトムアップアルゴリズム(Q1)よりもわずかに遅く、それは、それらがカバーされたタプルを速すぎるとして却下することができず、故に本質的により多くのインデックスコールを発行するためである。Q4の重複除去は、コストがかかり、
【数１４７】
2018014096.tif 000149
の両方が、Q1〜3の自明な算術にわたっておおよそ3倍から4倍遅くなる。すべてのクエリQ1〜4にわたって
【数１４８】
2018014096.tif 000150
と比較すると、後者が平均しておよそ32%速いことが分かる。二項グループ化のオーバーヘッドは、eを2回評価すること(この場合はテーブルスキャンである)、およびe1およびe2タプルを関連付けるために必要とされる余分のインデックスコールから生じる。
【数１４９】
2018014096.tif 000151
は、大半はボトムアップQ1(例えば、k=2で≒11倍遅い)においてであるが、トップダウンQ2(k=2で≒3.5倍)においても、
【数１５０】
2018014096.tif 000152
よりも著しく遅く、ギャップは階層の高さと共に大きくなる。これは、ハッシュベースのequi-groupjoinsに関する報告と則して、階層の場合にも既知の「groupjoinの利点」を確証する。
【数１５１】
2018014096.tif 000153
は、使用され得る階層マージ結合アルゴリズムが前順ベースであるために、Q1においていくらか不利であり、前順がトップダウン演算にとってはより自然であるため、
【数１５２】
2018014096.tif 000154
は、Q2においては目立ってより良好に働く。興味深いことに、
【数１５３】
2018014096.tif 000155
は、Q1に対してQ4では他のものほど遅くならず、明らかに、中間結合がコストを支配するため、後続の処理に適したソートベースのグループ化はそれほど問題にならない。それに応じて、
【数１５４】
2018014096.tif 000156
にわたるオーバーヘッドは、Q4ではより小さくなるが、依然として顕著である。
【０１２７】
イテレーティブソリューションは、概して遅い。早期集約はボトムアップの場合には大いに役立ち、ここではイテレーティブ*が|HT|=106で
【数１５５】
2018014096.tif 000157
にさえアプローチする。しかしながら、トップダウンの場合、IS_PARENTがN:1結合であるため、早期集約は中間結果サイズを減少させるのに役に立たず、ここではイテレーティブにわたる(わずかな)節約は、以前のイテレーションの結果を再使用することによって、保存された算術動作から生じる。
【０１２８】
動的対静的インデックスに関して、前者のより複雑な軸チェックは、特に、本質的により多くの軸チェックが発行されるトップダウンQ2において、明白に顕著である。BO木は新たに一括読み込みされ、実際、大半の動的インデックスの性能は増分更新からさらに低下する傾向があることに留意されたい。
【０１２９】
階層形状、ディープk=2対フラットk=32、を検討する場合、イテレーティブおよびイテレーティブ*は、当然、それらの時間複雑性がhに比例するため、非常にセンシティブである一方、
【数１５６】
2018014096.tif 000158
は事実上無関係であることが分かる。
【数１５７】
2018014096.tif 000159
の中間結合結果は、いくらかhに比例するため、それもまたある程度は影響される(因子2-3)。
【０１３０】
階層サイズ|HT|を増加させることは、インデックスプリミティブのΟ(log|HT|)複雑性に起因して、ダイナミックを遅くするはずである。しかしながら、選択されたブロックベースのBO木インデックスについては、これは明らかに、実際にはそれほど問題にはならない:図は実際には、|HT|に無関係である。これの1つの理由は、順序付けされた入力における有益なデータ局所性である:is-beforeチェックに関与するノードは、通常、事前/事後の距離が近いため、関連するBO木ブロックはキャッシュ内にある。
【数１５８】
2018014096.tif 000160
およびイテレーティブは、それらの増加する中間結果に起因して|HT|に対してはるかにセンシティブである。
【０１３１】
上の実験は、e1=e2である、即ち、単項階層ウィンドウ設定である
【数１５９】
2018014096.tif 000161
のみを分析することに留意されたい。また、様々な|e1|および|e2|サイズでe1≠e2である測定を実行することができる。しかしながら、結果は、
【数１６０】
2018014096.tif 000162
の複雑性
【数１６１】
2018014096.tif 000163
に完全に則することが分かった。
【０１３２】
ソート。順序ベースであるため、
【数１６２】
2018014096.tif 000164
は、事前または事後順序付けされた入力を必要とする。(a)is-beforeを介した明示的なソート動作、(b)最初に順序を確立するための、ベーステーブルHTに対する順序付けされた階層インデックススキャン、(c)一旦確立された順序を保持するための、階層マージ結合などの順序保存演算子および
【数１６３】
2018014096.tif 000165
を用いることによって、それらを提供するのはコストベースのオプティマイザ次第である。図4のExpr.2bをHT上で直接実行することを検討する。ボトムアップの場合、ちょうど
【数１６４】
2018014096.tif 000166
内のようにすでに事後順序付けされたHTのコピー上の
【数１６５】
2018014096.tif 000167
、階層インデックススキャンによってHTにアクセスするフルソート
【数１６６】
2018014096.tif 000168
、および
【数１６７】
2018014096.tif 000169
を比較することができ、トップダウンの場合は必要な変更を加える。Rearrange演算子は、すでに事前に順序付けされたHTコピーを消費し、
【数１６８】
2018014096.tif 000170
に類似したスタックベースの構造ソートアルゴリズムを用いるが、その利点は、それが限定されたパイプラインを可能にすることである。
【０１３３】
図6の図600内の結果から、アルゴリズムがマルチスレッドでないことを考えると、フルソートは、予測し得るものよりも高価でない(静的ではおよそ3倍遅い)ことを観察することができる。インデックススキャンを活用することもかなり助けになる。しかしながら、最も興味深いことに、Rearrangeの「順序ベースのソート」は、フルソートよりもはるかに優れており、ボトムアップ静的の場合は特にである:Rearrangeは、e0の「完璧な」速度にかなり近づく。ここでも、これはパイプライン効果およびすでに事前に順序付けされた入力における有益なデータ局所性によって説明される。これは、ボトムアップアルゴリズムが後順に制限されないことを意味し、それらは、控えめな追加コストだけで前順入力にも適用され得る。度合いは少し減るが、これは、前順ベースのトップダウンアルゴリズムにも適用される。
【０１３４】
レポートクエリ。階層ウィンドウを切り離して分析すると、次に完全なクエリQ7を見ることができる、上のStmt.I-aの設定をエミュレートするために、|HT|=104およびk=8を使用し、階層HTのサブセットのみ、即ち、その8751の葉ノードのp%(無作為に選択される)を用いてテーブルInpを準備することができる。中心では、Q5がQ1としてボトムアップロールアップを実施するが、さらに(a)HTの関連出力ノードとの結合/和集合を必要とし、(b)各ノードのX値の親の合計に対する寄与を%で計算し、(c)演算によって128バイトのさらなるペイロードを運び、(d)前順に順序付けされる3つの上方レベル(584ノード)のみ出力し、デューイ式パス文字列によってノードの位置をユーザに可視化する。そのような追加の「ストレス因子」は、実際のクエリにおいてもよく見られる。例の結果ラインは、'/A1/B1'のX値が1250の場合、['/A1/B1/C2',125,10%,ペイロード]であり得る。SQLは以下になる:
【０１３５】
【数１６９】
2018014096.tif 000171
【０１３６】
以下の手動最適化されたプランを測定することができる:
【０１３７】
【数１７０】
2018014096.tif 000172
【０１３８】
すべてのプランにおいて、
【数１７１】
2018014096.tif 000173
はプッシュダウンされており、HTの順序付けされたインデックススキャンによって処理される。プランaおよびbは、
【数１７２】
2018014096.tif 000174
演算子を使用する。外部
【数１７３】
2018014096.tif 000175
は、両方のトップダウン演算を処理し、所望の前順を保存する。プランcでは、拡張なしの階層テーブルモデルを仮定することができる:それは、階層マージ結合、即ち、
【数１７４】
2018014096.tif 000176
アプローチのみに依存する。シンタックス拡張に欠けるため、多くの手動「SQL作業」が関与する:上方3つのレベルは、2つのIS_PARENT結合および手で構築されるパス文字列を介して結合されなければならない(2つの外部
【数１７５】
2018014096.tif 000177
およびc/d内のMap演算子)。プランdでは、手動実装された静的PPPL様のラベリングスキームを仮定することができる。エンジンサポートに欠けるため、それは、ネステッドループ結合、即ち、
【数１７６】
2018014096.tif 000178
アプローチのみを使用することができる。プランeでは、ここでも、隣接リストモデル、およびイテレーティブ不動点演算(Q1/Q2におけるイテレーティブのような)を行う手書きのストアドプロシージャを仮定することができる。プランd〜eは、a〜cと比較してひどく不利であるが、それらは実際のアプリケーションにおける最先端を代表するものである。
【０１３９】
図6は、様々なpにわたる測定されたクエリスループットを示す。このクエリにおける最大の痛点は、Inpの高コストなソートであり、それは並列ソートによって緩和され得る。それにもかかわらず、依然として提案されたシンタックスおよびアルゴリズムの長所を見ることができる:
【数１７７】
2018014096.tif 000179
の両方がクエリを合理的に処理するが、後者のほうがその二項性質により自然にフィットする。平易な
【数１７８】
2018014096.tif 000180
に勝るそれらの利点は、依然として見えるが、ソートの減衰効果に起因してあまり明白ではない。プランc、d、およびeが、扱いにくい手製のソリューションであることに加えて、表現性および効率性に関して維持できないことは驚きではない。Q7は、アプリケーションシナリオにおいて典型的に見られる単なる1つの例のクエリである。
【０１４０】
階層演算の表現。MDXまたはXML/XQueryなどのいくつかのクエリ言語は、階層データおよび特定の演算に対するネイティブなサポートを提供するが、目標は、SQLの世界に留まることである。階層テーブルの前に、均一データモデルおよびRDBMS内の階層を処理するための言語が欠けていた。初期のソリューションは、したがって、通常、表現され得る演算を主に命じる特定のリレーショナルエンコーディングにハードウェアで組み込まれる:ローエンドでは、親ノードへの外部キー参照に基づいた自明な隣接リストモデルであり、ここでは再帰(下を参照されたい)が単純なタスクにさえも必要とされる。より高度なパス(またはコンテインメント)ベースのエンコーディングは、再帰を階層結合に代えることを可能にすることによって多くのタスクを緩和するが、演算はjoin-group-aggregateステートメントができることに限られる。別の一般的な「スキーム」は、非正規テーブルが一定数の同種レベルを有する階層をエンコードする平準化モデルである。特にこのモデルを標的とすると、SQLは、単純な合計、計数などのためのROLLUP構造体を有するが、これは、GROUPING SETSのための糖衣構文にすぎず、ここでも限られた表現性のものである。階層テーブルモデルは、手動実装のエンコーディングの複雑性および制限に対処することからユーザを解放する。その抽象的な性質は、提供された構造体が、クエリ/更新性能スペクトルで多数のインデックス生成スキームと連携することを確実にする。さらに、階層をカプセル化するNODEフィールドのその主概念は、上で調査された魅力あるシンタックス機会を提供する。
【０１４１】
SQL内の再帰。再帰的に構築されたデータと連携するための唯一2つの一般的なRDBMSレベル機構は、RCTEおよび(イテレーティブまたは再帰的)ストアドプロシージャである。これらの機構は、生成的な再帰を与え、故にRECURSIVE表現の構造再帰よりも強力である。しかしながら、それらのパワーおよび普遍性はまた、処理および最適化することを困難にする。GROUP BYを用いた直線的に再帰的なCTEの最適化では、有向グラフが検討され得る一方で、焦点はとりわけ木構造に向けられる。当然のことながら、専用のアルゴリズムは、RCTEのための技術に容易に勝る。また、構造再帰の単純な性質(再帰木が予め定義される)は、上に説明されるように、最適化の余地をより多く残す。性能は別として、RCTEが表現性に関して少なくとも「十分である」かどうか、即ち、GROUP BYを用いたRCTEベースの再帰が構造グループ化をエミュレートするかを尋ねることができる。残念なことに、イテレーティブ方式でそのような演算を表現するすべての試み(<-最小タプルで始まり、<:によって入力にわたって幅優先で探索する)は、非常に入り組んだEXISTSサブクエリを導いた。また、GROUP BYは、セミナイーブな不動点評価を可能にするために、RCTE定義内では禁止されている。GROUP BYが使用され得るとしても、必ずしも各イテレーション内のすべての関連するカバーされたノードを捕捉するわけではない。したがって、ユースケースでは、RCTEの演算力は、理論的な関連性があるだけである。
【０１４２】
集約クエリの評価。GROUP BYを評価することは、ソートベースの方法またはハッシュベースの方法のいずれかを使用して行われ得る。ソートベースのグループ化のように、演算子は、順序付けされた入力を必要とし、順序保存である。Group-joinは、
【数１７９】
2018014096.tif 000181
を融合することによって、join-group-aggregateプランを改善する。
【数１８０】
2018014096.tif 000182
設定により匹敵するnon-equiの場合を検討する。ROLLUPに関して、1つのアプローチは、より低いレベルの結果を再使用する専用の単一パス演算子を使用することができる。標準のウィンドウ表示テーブルのための技術は、それらの独自のセマンティクスに起因して階層ウィンドウに容易に適合され得ないことを理解されたい。
【０１４３】
階層認識演算子。XMLデータは、本質的に階層的であり、多くの場合リレーショナルテーブル内に記憶されるため、ネイティブなXMLストアまたはXMLを強化したRDBMSにクエリを行うことに関する膨大な一連の作業が存在する。self-merge-joinsと似ている構造結合演算子は、利用可能な(ハードウェアに組み込まれることにより)階層エンコーディングを活用し、関連中間結果のスタックを維持する。XML世界のすべての技術が本設定に適合するわけではないが、より高度な結合演算子のうちの一部は、インデックス化されたXML文書上で直接働くように設計された。これが、スキッピングなどの高等の最適化を可能にする。対照的に、現在の演算子は通常、階層テーブル(例えば、HT)自体よりも、NODEフィールドを有する任意の入力テーブル(例えば、Inp1)に適用される。Inp1をオンザフライでインデックスすることは実現不可能に思えるため、HTのインデックスのみが依存され得、適用できない最適化の多くをレンダーする。演算がHT上で直接動作する場合には、例えば階段結合を適合し得るが、これは限られた数のクエリにのみ役立つ。二項構造結合を超越して、強力な木パターンマッチング演算子(例えば、小枝結合)がXMLコンテクスト内で提案されたが、これらはRDBMS内の階層データを処理するための要件を超越している。
【０１４４】
RDBMS内で階層演算を表現することは、常に、データモデルおよび言語問題によってかなり妨げられており、可能なときにさえも、入り組んだRCTEまたはプロシージャコールが有効な評価を非常に難しくした。この状況は、表現性およびエンジンサポートに関して、階層テーブルモデルの機会を利用することによって解決することができる。NODEタイプおよびSQLのウィンドウ表示テーブルは、自然に調和することが分かる。構造再帰と一緒に、演算の有用なクラスは、簡潔かつ直観的に表現され得る。それらの評価には、順序ベースのインデックス補助された構造グループ化演算子が提案される。それらは、前順および後順プリミティブに完全に依存し、故に、多数のインデックス生成スキームと連携する。現在の実験は、従来のアプローチに勝るそれらの長所を確証し、それはロバストな線形空間および時間複雑性ならびにそれらの演算力から生じるものである。本明細書において提供される新規機能はすべて、ビジネスソフトウェアおよび他の領域において、それらがさらに多くの論理をRDBMS層まで押し下げることを可能にすることによって、階層を取り扱う多くのアプリケーションを大いに単純化し高速化する。
【０１４５】
図7は、710でデータベースがクエリを受信するプロセスフロー図700である。クエリの一部は、データテーブルへの要求であり、ここでは各行がノードの階層内のノード(最大で1つ)、およびそのテーブル上の階層ウィンドウ句に関連付けられている。その後、720で、ウィンドウ表示テーブル内の行の少なくとも一部分の有向非巡回グラフが、階層ウィンドウ句に基づいて生成される(概念的に、またはメモリ内に具体化されるかのいずれか)。有向非巡回グラフを使用して、730では、クエリ内で指定される表現に基づいて、グラフのエッジにわたって行からデータを蓄積することによってクエリに応答した結果が得られる。次いで、730で、得られた結果の少なくとも一部分を含むデータが提供される。ただし、これに関連して、有形のデータストレージ内に得られた結果の少なくとも一部分を記憶するステップ、得られた結果の少なくとも一部分をメモリに読み込むステップ、得られた結果の少なくとも一部分を電子視覚表示装置に表示するステップ、および/または得られた結果の少なくとも一部分をリモートコンピューティングシステムに送信するステップのうちの1つまたは複数を含むことができる。
【０１４６】
本明細書に記載される主題の1つまたは複数の態様または特徴は、デジタル電子回路、集積回路、特別に設計された特定用途向け集積回路(ASIC)、フィールドプログラマブルゲートアレイ(FPGA)コンピュータハードウェア、ファームウェア、ソフトウェア、および/またはそれらの組み合わせにおいて実現され得る。これらの様々な態様または特徴は、データおよび命令を受信するために、ならびにデータおよび命令を送信するためにストレージシステム、少なくとも1つの入力デバイス、および少なくとも1つの出力デバイスに連結される、特殊用途または汎用であり得る少なくとも1つのプログラム可能なプロセッサを含むプログラム可能なシステム上で実行可能および/または翻訳可能である1つまたは複数のコンピュータプログラム内の実装を含み得る。プログラム可能なシステムまたはコンピューティングシステムは、クライアントおよびサーバを含み得る。クライアントおよびサーバは、概して互いから離れており、典型的には通信ネットワークを介して相互作用する。クライアントおよびサーバの関係は、それぞれのコンピュータ上で動作し、かつ互いにクライアント-サーバ関係を有するコンピュータプログラムによって生じる。
【０１４７】
プログラム、ソフトウェア、ソフトウェアアプリケーション、アプリケーション、コンポーネント、またはコードとも称され得るこれらのコンピュータプログラムは、プログラム可能なプロセッサのための機械命令を含み、高レベル手続型言語、オブジェクト指向プログラミング言語、関数型プログラミング言語、論理型プログラミング言語、および/またはアセンブリ/機械言語で実装され得る。本明細書で使用される場合、「機械可読媒体」という用語は、機械命令を機械可読信号として受信する機械可読媒体を含む、機械命令および/またはデータをプログラム可能なプロセッサに提供するために使用される、例えば、磁気ディスク、光学ディスク、メモリ、およびプログラム可能な論理デバイス(PLD)などの、任意のコンピュータプログラム製品、装置、および/またはデバイスを指す。「機械可読信号」という用語は、機械命令および/またはデータをプログラム可能なプロセッサに提供するために使用される任意の信号を指す。機械可読媒体は、例えば、非過渡ソリッドステートメモリまたは磁気ハードドライブまたは任意の同等の記憶媒体がそうであるように、そのような機械命令を非一時的に記憶することができる。機械可読媒体は、代替的に、または加えて、例えば、プロセッサキャッシュ、または1つもしくは複数の物理的プロセッサコアと関連付けられる他のランダムアクセスメモリがそうであるように、そのような機械命令を一時的な様式で記憶することができる。
【０１４８】
上記説明および請求項において、「のうちの少なくとも1つの」または「のうちの1つまたは複数の」などの語句が登場した後、要素または特徴の結合的なリストが続き得る。「および/または」という用語はまた、2つ以上の要素または特徴のリストにおいて登場し得る。別途それが使用される文脈により暗黙的または明示的に否定されない限り、そのような語句は、列挙された要素もしくは特徴のいずれかを個々に、または列挙された要素もしくは特徴を他の列挙された要素もしくは特徴のいずれかと組み合わせて、を意味することが意図される。例えば、「AおよびBのうちの少なくとも1つ」、「AおよびBのうちの1つまたは複数」、ならびに「Aおよび/またはB」という文言はそれぞれ、「Aだけ、Bだけ、またはAおよびBを一緒に」を意味することが意図される。同様の解釈はまた、3つ以上の項目を含むリストについても意図される。例えば、「A、B、およびCのうちの少なくとも1つ」、「A、B、およびCのうちの1つまたは複数」、ならびに「A、B、および/またはC」という文言はそれぞれ、「Aだけ、Bだけ、Cだけ、AおよびBを一緒に、AおよびCを一緒に、BおよびCを一緒に、またはAおよびBおよびCを一緒に」を意味することが意図される。加えて、上記および請求項における「に基づく」という用語の使用は、未列挙の特徴または要素も許容できるように、「に少なくとも部分的に基づく」ことを意味することが意図される。
【０１４９】
本明細書に記載される主題は、所望の構成に応じて、システム、装置、方法、および/または物品において具現化され得る。先述の説明において明らかにされる実装は、本明細書に記載される主題と一致するすべての実装を表すものではない。むしろ、それらは、記載された主題に関する態様と一致するいくつかの例にすぎない。上にはいくつかの変形形態しか詳細に説明されていないが、他の修正または追加が可能である。特に、さらなる特徴および/または変形形態が、本明細書内で明らかにされるものに加えて提供され得る。例えば、上記の実装は、開示された特徴の様々な組み合わせおよび副組み合わせ、ならびに/または上に開示されるいくつかのさらなる特徴の組み合わせおよび副組み合わせを対象とし得る。加えて、添付の図面に描写されるおよび/または本明細書に記載される論理フローは、望ましい結果を達成するために、必ずしも示される特定の順序、またはシーケンシャル順序を必要としない。他の実装は、以下の請求項の範囲内であり得る。
【図１】
2018014096.tif 000183
【図２】
2018014096.tif 000184
【図３】
2018014096.tif 000185
【図４】
2018014096.tif 000186
【図５】
2018014096.tif 000187
【図６】
2018014096.tif 000188
【図７】
2018014096.tif 000189
【外国語明細書】
2018014096000001.pdf