Estimating The Cost of Plan - A Typical Query Optimizer - Database Management Systems

Database Management Systemsの15章。

マインドマップから再構成したまとめ

SQL -> ALGEBRA

  • 流れ:SQL => 分解 => Blocks => Algebra
  • Block とは: 1つの Select, 1つの from 。
  • Block -> Algebra
    • select => projection
    • from => cross product
    • where => selection

Estimate

  • 大まかな流れ
    • 1. operator のコスト見積もり(Pipeline か Temp table かが支配的)
    • 2. result の size と sorted かどうか
  • ポリシ: Avoid worst, find good.
  • サイズの見積もり: where では reduction factor を使う
    • データが一様に分布している事が前提
    • col = value : Index があれば r = 1 / Indexの種類、なければ 1/10
    • col = col2 : r = 1 / Index の小さい方
    • col > value : r = (high - value) / (high - low)
  • 統計データを保持してサイズ見積もりをより正確に
    • 大きめの感覚で、ヒストグラムを保持して reduction factor を算出する

所感