UDFをSQLに変換する仕組みを作ることで大幅に性能が改善したという研究の紹介
この記事はデータベース・システム系 Advent Calendar 2023の記事です。 今回はFroid: Optimization of Imperative Programs in a Relational Databaseという論文の内容を紹介します。データベースエンジンの詳細な実装を知らなくてもイメージがつかみやすい内容だと思うのでこういう研究もあるんだなーという気持ちで楽しく読んでいただけたらと思います。なお、この記事では要点のみをかいつまんで紹介しますので詳細が気になった方はぜひ論文の方をご参照ください。また、CMUの講義でも紹介されているのでこちらもご参照ください。
UDFとは
多くのRDBMSにはUDFやStored ProcedureなどのプログラミングをするようにDBへの処理を記述できる仕組みが存在します。以下は論文中でも紹介されているT-SQLというSQL Serverで用いられている言語で書かれたUDFの例です。
create function total_price(@key int) returns char(50) as begin declare @price float, @rate float; declare @pref_currency char(3); declare @default_currency char(3) = 'USD'; select @price = sum(o_totalprice) from orders where o_custkey = @key; select @pref_currency = currency from customer_prefs where custkey = @key; if(@pref_currency <> @default_currency) begin select @rate = xchg_rate(@default_currency,@pref_currency); set @price = @price * @rate; end return str(@price) + @pref_currency; end
変数にSELECT文の結果を代入してその後の分岐処理などに利用し、最後に結果をreturnするといったプログラミング言語らしい記述ができている事が分かるかと思います。また、UDFはSQLの中で利用する事が可能なので、例えば以下のように上で紹介したtotal_priceというUDFをクエリの中で呼び出す事も可能です。
select c_name, dbo.total_price(c_custkey) from customer;
このように、UDFには単一のSQLでサブクエリなどを使いこなして記述するよりも人にとって分かりやすい記述になったり、コンポーネントの再利用ができたりするなどのメリットがあります。
UDFの性能問題とその原因
ここまでに述べたようにUDFは便利な機能ではあるのですが、いくつかの理由から性能が十分に最適化されていませんでした。以下に論文中に記載されているSQL Serverの場合の原因を抜粋しましたが、一般にほかのDBMSでも当てはまるものとも記載されています。
- UDFを含むSQLの最適化についてUDFの処理内容が考慮されないのでオプティマイザーのコスト評価にUDFの内容がうまく反映されない
- UDFの処理系はSQLの処理系から関数を呼び出す形で実装されており、UDFの処理のたびに関数呼び出しが発生し、コンテキストスイッチのオーバーヘッドが発生する
- UDF内のクエリに対しては通常のクエリの場合に行うような並列処理がサポートされていない
- UDFの処理系はあくまで一行ずつ上から処理していくようなモデルであり、コンパイル言語で行われるような最適化が行われていない。
これらの背景には宣言的なパラダイムであるSQLの処理系と命令的なパラダイムであるUDFの処理系の間のインピーダンスミスマッチがあると著者らは述べています。そこでこの問題を解決するためにUDFの処理系とSQLの処理系を分けるのではなくUDFをSQLに変換*1してSQLの処理系で処理してしまおうというのが今回のアイデアです。
UDFをSQLに変換する
UDFの性能が最適化されていない部分についての理解があれば今回の論文のアイデア自体はとても単純で、「UDFをSQLの処理系で処理できるように変換して単一のSQLと見なせるようにすれば単一のSQLの処理系になるし、労力を割いて作ったオプティマイザーがいい感じに最適化してくれるはず」というものです。以下ではその実現方法と動作イメージを紹介します。
変換方法
ここでは一番のエッセンスにあたる、逐次処理をどのようにSQLに変換するかという部分について書きます。実際の代入処理や分岐命令などのSQLへのマッピングやその妥当性については論文に記載があるので興味のある方はそちらをご確認ください。
逐次処理の変換方法についてですが、これにはApply operator、一般にはlateral joinと呼ばれる操作を用います。lateral joinは左テーブルの結果を右テーブルの処理で利用する事ができるというものです。イメージとしてはUDFの各行をSQLのサブクエリに変換して、上から順に左から右に結合することで、UDFの上から順番に処理するイメージをSQLで表現できます。以下は論文中で紹介されている、最初に紹介したUDF、total_priceをApply operatorを用いて関係代数形式に変換したときのUDFの結合の図です。
なお、Apply operatorはもちろんオプティマイザーによる最適化の対象にあたるため、最終的に生成される実行計画はこのjoinの内容を理解した上でのコスト評価が行われ、UDFの処理系のように逐次実行ではなく諸々の最適化が行われ、必要に応じて並列処理なども行われる事が期待されます。
SQLに変換したUDFが最適化される様子
UDFがSQLに変換される事で最適化の際にUDFの中身が考慮されない問題や関数呼び出しのオーバーヘッド、並列処理のサポートの問題が一気に解決されることが期待できるのは想像できますが、UDFの処理系の最適化相当の事もオプティマイザーによって行われるという事が記載されています。
図中で上の段がUDFに対してコンパイルによる最適化が行われていた時の処理、下の段がSQLに変換したUDFに対してオプティマイザーが行う対応する最適化になります。まず、この処理では@xが1000より大きいかによって処理が分岐していますが、@xが与えられた段階でそうでない分岐の処理は削除できます。このような最適化(dynamic slicing)はオプティマイザーの前処理でも行われます。次に既に変数の値が分かっている演算を先に行うような最適化(constant propagation)もオプティマイザーが行います。また、参照されないパスの削除(dead code elimination)相当の処理も同様に行われます。
これらの最適化はUDFの処理系を改善するという形でも実現できるものではありますが、SQLに変換する事でこれらのメリットもいっしょについてくるというのはとても面白いところです。
改善結果
著者らはAzure SQL DatabaseにFroidのアイデアを実装し、実際のユーザーのワークロードでの改善度合いを評価しました。その中から特に目を引く図を一つ紹介します。
図よりサンプリングしたユーザーのUDFについてほぼすべてのUDFが性能改善し、そのほとんどが10倍以上、ものによっては 100倍程度の性能改善が確認できます。このような劇的な変化は通常なかなか見られないものだと思うので、このアイデアの強力さが感じられます。再帰が深い場合など変換をサポートできないUDFもあるようなので万能というわけではなさそうですが、すごい成果だと思いました。
まとめ
今回はFroidというUDFの性能改善の研究の紹介をしました。データベースの論文となると僕のようなデータベースユーザーにとっては普段あまり触らない内部のアルゴリズムなどの話題が多いですが、今回の内容はエンジンの詳細な実装には特に触れない内容で、親しみが湧くと同時に実はまだまだデータベースには課題がいろいろあるんだなと感じました。僕も研究者という職種ではないですが自分が関わる物事の中に何か一般的な課題が無いかであったり、それに対して汎用性のある解決策がないかという事は考えていきたいと思いました。以上です。
