この記事では主に、相関サブクエリとは何か、相関サブクエリを通常のセマンティクスを持つ SQL クエリに書き換える方法について説明します。 背景の紹介では、一般的な相関サブクエリのセマンティクス、相関サブクエリ構文の利点、およびデータベース システムへの実行の課題について説明します。第2章では、関連付けられたサブクエリを通常のクエリの形に書き換える、つまり関連付けを解除する方法を中心に紹介します。第 3 章では、割り当て解除における最適化手法について紹介します。 1. 背景相関サブクエリは、外部クエリに関連付けられたサブクエリです。具体的には、外部クエリに含まれる列がこのサブクエリで使用されます。 関連付けられた列を柔軟に使用できるため、SQL クエリをサブクエリとして記述すると、SQL が大幅に簡素化され、SQL クエリのセマンティクスが理解しやすくなります。以下では、これを説明するために tpch スキーマを使用したいくつかの例を示します。 tpch スキーマは、以下に示すように、顧客テーブル、注文テーブル、明細項目テーブルなどを含む典型的な注文システム データベースです。 「注文をしたことがないすべての顧客の情報」を照会したい場合は、関連するサブクエリをフィルタリング条件として使用できます。相関サブクエリを使用して記述された SQL は次のとおりです。ここで、not exists サブクエリは列外の列 c_custkey を使用していることがわかります。 -- 一度も注文したことのないすべての顧客に関する情報
上記の形式で記述されていない場合は、まず顧客テーブルと注文テーブルを左結合することを検討し、結合されていない行を除外する必要があります。同時に、元々 null であった行が結合されたままになるように、順序のすべての行をマークする必要もあります。クエリSQLは次のとおりです。 -- 一度も注文したことのないすべての顧客に関する情報
この単純な例から、相関サブクエリを使用すると SQL の記述の難しさが軽減され、読みやすさが向上することがわかります。 関連付けられた列を EXISTS/IN サブクエリで使用するだけでなく、関連付けられたサブクエリをフィルタリング条件に必要な値として WHERE に表示することもできます。たとえば、tpch q17 では、フィルタリング条件として集計値を見つけるためにサブクエリが使用されます。
相関サブクエリは、where 内だけでなく、選択リスト内など、単一行 (スカラー) が許可される場所であればどこにでも出現できます。顧客情報をまとめたレポートを作成し、各顧客の合計注文金額を照会する必要がある場合は、相関サブクエリを含む次の SQL を使用できます。 -- 顧客とそれに応じた総消費量
より複雑な例として、各顧客と特定の日付までに署名された注文の合計金額を照会します。相関サブクエリを使用するには、次のようにいくつかの小さな変更を加えるだけです。
これらの例を読んだ後、相関サブクエリを使用することでもたらされる利便性を誰もがすでに実感していると思います。しかし同時に、相関サブクエリは実行上の課題ももたらします。関連する結果 (サブクエリの出力) の値を計算するには、反復実行が必要です。 前述の tpch 17 を例に挙げます。
ここでのサブクエリ部分では、外部クエリの列 p.partkey を使用します。
外部クエリの列オプティマイザーは、このクエリを次に示すように論理ツリーとして表します。 データベース システムが論理ツリーの表示をサポートしていない場合は、explain コマンドを使用して物理プランを表示できます。一般的な出力は次のとおりです。
外部クエリとサブクエリを接続するこの演算子を CorrelatedJoin (横方向結合、依存結合などとも呼ばれます) と呼びます。左側のサブツリーは外部クエリ (入力) と呼ばれ、右側のサブツリーはサブクエリと呼ばれます。サブクエリに表示される外側の列は相関列と呼ばれます。この例では、相関列は p.partkey です。 例の対応する論理プランと関連定義を次の図に示します。 Explain の戻り結果では、行 6 ~ 8 が外部クエリ、行 9 ~ 13 がサブクエリ、関連部分はサブクエリの行 12 のフィルターです。 この演算子の出力は、反復実行の結果と同等です。つまり、左側のサブツリー内の関連する列の各行の値が計算のために右側のサブツリーに取り込まれ、結果の行が返されます。これは、サブクエリをユーザー定義関数 (UDF) として扱うことに多少似ており、外部クエリの関連付けられた列の値が、この UDF の入力パラメータとして使用されます。サブクエリは決定論的である必要があることに注意してください。つまり、同じ値を持つ関連列の場合、サブクエリが実行されるたびに返される結果は決定論的である必要があります。 上記の例では、外部クエリに p.partkey 値が 25 の行がある場合、この行に対応する correlatedjoin の出力は次のクエリの結果になります。 -- p.partkey = 25の場合、対応するサブクエリは
計算結果が空のセットの場合は、null の行が返されることに注意してください。実行中にサブクエリが複数行の結果を返す場合は、ランタイム エラーが報告されます。論理プランでは、enforcesinglerow ノードを使用して制約します。 上記の紹介から、CorrelatedJoin 演算子は、ロジック ツリーの以前のトップダウン実行モードを破棄することがわかります。通常のロジックツリーはリーフノードからルートノードまで実行されますが、CorreltedJoin の右サブツリーは左サブツリーの行の値で繰り返し実行されます。 correlatedjoinnode の出力は、外部クエリの上にある追加の列ですが、この反復実行の複雑さは、外部クエリをサブクエリと相関させる前にツリーの一部をクロス結合する複雑さと同じであることがわかります。 同時に、この反復実行方法は、分散データベース システムにとって大きな課題となります。実行中のスケジュールのロジックを変更する必要があるためです。そして、この実行方法が結果をキャッシュしない場合、多くの繰り返し結果計算が実行されることがわかります。 従来のオプティマイザーの最適化ルールでは、Correlatedjoin ノードは特に処理されません。相関サブクエリの反復形式をサポートするために、Correlatedjoin はオプティマイザーの初期段階で同等に変換されます。変換後、論理ツリーは結合や集計などの一般的な演算子を使用して相関サブクエリの結果を計算します。このプロセスは、非相関/非ネスト化と呼ばれます。次の章では、主に相関関係を解除する一般的な方法を紹介します。 相関関係を解く2つの一般的な方法 便宜上、この章では、値のリストを出力する相関サブクエリであるスカラー相関サブクエリについてのみ説明します。 関連付けを解除する方法について説明する前に、関連付けられたサブクエリの出力の次の特性をまとめてみましょう。
関連付けを解除するための鍵は、サブクエリが対応する外部クエリの行の値を取得するようにすることです。 計画的には、相関結合演算子は、関連する部分の右下に配置されます。相関結合演算子の左側のサブツリーと右側のサブツリーに関連付けられた列がない場合、相関結合演算子を結合演算子に変換できます。このように、サブクエリは外部クエリと結合して関連する列の値を取得し、上から下に向かって計算して元の計算方法に戻すことができます。次の図に示すように、rest サブクエリは関連付けが生成される前のサブクエリ部分です。相関結合を関連パーツの下に押し込むと、通常の結合に変換できます。 相関結合によってプッシュされるすべての演算子は、同等性を維持するために書き直す必要があります (上記の例では、サブクエリはサブクエリ'になります)。 1 プッシュダウンルール 論文「サブクエリと集計の直交最適化」[2]では、相関結合演算子を他の演算子(フィルター、プロジェクト、集計、ユニオンなど)にプッシュダウンするための同等の変換規則が示されています。ただし、この論文の correlatedjoin 演算子は、内部結合 (論文では と呼ばれています) と同様に、外部クエリの行数をフィルター処理します。ここでは、左結合に似た、より一般的な相関結合 (論文では と呼ばれています) について説明し、外部クエリの行数がフィルタリングされないようにするために何を書き換える必要があるかについて説明します。 スペースの制限により、フィルター、プロジェクト、および集計演算子にプッシュダウンされた同等のルールのみを紹介します。 簡潔にするために、論理ツリーからenforcesinglerowを削除しました。 変換1: 関連付けがない場合に参加に変換する 前の記事で述べたように、相関結合演算子の左のサブツリーは入力であり、右のサブツリーはサブクエリです。相関結合の左サブツリーと右サブツリーが関連していない場合、サブクエリの結果は外部クエリの各行に対して同じになります。 相関結合を、結合条件のない通常の leftjoin 演算子に変換できます。 注: 結合セマンティクスが correlatedjoin と同じであることを確認するには (入力拡張を引き起こさずに)、サブクエリに enforcesinglerow を追加する必要があります。 変換2: 単純な結合条件を結合に変換する 相関結合の右側のサブツリーの最上位ノードが相関フィルターであり、その下に相関がない場合、フィルターを左側の結合の条件に直接追加することができ、これはフィルター リフトとも呼ばれます。以下のように表示されます。 変換3 フィルターを押し下げる この論文では、correlatedjoin* をフィルターに直接プッシュすることができます。相関結合をプッシュダウンする必要がある場合は、フィルターを case when を含むプロジェクトに書き換える必要があります。サブクエリ行がフィルタ条件を満たさない場合は、null が出力されます。 変革4 プロジェクトを通じて推進 プロジェクトを通じて相関結合をプッシュするには、入力の出力列をプロジェクトに追加する必要があります。 変換5 集約によるプッシュダウン 相関結合が group by による集計にプッシュダウンされる場合、集計を書き換える必要があります。 外部クエリのすべての列を集計のグループ化列に追加するように書き直します。ここでは、外部クエリにキーが必要です。そうでない場合は、一時キーを生成する必要があります。これを生成できる演算子は、図のassignuniqueid演算子です。 集計がグローバルな場合は、追加の処理が必要になります。以下のように表示されます。 相関結合がグローバル集計にプッシュダウンされる場合、入力列 (およびキー) をグループ化列として集計に追加する必要があります。このプッシュダウン ルールには前提条件も必要です。つまり、集計関数は agg()=agg(null) というプロパティを満たす必要があります。つまり、集計関数は空のセットと null に対して同じ結果を計算する必要があります。 注:MySQLおよびAnalyticDB for MySQL(Alibaba Cloudが独自に開発したMySQL構文と互換性のあるクラウドネイティブデータウェアハウス[1]、以下ADBと略す)の構文では、sum、avgなどはこの機能を満たしていません。空セットの平均は 0 であり、null 値を含むセットの平均は 0 ではなく null です。そのため、サブクエリ内の各行をマークし、空セットに対して特別な処理を実行する必要がありますが、ここでは説明しません。 論文「サブクエリと集計の直交最適化」[2]では、相関結合を通常の結合に変換できるようになるまで、上記のルールを繰り返し適用して相関結合をプッシュダウンします。 前の tpch q17 の例では、最初に相関結合をサブクエリのプロジェクトにプッシュし、クエリは次のようになります。 次に、この agg をプッシュダウンして、次のようにこの agg を書き換えます。 ここではavg()!=avg(null)は無視します。このような状況を考慮すると、サブクエリのすべての行をマークし、相関結合後に、サブクエリの結果とマーク値に基づいて空のセットに対して特別な処理を実行する必要があります(マークされた行の値を null から 0 に変更します)。興味のある読者は、次のシートの q17 の最終計画を参照してください。 次に、前のルール 2 を直接呼び出して、このフィルターを発生させます。この方法では、クエリは関連付けのない通常のクエリになります。 2. 結果の再利用 前のセクションで述べたことを思い出すと、サブクエリのクエリ結果は、各行の関連する列の値を取り込むことによって計算されます。同じ値を持つ関連列をサブクエリに持ち込むことで計算された結果がまったく同じであることは明らかです。上記の例では、同じ p.partkey に対して、correlatedjoin によって出力されるサブクエリの結果は同じになります。下の図に示すように、外部クエリのパートキーが 25 の場合、生成される関連サブクエリはまったく同じなので、結果も当然同じになります。 ニューマンの2015年の論文「Unnesting Arbitrary Queries」[3]では、まず外部クエリの関連列に異なる値を取り、次に関連列に基づいて相関結合と元の外部クエリによって返された値に対して左結合を実行する方法が紹介されています(次の図を参照)。 ここでの not distinctive join の条件は、MySQL の <=> に相当します。 null<=>null の結果は true であり、それらを結合できます。 下の図に示すように、外部クエリの関連列の部分キーは最初に区別され、次にサブクエリの計算結果が取り込まれ、最後に対応する結果が結合を通じて元の外部クエリに接続されます。 上記の変換を実行すると、新しい入力の関連する列は常に異なると想定できます。 correlatedjoin* 演算子を使用すると、入力列をフィルター処理できるようになりました。同じ列に対して繰り返しサブクエリ計算を実行しないことに加えて、次の 2 つの主な利点があります。
上記の変換を実行した後、以前の同等のプッシュダウン ルールを適用し、correlatedjoin* を左と右のサブツリーが関連しない場所までプッシュダウンして、内部結合として書き換えることができます。 アンネスト任意クエリ[3]方式に従って相関除去を実行する場合、入力結果の一部を再利用する必要があり、この再利用には実行エンジンのサポートが必要です。システムが再利用をサポートしていない場合は、入力サブツリーを 2 回実行する必要があることに注意してください (以下を参照)。このとき、このサブツリーの入力結果は決定論的である必要があります。そうでない場合、このメソッドを使用して関連付けを解除することはできません。 3重相関サブクエリの最適化 ADB オプティマイザでは、各変換ルールに従って論理プランがマッチングされ、変換されます。つまり、関連付けが解決された後は、解決によって生成されたプランの効率を心配する必要がなく、後続の最適化ルールに直接引き渡すことができます。しかし、現実はそれほど良くありません。後続のルールが完全ではなく、外部クエリとサブクエリの関係が分離後に失われるからです。切り離す際には、計画を可能な限り最適化したいと考えています。 1 存在する/中にある/フィルター関連サブクエリ 前の章では、簡潔にするために、スカラー サブクエリについてのみ説明しました。 exists/in などのサブクエリはスカラー サブクエリとして書き換えることができるためです。たとえば、count(*) > 0 として書き換えが存在する しかし、サブクエリによって返された結果を使用して外部クエリの行をフィルター処理すると、実際には関連付け解除プロセス全体が簡素化されることがわかります。そのため、exists/in などのサブクエリに対して特別な処理を実行し、構文解析時にそれらを区別します。関連付け解除プロセス中に、セミ結合/アンチ結合演算子を使用して関連付けを解除できる場合、関連付けは直接解除されます。それ以外の場合は、スカラー サブクエリ、つまり相関結合に変換されます。 2. 関連する条件の引き上げ ここでわかるように、correlatedjoin がプッシュダウンされると、ロジック ツリーが複雑になるため、プッシュダウンする前にサブクエリ内の関連演算子をプッシュアップします。ロジックでは、関連付けを生成する演算子が上位にあるほど、相関結合を関連部分の下部に早くプッシュできます。たとえば、次のクエリ:
ここで、t2.c1 = t2.c1 を agg にプッシュできるため (サブクエリの場合、これは group by 列の条件であるため)、次の変換を実行できます。まず、関連するフィルターをプルアップします (場合によっては書き換える必要があります)。これにより、相関結合をフィルターにプッシュし、変換 2 を呼び出すだけで済みます。 このスカラー サブクエリはフィルター条件として使用されるため、この場合、サブクエリに結果がなく null を返すと、対応する外部クエリは確実にフィルター処理されます。したがって、correlatedjoin は correlatedjoin* に直接変換でき、フィルターを上げると、次のプランを取得できます。この書き換えの利点は、結合前に agg (early agg) を実行できることです。欠点は、注意しないと、簡単に意味の不一致が発生し、カウント バグが発生する可能性があることです。 3 コスト依存サブクエリの最適化 ウィンドウ演算子を使用して関連付けを解く これまで説明してきたことを振り返ってみると、最も印象的なのは、相関結合演算子が外部クエリに列を追加することです。そして、その動作はウィンドウ演算子に似ています。ウィンドウ演算子のセマンティクスは、入力行の数を変更するのではなく、ウィンドウ フレームで計算された値を各行に追加することです。したがって、ウィンドウ演算子を使用して関連付けを解決できます。ご興味があれば、次の2つの論文を参照してください。Oracleでの拡張サブクエリ最適化[4]およびWinMagic: ウィンドウ集計を使用したサブクエリの除去[5]。 ウィンドウの関連付け解除の書き換えでは、外部クエリにサブクエリのすべてのテーブルと条件が含まれている場合、ウィンドウを直接使用してサブクエリの結果を外部クエリに接合できます。利点は、テーブルスキャンを大幅に節約できることです。たとえば、tpch q2。次のように書き換えることができます。 ここで window と書き換えられる理由は、外部クエリに内部クエリのすべてのテーブルと条件が含まれているためです。さらに、agg 関数 min は、プロパティ agg()=agg(null) も満たします (満たさない場合は、行をマークし、case when を使用して出力を書き換える必要があります)。 書き換え後はテーブルスキャンの数が大幅に減少していることがわかります。さらに、オプティマイザの後続の最適化ルールは、主キーの情報と agg 関数の特性に応じて結合とウィンドウの順序を交換し、ウィンドウ演算子へのデータ入力量をさらに削減します (フィルター結合プッシュダウン)。 これらの利点は多くの記事で言及されています。ここで、この書き直しの欠点について議論しましょう。
要約すると、相関サブクエリを書き換えるためにウィンドウを使用するタイミングには、利点とコストの見積もりが必要になります。 外部クエリでの CorrelatedJoin プッシュダウン 相関結合をサブクエリにプッシュダウンする前に、まず相関結合を外部クエリにプッシュダウンします (たとえば、クロス結合などを通じて)。 これは、correlatedJoin によってデータが肥大化することはないため、理論的にはより早く実行する必要があるために行われます。しかし実際には、correlatejoin がプッシュダウンされた後、joingraph もカットされ、ウィンドウの書き換えと同様の問題が発生する場合があります。 4. 等価列の利用 サブクエリ内に外部列と同等の列がある場合は、まずこの列を使用してサブクエリ内の関連列を書き換え、関連列の数を減らしてクエリを簡素化することができます。ここに簡単な例を示します。 Select t1.c2From t1Where t1.c3 < ( Select min(t2.c3) From t2 Where t1.c1 = t2.c1 group by t1.c1 ) -- サブクエリで t1.ct の代わりに t2.c1 を使用して簡略化します。 Select t1.c2From t1Where t1.c3 < ( Select min(t2.c3) From t2 Where t1.c1 = t2.c1 group by t2.c1 ) 5 サブクエリ関連の最適化ルール 一方、相関結合演算子の特性は、最適化のための情報を提供します。以下にいくつか例を挙げます。
一方、サブクエリの書き換えでは、属性推論によってサブクエリを簡素化することができます。例えば:
16 留意点 サブクエリの関連付けを解決するときに最も注意が必要な領域が 2 つあります。 1 つは、外部クエリに 1 つの列のみが追加されるようにすることであり、もう 1 つは null 値を処理することです。 カウントエラー 古典的な非相関化ではエラーが発生しやすいことが文献でよく言及されています。たとえば、次のクエリでは、t1.c3 がすべて 0 未満であるという前提条件があります。この場合、サブクエリが参加する結合条件には、フィルタリングの度合いがあってはなりません。これを内部結合として書き換えると、一部の行が除外されます。意味的には同等ではありません。
分散型左マーク結合 もう一つのエラーが発生しやすい領域は、論文「Unnesting Arbitrary Queries[3]」のLeftMarkJoinです。その出力は、と同じセマンティクスを持ちます。簡単に言えば、これは次のクエリの結果です。
このクエリの論理プランは次のとおりです。 出力結果は、左のサブツリー結果に in 結果の列を追加することです。結果には、true、false、null の 3 つの値があります。 分散環境では、この演算子を再パーティション化してフラッシュすると、null 値に関連する計算エラーが簡単に発生する可能性があります。 簡単な例を挙げると、leftmarkjoin が repartition モードで実行されると、左テーブルと右テーブルのデータは c1 のハッシュ値に従って再配分され、再シャッフルされます。次に、t1.c1 内の null の行が同じエグゼキュータにシャッフルされます。この時点で、右側のテーブルからこのマシンにデータがシャッフルされていない場合、このエグゼキュータはこれらの null 行に対して null を出力するか false を出力するかを知りません。空のセット内の null は false と評価されますが、空でないセット内の null は null と評価されます。この時点では、実行者は適切なテーブルが空かどうかを認識しません。 デカップリング後の効率 冒頭で、反復実行方式について説明しました。ここで、一部の関連サブクエリでは、関連が join/agg などの演算子に解決されても、クエリ結果を計算するにはクロス結合のコストが必要になることを説明する必要があります。 たとえば、次の 2 つのクエリでは、最初のクエリは共通の相関サブクエリであり、inner join + early agg の形式に変換できます。 2 番目は、関連付けを解除した後、非等価条件での左結合になります (クロス結合と同じコスト)。
sq1 が解除された後の計画は次のとおりです。 sql2 が関連付けを解除した後のプランは次のようになります。 sql1 の場合、セマンティックな観点から、サブクエリに取り込まれる外部クエリの各行によってスキャンされる行には重複がないため、コストは同等の条件での内部結合と同じになります。さらに、同じ外部行に対応するサブクエリの min 結果が同じである場合は、早期 agg を適用してさらに最適化することができます。 SQL2 の場合、意味論的な観点から、条件 t2.c1 > t1.c1 が満たされた場合にサブクエリの出力がどうなるかを判断するために、外部クエリの各行をサブクエリに取り込んですべての行をスキャンする必要があります。このコストは、結果を計算するための最適化によって節約することはできません。しかし、同じt1.c1の出力は常に同じであり、Unnesting Arbitrary Queries[3]で結果を再利用することで最適化を実現できます。 参考文献 [1] https://www.aliyun.com/product/ApsaraDB/ads [2] Galindo-Legaria、César、Milind Joshi。 「サブクエリと集計の直交最適化」 ACM SIGMODプロシーディング30.2(2001):571-581。 [3] ノイマン、トーマス、アルフォンス・ケンパー。 「任意のクエリのネスト解除」ビジネス、テクノロジー、ネットワークデータベースシステム(BTW 2015)(2015)。 [4] Bellamkonda、Srikanth、他。 「Oracle でのサブクエリ最適化の強化」 VLDB財団の議事録2.2(2009):1366–1377 [5] Zuzarte、Calisto、et al。 「Winmagic: ウィンドウ集計を使用してサブクエリを削除する」 2003 ACM SIGMOD 国際データ管理会議の議事録より。 2003。 [6] ノイマン、トーマス、ヴィクトール・ライス、アルフォンス・ケンパー。 「ジョインの全容(inHyPer)」ビジネス、テクノロジー、ネットワークデータベースシステム(BTW 2017)(2017)。 [7] Galindo-Legaria, C.A.、「パラメータ化されたクエリとネストされた同等物」技術レポート、Microsoft、2001 年。MSR-TR-2000-31、2000 年。 |
<<: デジタル変革は必須です。企業はどのようにこれを活用できるでしょうか?
第2四半期の業務・生産再開に伴い、エンターテインメント生放送市場は徐々に「爆発的成長期」から「調整期...
BandwagonHost VPS(BandwagonHost サーバー)を購入してしばらく使用する...
Hostvenom は別の情報を公開しました。E3 の Little Chicken はシカゴのデー...
2005年にインターネットに触れてから6、7年が経ちました。最初はチャットをしたり、音楽を聴いたり、...
今日の SEO 担当者はインターネット上のゴミの作成者であると多くの人が言います。私はこの発言を否定...
データベースの移行には、1 つ以上のソース プラットフォームから別のデータベースへのデータの移動が含...
ZXPlay【 VAT Number : 206 5572 17】からすごいものが発売されました。今...
フレンドリー リンクを交換するのが容易ではない 10 の状況: 熟練したウェブマスターは、フレンドリ...
Java のかつての有名なモットー、「一度書けばどこでも実行できる」は、今ではコンテナ内でコードを実...
6月末、raksmartが開発した新製品「クラウドサーバー」が正式に販売開始されました。現在は米国シ...
カナダのホスティング会社 myhosting (1997 年設立) は、元旦に VPS の 30% ...
クラウド コンピューティング、ビッグ データ、モノのインターネットは、IT 分野における最大の技術開...
Weibo マーケティングをうまく行う方法は数多くあり、多くの企業の Weibo アカウントが独自の...
著者は、ウェブサイトの運用とメンテナンスの最適化は、日々の業務をこなすだけの単純なプロセスではないと...
cloudiplcが提供するKVMシリーズVPSは、福建省泉州のデータセンターで利用可能です。CN2...