SQL実行計画表現における関係演算子

この文書について

この文書では、SQL実行計画表現において、利用可能な関係演算子の種類と、その構成について検討する。

本内容は「 SQLにおける実行モデル」に基づいている。

SQL実行計画表現

本プロジェクトにおけるSQLの実行計画表現は、主に以下の3種類である。

論理実行計画 - logical execution plan ~ SQLが「何をするのか」を端的に表した表現。

ほぼSQLの構文を解析した抽象構文木 (AST: Abstract Syntax Tree) そのものであり、SQLコンパイラがプログラムの意味解析（列参照の解決など）を行うために存在する。

コンパイラ内部の中間表現であり、コンパイラの外側でこれを直接取り扱うことはほとんどない。

中間実行計画 - intermediate execution plan ~ 論理実行計画を関係演算子のグラフ形式に変形した表現。

ここで出現する演算子は「リレーションをどう処理するのか」について言及しており、例えば結合処理ではソートマージやハッシュ結合などのアルゴリズムの選択が行われた状態になっている。

主に、オプティマイザのための表現で、オプティマイザはこの表現の上で演算子の並び替えや入れ替えによって処理の最適化を実施する。

ステップ実行計画 - step execution plan ~ 中間実行計画をさらに構造化し、具体的な並列化方式や演算子間のデータ交換方式を含めた表現。いわゆる「ステップグラフ」として表現する。

ステップグラフにおけるプロセスは内部に関係演算子のグラフを有しており、かつその処理は並列化可能で、待ち合わせを行わないものに限定されている。なお、待ち合わせを要する処理は、ステップグラフにおけるエクスチェンジ内で行うことになる。このため、中間実行計画における演算子のいくつかを細分化して、上記の要件を満たす新たな演算子として導入している。

本モデルにおける実行エンジンは、主にこの表現を利用して処理を行うことになる。

本文書では、主に中間実行計画における関係演算子について解説したうえで、それらがステップ実行計画でどのように表現されるかを紹介する。論理実行計画については内部表現であるため、本文書では触れないものとする。

SQL実行計画表現の用語

上流 ~ ある関係演算子について、その演算子の入力となるリレーションを出力するような演算子のこと

下流 ~ ある関係演算子について、その演算子が出力するリレーションを入力にとるような演算子のこと

SQL実行計画表現のコンセプト

データは常に上流の演算子から下流の演算子に向かって渡される
- 下流の演算子の処理結果が、上流の演算子の処理に影響を及ぼさない
- 上流の演算子は、その出力結果のデータを以てのみ、下流の演算子の処理に影響を及ぼせる
リレーション内の行の順序は規定しない
- 何らかの順序が必要な場合、関係演算子内に閉じて順序付けを行う
- または「グループ表」を構築し、各グループ内の行を並び替える
リレーション内の列の順序は規定しない
- これにより、 LEFT/RIGHT OUTER JOIN 等を片側だけ考えればよくなる
必要でない列がリレーション内に存在してもよい
- DISTINCT のようにリレーションに含まれる列が動作に影響する場合、対象の列を明示的に指定する
- 関係演算グラフ上では不要な列を除去せず、後段の最適化によってのみ除去する
それぞれの行において列の値は不変で、計算結果は新しい列として定義する
- これは、後段のコード生成を容易にするための措置

中間実行計画とステップ実行計画の差異

中間実行計画は1個の関係演算グラフからなるが、ステップ実行計画はプロセスごとに独立した関係演算グラフを持つ
- ステップグラフにおけるエクスチェンジは関係演算子ではなく、プロセス間の関係演算グラフは隔絶している
- 中間実行計画にはエクスチェンジに相当するものは出現しない
ステップ実行計画における演算子は、グループ表（二階のリレーション）を入力にとるものがある
- 中間実行計画では、すべての演算子は一階のリレーションのみを入力にとる
- ステップ実行計画では、各演算子はそれぞれの「行」を並列処理できるように設計している
  - グループ表を取り入れることで、上記の制約のまま「グループ」を取り扱う演算子も並列処理できるようになる
ステップ実行計画では、中間実行計画における演算子を「データ交換」と「残りの部分」に分けて表現する場合がある
- 例えば、中間実行計画における「ソートマージ結合」は単一の演算子として表現する
- ステップ実行計画では、上記を「グループ表の構築」「グループ間の結合」「グループ内の結合」の3つの処理に分解している
  - このように処理を分解することで、それぞれを並列処理しやすくなっている
  - このうち「データ交換」に該当する箇所は「グループ表の構築」で、 shuffle エクスチェンジが実現している

notes:

上記は、主にそれぞれの表現の用途の差異から来ている
- 最適化では演算子の置換や並び替えが重要であるため、可能な限り「関係演算」という単位を崩していない
- 対して、ステップ実行計画ではデータ交換と並列化に重点を置いているため、元の関係演算からデータ交換処理部分を抽出し、複数の処理に分解している

関係演算子の基本性質

関係演算子は、基本的に1個以上のリレーションの入力に対し、1個のリレーションを出力するものである。本モデルではこの概念を拡張し、「0個以上のリレーションを入力に対し、0個以上のリレーションを出力する」というものを「関係演算子」とよぶものとする。

中間実行計画や、ステップ実行計画におけるプロセスはそれぞれ、上記の関係演算子を頂点とする関係演算グラフを用いて表現する。関係演算グラフは、最上流の演算子においてデータベースからリレーションを読み出し、それぞれの演算子がリレーションを処理して下流の演算子に引き渡すことをグラフ全体で繰り返すことで、SQLの処理を実現する。

本章では、それぞれの関係演算子が有するべき性質について検討する。なお、文脈上誤解がない限り、関係演算子を単に「演算子」として表記する。

演算子の入出力

ほとんどの演算子は、1個以上のリレーションの入力を変形し、ちょうど1個のリレーションを出力する。

上記の例外となるものは、以下のような演算子である。

入力が0個
- 「テーブルスキャン」など、関係演算グラフの 外部から データを取得する演算子
出力が0個
- 「テーブルの更新」など、関係演算グラフの 外部へ データを出力する演算子
出力が2個以上
- リレーションを2つ以上に複製し、複数の演算子が入力として利用できるようにする演算子 (buffer 演算子のみ)

リレーションの構造

演算子が入出力するデータは、すべて「リレーション」という形式である。

それぞれのリレーションは「行」と「列」からなり、以下のような特性を持っている。

リレーションには0個以上の行が含まれている
それぞれの行は、リレーションに定められた列の値を定められたデータ型で有する
リレーションに含まれる列とそのデータ型はコンパイル時に決定する
リレーションに含まれる行の具体的な内容や、行の個数は実行時に定められる

列の参照と定義

いくつかの演算子は、演算子の処理内容を表現する際に入力リレーション内の列を参照する場合がある。

この場合、参照する列は以下のいずれかを満たす必要がある。

自身の演算子が直接定義した列
上流の演算子のいずれかが下流に公開する列
- 公開可能な列は、公開した演算子が参照可能な列の一部または全部である

上記のように、参照可能な列は再帰的に定められる。多くのプログラミング言語と同様に、どこかで列を定義し、公開することで、以降でそれを参照できるという方式である。それぞれの演算子では、0個以上の列を定義できる。

なお、下流への列の公開は演算子ごとに定められており、細かな公開の制御はできなくなっている。公開のパターンは以下のいずれかである。

入力リレーションのすべての列と、自身が定義した列を公開 (ほとんどの演算子)
複数の入力リレーションがある場合に、そのいずれかに含まれる列と、自身が定義した列のみを公開 (半結合など)
演算子が定義した列のみを公開 (集約など)

基本的に、列は定義と参照のみを行え、列の内容を変更したり、細かな単位で列を除去したりすることはできない。これは、最適化による演算子の並び替えを容易にするための仕掛けである。ただし、実行時には最適化によって実際の処理に不要な列を、リレーションから除去することが可能である。

Object ID

演算子は、以下のリソースに対してオブジェクトIDがそれぞれ与えられているものとしてその処理を定義する。

テーブル
- テーブルの識別子
- 列の識別子
- 行の識別子
インデックス
- インデックスの識別子
- 列の識別子
- エントリの識別子
- エントリに対応するテーブルの行の識別子
リレーション
- 列の識別子 (列ID)
- 行の識別子 (行ID)
その他
- 関数の識別子 (関数ID)
- エクスチェンジの識別子

なお、上記のうち以下の要素は「静的オブジェクトID」が割り当てられているものとする。

テーブルの識別子
インデックスの識別子
列の識別子
関数の識別子
エクスチェンジの識別子

静的オブジェクトIDは「コンパイラから利用可能なID」であり、実行計画表現に具体的なIDの値が出現する。

対して、それ以外の要素は「動的オブジェクトID」が割り当てられているものとする。これらはコンパイル時にIDの具体的な値を利用することができず、実行計画表現には具体的なIDの値が出現しない。代わりに疑似的な「列」としてプログラム中に出現し、ほかの列と同様に定義や参照が実行計画表現内で行われる。

動的オブジェクトIDを表す列に対する操作の解釈は、実行エンジンにゆだねられている。例えば、テーブルが行のオブジェクトIDを持たないシステムである場合、代替として主キーの値の組をオブジェクトIDとして利用するなどが考えられる。

また、いくつかの演算子は「行IDの再生成」を行うが、このとき生成する識別子の形式は、実行エンジンが自由に定めてよい。

グループ表

ステップ実行計画におけるいくつかの演算子は、二階のリレーションである「グループ表」を取り扱うものがある。

グループ表とはリレーションの各行にリレーションが含まれるような表であり、各行に含まれるリレーションは、元のリレーションを特定の方法で直和分割したものである。 SQLの処理にはこのグループ表をもとにしたほうがやりやすい操作が多数存在し、かつこのグループ化の処理は「待ち合わせ」を伴う。このグループ化を shuffle エクスチェンジで実現し、以降の処理を別の演算子で実現することで、エクスチェンジを複雑化させることなく、SQLの処理を実現している。

なお、中間実行計画では一階のリレーションのみしか取り扱わない。二階以上の操作が必要である場合、演算子の内部で一時的に二階の表を作成して処理し、結果を一階の表として出力する。

中間実行計画における演算子

本章では、中間実行計画における個々の演算子について紹介する。

なお、それぞれの演算子の概要を一望することを目的にしており、厳密な定義は行わない。

以下の形式で、それぞれの関係演算子の構造を紹介する。

演算種 ~ 処理概要

共通構造: 継承する共通構造の一覧
入力数: 入力リレーションの個数
列の公開: 下流への列の公開方式 (すべて, 一部入力と定義のみ, 定義のみ)
プロパティ
- プロパティ名 - プロパティの概要
その他の特性
- 備考等

演算種に「(共通構造)」と記載してある場合、その項は演算子そのものではなく、演算子の共通構造を定義している。

なお、「プロパティ名」の末尾には以下の数量子を付与する場合がある。

? 0個または1個
* 0個以上
+ 1個以上

スキャン系

スキャン系演算子は、データベース上のインデックスを介してリレーションの一部または全部を読み出し、それらを出力する関係演算子である。いずれも演算子としての入力をとらない。

read (共通構造) ~ インデックスからデータを読み出すスキャン演算子の共通構造。

プロパティ
- relation - 外部リレーション (対象インデックス) の識別子
- columns+ - 定義する列の一覧
  - source - 対象リレーション上の列の識別子
  - destination - 列の定義
備考
- 本モデルでは、構造を簡単にするためにテーブルもインデックスの一種 (プライマリインデックス) として取り扱う
  - インデックスはリレーションそのものではなく、必ず裏側にリレーションであるテーブルが存在する
- TBD: 中間実行計画の途中では、外部リレーションはビューである可能性がある
  - ステップ実行計画ではこれらは展開され、ビューへの参照は行わない

find ~ 対象のインデックスから指定のキーを持つエントリを読み出し、リレーションとして出力する。

共通構造: read
入力数: 0
列の公開: すべて
プロパティ
- keys+ - キー構成要素の一覧
  - variable - 外部リレーション上の列の識別子
  - value - 対象の列に対する値
その他の特性
- keys.variable によって指定する列は、対象リレーションのキー全体と一致しなければならない
- keys.value の値に columns.destination で定義する列は出現できない
- 対象のインデックスのキーに対してエントリが一意でない場合、2行以上を取り出す場合がある

scan ~ 対象のインデックスから指定の範囲のキーを持つエントリを読み出し、リレーションとして出力する。

共通構造: read
入力数: 0
列の公開: すべて
プロパティ
- lower? - キー範囲の下限
  - keys - キー構成要素の一覧
    - variable - 対象リレーション上の列の識別子
    - value - 対象の列に対する値
  - endpoint_kind - 端点の種類
    - unbound - 端点指定なし
    - inclusive - 端点を含む
    - exclusive - 端点を含まない
    - prefixed_inclusive - 端点及びそのサブキーを含む
    - prefixed_exclusive - 端点及びそのサブキーを含まない
- upper? - キー範囲の上限
  - lower と同一の構造
- limit? - 最大件数
その他の特性
- {lower,upper}.keys.variable によって指定する列は、対象リレーションのキー全体と一致するか、またはその接頭辞でなければならない
- {lower,upper}.keys.value の値に columns.destination で定義する列は出現できない
- {lower,upper}.keys.value はいずれも対象の列が昇順に整列していることを想定している
  - 降順になっている場合、適宜 lower と upper を読み替える必要がある

notes:

read 共通構造を有する演算子でインデックスを読みだした場合、インデックスを経由して取得可能なテーブル上のデータも透過的に取得できる
- テーブルを参照せず、インデックス上の値を利用するかどうかは最適化の範疇である

結合系

結合系演算子は、SQLにおける結合演算に対応する処理を実現する関係演算子である。いくつかはステップ実行計画においても利用可能であるが、ステップ実行計画で置き換えられているものもある。

join 共通構造 ~ 複数のリレーションを結合する演算子の共通構造。

プロパティ
- join_kind - 結合の種類
  - inner, left_outer, full_outer, semi, anti のいずれか
その他の特性
- join_kind={semi,anti} 以外の場合、行IDを再生成する

join_relation (intermediate::join) ~ 何らかの方法で2入力の結合を行う演算子。

共通構造: join
入力数: 2
列の公開
- join_kind={semi,anti} 以外: すべて
- join_kind={semi,anti} の場合: 第一入力リレーションのみ
プロパティ
- condition - 結合条件
その他の特性
- なし

join_find ~ 入力リレーションに含まれる列の値を利用し、対象のリレーション上のエントリと結合する。

共通構造: join, read
入力数: 1
列の公開: すべて
プロパティ
- keys+ - 等価結合条件
  - variable - 外部リレーション上の列の識別子
  - value - 対象の列に対する値
- condition - 結合条件 (等価結合条件を除く)
その他の特性
- join_kind=full_outer は選択不可
- keys.variable によって指定する列は、対象リレーションのキー全体と一致しなければならない
- keys.value の値に columns.destination で定義する列は出現できない

join_scan ~ 入力リレーションに含まれる列の値を利用し、対象のリレーション上のエントリと結合する。

共通構造: join, read
入力数: 1
列の公開: すべて
プロパティ
- lower? - キー範囲の下限
  - keys - キー構成要素の一覧
    - variable - 外部リレーション上の列の識別子
    - value - 対象の列に対する値
  - endpoint_kind - 端点の種類
    - unbound - 端点指定なし
    - inclusive - 端点を含む
    - exclusive - 端点を含まない
    - prefixed_inclusive - 端点及びそのサブキーを含む
    - prefixed_exclusive - 端点及びそのサブキーを含まない
- upper? - キー範囲の上限
  - lower と同一の構造
- condition - 結合条件
その他の特性
- join_kind=full_outer は選択不可
- {lower,upper}.keys.variable によって指定する列は、対象リレーションのキー全体と一致するか、またはその接頭辞でなければならない
- {lower,upper}.keys.value の値に columns.destination で定義する列は出現できない
- {lower,upper}.keys.value はいずれも対象の列が昇順に整列していることを想定している
  - 降順になっている場合、適宜 lower と upper を読み替える必要がある
- join_kind={semi,anti} の場合、 columns.destination の列は実際には定義されない
- scan にあった limit はセマンティクスが複雑になるため不採用

notes:

CROSS JOIN は無条件の INNER JOIN で代替
NATURAL JOIN は INNER JOIN で代替
RIGHT OUTER JOIN は LEFT OUTER JOIN で代替
UNION JOIN は union で実現
外部リレーションを2個内包し、入力をとらない join は今回は見送り
join_find, join_scan は後述のステップ実行計画において、 broadcast エクスチェンジ上のリレーションを読みだすことができる

タプル系

タプル系演算子は、リレーションを行ごとに独立して処理可能な関係演算子である。ステップ実行計画においてもそのまま利用できる。

project ~ リレーションに列を追加する。

共通構造: なし
入力数: 1
列の公開: すべて
プロパティ
- columns+ - 追加する列の一覧
  - variable - 定義する列
  - value - 列の値
その他の特性
- なし

filter ~ リレーションから特定の行を取り除く。

共通構造: なし
入力数: 1
列の公開: すべて
プロパティ
- condition - 条件式
その他の特性
- なし

buffer ~ リレーションを2つ以上の演算子から入力として取り扱えるようにする。

共通構造: なし
入力数: 1
列の公開: すべて
プロパティ
- なし
その他の特性
- 同一のリレーションを2つ以上出力できる

identify ~ リレーションの各行に行識別子を追加する。

共通構造: なし
入力数: 1
列の公開: すべて
プロパティ
- variable - 定義する列
- type - 追加される値の row_id 型
その他の特性
- variable に格納される値は必ず特殊値にならないことが保証される

グループ系

グループ系演算子は、リレーションをグループ化して処理する必要がある関係演算子である。ステップ実行計画においては待ち合わせが必要となるため、別の演算子が割り当てられる。

aggregate_relation (intermediate::aggregate) ~ グループごとに集計を行う。

共通構造: なし
入力数: 1
列の公開: グループ化キーおよび定義のみ
プロパティ
- group_key* - グループ化キーの一覧
  - 列ID
- columns+ - 出力する列の一覧
  - function - 集約関数の関数ID
  - arguments* - 集約対象の列ID
  - destination - 出力先の列ID
その他の特性
- 行IDを再生成する
- グループ化キーが空の場合、リレーション全体を単一のグループとみなして集計を行う
  - この場合、リレーションが空の場合に空のグループに対する処理が必要になる
- 下流の演算子から利用可能な列は、 group_key および columns.destination である

distinct_relation (intermediate::distinct) ~ リレーション内でグループ化キー列が同値であるような行を1行に制限する。

共通構造: なし
入力数: 1
列の公開: すべて
プロパティ
- group_key+ - グループ化キーの一覧
  - 列ID
その他の特性
- なし

limit_relation (intermediate::limit) ~ リレーション内でグループ化キー列が同値であるような行を指定の行数に制限する。

共通構造: なし
入力数: 1
列の公開: すべて
プロパティ
- count? - 行数
- group_key* - グループ化キーの一覧
  - 列ID
- sort_keys* - ソートキーの一覧
  - variable - 列ID
  - direction - ascendant または descendant
その他の特性
- group_key が空であり、かつ sort_keys に一つ以上の要素が指定されている場合、この演算は「ソート済みリレーション」を出力する
  - 当該リレーションは各行が sort_keys で指定した順序によって整列されている
  - いくつかの演算子は、ソート済みリレーションを入力にとった際に特別な挙動を行う (e.g. emit)

intersection_relation (intermediate::intersection) ~ 2つのリレーションの（多重集合における）共通部分を出力する。

共通構造: なし
入力数: 2
列の公開: 第一入力リレーションのみ
プロパティ
- quantifier - 量子化の種類
  - all - 入力を多重集合として扱う
  - distinct - 入力を集合として扱う
- group_key_pairs* - グループ化キーの一覧
  - 列ID * 2
その他の特性
- 常に第一入力リレーションのみを出力する

difference_relation (intermediate::difference) ~ 2つのリレーションの（多重集合における）差を出力する。

共通構造: なし
入力数: 2
列の公開: 第一入力リレーションのみ
プロパティ
- quantifier - 量子化の種類
  - all - 入力を多重集合として扱う
  - distinct - 入力を集合として扱う
- group_key_pairs* - グループ化キーの一覧
  - 列ID * 2
その他の特性
- 常に第一入力リレーションのみを出力する

notes:

limit は「グループごとに行数を制限」という拡張を行っている

DML系

DML系演算子は、リレーションの出力を行わない関係演算子である。

emit ~ 入力リレーションの内容を問合せの結果として出力する。

共通構造: なし
入力数: 1
列の公開: -
プロパティ
- columns+ - 出力する列の一覧
  - column - 列ID
  - label? - 列のラベル
その他の特性
- 入力がソート済みリレーションである場合、リレーション内の行の順序を保ったまま出力を行う

write ~ 入力リレーションの内容を利用し、対象テーブルの内容を変更する。

共通構造: なし
入力数: 1
列の公開: -
プロパティ
- operator_kind - 書き込みの種類
  - insert - 対象の行が存在しなければ追加し、存在したらエラー
  - update - 対象の行が存在すれば変更し、存在しなければエラー
  - delete - 対象の行が存在すれば削除し、存在しなければ無視
  - insert_or_update - 対象の行が存在しなければ追加し、存在したら変更
- destination - 対象のインデックス識別子
- keys* - 出力先を特定するための列一覧
  - source - 入力リレーション上の列
  - destination - 出力先テーブル上の列
- columns* - 出力する列の一覧
  - source - 入力リレーション上の列
  - destination - 出力先テーブル上の列
その他の特性
- destination に指定するインデックスは、 keys で指定するキーに対して一意なエントリを持つようなインデックスでなければならない
  - 標準的にはプライマリキーをキーとするようなインデックス
    - ただし、テーブル上の OID が判明している場合、必ずしもプライマリキーを利用しなくてもよい
  - 必ずしも対象がプライマリインデックスである必要はない
- operator_kind が insert または insert_or_update の場合、 columns.destination で対象テーブルの指定可能なすべての列を指定しなければならない
- operator_kind が update で primary key を変更する場合、 keys には 変更前 の行を特定可能な入力リレーション上の列を指定しなければならない
- operator_kind が delete の場合、 columns.destination は指定できない
- インデックスの更新は同演算子の実装以降に任せる
- TBD: iterator-based な単純なケースの delete が少し迂遠になる

その他の演算子

その他、分類が難しかった演算子を紹介する。

values ~ 二次元のスカラー式のリストからリレーションを構築する。

共通構造: なし
入力数: 0
列の公開: すべて
プロパティ
- columns* - 出力リレーション上の列ID
- rows* - 出力するリレーションの行一覧
  - elements* - 行を構成する値の一覧
その他の特性
- columns[i] と rows[*].elements[i] が対応付けられる
- columns と rows.elements の個数は一致していなければならない
備考
- 行値を利用したい場合、 project と組み合わせる
  - 最適化の観点から、行構築子を利用していない
- join_values は存在せず、 join_find や join_scan のブロードキャスト利用で対応する

union_relation (intermediate::union) ~ 2つのリレーションの（多重集合における）和を出力する。

共通構造: なし
入力数: 2
列の公開: 定義のみ
プロパティ
- columns+ - 出力する列の一覧
  - left? - 第一入力リレーション上の列ID
  - right? - 第二入力リレーション上の列ID
  - destination - 出力リレーション上の列ID
- quantifier - 量子化の種類
  - all - 入力を多重集合として扱う
  - distinct - 入力を集合として扱い、集合における和を計算する
その他の特性
- 下流の演算子では、 columns.destination で指定した列のみが利用可能
- OUTER UNION や UNION JOIN は columns.{left, right} を空にすることで実現
- quantifier=distinct の場合、 columns.{left, right} はいずれも空であってはならない
- 行IDを再生成してもよい (しなくてもよいケースがありそう)

escape (intermediate::escape) ~ 列定義を退避する。

共通構造: なし
入力数: 1
列の公開: 定義のみ
プロパティ
- columns+ - 再定義する列の一覧
  - source - 再定義する列ID
  - destination - 再定義後の列ID
その他の特性
- 行IDを再生成する

notes:

escape は自己結合を行う際に同一の列IDが出現し、かつそれぞれに束縛された値が異なる可能性があるため
- ステップ実行計画では仕様上そのような構造をとりえない
TBD: 再帰問合せ関連はまだ入れていない

ステップ実行計画

ステップ実行計画において、演算子はステップグラフ上の「プロセス」内に出現する。プロセスはリレーションを何らかの方式で分割し、分割された領域ごとに待ち合わせなしに独立して処理できる必要がある。また、処理に待ち合わせが必要な場合は、ステップグラフ上の「エクスチェンジ」で行うことになる。

ステップ実行計画における演算子は、中間実行計画における演算子と比べて以下が変更されている。

一階のリレーションだけでなく、二階のリレーション（グループ表）を入力にとる演算子が存在する
- グループ表を取り入れることで、リレーションの分割単位を常に「行」にできる
エクスチェンジを入出力とする演算子が追加されている
中間実行計画で単一の演算子で実現できていた操作のいくつかは、ステップ実行計画ではエクスチェンジといくつかの演算子の組で表現される
- プロセスの特性上、待ち合わせを含む処理を演算子内で行えない
broadcast エクスチェンジ経由の入力は、演算子の入力として取り扱わない

演算子の入力

ステップ実行計画のプロセス内に出現する演算子は、入力として単一のリレーションか、または複数のリレーションの組を取り扱う。また、それぞれの演算子は入力にとれるリレーションの階があらかじめ定められている。

各演算子の入力は、以下のいずれかでなければならない。

一階のリレーション
グループ表
複数のグループ表をグループ化キーで結合したもの (以下、グループ結合表)

グループ結合表は複雑であるため、以下に例を示す。

以下のリレーション U, V について考える。

U = [(A, 1), (B, 2), (B, 3)]
V = [(A, 4), (A, 5), (C, 6)]

上記のリレーションについて、それぞれの第一列をグループ化キーとしてグループ化すると、それぞれのグループ表 G は次のようになる。

G(U) = {[(A, 1)], [(B, 2), (B, 3)]}
G(V) = {[(A, 4), (A, 5)], [(C, 6)]}

上記に対し、それぞれのグループ表をグループ化キーで結合（完全外結合）する。

G(U) |X| G(V) = {
  ([(A, 1)], [(A, 4), (A, 5)]),
  ([(B, 2), (B, 3)], []),
  ([], [(C, 6)])
}

上記のように2個のグループ表を結合したリレーションを、便宜上「2項のグループ結合表」とよぶことにする。このリレーションの各行は、 G(U) と G(V) からグループを一つ取り出したものを各列に持ち、かつそれぞれのグループは同じグループキーを持っている。このような操作を co-group とよび、ステップ実行計画では shuffle エクスチェンジでグループを作成したのち、 take_cogroup で結合することで同じ結果を得られる。

上記を入力にとる演算子は、以下をそれぞれ入力にとって処理することになる。

([(A, 1)], [(A, 4), (A, 5)])
([(B, 2), (B, 3)], [])
([], [(C, 6)])

たとえば、演算子が左外結合で不等価条件がないとすると、グループごとに以下を出力する。

([(A, 1)], [(A, 4), (A, 5)])
- (A, 1, A, 4)
- (A, 1, A, 5)
([(B, 2), (B, 3)], [])
- (B, 2, NULL, NULL)
- (B, 3, NULL, NULL)
([], [(C, 6)])
- なし

上記をグループ化した際のグループ化キーがそれぞれ k という列名だったとすると、上記の結果は SELECT * FROM U LEFT OUTER JOIN V ON U.k = V.k と等しくなる。

notes:

演算子の入力に「複数の一階のリレーションを結合したもの」がないのは、それは別の処理の組み合わせで実現できるためである
三階以上のリレーションには今のところ対応していない
- TBD: キューブ演算の効率化には使えそうだが、ほかにあるか？
co-group は、等価完全外結合を「途中で止めた」処理である
- shuffle 単体ではグループ化までだが、それぞれのグループをグループのままソートマージ結合することでこの状態を作れる
- 続きの処理を行えば、2項のあらゆる結合処理をグループの組ごとに並列計算できる
- 例で紹介した co-group を利用した結合処理は、 join_group の演算子で実現できる

演算子の出力

ステップ実行計画のプロセス内に出現する演算子は、いくつかの例外を除き、高々1つの一階のリレーションを出力する。

上記に沿わない演算子は以下のとおりである。

take_group
- 二階のリレーション（グループ表）を出力する
take_cogroup
- 二階のリレーション（グループ結合表）を出力する
buffer
- 2つ以上のリレーションを出力する

エクスチェンジの挙動

ステップ実行計画において、エクスチェンジは関係演算子ではなく、あくまでプロセス間のデータ交換を行うことを主目的にしている。ただし、それぞれのエクスチェンジの機能は単にデータ交換のみにとどまらず、それぞれ以下のような処理を行う。

forward エクスチェンジ
- 入力された1個以上のリレーションの多重集合和を、一階のリレーションとして出力する
  - 全体の行数を制限することもできる
shuffle エクスチェンジ
- 入力された1個以上のリレーションの多重集合和に対し、指定されたキーでグループ化したグループ表を出力する
  - 各グループ内の行を指定の方法でソートすることもできる
  - グループごとの行数を制限することもできる
broadcast エクスチェンジ
- 入力された1個以上のリレーションの多重集合和を出力する
  - 出力されたリレーションは関係演算子の明示的な入力としては取り扱わず、任意の処理を施した結果を演算子から直接参照できる

ステップ実行計画における演算子

本章では、ステップ実行計画上のみで出現する演算子について紹介する。

なお、それぞれの演算子の概要を一望することを目的にしており、厳密な定義は行わない。

以下の形式で、それぞれの関係演算子の構造を紹介する。

演算種 ~ 処理概要

共通構造: 継承する共通構造の一覧
入力形式: 一階のリレーション、グループ表、N項のグループ結合表のいずれか
列の公開: 下流への列の公開方式 (すべて, 一部入力と定義のみ, 定義のみ)
プロパティ
- プロパティ名 - プロパティの概要
その他の特性
- 備考等

なお、「共通構造」は中間実行計画における演算子で定義したものを参照する。

ステップ実行計画で利用可能な演算子

ステップ実行計画では、中間実行計画における以下の演算子を利用可能である。

find
scan
join_find
join_scan
project
filter
buffer
identify
emit
write
values

上記はいずれも、一階のリレーションを入力にとり、かつ broadcast エクスチェンジを必要としない。

ステップ実行計画で利用不可能な演算子

ステップ実行計画では、以下の演算子を利用できない。

join_relation -> shuffle エクスチェンジ + join_group (またはその他の join_* 系演算子)
aggregate_relation -> shuffle エクスチェンジ + aggregate_group
distinct_relation -> shuffle エクスチェンジ + flatten_group
limit_relation -> forward エクスチェンジ、または shuffle エクスチェンジ + flatten_group
intersection_relation -> shuffle エクスチェンジ + intersection_group
difference_relation -> shuffle エクスチェンジ + difference_group
union_relation -> forward エクスチェンジ、または shuffle エクスチェンジ + flatten_group
escape -> ステップ実行計画では不要

上記はいずれも、その処理の一部または全部をエクスチェンジで行うべき演算子である。

一部の挙動が変化する演算子

以下の演算子は、中間実行計画とステップ実行計画で一部の挙動が変化する。

join_find : 外部リレーションに broadcast エクスチェンジを指定できる
join_scan : 外部リレーションに broadcast エクスチェンジを指定できる

グループ系 (ステップ実行計画)

グループ系演算子は、二階のリレーションを入力にとる関係演算子である。

join_group (step::join) ~ グループ単位でネステッドループ結合を行う演算子。

共通構造: join
入力形式: 二項以上 のグループ結合表
列の公開: すべて
プロパティ
- condition - 結合条件 (等価結合条件を除く)
その他の特性
- 実際にはネステッドループ以外を行ってもよい
- 2グループを入力にとる場合、第1グループを左項, 第2グループを右項とした結合を行う
- 3グループ以上を入力にとる場合、結合の種類ごとに以下のような挙動となる:
  
  inner ~ すべてのグループが空でなく、かつ結合条件があればそれを満たす場合のみ、結合に成功する。出力は、各項のグループに出現する列がすべて含まれる。
  
  left_outer ~ 第1項のグループが空でない場合のみ結合に成功する。出力は、各項のグループに出現する列がすべて含まれる。第2項以降のグループが空である場合、出力の対応する列は特殊値が設定される。または、結合条件を満たさない場合、第2項以降のすべての列は特殊値が設定される。
  
  full_outer ~ 常に結合に成功する。出力は、各項のグループに出現する列がすべて含まれる。いずれかのグループが空である場合、出力の対応する列は特殊値が設定される。結合条件は 指定できない 。
  
  semi ~ すべてのグループが空でなく、かつ結合条件があればそれを満たす場合のみ、結合に成功する。出力する列は、第一項のグループのもののみ。
  
  anti ~ 第1項のグループが空でなく、かつ { 第2項以降のいずれかのグループが空であるか、または結合条件があればそれを満たさない } 場合のみ、結合に成功する。出力する列は、第一項のグループのもののみ。

aggregate_group (step::aggregate) ~ グループごとに集計を行う。

共通構造: なし
入力形式: グループ表
列の公開: グループ化キーおよび定義のみ
プロパティ
- columns+ - 出力する列の一覧
  - function - 集約関数の関数ID
  - arguments* - 集約対象の列ID
  - destination - 出力先の列ID
その他の特性
- 行IDを再生成する
- リレーション全体を集計している場合、「0件のグループ」に対する処理が必要になる
- 下流の演算子から利用可能な列は、 columns.destination と、入力グループのグループ化キーである

intersection_group (step::intersection) ~ 2組のグループごとに、第一グループの行数を第二グループの行数に制限する。

共通構造: なし
入力形式: 二項のグループ結合表
列の公開: すべて
プロパティ
- なし
その他の特性
- 常に第一入力リレーションのみを出力する

difference_group (step::difference) ~ 2組のグループごとに、第一グループから第二グループの行数分だけ除去する。

共通構造: なし
入力形式: 二項のグループ結合表
列の公開: すべて
プロパティ
- なし
その他の特性
- 常に第一入力リレーションのみを出力する

flatten_group (step::flatten) ~ グループ表を1階のリレーションとして出力する。

共通構造: なし
入力形式: グループ表
列の公開: すべて
プロパティ
- なし
その他の特性
- 入力にとったグループ表がソート済みグループ表であり、かつそのグループ化キーが空である場合、この演算はソート済みリレーションを出力する
  - 各行の順序は、グループ表におけるソート順と一致する

notes:

limit, distinct は基本的にエクスチェンジ内で行数の制限を行い、特別な演算子を用意しない
flatten_group は二階のリレーションを平坦化して一回のリレーションを出力する
- distinct などが shuffle エクスチェンジ内で完結するようになったときに、代わりに配置されることを想定している

エクスチェンジ系

エクスチェンジ系演算子は、プロセスの入出力を行う関係演算子である。いずれもステップグラフにおける上流や下流のエクスチェンジのデータを取り扱う。

take_flat (step::take_flat) ~ forward エクスチェンジから次の入力を取り出す。

共通構造: なし
入力形式: (入力なし)
列の公開: すべて
プロパティ
- source - 対象のエクスチェンジ識別子
- columns* - 定義する列の一覧
  - source - 入力にとるエクスチェンジ上の列
  - destination - 出力するリレーションの列
その他の特性
- プロセス内に take_* は一つしか存在しない
- columns は入力にとるエクスチェンジの列をすべて包含する必要はない

take_group (step::take_group) ~ 単一の shuffle エクスチェンジから次の入力を取り出す。

共通構造: なし
入力形式: (入力なし)
列の公開: すべて
プロパティ
- source - 対象のエクスチェンジ識別子
- columns* - 定義する列の一覧
  - source - 入力にとるエクスチェンジ上の列
  - destination - 出力するリレーションの列
その他の特性
- プロセス内に take_* は一つしか存在しない
- グループ表を出力する
- columns は入力にとるエクスチェンジの列をすべて包含する必要はない

take_cogroup (step::take_cogroup) ~ 2個以上の shuffle エクスチェンジから次の入力を取り出し、結合する。

共通構造: なし
入力形式: (入力なし)
列の公開: すべて
プロパティ
- groups+ - 出力するグループの一覧
  - source - このグループに関連付けられたエクスチェンジ識別子
  - columns* - 定義する列の一覧
    - source - 入力にとるエクスチェンジ上の列
    - destination - 出力するリレーションの列
  - mandatory - 必須グループかどうか
    - true - このグループが空である場合、当該キーに対する行をスキップする
    - false - このグループが空である場合、当該キーにおけるこのグループは空のまま下流に渡される
その他の特性
- プロセス内に take_* は一つしか存在しない
- groups で定義された件数だけのグループ結合表を出力する
- グループ結合に必要なキー情報は、それぞれ groups.source 経由で取得する
- groups.columns は入力にとるエクスチェンジの列をすべて包含する必要はない

offer (step::offer) ~ エクスチェンジにプロセスの結果を出力する。

共通構造: なし
入力形式: 一階のリレーション
列の公開: -
プロパティ
- destination - 出力先のエクスチェンジ識別子
- columns* - 定義する列の一覧
  - source - 入力リレーション上の列
  - destination - 対象のエクスチェンジ上の列
その他の特性
- destination は対象のエクスチェンジのすべての一部でもよい
  - 指定しなかったエクスチェンジ上の列は特殊値が設定される (INSERT 文で未指定の列がある場合に類似)

notes:

broadcast エクスチェンジに対応する take_* は存在しない

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

relational-operators.md

relational-operators.md

SQL実行計画表現における関係演算子

この文書について