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 を算出する

所感

• ヒストグラムの話が面白い。

リンク

一人読書会 - Database Management System