《关系查询处理和查询优化课件》由会员分享，可在线阅读，更多相关《关系查询处理和查询优化课件（48页珍藏版）》请在金锄头文库上搜索。
1、An Introduction to Database System,上海第二工业大学 计算机与信息学院,数据库系统概论 An Introduction to Database System 第九章 关系查询处理和查询优化,An Introduction to Database System,第九章 关系查询处理和查询优化,9.1 关系数据库的查询处理 9.2 关系数据库系统的查询优化 9.3 代数优化 9.4 物理优化,An Introduction to Database System,9.1 关系数据库的查询处理,9.1.1 查询处理的步骤 查询分析：对查询语句进行语法和词法分析 查询检
2、查： 检查语义：语句中使用的对象的存在性和有效性 用户权限和和完整性检查 检查通过后，把查询语句转换成等价的关系代数表达式（查询树即语法分析树）,An Introduction to Database System,语法分析树：,An Introduction to Database System,查询优化：选择一个高效的查询处理策略，方法有代数优化、物理优化，选择的依据有基于规则、基于代价或基于语义 执行查询：依据优化器得到的策略生成查询计划，由代码生成器生成可执行代码。,An Introduction to Database System,9.1.2 实现查询操作的算法示例,1.选择操作的
3、常用算法 全表扫描，选出符合条件的元组 使用索引可快速获取符合选择条件的元组指针，如sage=20或sage20。 组合条件如：sage20 and sdept=CS 方法1：分别选出符合sage20条件的元组指针和符合sdept=CS条件的元组指针，然后求它们的交集 方法2：先选出符合sage20条件的元组指针，然后对选出的元组判断是否符合sdept=CS条件。 第一种方法在sage和sdept上均有索引的情况下比较有效，第二种方法应该优先选出选择条件中有索引的元组。,An Introduction to Database System,2.连接操作的常用算法（假定为等值连接）： Selec
4、t a.sno,a.sname,o,b.grade from student a,sc b where a.sno=b.sno 连接的总体思路：扫描student，对每一元组的sno，扫描grade的sno，把相同值的元组和student对应元组进行连接后输出。,An Introduction to Database System,循环嵌套方法：嵌套扫描两个表，总循环次数为两个元组个数的乘积。 排序-合并方法：根据两个表的sno进行排序，两个循环均不必进行全表扫描。效率大大提高。 索引连接方法：对sc关于sno建立索引，内层循环中由于sc建立的索引，所以不必全表扫描。,An Introduct
5、ion to Database System,Hash join方法：适用大表和小表的连接 1 依据Hash函数把小表数据放入内存（可保留少量数据在临时表空间中）（小表数据的一次扫描） 2 每读取大表的一条记录（大表数据的一次扫描） ，就和小表中内存中的数据进行比较（有了hash函数，比较就不需要扫描小表），如果符合，则立即输出数据。而如果大表的数据与小表中临时表空间的数据相符合，先不输出，而等大表的所有数据都读取完毕，才一起输出（减少读取硬盘的次数）。 3.Hash Join方法只需要对两个表进行一次扫描，并且极大地降低了读取硬盘的次数。,An Introduction to Databas
6、e System,9.2.1 查询优化概述,查询效率是衡量RDBMS重要性能指标。 RDBMS通过查询优化提升查询效率。 关系的结构化查询语言SQL高级别的语义（只需指出做什么而不必给出怎么做），使RDBMS进行查询优化成为可能。 RDBMS的查询优化，使用户不必考虑如何最好地表达查询以获得较好的效率。,An Introduction to Database System,系统进行优化较用户优化的优势：,优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息。 如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划而不必重写程序。 优化器可以考虑数百种不
7、同的执行计划，而程序员一般只能考虑有限的几种可能性。 优化器中包括了很多复杂的优化技术。,An Introduction to Database System,查询优化目标,查询优化的总目标 选择有效策略，求得给定关系代数表达式的值（关系），使得查询代价最小。 查询执行策略的代价构成： 总代价=I/O代价 + CPU代价 + 内存代价 + 通信代价,An Introduction to Database System,9.2.2 查询优化的必要性,例：求选修了课程2的学生姓名 SELECT Student.Sname FROM Student, SC WHERE Student.Sno=SC.
8、Sno AND SC.Cno=2; 以下考察不同的执行策略对数据读写上需要的时间,An Introduction to Database System,查询优化的必要性（续）,假设： 1：Student:1000条，SC:10000条， 选修2号课程:50条 2：一个内存块可存放元组:10个Student，或100个SC，内存容量可以存放: 5块Student元组、 1块SC元组和若干块连接结果元组 3：读写速度：20块/秒 4：连接方法：基于数据块的嵌套循环法,An Introduction to Database System,执行策略1:笛卡尔积、选择、投影,Q1sname(Studen
9、t.Sno=SC.SnoSC.Cno=2 (StudentSC) StudentSC： 读取总块数= 读Student表块数 + 读SC表遍数 *每遍块数 =1000/10+(1000/(105) (10000/100) =100+20100=2100 读数据时间=2100/20=105秒,每次可读student的10X5个元组，然后以块为单位读入全部SC，产生笛卡尔积,An Introduction to Database System,中间结果大小 = 1000*10000 = 107 写中间结果时间 = 10000000/10/20 = 50000秒 （假设每个内存块可存放10个元组的中
10、间结果） 读数据时间 = 50000秒 总时间 =1055000050000秒 = 100105秒 = 27.8小时,An Introduction to Database System,执行策略2：自然连接、选择、投影,2. 2 name(SC.Cno= 2 (Student SC) 读取总块数= 2100块 读数据时间=2100/20=105秒 中间结果大小=10000 （减少1000倍） 写中间结果时间=10000/10/20=50秒 读数据时间=50秒 时间1055050秒205秒=3.4分,An Introduction to Database System,执行策略3：选择、自然连
11、接、投影,3. 3 Sname(Student SC.Cno= 2 (SC) 读SC表总块数= 10000/100=100块 读数据时间=100/20=5秒 中间结果大小=50条 不必写入外存 读Student表总块数= 1000/10=100块 读数据时间=100/20=5秒 总时间55秒10秒,An Introduction to Database System,9.3 代数优化,关系代数表达式：关系代数运算符经过有限次复合后得到的式子，其值仍为关系。（P60） 关系代数表达式等价：即关系代数表达式E1和E2中代入相同的关系，其结果相同，记为：E1E2。,An Introduction t
12、o Database System,9.3.1 关系代数表达式等价变换规则,设E1、E2等是关系代数表达式，F是条件表达式 l. 连接、笛卡尔积交换律 E1 E2 E2E1 E1 E2E2 E1 E1 F E2E2 F E1,An Introduction to Database System,关系代数等价变换规则（续）,2. 连接、笛卡尔积的结合律 (E1E2) E3 E1 (E2E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) F1 F2 F1 F2,An Introduction to Database System,关系代数等价变换规则（续
13、）,3. 投影的串接定律 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的子集,An Introduction to Database System,关系代数等价变换规则（续）,4. 选择的串接定律 F1 （ F2（E） F1 F2(E) 选择的串接律说明选择条件可以合并 这样一次就可检查全部条件。,An Introduction to Database System,关系代数等价变换规则（续）,5. 选择与投影的
14、交换律 (1)假设: 选择条件F只涉及属性A1，An F (A1,A2, ,An(E) A1,A2, ,An(F(E) (2)假设: F中有不属于A1, ,An的属性B1,Bm A1,A2, ,An ( F (E) A1,A2, ,An(F (A1,A2,An,B1,B2, ,Bm(E),An Introduction to Database System,关系代数等价变换规则（续）,6. 选择与笛卡尔积的交换律 (1) 假设：F中涉及的属性都是E1中的属性 F (E1E2)F (E1)E2 (2) 假设：F=F1F2，并且F1只涉及E1中的属性， F2只涉及E2中的属性，则由上面的等价变换规
15、则1，4，6可推出： F(E1E2) F1(E1)F2 (E2),An Introduction to Database System,关系代数等价变换规则（续）,(3) 假设： F=F1F2，F1只涉及E1中的属性，F2涉及E1和E2两者的属性，则： F(E1E2) F2(F1(E1)E2) 7. 选择与并的交换 假设：E=E1E2，E1，E2有相同的属性名 F(E1E2) F(E1) F(E2) 8. 选择与差运算的交换 假设：E1与E2有相同的属性名 F(E1-E2) F(E1) - F(E2),An Introduction to Database System,关系代数等价变换规则（续）,9. 投影与笛卡尔积的交换 假设：E1和E2是两个关系表达式， A1，An是E1的属性， B1，Bm是E2的属性 A1,A2, ,An,B1,B2, ,Bm （E1E2) A1,A2, ,An（E1) B1,B2, ,Bm(E2),An Introduction to Database System,关系代数等价变换规则（续）,l0. 投影与并的交换 假设：E1和E2 有相同的属性名： A1,A2, ,An(E1E2)
