Advanced Database Systems(2020)のOptimizer Implementation(Part1~3)を視聴したときのメモ
Advanced Database Systemsという講義のOptimizer Implementation(Part 1~3)を視聴したときのメモ。殆どPart1の内容。
基礎事項
クエリ最適化とは
- クエリに対して、コストが最も小さく、正しい実行計画を探すこと
- コストは実行時間やデータサイズ、CPU/IO/ネットワーク使用量など様々な視点がある
- DBMSの構成要素の中でもかなり難しい部分(最適な計画を探すのはNP-Complete)
- そのため、コストの推定や探索空間を減らすためのヒューリスティクスを使う
logical plan と physical plan
ざっくり、logical planは「何をするのか」を論理演算子で定義したもので、
physical planは「どうやってするのか」をアクセスパスのレベルで定義したもの。
オプティマイザはlogical planを最適で等価なpysical planへの対応を生成する。
(この対応は1:1とは限らない)
オプティマイザを設計するときに考えること
講義では以下の軸が紹介されていた。
最適化の粒度
- Single Query
- 探索空間が狭い。他クエリの結果を再利用することは一般にない。
- Multiple Query
- 探索空間が広い。クエリ間で結果をシェアするので、類似するクエリが多い場合に効率的。
最適化のタイミング
- Static Optimization
- 実行前に最適な計画を選ぶ。
Prepared Statement
を使用して実行を償却できる?
- 実行前に最適な計画を選ぶ。
- Dynamic Optimization
- 実行時に最適な計画を選ぶ。複数の実行に対して再最適化される。
- Adaptive Optimization
Prepared Statement
とは、以下のように一部の値が変数に置き換わったクエリのこと。
PREPRARE MyQuery AS SELECT * FROM table WHERE value > ? EXECUTE myQuery(10) # SELECT * FROM table WHERE value > 10
Prepared Statements
- 最後の計画を再使用
- 前実行時に生成された計画を再利用
- 再最適化
- クエリが実行されるたびにオプティマイザを実行する。(注: 出発点として既存の計画を再利用するのは難しいらしい。)
- 複数の計画
- パラメタ(引数)の値によって別々の実行計画を生成する
- 平均の計画
- パラメタの平均値を選択し、それをすべての呼び出しに使用する。
プランの安全性
検索の終了条件
- Wall-clock
- オプティマイザが一定時間実行された後に停止
- Costの閾値
- コストが閾値より小さいプランが見つかったら停止
- Exhaustion
- ターゲットプランの列挙がなくなったら停止。通常、グループ毎に実施される。(?)
#### 最適計画の探索手法
講義では以下の手法が紹介されていた。
リストの下に行くほど新しく複雑な手法になっていく。
- ヒューリスティクス
- ヒューリスティクス + Cost-based Join Order Search
- 乱択アルゴリズム
- Stratified Search : 層別検索
- 2ステップに分けて実行する。
- logical -> logical ... logical planを変換ルールを使って書き換える。この時、その変換が許されるかを確認する。また、このステップでコストは考慮されない。
- logical -> physical ... コストに基づく探索を行い、logical planを physical plan に対応させる。
- ex : Starburst
- Pros : 実際、いい感じに機能する
- Cons: 変換に優先順位を割り当てるのが難しく、ルールのメンテナンスのコストが大きい。
- 2ステップに分けて実行する。
- Unified Search : 統合検索 (Volcano)
- logical -> logicalとlogical -> physicalの概念を統合する。また、多くの変換が生成されるので、メモ化により冗長な作業を減らす。top-downの手法。
- Pros : 宣言的なルールを使って変換を生成する。メモ化。
- Cons: 全ての等価なクラスは完全に拡張され、最適化検索の前に全ての可能な論理演算子を生成する。一方、述語を変更するのは容易ではない。