この記事の趣旨
2018年に発表された分析ワークロードなどで発生しがちな最終結果に比べ、非常に大きな中間結果を 作成してしまうクエリを多方向結合で最適化する論文を読みました。
Adopting Worst-Case Optimal Joins in Relational Database Systems
著者について
Michael Freitag、Maximilian Bandle、Tobias Schmidt、Alfons Kemper、Thomas Neumannによるグループの論文 いずれの著者もDBMSにおける最適化を中心に研究しており、それぞれ分析ワークロードにおける最適化や 最新のハードウェアにおける最適化などを研究している。
問題意識
従来のRDBMSにおける結合処理のほとんどはバイナリ結合に依存して複数のリレーションにまたがるクエリを処理してきた。 数十年に渡る研究によりバイナリ結合は幅広い柔軟性と優れた性能を発揮するようになった。
その一方でバイナリ結合による実行計画は特定のワークロードでは最適ではないケースを示すことが知られている。 主な原因として実際のクエリ結果に比べて非常に大きな中間結果を生成するためである。 とくにPK以外のキーによる結合が多くなる分析ワークロードではそのような状態を避けることが難しく、 またグラフ分析のようなクエリパターンでも多く見られる。
近年の論理的な進歩により中間結果の列挙を避ける多方向結合のアルゴリズムが開発可能になった。 この手法はバイナリ結合計画より優れた実行時間を保証できるため、RDBMSの堅牢性を大幅に向上させる 可能性を持っている。
しかし現状最悪ケース最適化結合アルゴリズムでは以下のような問題を抱えている。 1. 膨大なストレージとメンテナンスを必要とする結合に参加出来るカラムを含むインデックスを必要とする。 1. RDBMSは挿入と更新のサポートが必要なものの、既存のアルゴリズムは高価な事前計算を必要とする。
そのため本論文は以下の制約を満たすアプローチを提案している 1. 多方向結合が有益な場合のみ多方向結合を使用するオプティマイザを必要とする。 1. 実行中に効率的に実行でき、ディスクのに永続化する必要のないパフォーマントインデックスを必要とする。
手法
提案手法では比較ベースではなくハッシュベースの結合のため、2の「実行中に効率的に実行でき、 ディスクのに永続化する必要のないパフォーマントインデックスを必要とする。」という要素の考慮を除いている。
またオプティマイザについては既存のコストベースのものを拡張し適応している。 提案手法では潜在的に成長している結合のカスケードを最悪の場合の最適結合に置き換えることで、 最適化されたバイナリ結合計画を洗練させるヒューリスティックなアプローチを提案している。
通常の結合順序最適化で使用されるのと同じカーディナリティ推定値に基づいて、中間テーブルが膨大になる結合を 特定する。
作業時間
- read
- 22:13
- 22:13
- author
- 25:48
- 3:35
- summary
- 52:58
- 26:50
感想
とても難しい内容に感じてしまい、殆ど頭を通りすぎてしまった気がする。
今まで最適化は触れずに来たため、理解が浅い領域だった。よくよく考えるとDBMSの 話しに最適化が登場するのはあたりまえなので、今後はその方面にも触れて行きたい。
