database-theory-6

关系查询处理与查询优化

关系查询处理步骤

• 关系查询处理的四个阶段:

  • 查询分析

  • 查询检查

  • 查询优化

  • 查询执行

查询优化

• 查询优化目标

  • 选择一个高效执行的查询处理策略，使得查询代价最小

• 查询的执行开销（集中式数据库）

  • 总代价=I/O代价 + CPU代价 + 内存代价
  • I/O代价是最主要的

• 按照优化的层次分为代数优化和物理优化。

  • 代数优化：关系代数表达式的优化，即按照一定的规则，改变代数表达式中操作的次序和组合
  • 物理优化：存取路径和底层操作算法的选择。选择依据——基于规则的、基于代价的、基于语义的

查询的代数优化

• 通过对关系代数表达式的等价变换来提高查询效率

• 关系代数表达式的等价

  • 指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的

• 查询树的启发式优化（优化的一般准则）

  • 选择运算尽可能先做。是优化策略中最重要、最基本的一条。（减小中间关系）

  • 把投影运算和选择运算同时进行；把投影同其前或其后的双目运算结合起来。（减少扫描关系的次数）

  • 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算。（把笛卡尔积与选择转换为连接）

  • 找出公共子表达式，把公共子表达式的结果写入中间文件，重复使用。（中间结果复用）

查询的物理优化

• 选择高效合理的操作算法或存取路径，得到优化的查询计划。

• 常用方法

  • 基于规则的启发式优化方法

  • 基于代价估算的优化方法

  • 两者结合的优化方法

• 选择(选取)操作的实现算法示例

  • 全表扫描法

  • 索引扫描法

    • 如果在选择条件的属性上有索引，先通过索引找到目标索引项，再通过索引项找到元组

• 连接操作的实现算法示例

  • 嵌套循环法

    • 两个连接的表，第一个表为外循环，另一个为内循环

  • 排序-合并法

    • 两个表都按照连接属性排序，取第一个表元组的连接属性与第二个表元组的比较

  • 索引连接法

    • 第二个表按照连接属性建索引，取第一个表元组的连接属性与第二个表元组的连接属性比较

  • Hash join法

    • 连接属性作为hash码，用同一个hash函数把两个连接表的元组散列到同一个hash文件

• 基于启发式规则的存取路径选择优化

  • 选择操作的启发式规则

    • 对于小关系，使用全表顺序扫描。

    • 对于大关系：可以采用索引扫描法（如结果的元组数目较小），全表顺序扫描。

  • 连接操作的启发式规则

    • 如果两个表都已经按照连接属性排序——排序-合并法；

    • 如果一个表在连接属性上有索引——索引连接法；

    • 如果连接属性上未排序且未建索引，且其中一个表较小——Hash join法；

    • 最后可选用嵌套循环法，并选择较小的表为外循环表。

查询优化的一般步骤

• 把查询转换成语法树，如关系代数语法树。

• 把语法树利用代数优化转换成优化后的标准形式。

• 利用基于启发式规则的物理优化，选择底层的存取路径。

• 生成查询计划，利用基于代价的物理优化，选择代价最小的。