Query Planning and Optimization¶

catalog 是一个记录元数据信息的文件

The Physical Plan¶

Query Optimization(QO)¶

Heuristics/Rules¶

• 重写查询来去除那些无效的条件
• 这些技巧需要访问 catalog，但是它们不需要访问数据

Predicate Pushdown¶

Replace Cartesian Product¶

Projection Pushdown¶

Equivalence¶

Architecture Overview¶

Cost-based Search¶

• 使用一个模型来预测执行一个计划的成本
• 遍历多种计划，选择一个成本最小的计划来执行

Bottom-up Optimization¶

使用动态规划，自底向上构建查询计划成本最低的计划

• single-relation query palnning

system R optimization 将逻辑计划构建为左深树

Top-Down Optimization¶

自顶向下的优化控制权更多，我们可以从一个计划开始逐步细化过程

Nested Sub-queries¶

相关子查询很容易被扁平化为 join 的查询
不相关的子查可以拆分成不同的语句进行执行

Rewrite¶

Decomposing Queries¶

Expression rerwriteing¶

Cost Estimation¶

• Physical Costs

predict CPU-cycles, I/O, cache misses, RAM consumption, network messages...
Depends heavily on hardware

• Logical Costs

  estimate output size per operator
  independent of the operator algorithm
  need estimations for operator result sizes

selection cardinality¶

可以使用 selection cardinality 来推测输出的大小

Statistics¶