SQLリクエストの構文解析ツリー表記
最適化ルーチンでは、多くのコスト ベースの最適化ルーチンのように、SQLリクエストが構文解析ツリーとして内部的に表記されます。構文解析ツリーの基礎となる構成要素のことをルートと言います。ツリーの各ノードには、0個以上のサブツリーがあります。
構文解析ツリーの構成要素は、有効な式を構成するために使用できる、テキスト文字列、数理演算子、区切り文字、およびその他のトークンです。これらの構成要素はSQLリクエストの構成ブロックであり、構文解析ツリーのノードとリーフを形成します。
ここに示す構文解析ツリーは上にルート、下にリーフがあるので、後付けという表現は、そうではない場合と比べて、式がプロセスの中でより早く評価されることになります。ツリーの各ノードはデータベース操作を表わし、そのサブツリーはこの操作のオペランドです。これは普通は何らかの種類の式ですが、テーブルなど、さまざまなデータベース オブジェクトである可能性もあります。
次の図は、1つのノードと2つのリーフを持つ最小の構文解析ツリーです。
例で使用されているテーブル
次の問合わせの部分は、構文解析ツリーを使用してどのように表記して最適化できるかを考えてください。リクエストの例に使用されるテーブルは、次のように定義されます。
part_num | description | mfg_name | mfg_part_num |
---|---|---|---|
PK | FK | ||
PI |
part_num | mfg_name | mfg_address | mfg_city |
---|---|---|---|
PK | |||
PI |
cust_num | cust_name | cust_address | cust_city |
---|---|---|---|
PK | |||
PI |
order_num | cust_name | mfg_part_num | order_date |
---|---|---|---|
PK | FK | ||
PI |
SQLリクエストの例
次のSQLリクエストの例を考えてください。
SELECT part_num, description, mfg_name, mfg_part_num, cust_name, cust_address, cust_num, order_date FROM order INNER JOIN customer INNER JOIN parts WHERE customer.cust_num = order.cust_num AND parts.mfg_part_num = order.mfg_part_num AND order_date < DATE ’2001-01-01’ ;
リクエストの構文解析ツリーへの初期変換は、構文解析ルーチン(構文解析ルーチンを参照)によってリクエスト テキストの構文エラーが検査された後に実行されます。クエリー リライトは意味解釈ルーチンからの入力として処理された構文解析ツリーを受け取り、書き換えられている一方で意味的に同等の構文解析ツリーを最適化ルーチンへの出力として生成します。このリクエスト ツリーは、元のリクエスト テキストを単に構文解析ツリー表記にしただけです。
最適化ルーチンは、結果の構文解析ツリーを生成ルーチンに渡す前に、最適な計画を決定し、該当する場合には、テーブル結合の順序と結合計画を決定することによって、ツリーをさらに変換します。
この時点で、元のリクエスト ツリーは破棄されていて、リクエストを実行するための命令を含む新しい構文解析ツリーに置き換えられています。この構文解析ツリーが操作ツリーになります。これは、このツリーのテキスト形式であり、ホワイト ツリー(EXPLAINを実行するときに、最適化ルーチンがEXPLAINテキストを生成するために使用するツリー)とも呼ばれます。EXPLAINテキストが出力用に生成される前に、最適化ルーチンがホワイト ツリーに対して見積もりをしない操作に関して、個別のサブシステムが追加のコスト計算情報を追加することに注意してください。
最適化ルーチンが、次のような簡略化された構文解析ツリーをクエリー リライトから渡されるとします。このツリーは、実際には簡単なSynTreeの例ですが、注釈のあるResTreeでは、説明に役立つものを追加するのでない限り、説明を複雑にする必要はありません。
図では、直積演算子をXというシンボルで表記しています。
最適化の最初のステップは、述部(代数的に、リレーショナルな選択操作、または制限操作として機能する)を整理して、それらのうち3つすべてをできるだけツリーの下に後付けすることです。この目的は、取出しプロセスの中でできるだけ早く、すべてのSELECTIONおよびPROJECTION演算を実行することです。SQLでは、リレーショナルSELECT演算子は、応答セットの行を制限しているのでWHERE句に類似しており、SQL SELECT文のSELECT句は、応答セットで示される列数を制限しているので代数のPROJECT演算子に類似しています。
このような述部を後付けするときに関係するプロセスを、次のプロセス テーブルに示しています。書き換えの演算の中には、さまざまな論理ルールを呼び出すことによって調整されるものもあります。そのようなルールを詳しく知っていなくても構いません。表記から理解する必要のある要点は、プロセスの実行方法の正確な詳細ではなく、一般の全体的なプロセスです。
プロセスの最初のセットは、クエリー リライトによって実行されます。
- 複合AND条件を個別の述部に分割します。結果は、次のような2つのSELECT演算になります。
SELECT customer.cust_num = order.cust_num SELECT parts.mfg_part_num = order.mfg_part_num
- 逆の方法として、SELECTION order.order_date < 2001-01-01は、ツリーの一番下に付け、orderおよびcustomerテーブルのPROJECTIONの下に後付けすることができます。
order_dateがorderテーブルだけの属性であるために可能になるこのような一連の代数変換は、次のようになります。
- 次の述部を開始します。
SELECT order_date < 2001-01-01((order X customer) X parts)
- 次の形式に変換します。
SELECT (order_date < 2001-01-01(order X customer)) X parts
- さらに次の形式に変換します。
SELECT ((order_date < 2001-01-01(order)) X customer) X parts
これは、述部が変換できる限り続き、構文解析ツリーに後付けできる限り下に移動します。
- 次の述部を開始します。
- 最適化ルーチンは、次のSELECT演算を調べ、構文解析ツリーのさらに下に後付けできるかどうかを確認します。
SELECT parts.mfg_part_num = order.mfg_part_num
このSELECTIONには、partsテーブルからの1列と、別のテーブル(order)からの列が含まれているため、すでに決定されている位置から先へはツリーに後付けできません。
- 最適化ルーチンは、次のSELECT演算を調べ、構文解析ツリーのさらに下に後付けできるかどうかを判別します。
SELECT customer.cust_num = order.cust_num
この式を後付けして、積に適用できます。order_date < 2001-01-01 (order) X customer
SELECTIONの結果は適用される式から属性を累積しているため、order.cust_numはSELECT date < 2001-01-01(order)の属性になります。
- 最適化ルーチンは、元の構文解析ツリーにある2つのPROJECTION演算を、1つのPROJECTION part_numにまとめます。
この結合後の構文解析ツリーの構造は、次の図のようになります。
- 構文解析ツリーのこの中間ステップでは、SELECTおよびPROJECT演算の換算ルールを適用し、次の一連の演算でPROJECT PartNumとSELECT customer.custnum = order.custnumを置き換えることにより、さらに最適化することができます。
PROJECT parts.part_num SELECT parts.mfg_part_num = order.mfg_part_num PROJECT parts.part_num, parts.mfg_part_num, order.mfg_part_num
- 直積を使用したPROJECTIONの換算ルールを使用し、段階6の最後のPROJECTIONを次のPROJECTIONと置き換えます。
PROJECT part_num, parts.mfg_part_num
- 同様に、PROJECTのorder.mfgpartnumを、2つの直積のうち、より高い左オペランドに適用します。さらに、このPROJECTIONは、すぐ下のSELECT演算(customer.custnum = order.custnum)と相互作用し、次の一連の代数演算の積を出します。
PROJECT order.mfg_part_num SELECT customer.cust_num = order.cust_num PROJECT order.mfg_part_num, customer.cust_num, order.cust_num
- ステップ8の最後の式は、UNION演算を使用したPROJECTIONの換算によって直積をバイパスし、SELECTION演算SELECT order.orderdate < 01-01-2001による換算も部分的にバイパスします。
- 最適化ルーチンは、PROJECTION用語に関して、結果の式PROJECT order.mfg_part_num, order.custnum, orderdateは冗長であると判断するため、クエリーの中でさらに考慮されることはありません。
これらすべての変換作業で変換された構文解析ツリーは、次の図に示されています。
この2つの直積演算は、より上位のSELECTIONと組み合わせられるときに、等結合と等しくなります("higher"とは、演算がクエリーの実行の後の方で行なわれることを意味します)。図では、演算子が境界線で分けられてグループ化されていることに注意してください。構文解析ツリーの各境界セグメントは、大まかに言ってAMPワーカー タスクに対応するものです。