9.关系查询处理与优化

一、关系数据库系统的查询处理

1、选择操作的实现算法：

2、连接操作的实现算法

二、关系数据库系统的查询优化

1、关系系统的查询优化

2、非关系系统的查询优化

三、代数优化 (逻辑优化 指关系代数表达式的优化)

1、查询树的启发式优化：

2、查询树的启发式优化算法

四、物理优化 （非代数优化 存取路径和底层操作算法的选择进行的优化）

1、代数优化与物理优化比较

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

选择操作

连接操作

3、基于代价的优化

基于启发式规则的优化与基于代价的优化对比

不同算法的代价估算

四、语义优化

五、查询计划的执行

补充、查询的过程

查询处理是RDBMS的核心，查询优化技术是查询处理的关键技术。

一、关系数据库系统的查询处理

查询处理(Query processing)指RDBMS执行查询语句的过程。

任务: 把用户提交给RDBMS的查询语句转换为高效的查询执行计划。

1、选择操作的实现算法：

1. 全表扫描
2. 索引扫描   B+树索引 普通索引

        

2、连接操作的实现算法

1. 嵌套循环算法(nested loop join)
2. 排序-合并算法(sort-merge join)
3. 索引连接(index join)算法
4. Hash Join算法

        

二、关系数据库系统的查询优化

1、关系系统的查询优化

        是RDBMS实现的关键技术又是关系系统的优点所在

        减轻了用户选择存取路径的负担

2、非关系系统的查询优化

        用户使用过程化的语言表达查询要求，执行何种记录级的操作，以及操作的序列是由用户来决定的

        用户必须了解存取路径，系统要提供用户选择存取路径的手段，查询效率由用户的存取策略决定

        如果用户做了不当的选择，系统是无法对此加以改进的

三、代数优化 (逻辑优化 指关系代数表达式的优化)

SQL语句经过查询分析、查询检查后变换为查询树。

查询树是关系代数表达式的内部表示。

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

1、查询树的启发式优化：

1. 选择运算应尽可能先做
   1. 在优化策略中这是最重要、最基本的一条
2. 把投影运算和选择运算同时进行
   1. 如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系
3. 把投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系
4. 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间
5. 找出公共子表达式
   1.  如果这种重复出现的子表达式的结果不是很大的关系，并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的。当查询的是视图时，定义视图的表达式就是公共子表达式的情况

2、查询树的启发式优化算法

四、物理优化 （非代数优化 存取路径和底层操作算法的选择进行的优化）

1、代数优化与物理优化比较

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

选择操作

连接操作

Br为外表占用块数 Bs为内表占用块数 占用块数小的表为外表，外表分配的块数多（K-1），内表就分配一块(1)，把内表读完之后再替换外表

3、基于代价的优化

基于启发式规则的优化与基于代价的优化对比

不同算法的代价估算

四、语义优化

查询优化器首先检测约束，如果约束不满足，则无需执行查询；否则，按之前的过程进行查询优化。

五、查询计划的执行