# CMU DB 15. Query Planning & Optimization II

tags: CMU DB

• Slides
• Notes
• Video

授業

今回は前回やったようにqueryの最適化についてやります．

ここではcost-based searchを扱います．

plan cost estimation

• queryが必要とする時間はいくらか
  • CPU: あまり影響せず，予想するのは難しい
  • Disk: ブロック転送の数に比例
  • Memory: 使われているDRAMの量に比例
  • Network: メッセージの数
  • どれだけのtuplesが読み書きされるかによる

統計を利用している．

selection cardinalityについて

• uniform data
  • 値の分布は同じであるという仮定
• independent predicates
  • attributeについての述語は独立である
• inclusion principle

sampling

plan enumeration

query optimization

rule-based rewritingの後，DBMSは異なるクエリを数え上げ，コストを予想する．

• single-relation
  • もっともよいサクセス方法を選ぶ．
    • sequential scan
    • binary search
    • index scan
  • 述語評価によって整列する．
  • OLTPに向いている．
• multiple relation
  • 代わりとなる計画の数はJOINの数が増えると，急速増える．
  • 動的計画法でコスト予測の数を減らすことが可能
• nested sub-queries

これらの計画全てを試したあと，クエリに最適なプランを選ぶ．

nested sub-queries

DBMSはWHERE節にあるnested sub-queriesを関数として扱う．

conclusion

出来るだけ早くフィルターをする

selectivity estimations

• uniformity
• independence
• histograms
• join selectivity

DPをJOINでの整列に使う．

nested queriesを書き直す．

query optimizationは難しい…

感想

難しいのだな〜ということだけ分かりましたw

このような最適化とは統計学を絡めた最適化が相性がよく，DBMSを勉強するならMLをやった方が良さそうだと思いました．