查询处理与查询代价估计PPT课件

查询处理与查询代价估计,1,.,目录,查询处理1、查询分析2、查询优化3、查询执行,查询代价估计,2,.,查询处理,3,.,查询处理,查询处理是指从数据库中提取数据的一系列活动。包括：1、将用高层数据库语言表示的查询语句翻译成文件系统这一物理层次上实现的表达式；2、为优化查询进行各种转换；3、查询的实际执行。,4,.,查询处理过程,关系代数表达式,5,.,查询分析,在数据库执行查询处理之前，系统先将查询语句翻译成可使用的形式。翻译过程：1、语法分析器将查询翻译成系统内部表示形式；2、翻译的同时进行语法检查；3、构造查询语句的语法分析树；4、翻译成关系代数表达式。对于给出的一个查询，一般经过翻译器翻译后都会有多种关系代数表达式与之对应。,6,.,查询分析实例,查询实例:求选修2号课程的学生姓名SQL表示:selectSnamefromStudents,SCwhereStudents.Sno=SC.SnoandCno=2；翻译结果：Q1=Sname(Student.Sno=SC.SnoSc.Cno=2(StudentSC)Q2=Sname(Sc.Cno=2(StudentSC)Q3=Sname(StudentSc.Cno=2(SC),7,.,优化器功能,功能：负责产生最有效的查询执行计划（QEP）逻辑转换部分：对于一个语法树，根据关系代数等价变换规则，得到所有的等价的关系代数表达式；物理转换部分：对于每一个关系代数表达式，根据查询引擎提供的物理操作，找出所有可能的查询执行计划。比较和查找：根据代价估计函数，估计每一个查询执行计划的代价，并从中找出代价最小的查询执行计划。,8,.,优化器处理过程,查询请求,等价变换规则集,逻辑转换,物理转换,物理操作集,查找,代价估计函数,代价最小QEP,等价的语法树集合,等价的QEP,9,.,查询执行引擎,功能：查询执行引擎为每一个关系操作的实现提供多种物理实现方法。选择操作有两种可能的物理操作：顺序扫描和索引扫描连接操作有三种可能的物理操作：嵌套循环连接、合并连接和散列连接。查询执行引擎还可以提供更多的物理实现方法。每一种物理实现方法利用不同的存取路径（如索引、数据的存储分布、元组的排序等）负责产生执行查询的代码,10,.,查询代价的估计,11,.,查询的代价,查询执行开销主要包括集中式数据库总代价=I/O代价+CPU代价+内存代价分布式数据库总代价=I/O代价+CPU代价+内存代价+通信代价查询代价主要取决于磁盘访问的次数。一个给定的查询，对应多种可能的处理策略。策略不同，访问磁盘的次数相差很大，甚至相差几个数量级。,12,.,查询代价的度量,对于大型数据库系统而言，在磁盘上存取数据的代价通常是最重要的代价，可以通过传输磁盘块数以及搜索磁盘次数来度量。使用tT表示传输一块数据的平均耗时，tS表示搜索一次磁盘的平均定位时间(包括搜索时间加旋转时间)。则一个传输b块并作s次磁盘搜索的操作将耗时b*tT+s*tS毫秒(ms)写磁盘块的代价通常是读磁盘块的2倍执行计划所需挂钟时间,13,.,用于代价估算的统计信息,相关的统计信息主要包括：nr：关系r中的元组数目。br：用于存储关系r所有元组的块数目。sr：关系r中一个元组的大小。fr：关系r的块因子，即一个物理块中能存放的关系r的元组数目。V(A,r)：关系r中属性A所具有的不同值的数目，该数目与A(r)的大小相同。若A为关系r的码，则V(A,r)=nr。SC(A,r)：关系r关于属性A的选择度，表示在属性A上满足某个等值条件（假设至少有一条记录满足该等值条件）的平均记录数。,14,.,用于代价估算的统计信息,fi:索引i的内节点的平均扇出,适用于树结构索引,如B+树HTi:索引i的层数即高度对于关系r上A属性的平衡树索引(如B+-树),HTi=logfi(V(A,r)对于散列索引,HTi为1LBi:索引i的底层索引块数即索引叶子层的块数,15,.,查询代价估计举例,查询实例:求选修2号课程的学生姓名SQL表示:selectSnamefromStudents,SCwhereStudents.Sno=SC.SnoandCno=2;数据库模式的样例Students(Sno,Sname,Ssex,Sage,Sdept)SC(Sno,Cno,Grade)假定学生-课程数据库中有1000个学生记录，10000个选课记录其中选修2号课程的选课记录为50个,16,.,可能的语句翻译结果,Q1=Sname(Student.Sno=SC.SnoSc.Cno=2(StudentSC)Q2=Sname(Sc.Cno=2(StudentSC)Q3=Sname(StudentSc.Cno=2(SC),17,.,硬盘的数据以何种形式被加载到内存中？内存是否足够大？主要代价？,查询代价估计,Students,SC,硬盘/外存,18,.,查询处理的过程,Students,SC,硬盘/外存,第1步:加载数据,第2步:内存中进行关系操作,第3步:输出最终结果;或产生临时结果,写回硬盘,重复1-2步,第1步:加载数据,内存（DBMS驻留）,19,.,Q1代价估计,Q1关系代数语法树,1、笛卡尔集生产,硬盘到内存：读取的总块数=100+2000=2100块,假设每秒读写20块,则花费105s,连接后的元组数为103104=107。设每块能装10个元组，则写出这些块要用106/20=5104s,20,.,Q1代价估计,Q1关系代数语法树,2、选择操作,依次读入连接后的元组（107个），按照选择条件选取满足要求的记录假定内存处理时间忽略。读取中间文件花费的时间(同写中间文件一样)需5104s,21,.,Q1代价估计,Q1关系代数语法树,3.投影操作,把第2步的结果在Sname上作投影输出，得到最终结果执行查询的总时间105+25104105s（所有内存处理时间均忽略不计）,22,.,Q2代价估计,1、自然连接,执行自然连接，读取Student和SC表的策略不变，总的读取块数仍为2100块，花费105s；自然连接的结果比第一种情况大大减少，为104个；写出这些元组时间为104/10/20=50s；,23,.,Q2代价估计,2、选择运算,读取中间文件块104个元组，执行选择运算，花费时间为104/10/20=50s。,3、投影输出总的执行时间105+50+50205s,24,.,索引代价估计,Q3=Sname(StudentSc.Cno=2(SC)假如SC表的Cno字段上有索引第一步只需读取Cno=2的元组(50个)存取的索引块和SC中满足条件的数据块大约总共34块若Student表在Sno上也有索引第二步也不必读取所有的Student元组因为满足条件的SC记录仅50个，涉及最多50个Student记录读取Student表的块数也可大大减少总的存取时间将进一步减少到数秒,25,.,查询代价的优化,把代数表达式Q1变换为Q2，即有选择和连接操作时，先做选择操作，这样参加连接的元组就可以大大减少，这种优化是代数优化在索引中SC表的选择操作算法有全表扫描和索引扫描2种方法，经过初步估算，索引扫描方法较优，这种优化是物理优化,26,.,问题,数据库模式的样例Students(Sno,Sname,Ssex,Sage,Sdept)SC(Sno,Cno,Grade)假定学生-课程数据库中有1000个学生记录，10000个选课记录其中选修2号课程的选课记录