Query Planning and Optimization

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





The Physical Plan

Query Optimization(QO)

Heuristics/Rules

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

Predicate Pushdown

Replace Cartesian Product

Projection Pushdown

Equivalence

Architecture Overview

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

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