数据库课件第10章

数据库原理与设计兰州大学信息学院第十章查询处理和查询优化兰州大学信息科学与工程学院数据库原理与设计兰州大学信息学院IDM实验室第十章查询处理和查询优化查询处理器是DBMS的核心组成部分之一，主要接受用户的SQL查询语句，对语句进行语法分析和有效性检查，建立查询的内部表示——关系代数表达式或查询树，设计执行计划，选择执行得最快或代价最低的查询计划，执行该查询计划，得到查询结果。一般情况下，每个查询都会有很多侯选的执行计划，查询优化就是从中选择适当的但不一定是最优的查询处理策略的过程。数据库原理与设计兰州大学信息学院IDM实验室10.1查询处理数据库原理与设计兰州大学信息学院IDM实验室10.1查询处理查询处理器将为每个查询块制定若干执行计划。给定的查询的不同执行计划将有不同的执行代价。选定、构造具有最小查询执行计划代价的查询计划是系统来完成的。选定查询计划以后，便用该计划来执行查询并输出查询结果。数据库原理与设计兰州大学信息学院IDM实验室10.1查询处理数据库原理与设计兰州大学信息学院IDM实验室10.1.1查询代价的评估数据库原理与设计兰州大学信息学院IDM实验室为了实现可能出现在查询执行策略中的不同类型的关系操作，DBMS就必须包含实现这些操作的算法。对每一种操作或操作的组合，一般都会有一种或多种执行这个操作的算法。但是一种算法可能只适用于特定的存储结构或存取路径，只有当操作涉及的文件中包含特定的存取路径时，才能使用这种算法。下面分析实现选择、排序、连接和其他关系操作的典型算法和算法开销。数据库原理与设计兰州大学信息学院IDM实验室10.1.2选择操作选择操作就是从表中查找满足条件的记录,它是由文件扫描加上匹配选择的条件两个步骤所构成的搜索算法。1.选择操作的基本实现算法(1)线性查找的代价和实现方法(2)二分查找算法的代价和实现方法2.使用索引的选择操作(1)等值比较的B+树索引选择算法键属性等值比较非键属性等值比较(2)等值比较的哈希索引选择算法键属性等值比较非键属性等值比较数据库原理与设计兰州大学信息学院IDM实验室10.1.2选择操作3.具有比较的选择查询(1)主索引比较(2)辅助索引比较4.复杂查询的实现复杂查询是指在选择条件中有更复杂的选择谓词，包括合取、析取、取反、索引的合取、组合索引的合取等。合取：合取选择是形如析取：析取选择是形如取反：选择的结果就是关系R中对条件求值为假的记录的集合。如果没有空值的存在，该结果就是那些不在中的记录的集合。(1)无析取的选择(2)有析取的选择12()nR12()nR()R数据库原理与设计兰州大学信息学院IDM实验室10.1.3排序操作1.排序操作对于数据访问的意义2.排序的种类根据待排序的整个关系是否在内存的情况，分为外排序和内存中的排序。待排序的整个关系完全被内存容纳时，此时所使用的排序技术，如快速排序叫内存中的排序。对不能全部放在内存中的关系进行排序称为外排序。如外部归并算法。(1)两路归并排序算法数据库原理与设计兰州大学信息学院IDM实验室10.1.3排序操作输入：包含M个数据页的无序关系R，分成n个小文件输出：排序后的关系R过程：i=0；if(in){将子文件Ri读入内存进行排序；将排好序的子文件Ri写回磁盘；i++；}j=0；if(j2log1M){//2log1M为归并的趟数repeat{将两个未归并的子文件读入内存进行归并；将归并结果写回磁盘；}until(所有的段都两两归并)}j++；两路归并排序算法描述数据库原理与设计兰州大学信息学院IDM实验室10.1.3排序操作（2）N路归并排序算法输入：包含M个数据页的无序关系R，分成MB个小文件输出：排序后的关系R过程：i=0；if(iMB)then{将子文件Ri读入内存进行排序；将排好序的子文件Ri写回磁盘；i++；}j=0；if(1log1BjMB)then{//1log1BMB为归并趟数repeat{将B-1个未归并的子文件读入内存进行归并；将归并结果写回磁盘；）until（所有的段都已归并）}j++；N路归并排序算法描述数据库原理与设计兰州大学信息学院IDM实验室10.1.4连接操作1.满足不同条件的连接操作的处理方式和代价(1)嵌套循环连接输入：关系R和S，及它们的记录数NR，NS输出：满足连接条件ri=sj的记录集过程：for(i=0；iNR；i++)for(j=0；jNS；j++){测试记录对(ri，sj)是否满足连接条件ri=sj；如果满足，把ri，sj加到结果中；}嵌套循环算法描述数据库原理与设计兰州大学信息学院IDM实验室10.1.4连接操作（2）块嵌套循环连接按照缓冲区的大小，块嵌套循环连接算法可以分两种情况：第一种：假设有足够的内存可以容纳下其中较小的关系（比如R），并且还剩余至少两个额外的缓冲区页第二种：如果没有足够的内存可以容纳整个关系R时，可以把关系R按照缓冲区的大小等分成块，对R的每个块扫描关系S（3）使用索引的嵌套循环连接数据库原理与设计兰州大学信息学院IDM实验室10.1.4连接操作2.归并连接（排序归并连接）输入：关系R，S输出：满足连接条件ri=sj的记录集过程：ifR在属性i上无序then对关系R在属性i上进行排序；ifS在属性j上无序then对关系S在属性j上进行排序；Tr=关系R中的第一条记录；Ts=关系S中的第一条记录；Gs=关系S中的第一条记录；WhileTr≠eofandTs≠eofdo{WhileTriGsjdoTr=关系R中Tr后的下一条记录；WhileTriGsjdoGs=关系S中Ts后的下一条记录；Ts=Gs;WhileTri=Gsjdo{Ts=Gs;WhileTri=Tsjdo{将Tr,Ts添加都连接结果；Ts=关系S中Ts后的下一条记录；}Tr=关系R中Tr后的下一条记录；}Gs=Ts;}排序归并连接算法描述数据库原理与设计兰州大学信息学院IDM实验室10.1.4连接操作3.使用hash索引连接输入：关系R，S输出：满足连接条件ri=sj的记录集过程：//将关系R划分为k个部分foreach记录rinRdo{n=h(ri)；将ri添加到缓冲区Rn中；}//将关系S划分为k个部分foreach记录sinSdo{n=h(sj)；将sj添加到缓冲区Sn中；}//连接阶段forn=1，…，kdo{读Sn，在内存中建立起hash索引；foreach记录rinRndo{检索Sn的hash索引，定位所有满足ri=sj的记录；foreach匹配的记录sinSndo{把r，s加到结果中；}}}哈希索引连接算法描述数据库原理与设计兰州大学信息学院IDM实验室10.1.5其他操作1.复杂消重操作对于重复的记录，我们可以采用排序方法或者hash索引方法来消除重复。(1)使用外部归并排序来消重(2)使用hash索引来消重2.投影操作一般投影操作可以分为两步第一步：对每个记录作投影，清除不需要的属性值第二步：如果所得结果关系中有重复记录，删除重复记录3.集合操作集合操作R∪S、R∩S、R-S的实现有两种算法：一种基于排序，另外一种基于哈希函数数据库原理与设计兰州大学信息学院IDM实验室10.1.5其他操作4.外连接外连接操作可分为三种：左外连接、右外连接和全连接。实现外连接有两种策略，第一种是计算匹配的记录，然后把其它记录并入外连接的结果中；第二种是对连接算法进行适当的修改。(1)计算相应的连接，然后将适当的记录加入到连接结果中以得到外连接结果。例如：要进行右外连接运算可以用与左外连接类似的方法实现。要实现全外连接运算，可以先做自然连接运算然后加入左、右外连接的额外记录。(2)对连接算法进行修改。自然外连接与具有等值连接条件的外连接可以通过扩展归并连接算法与散列连接算法来实现。对归并连接加以扩展，可以用来计算完全外连接。过程如下：当两个关系的归并完成后，将两个关系中那些不与另一个关系的任何记录相匹配的记录在填充空值后写到结果中。数据库原理与设计兰州大学信息学院IDM实验室10.2查询优化一、查询优化概述查询优化的必要性–查询优化极大地影响RDBMS的性能。查询优化的可能性–关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义。数据库原理与设计兰州大学信息学院IDM实验室代价模型集中式数据库•单用户系统总代价=I/O代价+CPU代价•多用户系统总代价=I/O代价+CPU代价+内存代价分布式数据库总代价=I/O代价+CPU代价[+内存代价]+通信代价数据库原理与设计兰州大学信息学院IDM实验室二、一个实例例：求选修了课程Ｃ2的学生姓名SELECTStudent.SnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno='2';数据库原理与设计兰州大学信息学院IDM实验室查询优化的必要性（续）假设1：外存：Student:1000条,SC:10000条,选修2号课程:50条假设2：一个内存块装元组:10个Student,或100个SC,内存中一次可以存放:5块Student元组,1块SC元组和若干块连接结果元组假设3：读写速度：20块/秒假设4：连接方法：基于数据块的嵌套循环法数据库原理与设计兰州大学信息学院IDM实验室执行策略1Ｑ1＝ПＳname(бStudent.Sno=SC.Sno∧SC.Cno='2'(Student×SC))①Student×SC读取总块数=读Student表块数+读SC表遍数*每遍块数=1000/10+(1000/(10×5))×(10000/100)=100+20×100=2100读数据时间=2100/20=105秒数据库原理与设计兰州大学信息学院IDM实验室不同的执行策略,考虑I/O时间中间结果大小=1000*10000=107(1千万条元组)写中间结果时间=10000000/10/20=50000秒②б读数据时间=50000秒③П总时间=105＋50000＋50000秒=100105秒=27.8小时数据库原理与设计兰州大学信息学院IDM实验室查询优化的必要性（续）2.Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))①读取总块数=2100块读数据时间=2100/20=105秒中间结果大小=10000（减少1000倍）写中间结果时间=10000/10/20=50秒②б读数据时间=50秒③П总时间＝105＋50＋50秒＝205秒=3.4分数据库原理与设计兰州大学信息学院IDM实验室查询优化的必要性（续）3.Ｑ2＝ПSname(StudentбSC.Cno='2'(SC))①б读SC表总块数=10000/100=100块读数据时间=100/20=5秒中间结果大小=50条不必写入外存②读Student表总块数=1000/10=100块读数据时间=100/20=5秒③П总时间＝5＋5秒＝10秒数据库原理与设计兰州大学信息学院IDM实验室查询优化的必要性（续）4.Ｑ2＝ПＳname(StudentбSC.Cno='2'(SC))假设SC表在Cno上有索引，Student表在Sno上有索引①б读SC表索引=读SC表总块数=50/1001块读数据时间中间结果大小=50条不必写入外存数据库原理与设计兰州大学信息学院IDM实验室查询优化的必要性（续）②读Student表索引=读Student表总块数=50/10=5块读数据时间③П总时间10秒数据库原理与设计兰州大学信息学院IDM实验室查询优化的一般准则选择运算应尽可能先做–目的：减小中间关系在执行连接操作前对关系适当进行预处理–按连接属性排序–在连接属性上建立索引投影运算和选择运算同时做–目的：避免重复扫描关系将投影运算与其前面或后面的双目运算结合–目的：减少扫描关系的遍数数据库原理与设计兰州大学信息学院IDM实验室9.3代数优化关系代数表达式等价–指用相同的关系代替两个表达式中相应的关系所