关系查询处理和查询优化

《关系查询处理和查询优化》由会员分享，可在线阅读，更多相关《关系查询处理和查询优化（58页珍藏版）》请在金锄头文库上搜索。

1、第九章 关系查询处理和查询优化授课内容 9.1 关系数据库系统的查询处理 9.2 关系数据库系统的查询优化 9.3 代数优化 9.4 物理优化9.1 关系数据库系统的查询处理 查询处理步骤 RDBMS查询处理阶段 ： 1. 查询分析 2. 查询检查 3. 查询优化 4. 查询执行查询处理步骤 1. 查询分析对查询语句进行扫描，从查询语句中识 别出语言符号，如SQL关键字、数据库 对象名。 进行语法检查和语法分析，判断查询语 句是否符合SQL语法规则。查询处理步骤 查询检查根据数据字典对合法的查询语句进行语 义检查 根据数据字典中的用户权限和完整性约 束定义对用户的查询请求进行检查 检查通过后把

2、SQL查询语句转换成等价 的关系代数表达式 RDBMS一般都用查询树(语法分析树)来 表示扩展的关系代数表达式 查询处理步骤 查询优化 每个查询都会有多个可供选择的执行策 略，查询优化就是选择一个高效率的执 行策略 查询优化分类 ： 代数优化：指关系代数表达式的优化 物理优化：指存取路径和底层操作算法 的选择查询处理步骤 查询执行 依据优化器得到的执行策略生成查询计 划 代码生成器(code generator)生成执行查 询计划的代码实现查询操作的算法示例 1. 选择操作的实现 SELECT * FROM Student where sno = 95006 2. 连接操作的实现 SELECT

3、 * FROM Student inner join SC on Student.Sno = SC.Sno；选择操作的实现 1. 简单的全表扫描方法 对查询的基本表顺序扫描，逐一检查每 个元组是否满足选择条件，把满足条件 的元组作为结果输出 适合小表，不适合大表 2. 索引(或散列)扫描方法 选择条件中的属性上有索引(例如B+树 索引或Hash索引) 通过索引先找到满足条件的元组指针， 再通过元组指针直接在查询的基本表中 找到元组 选择操作的实现snosname ssex sage sdept 95007 李勇7男20IS 95003 李勇3男20IS 95001 李勇1男20IS 95002

4、 李勇2男20CS 95005 李勇5男20IS 95004 李勇4男20CS 95006 李勇6男20IS1756243物理95007950069500595004950039500295001sno物理 1 2 3 4 5 6 7索引表连接操作的实现 连接操作是查询处理中最耗时的操作之一 SELECT * FROM Student inner join SC on Student.Sno = SC.Sno；连接操作的实现 嵌套循环方法(nested loop) 对外层循环(Student)的每一个元组，检 索内层循环(SC)中的每一个元组 检查这两个元组在连接属性(sno)上是否 相等 如

5、果满足连接条件，则串接后作为结果 输出，直到外层循环表中的元组处理完 为止 连接操作的实现 2. 排序-合并方法(sort-merge join 或merge join) 常用算法，尤其适合连接的诸表已经排 好序的情况95001 王三 95002 王四 95003 王五 95004 王六.95001 1 92 95001 2 85 95001 3 88 95003 2 90 95003 3 80.连接操作的实现 3. 索引连接(index join)方法 步骤： 如果SC表的属性Sno上原来没有索引 ，在SC表的属性Sno上建立索引， 对Student中每一个元组，由Sno值通 过SC的索引查

6、找相应的SC元组 把这些SC元组和Student元组连接起 来 循环执行，直到Student表中的元组 处理完为止连接操作的实现 4. Hash Join方法 把连接属性作为hash码，选用同一个hash函 数95001 1 92 95001 2 85 95001 3 88 95002 2 90 95002 3 80 95003 1 75.9500195001 1 92 95001 2 85 95001 3 889500295002 2 90 95002 3 809500395003 1 759.2 关系数据库系统的查询优化 关系数据库系统的查询优化 关系语言（关系代数，关系演算语言和 SQL

7、语言）是一个非过程化的语言，用户 只要提出“干什么”，不必指出“怎么干”。 SELECT sname FROM Student inner join SC on Student.SNO=SC.SNO where SC.CNO=2关系数据库系统的查询优化 (1) 优化器可以从数据字典中获取许多统计信息 ，而用户则难以获得这些信息 (2)如果数据库的物理统计信息改变了，系统可 以自动对查询重新优化以选择相适应的执行计 划。 (3)优化器可以考虑数百种不同的执行计划，程 序员一般只能考虑有限的几种可能性。 (4)优化器中包括了很多复杂的优化技术，这些 优化技术往往只有最好的程序员才能掌握。系 统的自

8、动优化相当于使得所有人都拥有这些优 化技术关系数据库系统的查询优化 RDBMS通过某种代价模型计算出各种查 询执行策略的执行代价，然后选取代价最 小的执行方案 查询执行方案的代价 集中式数据库 总代价 = I/O代价 + CPU代价 + 内存 代价 分布式数据库 总代价 = I/O代价 + CPU代价 + 内存 代价 + 通信代价 9.3 代数优化 代数优化 代数优化策略：通过对关系代数表达式的 等价变换来提高查询效率 关系代数表达式的等价： 指用相同的关系代替两个表达式中相应 的关系所得到的结果是相同的 两个关系表达式E1和E2是等价的，可记 为E1E2关系代数的等价变换规则 连接、笛卡儿积

9、的交换律 E1E2E2E1 E1E2E2E1 E1E2E2E1 其中F为连接运算条件 、的结合律 (E1E2)E3E1(E2E3) (E1E2) E3E1(E2E3) (E1E2) E3E1 (E2E3) FFF1F2F1F2关系代数的等价变换规则 投影串接定律 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的 子集 Sname,sage( Sname,sno,sage(Student) )

10、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)关系代数的等价变换规则 与笛卡尔积的交换律 1：若F中只涉及E1中的属性，则 F(E1E2)

11、 F(E1)E2 SC.Cno=2(SCStudent) SC.Cno=2(SC) Student 2：若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)E2) 使部分选择在笛卡儿积前先做。关系代数的等价变

12、换规则 与的交换律 设E=E1E2, 且E1与E2有相同的属性名 ，则 F(E1E2)F(E1)F(E2)c1b23c2b22c1b11CBAc1b21c2b32c2b22CBAE1E2A=2(E1E2)c1b23c2b32c2b22CBAA=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,

13、 , An, B1, , Bm(E1E2) A1 , , An(E1)B1 , , Bm(E2) 与的分配律 设E1与E2有相同的属性名，则 A1, , An (E1E2) A1, , An(E1) A1, , An (E2)查询树的启发式优化 驾驶汽车到达某人的家，写成算法是这样的： 沿167 号高速公路往南行至阳谷；从阳谷高速 出口出来后往山上开4.5 英里；在一个杂物店旁 边的红绿灯路口右转，接着在第一个路口左转 ；从左边褐色大房子的车道进去，就是某人的 家。 启发式方法来描述则可能是这样：找出上一次 我们寄给你的信，照着信上面的寄出地址开车 到这个镇；到了之后你问一下我们的房子在哪 里

14、。这里每个人都认识我们肯定有人会很 愿意帮助你的；如果你找不到人，那就找个公 共电话亭给我们打电话，我们会出来接你。 查询树的启发式优化 简而言之，启发式是一种经验性的指导原则， 依靠好的启发式，我们可以大得到进行高效， 快速的问题求解。 查询树的启发式优化 典型的启发式规则： 1. 选择运算应尽可能先做。在优化策略 中这是最重要、最基本的一条 2. 把投影运算和选择运算同时进行如有若干投影和选择运算，并且它们 都对同一个关系操作，则可以在扫描 此关系的同时完成所有的这些运算以 避免重复扫描关系。查询树的启发式优化 典型的启发式规则： 3. 把投影同其前或其后的双目运算 结合起来 4. 把某些选择同在它前面要执行的 笛卡尔积结合起来成为一个连接运 算 Studnet.Sno=SC.Sno (StudnetSC) Studnet SC查询树的启发式优化 典型的启发式规则： 5. 找出公共子表达式如果这种重复出现的子表达式的结果 不是很大的关系并且从外存中读入这 个关系比计算该子表达式的时间少得 多，则先计算一次公共子表达式并把 结果写入中间文件是合算的查询树的启发式优化 算法：关系表达式的优化 输入：一个关系表达式的查询树 输出：优化的查询树查询树的启发式优化 算法步骤： 查询选修了2号课的学生学号、姓名以 及该门课的成绩 sno,sname,grad