第8章系查询处理与查询优化

1、第第8 8章章8.1 关系数据库系统的查询处理关系数据库系统的查询处理8.2 关系数据库系统的查询优化关系数据库系统的查询优化8.3 查询优化的一般准则查询优化的一般准则 8.4 代数优化代数优化8.5 物理优化物理优化8.6 小结小结本章要求与重难点本章要求与重难点v掌握关系数据库系统的查询处理步骤掌握关系数据库系统的查询处理步骤v掌握掌握rdbms中查询优化技术中查询优化技术(重点和难点重点和难点)第第8 8章章8.1 关系数据库系统的查询处理关系数据库系统的查询处理8.2 关系数据库系统的查询优化关系数据库系统的查询优化8.3 查询优化的一般准则查询优化的一般准则 8.4 代数优化代数优

2、化8.5 物理优化物理优化8.6 小结小结3. 查询优化查询优化选择低层的操作算法选择低层的操作算法第第8 8章章8.1 关系数据库系统的查询处理关系数据库系统的查询处理8.2 关系数据库系统的查询优化关系数据库系统的查询优化8.3 查询优化的一般准则查询优化的一般准则 8.4 代数优化代数优化8.5 物理优化物理优化8.6 小结小结8.2关系数据库系统查询优化关系数据库系统查询优化v查询优化的必要性查询优化的必要性查询优化极大地影响查询优化极大地影响rdbms的性能。的性能。 关系数据库系统查询优化（续）关系数据库系统查询优化（续）关系数据库系统查询优化（续）关系数据库系统查询优化（续）(2

3、)如果数据库的物理统计信息改变了，系统可以自动如果数据库的物理统计信息改变了，系统可以自动对查询对查询重新优化重新优化以选择相适应的执行计划。以选择相适应的执行计划。 在非关系系统中必须重写程序，而重写程序在实际应在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。用中往往是不太可能的。(3)优化器可以考虑数百种不同的执行计划，而程序员优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性一般只能考虑有限的几种可能性。关系数据库系统查询优化（续）关系数据库系统查询优化（续）v查询优化的总目标查询优化的总目标 选择有效策略，求得给定关系表达式的值选择有效策略，求

4、得给定关系表达式的值关系数据库系统查询优化（续）关系数据库系统查询优化（续）例：求选修了课程例：求选修了课程2的学生姓名的学生姓名 select student.snamefrom student, scwhere student.sno=sc.snoand sc.cno=2; 关系数据库系统查询优化（续）关系数据库系统查询优化（续）假设假设1：外存：外存：student:1000条条,sc:10000条条, 选修选修2号课程号课程:50条条假设假设2：一个内存块：一个内存块内存中一次可以存放内存中一次可以存放: 5块块student元组元组, 1块块sc元组和若干块连接结果元组元组和若干块连

5、接结果元组假设假设3：读写速度：读写速度：20块块/秒秒假设假设4：连接方法：连接方法：基于数据块基于数据块的嵌套循环法的嵌套循环法 执行策略执行策略11 n a m e(s t u d e n t . s n o =s c . s n o s c . c n o = 2 (studentsc) studentsc 读取总块数读取总块数= 读读student表块数表块数 + 读读sc表遍数表遍数 *每遍块数每遍块数 =1000/10+(1000/(105) (10000/100) =100+20100=2100 读数据时间读数据时间=2100/20=105秒秒不同的执行策略不同的执行策略,考虑

6、考虑i/o时间时间中间结果大小中间结果大小 = 1000*10000 = 107 (1千万条元千万条元组组)写中间结果时间写中间结果时间 = 10000000/10/20 = 50000秒秒 读数据时间读数据时间 = 50000秒秒 总时间总时间 =1055000050000秒秒 = 100105秒秒 = 27.8小时小时关系数据库系统查询优化（续）关系数据库系统查询优化（续）2. 2 name(sc.cno= 2 (student sc) 读取总块数读取总块数= 2100块块读数据时间读数据时间=2100/20=105秒秒中间结果大小中间结果大小=10000 （减少（减少1000倍）倍）写中

7、间结果时间写中间结果时间=10000/10/20=50秒秒 读数据时间读数据时间=50秒秒 总时间总时间1055050秒秒205秒秒=3.8分分 关系数据库系统查询优化（续）关系数据库系统查询优化（续）3. 2 sname(student sc.cno= 2 (sc) 读读sc表总块数表总块数= 10000/100=100块块读数据时间读数据时间=100/20=5秒秒 中间结果大小中间结果大小=50条条 不必写入外存不必写入外存 读读student表总块数表总块数= 1000/10=100块块读数据时间读数据时间=100/20=5秒秒 总时间总时间55秒秒10秒秒 关系数据库系统查询优化（续）

8、关系数据库系统查询优化（续）4. 2 name(student sc.cno=2 (sc)假设假设sc表在表在cno上有索引，上有索引，student表在表在sno上上有索引有索引 读读sc表索引表索引=读读sc表总块数表总块数= 50/1001块块读数据时间读数据时间 中间结果大小中间结果大小=50条条 不必写入外存不必写入外存关系数据库系统查询优化（续）关系数据库系统查询优化（续） 读读student表索引表索引=读读student表总块数表总块数= 50/10=5块块读数据时间读数据时间 总时间总时间10秒秒第第8 8章章8.1 关系数据库系统的查询处理关系数据库系统的查询处理8.2 关

9、系数据库系统的查询优化关系数据库系统的查询优化8.3 查询优化的一般准则查询优化的一般准则 8.4 代数优化代数优化8.5 物理优化物理优化8.6 小结小结8. 3 查询优化的一般准则查询优化的一般准则 v选择运算应尽可能先做选择运算应尽可能先做 目的：减小中间关系目的：减小中间关系查询优化的一般准则查询优化的一般准则 （续）（续）v某些选择运算在其前面执行的笛卡尔积某些选择运算在其前面执行的笛卡尔积 第第8 8章章8.1 关系数据库系统的查询处理关系数据库系统的查询处理8.2 关系数据库系统的查询优化关系数据库系统的查询优化8.3 查询优化的一般准则查询优化的一般准则 8.4 代数优化代数优

10、化8.5 物理优化物理优化8.6 小结小结8. 4 代数优化代数优化 v关系代数表达式等价关系代数表达式等价常用的等价变换规则常用的等价变换规则关系代数等价变换规则（续）关系代数等价变换规则（续） 2. 连接、笛卡尔积的结合律连接、笛卡尔积的结合律 (e1e2) e3 e1 (e2e3) (e1 e2) e3 e1 (e2 e3) (e1 e2) e3 e1 (e2 e3) f f f f关系代数等价变换规则（续）关系代数等价变换规则（续） 3. 投影的串接定律投影的串接定律 a1,a2, ,an( b1,b2, ,bm(e) a1,a2, ,an (e)假设：假设：1)e是关系代数表达式是关

11、系代数表达式2)ai(i=1，2，n), bj(j=l，2，m)是属性名是属性名3)a1, a2, , an构成构成bl，b2，bm的子集的子集 关系代数等价变换规则（续）关系代数等价变换规则（续） 4. 选择的串接定律选择的串接定律 f1 （ f2（e） f1 f2(e)关系代数等价变换规则（续）关系代数等价变换规则（续） 5. 选择与投影的交换律选择与投影的交换律(1)假设假设: 选择条件选择条件f只涉及属性只涉及属性a1，an f (a1,a2, ,ane) a1,a2, ,an(f(e) (2)假设假设: f中有不属于中有不属于a1, ,an的属性的属性b1,bm a1,a2, ,an

12、(f e) a1,a2, ,an(f(a1,a2, ,an,b1,b2, ,bm(e)关系代数等价变换规则（续）关系代数等价变换规则（续） 6. 选择与笛卡尔积的交换律选择与笛卡尔积的交换律(1) 假设：假设：f中涉及的属性都是中涉及的属性都是e1中的属性中的属性 f (e1e2)f (e1)e2 (2) 假设：假设：f=f1f2，并且，并且f1只涉及只涉及e1中的属性，中的属性， f2只涉及只涉及e2中的属性中的属性 则由上面的等价变换规则则由上面的等价变换规则1，4，6可推出：可推出： f(e1e2) f1(e1)f2 (e2) 关系代数等价变换规则（续）关系代数等价变换规则（续） (3)

13、 假设：假设： f=f1f2， f1只涉及只涉及e1中的属性，中的属性， f2涉及涉及e1和和e2两者的属性两者的属性关系代数等价变换规则（续）关系代数等价变换规则（续） 7. 选择与并的交换选择与并的交换假设：假设：e=e1e2，e1，e2有相同的属性名有相同的属性名f(e1e2) f(e1) f(e2) 8. 选择与差运算的交换选择与差运算的交换假设：假设：e1与与e2有相同的属性名有相同的属性名f(e1-e2) f(e1) - f(e2) 关系代数等价变换规则（续）关系代数等价变换规则（续） 9. 投影与笛卡尔积的交换投影与笛卡尔积的交换假设：假设：e1和和e2是两个关系表达式，是两个关

14、系表达式， a1，an是是e1的属性，的属性， b1，bm是是e2的属性的属性关系代数等价变换规则（续）关系代数等价变换规则（续） l0. 投影与并的交换投影与并的交换假设：假设：e1和和e2 有相同的属性名有相同的属性名 a1,a2, ,an(e1e2) a1,a2, ,an(e1) a1,a2, ,an(e2) 小结小结1-2: 连接、笛卡尔积连接、笛卡尔积的交换律、结合律的交换律、结合律3： 合并或分解合并或分解投影投影运算运算4： 合并或分解合并或分解选择选择运算运算5-8： 选择运算与其他运算交换选择运算与其他运算交换5，9，10： 投影运算与其他运算交换投影运算与其他运算交换 关系

15、代数表达式的优化算法关系代数表达式的优化算法 算法：关系表达式的优化算法：关系表达式的优化输入：一个关系表达式的语法树。输入：一个关系表达式的语法树。输出：计算该表达式的程序。输出：计算该表达式的程序。方法：方法：（1）分解选择运算）分解选择运算 利用规则利用规则4把形如把形如f1 f2 fn (e)变换为变换为 f1 (f2( (fn(e) ) 关系代数表达式的优化算法关系代数表达式的优化算法 (续续)（2）通过交换选择运算，将其尽可能移到叶端）通过交换选择运算，将其尽可能移到叶端 对每一个选择，利用规则对每一个选择，利用规则48尽可能把它移到尽可能把它移到树的叶端。树的叶端。 （3）通过交

16、换投影运算，将其尽可能移到叶端）通过交换投影运算，将其尽可能移到叶端对每一个投影利用规则对每一个投影利用规则3，9，l0，5中的一般形中的一般形式尽可能把它移向树的叶端。式尽可能把它移向树的叶端。 关系代数表达式的优化算法关系代数表达式的优化算法 (续续)（4）合并串接的选择和投影，以便能同时执行或）合并串接的选择和投影，以便能同时执行或在一次扫描中完成在一次扫描中完成关系代数表达式的优化算法关系代数表达式的优化算法 (续续)（5）对内结点分组）对内结点分组关系代数表达式的优化算法关系代数表达式的优化算法 (续续)（6）生成程序）生成程序第第8 8章章8.1 关系数据库系统的查询处理关系数据库

17、系统的查询处理8.2 关系数据库系统的查询优化关系数据库系统的查询优化8.3 查询优化的一般准则查询优化的一般准则 8.4 代数优化代数优化8.5 物理优化物理优化8.6 小结小结 物理优化就是要选择高效合理的物理优化就是要选择高效合理的操作算法或存取路径，求得优化得查操作算法或存取路径，求得优化得查询计划，达到查询优化的目标。询计划，达到查询优化的目标。选择的方法可以是：选择的方法可以是：v基于规则的启发式优化基于规则的启发式优化v基于代价估算的优化基于代价估算的优化v两者结合的优化方法两者结合的优化方法优化的一般步骤优化的一般步骤 1把查询转换成某种内部表示把查询转换成某种内部表示2代数优

18、化：把语法树转换成标准（优化）代数优化：把语法树转换成标准（优化） 形式形式3物理优化：选择低层的存取路径物理优化：选择低层的存取路径4生成查询计划，选择代价最小的生成查询计划，选择代价最小的 优化的一般步骤优化的一般步骤 (续续)（1）把查询转换成某种内部表示）把查询转换成某种内部表示例：求选修了课程例：求选修了课程2的学生姓名的学生姓名select student.snamefrom student, scwhere student.sno=sc.snoand sc.cno=2; （1）把查询转换成某种内部表示）把查询转换成某种内部表示语法树语法树 结果结果project(sname) select(sc.cno= 2 ) join(student.sno=sc.sno) studentsc关系代数语法树关系代数语法树sname sc.cno=2 student.sno=sc.s studentsc（2）代数优化）代数优化利用优化算法把语法树转换成标准（优化）形式利用优化算法把语法树转换成标准（优化）形式 sname student.sno=sc.sno sc.