查询优化

Query Optimization

这是一个NP难问题

1. 逻辑查询优化

• 将一个关系代数表达式转换成另一个可以更快执行的关系代数表达式
  • 逻辑查询计划：关系代数表达式
  • 

基于代价的查询优化

查询计划枚举

• 等价关系代数表达式
  • 如果两个关系代数表达式在任意数据库实例上的结果都相同，则这两个关系代数表达式等价
• 选择下推
  • $\theta$连接满足交换律，但不满足结合律
  • 将关系代数表达式树中的选择操作向下推，通常可以提高查询的执行效率，可以尽早过滤掉与结果无关的元组
    • 
  • 选择度高的操作优先做
    • 选择度：满足选择条件的元组所占的比例（比例越低，选择度越高）
    • 
  • 将复杂的选择条件分解，然后再进行选择下推
    • 
  • 选择操作可以向关系代数表达式树的多个分支下推时，需要考虑哪个分支下推更合适
    • 选择操作的结果上没有索引
    • 
• 投影下推
  • 投影下推可以降低元组的大小
  • 
  • 投影操作的结果上没有索引，所以有些时刻反而不会优化查询

基数估计

• 逻辑查询计划的代价用执行计划过程中产生的中间结果的元组数来度量
• 估计查询结果的元组数
• 估计需要的数据库统计信息：系统目录
  • T(R)：关系R的元组数
  • V(R, A)：关系R的属性集A的不同值的个数

连接顺序优化

• 重要性
  • 连接操作的执行代价高
  • 在数据库上执行几十个关系的连接很常见，如联机分析处理任务
  • 不同的连接顺序的执行待机差异巨大
• 连接数
  • 左深连接数：只有一个左关系
  • 右深连接数：只有一个右关系
  • 浓密树

2. 物理查询优化

• 基于选定的逻辑查询计划，生成一个优化的物理查询计划，使DBMS按照该物理查询计划执行可以快速得到查询结果
  • 物理查询计划：带有“如何执行”注释的关系代数表达式
  •