《0009 关系查询处理和查询优化》由会员分享，可在线阅读，更多相关《0009 关系查询处理和查询优化（58页珍藏版）》请在金锄头文库上搜索。
1、第九章 关系查询处理和查询优化,授课内容,9.1 关系数据库系统的查询处理 9.2 关系数据库系统的查询优化 9.3 代数优化9.4 物理优化,9.1 关系数据库系统的查询处理,查询处理步骤,RDBMS查询处理阶段 ： 1. 查询分析2. 查询检查3. 查询优化 4. 查询执行,查询处理步骤,1. 查询分析对查询语句进行扫描，从查询语句中识别出语言符号，如SQL关键字、数据库对象名。进行语法检查和语法分析，判断查询语句是否符合SQL语法规则。,查询处理步骤,查询检查根据数据字典对合法的查询语句进行语义检查根据数据字典中的用户权限和完整性约束定义对用户的查询请求进行检查 检查通过后把SQL查询语
2、句转换成等价的关系代数表达式 RDBMS一般都用查询树(语法分析树)来表示扩展的关系代数表达式,查询处理步骤,查询优化每个查询都会有多个可供选择的执行策略，查询优化就是选择一个高效率的执行策略 查询优化分类 ：代数优化：指关系代数表达式的优化物理优化：指存取路径和底层操作算法的选择,查询处理步骤,查询执行依据优化器得到的执行策略生成查询计划代码生成器(code generator)生成执行查询计划的代码,实现查询操作的算法示例,1. 选择操作的实现 SELECT * FROM Student where sno = 950062. 连接操作的实现SELECT * FROM Student in
3、ner join SC on Student.Sno = SC.Sno；,选择操作的实现,1. 简单的全表扫描方法 对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出 适合小表，不适合大表2. 索引(或散列)扫描方法 选择条件中的属性上有索引(例如B+树索引或Hash索引) 通过索引先找到满足条件的元组指针，再通过元组指针直接在查询的基本表中找到元组,选择操作的实现,索引表,连接操作的实现,连接操作是查询处理中最耗时的操作之一 SELECT * FROM Student inner join SC on Student.Sno = SC.Sno；,连接操作的
4、实现,嵌套循环方法(nested loop)对外层循环(Student)的每一个元组，检索内层循环(SC)中的每一个元组检查这两个元组在连接属性(sno)上是否相等如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止,连接操作的实现,2. 排序-合并方法(sort-merge join 或merge join) 常用算法，尤其适合连接的诸表已经排好序的情况,95001 王三95002 王四95003 王五95004 王六.,95001 1 9295001 2 8595001 3 8895003 2 9095003 3 80.,连接操作的实现,3. 索引连接(index jo
5、in)方法步骤：如果SC表的属性Sno上原来没有索引，在SC表的属性Sno上建立索引， 对Student中每一个元组，由Sno值通过SC的索引查找相应的SC元组 把这些SC元组和Student元组连接起来 循环执行，直到Student表中的元组处理完为止,连接操作的实现,4. Hash Join方法 把连接属性作为hash码，选用同一个hash函数,95001 1 9295001 2 8595001 3 8895002 2 9095002 3 8095003 1 75.,95001,95001 1 9295001 2 8595001 3 88,95002,95002 2 9095002 3 8
6、0,95003,95003 1 75,9.2 关系数据库系统的查询优化,关系数据库系统的查询优化,关系语言（关系代数，关系演算语言和SQL语言）是一个非过程化的语言，用户只要提出“干什么”，不必指出“怎么干”。SELECT sname FROM Student inner join SC on Student.SNO=SC.SNO where SC.CNO=2,关系数据库系统的查询优化,(1) 优化器可以从数据字典中获取许多统计信息，而用户则难以获得这些信息(2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。(3)优化器可以考虑数百种不同的执行计划，程序员一
7、般只能考虑有限的几种可能性。(4)优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术,关系数据库系统的查询优化,RDBMS通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案查询执行方案的代价集中式数据库总代价 = I/O代价 + CPU代价 + 内存代价分布式数据库总代价 = I/O代价 + CPU代价 + 内存代价 + 通信代价,9.3 代数优化,代数优化,代数优化策略：通过对关系代数表达式的等价变换来提高查询效率 关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相
8、同的两个关系表达式E1和E2是等价的，可记为E1E2,关系代数的等价变换规则,连接、笛卡儿积的交换律E1E2E2E1E1E2E2E1E1E2E2E1 其中F为连接运算条件 、的结合律(E1E2)E3E1(E2E3)(E1E2) E3E1(E2E3)(E1E2) E3E1 (E2E3),F,F,F1,F2,F1,F2,关系代数的等价变换规则,投影串接定律A1,A2, , An(B1,B2, , Bm(E)A1,A2, , An(E)其中：1) E是关系代数表达式2)Ai(i=1, 2, , n), Bj(j=l, 2, , m)是属性名3)A1, A2, , An构成Bl, B2, , Bm的子
9、集Sname,sage( Sname,sno,sage(Student) )Sname,sage(Student),关系代数的等价变换规则,选择串接定律F1(F2(E)F1F2(E)SC.Grade60 (SC.Cno=2(SC) ) SC. Grade60 SC.Cno =2 (SC) ),关系代数的等价变换规则,选择与投影的交换律F(A1,A2, , An(E) A1,A2, , An(F(E)其中F涉及A1,A2,An中的部分属性。SC.Grade60 (SC.Sno, SC.Grade(SC) SC.Sno,SC.Grade ( SC.Grade60 (SC),关系代数的等价变换规则,
10、 与笛卡尔积的交换律1：若F中只涉及E1中的属性，则F(E1E2) F(E1)E2SC.Cno=2(SCStudent) SC.Cno=2(SC) Student2：若F=F1F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则F(E1E2)F1F2(E1E2) F1(E1)F2(E2)SC.Cno=2 sdept = IS(StudentSC) sdept = IS(Student)SC.Cno=2(SC),关系代数的等价变换规则, 与笛卡尔积的交换律3：若F=F1F2，并且F1只涉及E1中的属性，F2涉及E1和E2中的属性，则F(E1E2) F1 F2(E1E2) F2(F1(E1
11、)E2)使部分选择在笛卡儿积前先做。,关系代数的等价变换规则, 与的交换律设E=E1E2, 且E1与E2有相同的属性名，则F(E1E2)F(E1)F(E2),A=2(E1E2),A=2(E1)A=2(E2),关系代数的等价变换规则,与差的分配律若E1与E2有相同的属性名，则F(E1-E2)F(E1)- F(E2)与的分配律若E1与E2有相同的属性名，则F(E1 E2)F(E1) F(E2),关系代数的等价变换规则, 与的分配律设E1和E2是两个关系表达式，A1, , An是E1的属性，B1, , Bm是E2的属性,则A1, , An, B1, , Bm(E1E2)A1 , , An(E1)B1
12、 , , Bm(E2) 与的分配律设E1与E2有相同的属性名，则A1, , An (E1E2)A1, , An(E1) A1, , An (E2),查询树的启发式优化,驾驶汽车到达某人的家，写成算法是这样的：沿167 号高速公路往南行至阳谷；从阳谷高速出口出来后往山上开4.5 英里；在一个杂物店旁边的红绿灯路口右转，接着在第一个路口左转；从左边褐色大房子的车道进去，就是某人的家。启发式方法来描述则可能是这样：找出上一次我们寄给你的信，照着信上面的寄出地址开车到这个镇；到了之后你问一下我们的房子在哪里。这里每个人都认识我们肯定有人会很愿意帮助你的；如果你找不到人，那就找个公共电话亭给我们打电话，
13、我们会出来接你。,查询树的启发式优化,简而言之，启发式是一种经验性的指导原则，依靠好的启发式，我们可以大得到进行高效，快速的问题求解。,查询树的启发式优化,典型的启发式规则：1. 选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条2. 把投影运算和选择运算同时进行如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系。,查询树的启发式优化,典型的启发式规则：3. 把投影同其前或其后的双目运算结合起来4. 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算Studnet.Sno=SC.Sno (StudnetSC)Stu
14、dnet SC,查询树的启发式优化,典型的启发式规则：5. 找出公共子表达式如果这种重复出现的子表达式的结果不是很大的关系并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的,查询树的启发式优化,算法：关系表达式的优化输入：一个关系表达式的查询树输出：优化的查询树,查询树的启发式优化,算法步骤：查询选修了2号课的学生学号、姓名以及该门课的成绩sno,sname,grade(SC.Cno=2Studnet.Sno=SC.Sno(StudentSC),查询树的启发式优化,算法步骤：1、利用规则把形如F1 F2 Fn (E)变换为F1(F2(Fn
15、(E)sno,sname,grade(Studnet.Sno=SC.SnoSC.Cno=2(StudentSC)sno,Sname,grade(SC.Cno=2(Studnet.Sno=SC.Sno(StudentSC),查询树的启发式优化,算法步骤：2、对每一个选择，利用规则尽可能把它移到树的叶端。,查询树的启发式优化,算法步骤：3、对于每一个投影，利用规则，尽可能把它移到树的叶端。,查询树的启发式优化,算法步骤：4、利用规则、 、 把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。 sage18 ( sdept = IS (Student) sage18 sdept = IS (Student),
