第21讲——查询优化_基于等价变换的查询优化

第21讲——查询优化

目录

第21讲——查询优化

 

1.什么是查询优化

1.1 语义优化

1.2 语法优化

1.3 物理优化

2.逻辑层查询优化策略

3. 关系代数操作次序交换的等价性

3.1 关系代数操作次序交换的等价性的定义

3.2 定理L1: 连接与连接、积与积的交换律

3.3 定理L2: 连接与连接、积与积的结合律

3.4 定理L13: 投影串接律

3.5 连接串接律

3.6 定理L5: 选择和投影交换律

3.7 定理L6: 选择和积的交换律

3.8 定理L7:投影和积的交换律

3.9 定理L8:选择和并的交换律

3.10 定理L9: 投影和并的交换律

4. 基于关系代数的查询优化算法及示例

5.物理层查询优化

6.代价估算

6.2 选择运算的故居代价

6.3 连接运算的代价估计

6.4 代价估计

---

1.什么是查询优化

三个层面进行优化:

• 语义优化---利用模型的语义及完整性规则，优化查询。
• 语法优化---逻辑层优化:利用语法结构，优化操作执行顺序;
• 执行优化---物理层优化︰存取路径和执行算法的选择与执行次序优化;

1.1 语义优化

语义优化: 内容等价性

去掉无关的表、去掉无关的属性、改写成等价的效果更好的语句

1.2 语法优化

语法优化: 语法等价性

尽可能早做选择运算、尽可能皁做投影运算、改写成等价的效果更好的语句

基本思想:

1. 改变关系代数的操作次序:尽可能早做选择和投影运算
2. 关系代数的五种基本操作中哪两个能够交换次序呢?
3. 次序改变前后两个表达式的等价性问题
4. 关系代数表达式的等价变换定理及其证明
5. 关系代数表达式的优化算法?-逻辑查询计划形成

1.3 物理优化

 

2.逻辑层查询优化策略

• (1)尽可能地早做选择和投影:可使中间结果变小，节省几个数量级的执行时间。
• ⑵把选择与投影串接起来:一元运算序列可一起执行，只需对整个关系扫描一遍。
• ⑶把投影与其前或后的二元运算结合起来:在第一次用关系时去掉一些无关属性，可以避免多次扫描整个关系。
• (4)把某些选择与其前的笛卡尔积合并成一个连接:当R×S前有选择运算且其中有条件是R、S属性间比较的运算时，可将其转化为连接运算可节省时间。
• (5)执行连接运算前对关系做适当预处理:文件排序、建立临时索引等，可使两关系公共值高效联接。
• (6)找出表达式里的公共子表达式:若公共子表达式结果不大，则预先计算，以后可读入此结果，节时多，尤当视图情况下有用。
   

3. 关系代数操作次序交换的等价性

3.1 关系代数操作次序交换的等价性的定义

3.2 定理L1: 连接与连接、积与积的交换律

 

3.3 定理L2: 连接与连接、积与积的结合律

3.4 定理L13: 投影串接律

3.5 连接串接律

3.6 定理L5: 选择和投影交换律

 

3.7 定理L6: 选择和积的交换律

 

3.8 定理L7:投影和积的交换律

3.9 定理L8:选择和并的交换律

 

3.10 定理L9: 投影和并的交换律

4. 基于关系代数的查询优化算法及示例

5.物理层查询优化

物理查询运算符

6.代价估算

6.1 投影运算的代价估计

6.2 选择运算的故居代价

6.3 连接运算的代价估计

6.4 代价估计