2014第八章-查询处理与优化

第六章查询处理与查询优化课程安排查询优化查询优化的必要性关系表达式的转换启发式优化临时关系大小估计基于代价的优化查询处理查询处理过程概述典型索引结构选择运算的查询处理连接运算的查询处理临时关系处理查询处理过程概述查询关系代数表达式执行计划查询结果数据基于数据的统计分析优化器分析器&翻译器评价引擎DBMS查询处理过程概述应用程序用户工作区数据库管理系统O.S.数据字典系统缓冲区数据库(7)(1)(12)(2)(3)(11)(10)(5)(8)(9)(6)(4)DBMS运行过程查询处理过程概述关系名别名建立者属性个数记录长度记录总数属性定义指针视图定义指针视图属性指针基关系指针视图表达式指针关系定义表视图表属性名类型长度记录内偏址完整性定义指针属性表达式指针视图属性名基关系属性指针属性表达式指针视图属性表用户名口令用户表用户名数据对象名数据对象类型操作权限存取谓词视图名表达式语法树根指针用户权限表属性表视图表达式表数据字典部分示意图典型索引结构Hash索引B+树索引典型索引结构—Hash索引散列函数以查找键为参数并计算出一个介于0到B-1的整数，其中B是桶的数目。当键为整数时常见的选择是计算Key/B的余数，通常B选为一个素数，也可以选2的幂。当键Key为字符串时，可以把每个字符看作一个整数来处理，将它们累加起来再除以B取余数。典型索引结构—Hash索引附加信息，如连接其它存储块例如h(x)=x%B;B=3;h(3)=h(6)=0;h(4)=h(7)=1;h(2)=h(5)=h(8)=2;索引项21036…47…258…数据项典型索引结构—B+树索引对应B树索引都有一个参数n，决定存储块的布局。每个存储块存放n个查找健值和n+1个指针173155内部节点叶子节点节点节点节点节点172330记录记录记录314052典型索引结构—B+树索引1015182022233133454852例如三层索引：255指针/块255子结点255X255叶子节点可索引约16M记录33182333选择运算的查询处理查询实例select*fromStudentswhere条件表达式;条件表达式的几种情况C1：无条件C2：Sno=‘2011003’;C3：Sage20;C4：Sdept=‘CS’andSage20;选择运算的查询处理—C1查询实例select*fromStudents;全表顺序扫描优点：简单有效2011001,…2011002,…2011003,…2011004,…2011005,……Students选择运算的查询处理—C22011001,…2011002,…2011003,…2011004,…2011005,……Students查询实例select*fromStudentswhereSno=‘2011003’;Sno是主码内存中磁盘上选择条件的属性上有索引索引/散列扫描选择运算的查询处理—C2查询实例select*fromStudentswhereSno=‘2011003’;选择条件的属性上有索引索引/散列扫描等值查询：使用索引得到符合等值条件的指针范围查询：仅适用于B+树索引选择运算的查询处理—C3查询实例select*fromStudentswhereSage20;选择条件是范围查询或非等值查询，或非主属性=值的查询查询结果数目不明确估算查询结果的元组数量如果查询结果的元组数量10%，且选择列上有索引使用索引/散列扫描否则，使用全表顺序扫描选择运算的查询处理—C4查询实例select*fromStudentswhereSdept=‘CS’andSage20;SdeptSage2011001,21,CS,…2011002,19,MA,…2011003,22,CS,…2011004,20,CS,…2011005,21,IS,……选择运算的查询处理—C4查询实例select*fromStudentswhereSdept=‘CS’andSage20;合取选择查询分别找到符合各个条件的元组指针，取指针的交集；或者找到符合第一个条件的元组指针，在此范围内检查另一条件是否满足析取选择查询：使用全表顺序扫描连接运算的查询处理查询实例select*fromStudents,SCwhereStudents.Sno=SC.Sno;嵌套循环方法（nestedloop）StudentsSC...外循环表内循环表2011001,…2011002,…2011003,…2011004,…2011005,……2011003,1…2011003,2…2011004,2...2011004,3...2011001,1…...选择占用内存块较少的表作为外表连接运算的查询处理查询实例select*fromStudents,SCwhereStudents.Sno=SC.Sno;排序-合并方法（sort-mergejoin或mergejoin）StudentsSC2011001,…2011002,…2011003,…2011004,…2011005,……2011001,1,852011003,2,942011003,2,872011004,3,652011004,1,92......连接的关系分别排序连接运算的查询处理查询实例select*fromStudents,SCwhereStudents.Sno=SC.Sno;索引连接方法（indexjoin）StudentsSC2011003,…2011002,…2011004,…2011001,…2011005,……2011003,2,942011003,2,872011004,3,652011004,1,922011001,1,85......201100120110032011004...SC上建立Sno的索引连接运算的查询处理查询实例select*fromStudents,SCwhereStudents.Sno=SC.Sno;Hash连接方法（Hashjoin）StudentsSC2011003,…2011002,…2011004,…2011001,…2011005,……2011003,2,942011003,2,872011004,3,652011004,1,922011001,1,85...20110012011004(1)20110022011005(2)2011003(0)为小表建Hash桶对大表顺序扫描临时关系的处理临时关系物化（materialized）计算结果被存储在临时关系中流水线（pipeline）减少查询执行中产生的临时文件数量将多关系操作组合成一个操作的流水线临时关系物化--查询树查询树的结构叶子节点–关系非叶子节点–临时关系(用关系操作表示)根节点–最终输出结果查询树的运算自底向上内存不够时：临时关系必须被写硬盘SnameStudentsSCSage20Sname(Sage〉20(Students)SC)流水线查询优化由系统完成,而不是由用户完成优化器从数据字典获取统计信息如果数据库的物理统计信息改变了,优化器重新优化,选择适应的执行计划优化器可以考虑数百种不同的执行计划优化器包括了许多复杂的技术关系系统的查询优化查询执行开销主要包括集中式数据库总代价=I/O代价+CPU代价+内存代价分布式数据库总代价=I/O代价+CPU代价+内存代价+通信代价优化目标寻求最优的执行计划使查询执行开销尽量小查询优化的必要性查询实例:求选修2号课程的学生姓名SQL表示:selectSnamefromStudents,SCwhereStudents.Sno=SC.SnoandCno=‘2’;数据库模式的样例Students(Sno,Sname,Ssex,Sage,Sdept)Courses(Cno,Cname,Cpno,Credit)SC(Sno,Cno,Grade)查询优化的必要性查询实例:求选修2号课程的学生姓名SQL表示:selectSnamefromStudents,SCwhereStudents.Sno=SC.SnoandCno=‘2’;关系代数表示:Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))Q2=sname(Cno=‘2’(StudentsSC))Q3=sname(StudentsCno=‘2’(SC))功能相等，查询性能差别大查询优化的必要性问题1：如何衡量查询性能？关系代数表示:Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))Q2=sname(Cno=‘2’(StudentsSC))Q3=sname(StudentsCno=‘2’(SC))功能相等，查询性能差别大查询请求查询结果数据DBMSO.S.查询结果查询优化的必要性问题2：如何比较查询性能？关系代数表示:Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))Q2=sname(Cno=‘2’(StudentsSC))Q3=sname(StudentsCno=‘2’(SC))功能相等，查询性能差别大实际测试的方法不可行缺点1：实际测试需要花费时间缺点2：关系代数很难枚举查询请求数据DBMSO.S.查询优化的必要性问题2：如何比较查询性能？关系代数表示:Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))Q2=sname(Cno=‘2’(StudentsSC))Q3=sname(StudentsCno=‘2’(SC))功能相等，查询性能差别大实际测试的方法不可行缺点1：实际测试需要花费时间缺点2：很难枚举所有的关系代数查询处理的一般步骤snosnamessexsagesdeptStudentsnocnogradeSC内存（DBMS驻留）硬盘/外存StudentsSC硬盘的数据以何种形式被加载到内存中？内存是否足够大？查询处理的一般步骤snosnamessexsagesdeptStudentsnocnogradeSC内存（DBMS驻留）硬盘/外存StudentsSC第1步:加载数据10个Students元组10个Students元组10个Students元组10个Students元组10个Students元组100个SC元组第2步:内存中进行关系操作第3步:输出最终结果;或产生临时结果,写回硬盘,重复1-2步1000个元组10000个元组选2号课程的有50个元组主要考虑I/O代价对关系代数Q1的估算Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))内存（DBMS驻留）Student块数SC读入的次数SC块数硬盘到内存：读取的总块数假设每秒读写20块,则花费s105202100①求笛卡尔集的花费10个Students元组10个Students元组10个Students元组10个Students元组10个Students元组100个SC元组对关系代数Q1的估算Q1=sname(Students.Sno=SC.SnoandCno=‘2’(StudentsSC))内存（DBMS驻留）10个Students元组10个Students元组10个Students元组10个Students元组10个Students元组100个SC元组②内存到硬盘：写笛卡尔集中间结果的总花费若每块可装10个完成迪卡尔集后的元组,则写这些元组需:(107/10)/20=5104s③选择操作的花费:载入中间结果需要5104s④投影操作的花费:假设选择后剩的50个元组均可放入内存，因此只需要CPU时间查询总花费：105+25104105