LLMエージェントは結合順序最適化が得意ですか？

はじめに

Databricksインテリジェンスプラットフォームでは、エンジンのパフォーマンスを向上させ、ユーザーエクスペリエンスを簡素化するために、新しいAI技術を定期的に探求および活用しています。ここでは、最も古いデータベースの課題の1つである結合順序付けに最先端モデルを適用した実験結果を紹介します。

このブログは、UPennとの共同研究の一部です。

課題：結合順序付け

リレーショナルデータベースのクエリオプティマイザは、考案されて以来、SQLクエリの適切な結合順序を見つけるのに苦労してきました。結合順序付けの難しさを説明するために、次のクエリを考えてみましょう。

ソニーが製作し、スカーレット・ヨハンソンが主演した映画は何本ありますか？

次のスキーマでこのクエリを実行すると仮定します。

Actor、Company、Movieのエンティティテーブルは、ProducesおよびStarsリレーションシップテーブル（例：外部キー経由）を介して接続されています。このクエリのSQLバージョンは次のようになります。

論理的には、単純な結合操作を実行したいと考えています：Actor ⋈ Stars ⋈ Movie ⋈ Produces ⋈ Company。しかし、物理的には、これらの結合はすべて可換および結合法則を満たすため、多くの選択肢があります。クエリオプティマイザは次のいずれかを選択できます。

1. まず、スカーレット・ヨハンソンが主演したすべての映画を見つけ、次にソニーが製作した映画のみをフィルタリングします。
2. まず、ソニーが製作したすべての映画を見つけ、次にスカーレット・ヨハンソンが主演した映画をフィルタリングします。
3. 並列で、ソニーの映画とスカーレット・ヨハンソンの映画を計算し、それらの積集合を取ります。

どのプランが最適かはデータによって異なります。スカーレット・ヨハンソンがソニーが製作した映画よりも大幅に少ない映画に主演している場合、最初のプランが最適かもしれません。残念ながら、この数量を推定することは、クエリ自体を実行することと同じくらい困難です（一般的に）。さらに悪いことに、選択肢は通常3つ以上のプランがあり、テーブルの数が増えると可能なプランの数は指数関数的に増加します。分析クエリは通常、20〜30の異なるテーブルを結合します。

今日の結合順序付けはどのように機能しますか？従来のクエリオプティマイザは、3つのコンポーネントでこの問題を解決します。サブクエリのサイズをすばやく推測するように設計されたカーディナリティ推定器（例：ソニーが製作した映画の数を推測するため）、さまざまな潜在的なプランを比較するためのコストモデル、および指数関数的に大きな空間をナビゲートする検索手順です。カーディナリティ推定は特に困難であり、さまざまなアプローチを使用した推定精度を向上させるための広範な研究につながっています[A]。

これらのすべてのソリューションは、クエリオプティマイザにかなりの複雑さを追加し、統合、保守、および本番環境への導入にかなりのエンジニアリング作業が必要です。しかし、プロンプ​​トで新しいドメインに適応する能力を持つLLM駆動エージェントが、この数十年前の問題を解決する鍵を握っているとしたらどうでしょうか？

エージェントによる結合順序付け

クエリオプティマイザが悪い結合順序を選択した場合¹、人間の専門家は、問題を診断し（多くの場合、カーディナリティの誤推定）、クエリオプティマイザに別の順序を選択するように指示することで修正できます。このプロセスでは、多くの場合、複数回のテスト（例：クエリの実行）と中間結果の手動検査が必要です。

クエリオプティマイザは通常、数百ミリ秒で結合順序を選択する必要があります。そのため、クエリオプティマイザのホットパスにLLMを統合することは、有望である可能性がありますが、今日では不可能です。しかし、クエリの結合順序を最適化する反復的かつ手動のプロセスは、人間の専門家が数時間かかる場合があり、LLMエージェントによって自動化できる可能性があります！このエージェントは、その手動チューニングプロセスを自動化しようとします。

これをテストするために、プロトタイプのクエリオプティマイザエージェントを開発しました。エージェントは単一のツールにアクセスでき、クエリの潜在的な結合順序を実行し、結合順序の実行時間（元のクエリの実行時間のタイムアウト付き）と各計算サブプランのサイズ（例：EXPLAIN EXTENDEDプラン）を返します。

エージェントに50回の反復を実行させ、エージェントがさまざまな結合順序を自由に試せるようにしました。エージェントは、有望なプランをテストするため（「活用」）、またはリスクはあるが有益な代替案を探索するため（「探索」）に、これらの50回の反復を自由に利用できます。その後、エージェントがテストした中で最もパフォーマンスの高い結合順序を収集し、それが最終結果となります。しかし、エージェントが有効な結合順序を選択したことをどのようにして確認できるでしょうか？正確性を確保するために、各ツール呼び出しは構造化されたモデル出力を使用して結合順序を生成し、モデルの出力が指定された文法に一致するように強制して、有効な結合再順序付けのみを許可します。これは、LLMにクエリオプティマイザの「ホットパス」で結合順序を即座に選択するように依頼する以前の研究[B]とは異なり、LLMはオフラインの実験者のように動作し、多くの候補プランをテストし、観察された結果から学習します。これは、人間が手動で結合順序を調整するのと同じです！

DBRでエージェントを評価するために、最適化が難しいように設計されたクエリセットであるJoin Order Benchmark (JOB)を使用しました。JOBで使用されるデータセットであるIMDbデータセットは、約2GB（したがって、Databricksは貧弱な結合順序付けでもかなり迅速に処理できます）であるため、各行を10倍に複製してデータセットをスケーリングしました[C]。

エージェントに、結合順序ベンチマークのすべての113クエリに対して、クエリごとに15回の結合順序（ロールアウト）をテストさせました。クエリごとに見つかった最良の結合順序の結果を報告します。最先端モデルを使用したとき、エージェントはクエリレイテンシを1.288倍（幾何平均）改善できました。これは、完全なカーディナリティ推定（実際には実行不可能）、より小さなモデル、および最近のBayesQOオフラインオプティマイザ（BayesQOはPostgreSQL用に設計されましたが、Databricks用ではありません）よりも優れています。

真に印象的な改善は分布のテールにあり、P90クエリレイテンシは41％低下しました。以下に、標準のDatabricksオプティマイザ（「Default」）とエージェント（「Agent」）の両方の完全なCDFをプロットします。クエリレイテンシは、Databricksオプティマイザの中央値レイテンシ（つまり、1で青い線が0.5の割合に達する）に対して正規化されています。

エージェントは、テストされた各プラン（「ロールアウト」とも呼ばれる）でワークロードを段階的に改善し、単純な「いつでもアルゴリズム」を作成します。これにより、より大きな時間予算をクエリパフォーマンスの向上に変換できます。もちろん、最終的にはクエリパフォーマンスは改善されなくなります。

エージェントが見つけた最も大きな改善点の1つは、クエリ 5bにありました。これは、1994年を参照するメモとともに、VHSで2010年以降の映画をリリースしたアメリカの制作会社を探すシンプルな5者結合です。Databricksオプティマイザは、まずアメリカのVHS制作会社を見つけることに焦点を当てました（これは確かに選択的で、わずか12行しか生成しません）。エージェントは、まず1994年を参照するVHSリリースを探すプランを見つけますが、これは大幅に高速であることが判明します。これは、クエリがLIKE述語を使用してVHSリリースを識別するためであり、これはカーディナリティ推定器にとって例外的に困難です。

私たちのプロトタイプは、エージェントシステムがデータベースクエリを自律的に修復および改善する可能性を示しています。この演習により、エージェント設計に関していくつかの疑問が生じました。

1. エージェントにどのようなツールを与えるべきか？現在の私たちの方法では、エージェントは候補となる結合順序を実行できます。なぜエージェントに特定のカーディナリティクエリ（例：特定のサブプランのサイズを計算する）を発行させたり、データに関する特定の仮定をテストするクエリ（例：1995年より前のDVDリリースがなかったことを判断する）を発行させたりしないのでしょうか。
2. このエージェントによる最適化はいつトリガーされるべきか？確かに、ユーザーは介入のために問題のあるクエリを手動でフラグを立てることができます。しかし、定期的に実行されるクエリにこの最適化を積極的に適用することもできるでしょうか？クエリが最適化の「可能性」を持っているかどうかをどのように判断できますか？
3. 改善を自動的に理解できますか？エージェントがデフォルトのオプティマイザよりも優れた結合順序を見つけた場合、この結合順序は、デフォルトのオプティマイザが最適ではない順序を選択していることの証明と見なすことができます。エージェントが基盤となるオプティマイザの体系的なエラーを修正した場合、それを発見してオプティマイザを改善するために使用できますか？

もちろん、クエリ最適化におけるLLMの可能性について考えているのは私たちだけではありません[D]。Databricksでは、データシステム自体を改善するためにLLMの汎用性を活用する可能性に興奮しています。

このトピックに興味がある場合は、UCBのフォローアップブログ「LLMエージェントはSQL結合順序をどのように考えますか？」も参照してください。

参加しませんか

今後、AIがデータベース最適化をどのように形成できるかの境界を押し広げ続けることに興奮しています。データベースエンジンの次世代を構築することに情熱を注いでいるなら、ぜひご参加ください！

¹ Databricksは、ランタイムフィルターなどの技術を使用して、結合順序が悪い影響を軽減します。ここで提示される結果には、これらの技術が含まれます。

注記

A. カーディナリティ推定のための技術には、例えば、アダプティブフィードバック、ディープラーニング、分布モデリング、データベース理論、学習理論、および因子分解が含まれます。以前の研究では、従来のクエリオプティマイザアーキテクチャを完全に置き換えることも試みられています。ディープ強化学習、マルチアームバンディット、ベイズ最適化、またはより高度な結合アルゴリズム。

B. 例えば、RAGベースのアプローチは、「ホットパスのLLM」システムを構築するために使用されてきました。

C. これは粗雑ですが、このアプローチは以前の研究で使用されています。

D. 他の研究者は、RAGベースのクエリ修復システム、LLM搭載クエリ書き換えシステム、さらにはLLMによって合成された完全なデータベースシステムを提案しています。

(このブログ記事はAI翻訳ツールを使用して翻訳されています) 原文記事