LQRS: Learned Query Re-optimization Framework for Spark SQL

本論文は、Spark SQL 上で実行時の観測データを活用して動的に計画を再最適化する強化学習ベースのフレームワーク「LQRS」を提案し、これにより他の手法と比較して最大 90% の実行時間短縮を実現したことを報告しています。

要約

LQRS：Spark SQL のための「学習型クエリ再最適化」フレームワークの解説

この論文は、データベースが大量のデータを処理する際に行う「クエリ（検索命令）」の最適化について書かれています。特に、**「実行中に状況を見て、計画をその場で書き換えることができる新しい AI 」**を紹介しています。

これを、**「料理のレシピとシェフ」**に例えて説明しましょう。

---

1. 従来の問題点：「完璧なレシピ」の罠

通常、データベースのオプティマイザ（最適化エンジン）は、クエリを受け取ると、事前に計算された統計情報（「この材料は 100 個あるだろう」「この鍋は 5 分かかるだろう」など）に基づいて、**「最も効率的なレシピ（実行計画）」**を事前に決めてしまいます。

• 従来の AI（Lero など）： 過去のデータから学習して、より良いレシピを提案するようになりました。しかし、**「料理が始まる前に計画を決めて、一度も変えられない」**というルールに従っていました。
• 現実のジレンマ： 料理を始めてみたら、「あ、この野菜は予想より 100 倍も大きかった！」「実はこの材料は 1 個しか残っていなかった！」という予期せぬ状況が発生することがあります。
  • 従来のシステムは、この「実行中のリアルタイムな情報」を無視して、最初から決めた計画を突き進んでしまいます。
  • その結果、**「巨大な鍋で 1 個の野菜を炒める」**ような、無駄な時間とリソースを浪費してしまいます。

2. LQRS の解決策：「状況を見て臨機応変に変える天才シェフ」

この論文が提案するLQRSは、**「実行中に状況を見て、レシピをその場で書き換える」**という新しいアプローチです。

具体的な仕組み：

1. 学習と観察（リハーサル）：
   AI は過去の料理（クエリ実行）から学びます。しかし、単に「レシピ本」を作るだけでなく、**「実際に火をつけて、鍋の中を見て、味見をする」**プロセスも学習に組み込みます。
2. 実行中の修正（リハーサル）：
   料理（クエリ実行）が始まると、LQRS は「あ、この材料（データ）の量が予想と全然違うな！」と気づきます。
   • 例： 「この野菜（テーブル）は 1 個しかないから、巨大な鍋（ハッシュ結合）を使う必要はない。むしろ、別の鍋（バースト結合）でサッと炒めたほうが速い！」と判断します。
   • アクション： 実行中の計画を**「その場で書き換えます」**。
3. 報酬システム：
   AI は「早く美味しくできた（実行時間が短縮）」場合は褒美をもらい、「失敗した（メモリ不足や遅延）」場合は罰を受けます。これを繰り返すことで、**「実行中の情報に基づいて、最も賢い判断ができる」**ようになります。

3. 何がすごいのか？（3 つのポイント）

① 「実行中」に計画を変えることができる

これまでの AI は「実行前」に計画を決めるだけでしたが、LQRS は**「実行中」**に計画を修正できます。

• 比喩： 従来の AI は「出発前に GPS でルートを決め、渋滞しても無視して走り続ける」車。
• LQRS： 「渋滞を見つけたら、その場でナビが「こっちの道に変えよう！」と指示を出して、ルートを変更する」車。

② 「カリキュラム学習」で段階的に成長

いきなり難しい料理（複雑なクエリ）を任せるのではなく、最初は簡単なタスクから始め、徐々に難易度を上げていきます。

• 比喩： 料理見習い（AI）に、最初は「卵を割る」ことから始め、次に「炒める」を教え、最後に「複雑なコース料理」を任せるようにしています。これにより、AI は安定して賢くなります。

③ Spark SQL との完璧な連携

LQRS は、世界中で使われている大規模データ処理システム「Spark SQL」の仕組み（AQE：適応型クエリ実行）に、**「プラグイン（差し込み機能）」**として組み込まれています。

• 比喩： 既存の高級レストラン（Spark SQL）に、**「天才シェフの助手」**を新しく雇って、厨房（実行エンジン）の中でリアルタイムに指示を出せるようにした感じです。特別な設備変更なしで導入できます。

4. 結果：劇的なスピードアップ

実験の結果、LQRS は他の最新の AI 最適化ツールや、従来の方法と比較して、最大 90% も実行時間を短縮することに成功しました。

• 21 秒かかっていた処理が、15 秒に短縮されるなど、劇的な改善が見られました。

まとめ

LQRS は、「事前に完璧な計画を立てる」ことよりも、「実行中のリアルな状況を見て、柔軟に計画を修正する」ことの重要性を証明した画期的なシステムです。

まるで、**「状況に応じて臨機応変に動き回る、経験豊富なベテランシェフ」**が厨房に入り、無駄な動きを削ぎ落とし、最短ルートで美味しい料理（クエリ結果）を届けてくれるようなものです。これにより、データベースはより速く、賢く、効率的に動くことができるようになります。

技術概要

LQRS: Spark SQL 向け学習型クエリ再最適化フレームワークの技術的概要

本論文は、Apache Spark SQL におけるクエリ最適化の課題を解決し、実行時の観測データを活用した動的な再最適化を実現するLQRS (Learned Query Re-optimization Framework) を提案しています。従来の学習型クエリ最適化（LQO）が抱える「実行前の統計情報に基づく静的な計画のみ」という限界を克服し、実行中のフィードバックを用いて計画を逐次改善する新しいアプローチを示しています。

以下に、問題定義、手法、主要な貢献、実験結果、および意義について詳細にまとめます。

---

1. 背景と問題定義

従来のクエリ最適化の限界

• コストベース最適化 (CBO): 手作業で設計されたコストモデルに依存しており、実際のデータ分布や選択性を正確に推定できず、非効率な実行計画が生成されることが多い。
• 既存の学習型クエリ最適化 (LQO): 過去の履歴データから学習したモデルを用いて計画を選択するが、「最適化→実行」のパラダイムに縛られている。
  • 実行前に決定された計画は、実行中に生成される貴重なランタイム情報（実際のカーディナリティ、中間結果のサイズなど）を反映できず、動的に修正できない。
  • 例：結合順序が最適でない場合、実行中にその情報が判明しても、LQO は計画を変更できないため、パフォーマンスが低下したままとなる。

解決すべき課題

• 実行時に得られる観測データ（実際の中間結果のサイズや行数）を即座に活用し、実行中の計画を動的に再最適化できる学習フレームワークの構築。
• Spark SQL の適応的クエリ実行（AQE）の機能を拡張し、学習アルゴリズムと統合すること。

---

2. 提案手法：LQRS

LQRS は、Spark SQL の AQE (Adaptive Query Execution) 基盤の上に構築されたフレームワークであり、実行前最適化と実行中最適化の両方を単一の学習プロセスで統合します。

2.1 全体アーキテクチャ

LQRS は主に 2 つのコンポーネントで構成されます。

1. Planner Extension (プランナー拡張):
   • Spark AQE の拡張ルールとして実装され、クエリステージ（Shuffle の境界）ごとに実行を一時停止します。
   • 部分的に実行された計画と、そのステージで得られた実際の統計情報（行数、データサイズ）を抽出し、意思決定モデルに送信します。
   • 意思決定モデルからのアクションを受け取り、実行中の計画に適用（結合順序の変更、ブロードキャスト戦略の強制など）し、AQE エンジンに再投入します。
2. Decision Model (意思決定モデル):
   • Actor-Critic 構造を採用した強化学習モデルです。
   • 状態 (State): 部分的に実行された計画ツリーと、完了したステージの実際の統計情報（真のカーディナリティ、バイトサイズ）。
   • 行動 (Action): 計画の初期化戦略の選択、結合順序の入れ替え（swap）、特定のテーブルの優先結合（lead）、ブロードキャスト結合の強制（broadcast）、何もしない（no-op）など。
   • 報酬 (Reward): 最終的な実行時間だけでなく、中間的なシャッフル操作の増加数などを考慮した形状付け報酬（Shaping Reward）を使用し、学習の安定性と効率性を向上させています。

2.2 学習戦略とモデル設計

• Curriculum Reinforcement Learning (カリキュラム強化学習):
  • 学習の初期段階では単純な決定（計画初期化戦略の選択）のみを許可し、徐々に実行中の計画調整（結合順序の変更など）を許可する段階的な学習を行います。これにより、モデルの学習安定性を高めています。
• モデル構造 (TreeCNN):
  • 計画ツリーをベクトル化して処理するために、TreeCNN (Tree Convolutional Neural Network) を採用しています。
  • 入力特徴量には、ノードの種類、関連するテーブル、および実行時に観測された真のカーディナリティが含まれます。
  • Actor は行動の確率分布を出力し、Critic は状態の価値（将来の報酬の期待値）を評価します。

2.3 計画変換と安全性

• Bushy Join の探索: 実行中に結合順序を変更する際、LQRS は左深型（Left-deep）の計画を木型（Bushy）の計画に変換するアルゴリズムを実装しています。
• 安全性: 変更された計画が元のクエリと意味的に等価であることを AQE エンジンが保証するため、LQRS はセマンティックチェックやコード生成の低レベルな処理を担わず、最適化アクションの適用に集中できます。

---

3. 主要な貢献

1. 実行時再最適化の学習フレームワークの提案:
   • Spark SQL 上で、実行中の観測データに基づいて動的に計画を修正する初の学習型クエリ最適化フレームワークを実装しました。
2. TreeCNN を用いた効率的な意思決定モデル:
   • 実行ステージレベルのフィードバック（真のカーディナリティなど）を直接入力として利用し、簡素なアーキテクチャで高いパフォーマンスを実現するモデルを設計しました。
3. プラグアンドプレイ型のプランナー拡張:
   • Spark SQL の拡張インターフェースを活用し、実行中の計画をオンラインで変更可能なモジュールを設計しました。結合順序の入れ替えや戦略の変更を動的に適用できます。
4. 広範な実験による性能検証:
   • 4 つのベンチマーク（JOB, ExtJOB, STACK, TPC-H）を用いた大規模実験により、他の学習型オプティマイザや再最適化手法と比較して、最大 90% の実行時間短縮を達成したことを示しました。

---

4. 実験結果

4.1 性能評価

• 比較対象: Spark SQL (デフォルト AQE), Lero, AutoSteer, QuerySplit (SSA)。
• 結果:
  • LQRS はすべてのベンチマークで最良の性能を示しました。
  • Spark SQL と比較して、全体の実行時間を 16.3%〜73.3% 削減。
  • 他の学習型オプティマイザ（Lero など）と比較しても大幅に優れており、特に複雑な結合クエリにおいて、実行時の観測に基づく動的な結合順序の再編成が有効に機能しました。
  • 例: STACK ベンチマークの Q1#1 では、Lero が 21.52 秒かかったクエリを、LQRS は 15.24 秒（約 30% 短縮）で実行しました。これは、実行中に「テーブル t のスキャン結果が 1 行しかない」ことを検知し、結合順序を最適化したためです。

4.2 動的評価（ロバスト性）

• データ分布の変化（IMDb の異なる年次データ）やワークロードの変化（JOB と ExtJOB の相互評価）に対して、LQRS は高いロバスト性を示しました。
• 学習データとテストデータの分布が異なる場合でも、実行時の観測に基づいて適応するため、性能劣化が比較的少ないことが確認されました。

4.3 オーバーヘッド

• LQRS の最適化にかかるオーバーヘッドは、Lero や AutoSteer に比べて極めて低く抑えられています。
• これは、実行前に大規模な計画列挙を行わず、実行中の観測データに基づいて段階的に最適化を行うためです。

---

5. 意義と結論

LQRS は、データベースクエリ最適化のパラダイムを「事前の統計に基づく静的な最適化」から「実行時の観測に基づく動的な適応」へと転換させる重要なステップです。

• 理論的意義: 強化学習と適応的クエリ処理（AQP）を統合し、実行中のフィードバックループを学習プロセスに組み込むことで、より高精度な最適化決定が可能であることを実証しました。
• 実用的意義: Spark SQL の AQE 機能を拡張するプラグインとして実装されており、既存のシステムに導入しやすく、大規模データ処理におけるクエリ実行時間の大幅な短縮に寄与します。
• 将来展望: 現在のフレームワークでは、学習中に探索が不足した場合に性能が劣化するリスクがありますが、オフライン RL やより広範な経験バッファの導入などによるさらなる改善の余地があります。

総じて、LQRS は「学習」と「実行時の適応」を融合させることで、従来の手法では到達できなかったクエリパフォーマンスの限界を押し広げる画期的なアプローチです。