查询优化

1. 查询优化概述
   RDBMS查询处理步骤：

• 查询分析： 对查询语句进行扫描、词法分析和语法分析

• 查询检测：查询数据库对象、用户权限、完整性约束等

• 查询优化：高效执行的查询处理策略，查询优化器

• 查询执行：执行代码生成器，生成执行查询计划的代码

  
  

• 关系查询优化是影响RDBMS性能的关键因素

• 查询优化利用优化器完成。其优点是不仅用户不必考虑如何最好地表达查询以获得较好地效率，而且在于系统可以比用户程序地“优化”做得更好

• 优化器可以从数据字典获取许多统计信息
• 如果数据库的物理统计信息改变了，优化器可以自动对查询重新优化已选择相适应的执行计划
• 优化器可以考虑数百种不同的执行计划
• 优化器包括了很多复杂的优化技术

• RDBMS 通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案

• 集中式数据库
  总代价=I/O代价+CPU代价+内存代价
• 分布式数据库
  总代价=I/O代价+CPU待机+内存代价+通信代价
  查询优化的总目标:选择有效的策略、求得给定关系表达式的值、使得查询代价最小（实际上是较小）

2. 查询优化实例
   eg:求学修了2号课程的学生姓名。用SQL表达：
   SELECT Student.Sname FROM Student,SC WHERE Student.Sno = SC.Sno AND SC.Cno='2'

系统可以用多种等价的关系代数表达式来完成这一查询

1. 计算广义笛卡尔积

• Q1的算法 把Student和SC的每个元组连接起来的做法

• 把内存中尽可能地多装入Student表地若干块，留出一块存放另一个表(如SC表)地元组
• SC中地每个元组和Student中每个元组连接，连接后地元组装满一块后就写到中间文件上
• 从SC中读入一块和内存中的Student元组连接，知道SC表处理完
• 再读入若干个Student元组，读入一块SC元组
• 重复上述处理过程中，直到把Student表处理完

• 设一个块能装10个Student元组或100个SC元组，把内存中存放5块Student元组和1块SC元组，则读取总块数为
  1000/10+(1000/(105))(10000/100)
• 其中，读Student表100块。读SC表20遍，每遍100块。若每秒读20块，则总计要花105s
• 

2. 作选择操作

• 依次读入连接后的元组，按照选择条件选择满足要求的记录
• 假定内存处理时间忽略。读取中间文件花费的时间（同写中间文件一样）需要
• 满足条件的元组假设仅50个，均可存放在内存

3. 作投影操作

• 把第二步的结果在Sname上作投影输出，得到最终结果

  
  

• 先对SC表作选择运算，只需读一遍SC表，存取100块花费时间为5s,因为满足条件的元组仅50个，不必使用中间文件
• 读取Student表，把读入的Student元组和内存中的SC元组作连接。也只需读一遍Student表共100块，花费时间为5s
• 把连接结果投影输出
  第二种情况总的执行时间约等于5+5约等于10s

3. 代数优化

• 代数优化策略: 通过对关系代数表达式的等价变换来提高查询效率
• 两个关系表达式E1和E2是等价的,可记为
  

  关系代数表达式等价变换规则请查看教材

查询树的启发优化

• 典型的启发式规则:

• 选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条
• 把投影运算和选择运算同时进行。避免重复扫描关系。
• 把投影同其他或其后的双目运算结合起来
• 把某些选择同在它前面执行的笛卡尔积结合起来成为一个连接运算

• 找出公共子表达式: 如果重复出现的子表达式的结果不是很大的关系并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算