10,000倍速い！バークレーはSQLクエリを最適化するためにディープRLを使用することを提案している

SQL 結合を最適化する方法は、データベース コミュニティが何十年にもわたって研究してきた大きな問題です。最近、Berkeley RiseLab は、深層強化学習が SQL 接続の最適化にうまく適用できることを示す研究を発表しました。大規模な結合の場合、この手法は従来の動的プログラミングよりも最大 10 倍、網羅的な列挙よりも最大 10,000 倍高速に実行できます。この記事では、SQL 結合の問題とこの強力な最適化手法について紹介します。

データベース コミュニティは、System R の動的プログラミング アプローチにまで遡って、ほぼ 40 年にわたって SQL クエリの最適化問題を研究してきました。クエリ最適化の中核は結合ソートの問題です。この問題は古くからあるものの、マルチ結合クエリにおける結合オプティマイザーのパフォーマンスをより深く理解したり、エンタープライズ レベルの「データ レイク」に遍在する大規模な結合クエリの問題を解決したりしようとする研究プロジェクトが今も数多く存在します。

私たちの論文では、この数十年にわたる課題が深層強化学習技術を使用してどのように解決できるかを示します。接続のランキング問題をマルコフ決定過程 (MDP) として定式化し、ディープ Q ネットワーク (DQN) を使用して最適化プログラムを構築し、接続を効率的にランキングします。私たちは、結合の最適化をストレステストするために特別に設計された、最近提案されたワークロードである結合順序ベンチマークでアプローチを評価します。強化学習ベースのディープ オプティマイザーは、適度な量のトレーニング データのみを使用して、考えられるすべての最良のコスト モデル ソリューションよりも 2 倍、次善のヒューリスティックよりも最大 3 倍優れた実行プランを実現します。しかも、そのレイテンシは、動的プログラミングよりも 10 倍、網羅的な列挙よりも 10,000 倍高速です。

背景: 結合が順序付けられる理由

強化学習は結合ソート問題を解決するための良いアプローチでしょうか? この質問に答えるために、まず従来の動的プログラミング (DP) アプローチを確認しましょう。

データベースに従業員、給与、税金の 3 つのテーブルが含まれているとします。次のクエリは、マネージャー 1 の全従業員の合計税額を調べるために使用されます。

このクエリには 3 つのリレーショナル結合が含まれています。次の例では、基本関係 R にアクセスするコストを表すために J(R) を使用し、T1 と T2 を結合するコストを表すために J(T1,T2) を使用します。簡単にするために、アクセス方法、結合方法、および対称結合コスト（つまり、J(T1,T2) = J(T2,T1)）を想定します。

古典的な「左深」DP 法では、まず 3 つの基本関係にアクセスするための最大コストを計算します。結果を次の表に示します。

次に、この情報に基づいてすべてのバイナリ関係を列挙します。たとえば、接続 {E,S} の最高コストを計算する場合、以前に関連付けられた計算結果が検索されます。

ベスト({E, S}) = ベスト({E}) + ベスト({S}) + J({E}, S)

これにより、新しい行が作成されます。

アルゴリズムは他のバイナリ関係のセットを走査し、最終的に 3 つのテーブルすべてを接続するための最高コストを見つけます。これには、バイナリ関係と基本関係のすべての可能な「左深」の組み合わせの中から最小のものを取る必要があります。

これは動的計画法です。 J の 2 番目のオペランド (関係の右側) は常に基本関係ですが、左側は中間結合結果になる可能性があることに注意してください (そのため、「左深」という名前が付けられています)。このアルゴリズムの空間と時間の複雑さは、関係の数に応じて指数関数的に増大します。そのため、通常は 10 ～ 15 の関係を持つ結合クエリにのみ使用されます。

強化学習による接続ソート

私たちの主なアイデアは次のとおりです。結合順序付け問題を解決するために、上記のような動的プログラミングを使用する代わりに、問題をマルコフ決定プロセス (MDP) として定式化し、MDP を解決するための一般的な確率的最適化ツールである強化学習 (RL) を使用して解決します。

まず、結合順序を MDP として定式化します。

• 状態、G: 接続する必要がある残りの関係。
• アクション、c: 残りの関係の外側にある有効な接続。
• 次の状態、G': これは、2 つの関係が削除され、その結果の結合が追加された「残りの関係」の古いセットです。
• 報酬、J: 新しい接続の推定コスト。

これは単純に (G, c, G', J) と表現できます。

結合順序付け MDP を解決するために、一般的な RL 手法である Q 学習を使用します。各接続の長期コスト、つまり現在の接続決定後のすべての後続接続で実行する最善のアクションの累積コストを直感的に説明するQ関数Q(G,c)を定義します。

Q(G, c) = J(c) + \min_{c'} Q(G', c')

実際の Q 関数にアクセスできる場合は、貪欲な結合順序付けを実行できることに注意してください。

アルゴリズム1

• 最初のクエリ グラフから開始します。
• Q(G,c)***の接続を見つけます。
• クエリ グラフを更新して繰り返します。

ベルマンの普遍性原理によれば、私たちのアルゴリズムは普遍的であることが証明できます。このアルゴリズムの魅力的な点は、計算の複雑さが O(n^3) であることです。これはまだ高い数値ですが、動的プログラミングの指数関数的な実行時複雑さよりもはるかに低い数値です。

図 1: ニューラル ネットワークを使用して Q 関数を近似する。出力は、「現在のクエリ グラフ G で c を結合する場合、最小の長期結合プラン コストはいくらですか?」を意味します。

もちろん、実際には真の Q 関数にアクセスすることはできないため、近似する必要があります。この目的のために、ニューラル ネットワーク (NN) を使用して Q 関数を学習し、これをディープ Q ネットワーク (DQN) と呼びます。これは、エキスパートレベルで Atari ゲームのプレイ方法を学ぶために使用されるのと同じテクニックです。要約すると、私たちの目標は、(G,c) を入力として受け取り、Q(G,c) の推定値を出力するニューラル ネットワークをトレーニングすることです (図 1 を参照)。

深層強化学習オプティマイザー DQ

ここで、深層強化学習オプティマイザー DQ を紹介します。

データ収集。 Q 関数を学習するには、まず過去の実行データを観察する必要があります。 DQ は、基礎となるオプティマイザーから (G、c、G'、J) のシーケンスを受け入れることができます。たとえば、従来の左深層動的計画法 (背景セクションで示す) を実行し、DP テーブルから一連の「接続軌跡」を計算することができます。完全なトレースのタプルは (G,c,G',J)=({E,S,T}, join(S,T), {E,ST}, 110) のようになり、これは初期クエリ グラフ (状態) から開始して S と T を結合する (アクション) 手順を表します。

結合の推定コストを表すために J を使用しましたが、データが実際のデータベース実行から収集された場合は実際の実行時間を使用することもできます。

状態とアクションの特性。 Q(G,c) を表すためにニューラル ネットワークを使用するため、状態 G とアクション c を固定長の特徴ベクトルとしてネットワークに入力する必要があります。 DQ の特徴付けスキームは非常にシンプルです。1 ホット ベクトルを使用して、(1) スキーマ内のすべての属性を含むクエリ グラフに存在するすべての属性のセット、(2) 結合の左側の参加属性、および (3) 結合の右側の属性をエンコードします。図2に示すように。

図 2: クエリとそれに対応する特徴量化。従業員、職位、給与の 3 つのテーブルを含むデータベースを想定します。この図は部分的な接続と完全な接続を示しています。 (G,c) の最終的な特徴ベクトルは、A_G (クエリ グラフの属性)、A_L (左側の属性)、および A_R (右側の属性) を連結したものです。

このスキームは非常にシンプルですが、表現力は十分であることがわかりました。私たちのスキーム (および学習されたネットワーク) では、属性とテーブルの正確なセットを知る必要があるため、固定データベースを前提としていることに注意することが重要です。

ニューラル ネットワークのトレーニングと計画。デフォルトでは、DQ は単純な 2 層の完全接続ネットワークを使用し、標準的な確率的勾配降下法を使用してトレーニングされます。トレーニング後、DQ はプレーンテキストの SQL クエリ ステートメントを受け入れ、それを抽象構文ツリーに解析し、ツリーを特徴付け、候補接続がスコア付けされるたびにニューラル ネットワークを呼び出すことができます (つまり、ニューラル ネットワークはアルゴリズム 1 のステップ 2 で呼び出されます)。 ***、DQ は実際の実行からのフィードバックを使用して定期的に再調整できます。

評価する

DQ を評価するために、最近リリースされた Join Order Benchmark (JOB) を使用しました。このデータベースは IMDB の 21 個のテーブルで構成され、33 個のクエリ テンプレートと 113 個のクエリを提供します。クエリ内の結合関係のサイズは 5 ～ 15 の範囲です。接続関係の数が 10 を超えない場合、DQ は網羅的な列挙からトレーニング データを収集します。

比較する。いくつかのヒューリスティック最適化ツール (QuickPick および KBZ) と従来の動的プログラミング (左深型、右深型、ジグザグ) と比較します。各オプティマイザーによって生成されたプランにスコアを付け、それらを（徹底的な列挙によって得られた）最良のプランと比較します。

コストモデル。新しいハードウェアのイノベーション (NVRAM など) とサーバーレス RDBMS アーキテクチャ (Amazon Aurora Serverless など) への移行により、さまざまなハードウェア特性を捉えることができる新しいクエリ コスト モデルが急増すると予想されます。学習ベースのオプティマイザーがさまざまな環境に適応できることを示すために、次の 3 つのコスト モデルを設計します。

• コスト モデル 1 (主にインデックス): メモリ内データベースをシミュレートし、インデックス結合の使用を推奨します。
• コスト モデル 2 (ハイブリッド ハッシュ): メモリ バジェットのあるハッシュ結合とネストされたループ結合のみが考慮されます。
• コスト モデル 3 (ハッシュの再利用): 構築されたハッシュ テーブルの再利用を検討します。

CM1 から CM3 にかけて、コストはより非線形性を示し、静的戦略に課題が生じます。

クロス検証を 4 回実行し、DQ がトレーニング ワークロードに表示されないクエリに対してのみ評価されるようにしました (各ケースで 80 個のクエリをトレーニングし、そのうち 33 個をテストしました)。クエリの平均的な準最適性は「コスト（アルゴリズム プラン）/ コスト（最適なプラン）」として計算されます。この数値が低いほど優れています。たとえば、Const Model 1 の場合、平均 DQ 距離は計画値の 1.32 倍になります。結果は図3に示されています。

図 3: さまざまなコスト モデルにおける平均計画の準最適性。

すべてのコスト モデルにおいて、DQ は指数構造に関する事前の知識がなくても、最適なソリューションで競争力を発揮します。これは固定動的プログラミングには当てはまりません。たとえば、左深型では CM1 では適切なプランが生成されますが (インデックス結合の使用が推奨されます)、CM2 および CM3 ではパフォーマンスが低下します。同様に、右深プランは CM1 では競争力がありませんが、CM2 または CM3 を使用すると、右深プランは突然それほど悪くなくなります。学習ベースのオプティマイザーは手動で設計されたアルゴリズムよりも堅牢であり、ワークロード、データ、またはコスト モデルの変更に適応できることに注意することが重要です。

さらに、DQ は従来の動的プログラミングよりもはるかに高速に優れた計画を生成します (図 4)。

図 4: クエリ内のリレーションの数ごとにグループ化された、113 個の JOB クエリすべてに対するオプティマイザーのレイテンシ。エラーバーは平均値の±標準偏差を表します。合計5つの実験が実施されました。

大規模な結合シナリオでは、DQ は劇的な高速化を実現します。大規模な結合の場合、DQ は網羅的列挙よりも 10,000 倍、ジグザグ列挙よりも 1,000 倍、左深列挙と右深列挙よりも 10 倍高速です。パフォーマンスの向上は主に、ニューラル ネットワークによって提供される豊富なバッチ処理の機会から生まれます。つまり、1 回の反復ですべての候補接続に対して、DQ はバッチ全体に対して NN を 1 回呼び出します。これは、このような学習オプティマイザーにとって大きなパフォーマンス向上であると考えています。大規模なクエリや、特殊なアクセラレータ (GPU、TPU など) で実行する場合に、さらに大きな利点が発揮されます。

まとめ

深層強化学習は結合順序付け問題の解決に適していると考えています。深層強化学習では、固定されたヒューリスティックを使用するのではなく、データ駆動型のアプローチを使用して特定のデータセットとワークロードのクエリ プランを調整し、結合コストを観察します。クエリ プランを選択するために、DQ はトレーニング中にステートフル プラン テーブルの圧縮バージョンをエンコードするニューラル ネットワークを使用します。

DQ は氷山の一角に過ぎず、データベース コミュニティでは、既存のシステムにさらに学習 (またはデータ適応性) を組み込む方法について活発な議論が行われています。私たちの取り組みがよりスマートなクエリ オプティマイザーへの第一歩となることを願っています。