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

  • 最後の計画を再使用
    • 前実行時に生成された計画を再利用  
  • 再最適化
    • クエリが実行されるたびにオプティマイザを実行する。(注: 出発点として既存の計画を再利用するのは難しいらしい。)  
  • 複数の計画  
    • パラメタ(引数)の値によって別々の実行計画を生成する
  • 平均の計画
    • パラメタの平均値を選択し、それをすべての呼び出しに使用する。

プランの安全性

  • ヒントの提供
  • オプティマイザのバージョンを固定
  • 計画の後方互換
    • 古いバージョンからのクエリを保存し、新しいDBMSに提供する

検索の終了条件

  • Wall-clock
  • Costの閾値  
    • コストが閾値より小さいプランが見つかったら停止
  • Exhaustion
    • ターゲットプランの列挙がなくなったら停止。通常、グループ毎に実施される。(?)

#### 最適計画の探索手法
講義では以下の手法が紹介されていた。
リストの下に行くほど新しく複雑な手法になっていく。

  • ヒューリスティクス
    • 静的なルールに基づき、論理演算を physical plan に変換する。
    • ex: INGRES, 昔のOracle
    • Pros : 実装が容易で、単純なクエリなら十分に良い結果を素早く得られる
    • Cons: マジックナンバーに頼る形になる。また、複雑なクエリにで良い結果を得るのは難しい
  • ヒューリスティクス + Cost-based Join Order Search
    • ルールによる最適化の後、動的計画法によりjoinの順序を調整する。bottom-upの手法。
    • ex: System R, 多くのOSSであるDBMS
    • Pros : 通常、網羅的な検索を実行せずにいい感じの計画が得られる
    • Cons: コストを考える時、データの物理的な性質を考慮に入れる必要がある。また、ヒューリスティクスのConsを引き継ぐ。
  • 乱択アルゴリズム
    • 探索範囲でランダムウォークを実施する。焼きなましとかも。
    • ex : Posgresの遺伝的アルゴリズム
    • Pros : 局所的な最適解を避けることができる。また、メモリのオーバーヘットは低い(履歴を保持しないならば)
    • Cons: なぜその実行計画が選ばれたのか解釈が難しく、再現性を担保する仕組みが必要。また、実行計画が正しいものであるかのルールが必要。
  • Stratified Search : 層別検索
    • 2ステップに分けて実行する。
      1. logical -> logical ... logical planを変換ルールを使って書き換える。この時、その変換が許されるかを確認する。また、このステップでコストは考慮されない。
      2. logical -> physical ... コストに基づく探索を行い、logical planを physical plan に対応させる。
    • ex : Starburst
    • Pros : 実際、いい感じに機能する
    • Cons: 変換に優先順位を割り当てるのが難しく、ルールのメンテナンスのコストが大きい。
  • Unified Search : 統合検索 (Volcano)
    • logical -> logicalとlogical -> physicalの概念を統合する。また、多くの変換が生成されるので、メモ化により冗長な作業を減らす。top-downの手法。
    • Pros : 宣言的なルールを使って変換を生成する。メモ化。
    • Cons: 全ての等価なクラスは完全に拡張され、最適化検索の前に全ての可能な論理演算子を生成する。一方、述語を変更するのは容易ではない。