数据库原理与技术.pptx

第六章第六章查询处理查询处理6.1查询处理概述查询处理概述6.2代价估算代价估算 6.3 基本运算的实现基本运算的实现6.4表达式计算表达式计算6.5关系表达式转换关系表达式转换6.6选择执行计划选择执行计划 6.1查询处理概述查询处理概述查询处理是指从数据库中提取数据的一系列活查询处理是指从数据库中提取数据的一系列活动。主要包括：动。主要包括：v将用高层数据库语言表示的查询语句翻译为将用高层数据库语言表示的查询语句翻译为能在文件系统这一物理层次上实现的表达式能在文件系统这一物理层次上实现的表达式 v为优化查询而进行各种转换为优化查询而进行各种转换 v查询的实际执行查询的实际执行 输入：输入：SQL语句语句输出：满足查询条件的数据输出：满足查询条件的数据 6.1查询处理概述（查询处理概述（2）查询处理的基本步骤：查询处理的基本步骤：1语法分析与翻译语法分析与翻译2优化优化3执行执行语法分析与翻译语法分析与翻译关系代数表达式关系代数表达式执行计划执行计划优化器优化器查询语句查询语句执行引擎执行引擎查询结果查询结果有关数据的统计值有关数据的统计值数据数据6.1查询处理概述（查询处理概述（3）查查询询优优化化是是为为关关系系代代数数表表达达式式的的计计算算选选择择最有效的查询计划的过程。最有效的查询计划的过程。查查询询执执行行计计划划：用用于于计计算算一一个个查查询询的的原原语语序列。序列。执执行行原原语语：加加了了“如如何何执执行行”注注释释的的关关系系代数运算。代数运算。6.1查询处理概述（查询处理概述（4）查询优化的过程：查询优化的过程：v代数优化：力图找出与给定关系代数表达式代数优化：力图找出与给定关系代数表达式等价的但执行效率更高的一个表达式。等价的但执行效率更高的一个表达式。v查询语句处理的详细策略的选择，例如选择查询语句处理的详细策略的选择，例如选择执行运算所采用的具体算法，选择将使用的执行运算所采用的具体算法，选择将使用的特定索引等等。特定索引等等。6.1查询处理概述（查询处理概述（5）对于关系数据库系统，查询优化是：对于关系数据库系统，查询优化是：v挑战：必须进行好的优化，才有可接受的性能挑战：必须进行好的优化，才有可接受的性能v机会：关系表达式的语义层次高，提供了优化机会：关系表达式的语义层次高，提供了优化的可能性。的可能性。优化器有理由比程序员做得更好：优化器有理由比程序员做得更好：优化器具有丰富的可使用的信息优化器具有丰富的可使用的信息当数据库发生变化时优化器容易再次进行优化当数据库发生变化时优化器容易再次进行优化优化器能够对多种实现策略逐一进行考虑优化器能够对多种实现策略逐一进行考虑优化器集中了最优秀的程序员的智慧和经验优化器集中了最优秀的程序员的智慧和经验 6.2代价估算代价估算 6.2.1用于估计代价的目录信息用于估计代价的目录信息 6.2.2查询代价的度量查询代价的度量 6.2.1用于估计代价的目录信息用于估计代价的目录信息 v有关关系的统计信息有关关系的统计信息nr：关系：关系r中的元组数目中的元组数目br：含有关系：含有关系r的元组的块数目的元组的块数目sr：关系：关系r中一个元组的大小中一个元组的大小fr：关关系系r的的块块因因子子，即即一一个个块块中中能能存存放放的的关关系系r的元组数的元组数若若假假定定关关系系r的的元元组组物物理理上上存存于于同同一一文文件件中中，则则：br=nr/fr 6.2.1用于估计代价的目录信息用于估计代价的目录信息（2）v有关关系的统计信息（续）有关关系的统计信息（续）V(A,r)：关系：关系r中属性中属性A所具有的不同值的数目。所具有的不同值的数目。V(A,r)等于等于A（r）的大小）的大小若若A为关系为关系r的码，则的码，则V(A,r)=nrSC(A,r)：关关系系r的的属属性性A的的选选择择基基数数。表表示示关关系系r中满足属性中满足属性A上的一个等值条件的平均元组数。上的一个等值条件的平均元组数。若若A为为r的码属性，则的码属性，则SC(A,r)1若若A为为非非码码属属性性，并并假假定定V(A,r)个个不不同同的的值值在在元元组组上均匀分布，则上均匀分布，则SC(A,r)(nr/V(A,r)。说明：说明：V(A,r)与与SC(A,r)中的中的A可以是属性组。可以是属性组。6.2.1用于估计代价的目录信息（用于估计代价的目录信息（3）v有关索引的统计信息：有关索引的统计信息：fi：树形结构：树形结构(如如B树树)索引索引i的内部结点的平均扇出。的内部结点的平均扇出。HTi：索引：索引i的层数。的层数。对于关系对于关系r的属性的属性A上所建的平衡树索引（如上所建的平衡树索引（如B树），树），HTi logfi(V(A,r)对于散列索引，对于散列索引，HTHTi i1 1 LBi：索引：索引i中最低层索引块数目，即索引叶层的块数。中最低层索引块数目，即索引叶层的块数。对于散列索引，对于散列索引，Lbi就是索引中的块数。就是索引中的块数。算法算法A的代价估计记为的代价估计记为EA。6.2.2查询代价的度量查询代价的度量查询代价：查询处理对各种资源的使用情况查询代价：查询处理对各种资源的使用情况 磁盘存取磁盘存取（简化为磁盘块传送数）（简化为磁盘块传送数）CPU时间时间 通信开销通信开销 一个重要的影响因素：主存中缓冲区的大小一个重要的影响因素：主存中缓冲区的大小M M最好的情形，所有的数据可以读入到缓冲区中最好的情形，所有的数据可以读入到缓冲区中最坏的情形，缓冲区只能容纳数目不多的数据块最坏的情形，缓冲区只能容纳数目不多的数据块大约每个关系一块。大约每个关系一块。6.3 基本运算的实现基本运算的实现每一个基本的代数运算都有多种不同的实现每一个基本的代数运算都有多种不同的实现算法。算法。适用于不同的情况适用于不同的情况等值条件，范围条件等值条件，范围条件数据是聚集的，数据是非聚集的数据是聚集的，数据是非聚集的相关属性上有索引，相关属性上没有索引相关属性上有索引，相关属性上没有索引 执行代价不同执行代价不同 6.3 基本运算的实现（基本运算的实现（2）6.3.1选择运算选择运算 6.3.2排序运算排序运算 6.3.3连接运算连接运算 6.3.4其他运算其他运算 6.3.1选择运算选择运算v全表扫描全表扫描 方方法法：依依次次访访问问表表的的每每一一个个块块，对对于于每每一一个元组，测试它是否满足选择条件。个元组，测试它是否满足选择条件。代价：代价：E=br 缺点：缺点：效率低效率低 优点：优点：对关系的存储方式没有要求，不需要索引。对关系的存储方式没有要求，不需要索引。适用于任何选择条件。适用于任何选择条件。6.3.1选择运算（选择运算（2）v索引扫描索引扫描 条件：表在选择条件的属性上建有索引。条件：表在选择条件的属性上建有索引。方方法法：访访问问索索引引，根根据据索索引引项项的的指指示示去去访访问问数据元组。数据元组。无序索引：访问满足等值条件的元组无序索引：访问满足等值条件的元组有序索引：访问满足范围查找条件的一系列元有序索引：访问满足范围查找条件的一系列元组。组。6.3.1选择运算选择运算.（3）代价：代价：利用主索引，等值比较：利用主索引，等值比较：E=HTi+SC(ASC(A，r)/fr)/fr r 利用辅助索引，等值比较：利用辅助索引，等值比较：E=HTi+SC+SC（A A，r r）利用主索引，非等值比较：利用主索引，非等值比较：E=HTi+br/2/2 （假设大约一半的元组满足比较条件）（假设大约一半的元组满足比较条件）利用辅助索引，非等值比较：利用辅助索引，非等值比较：E=HTi+LB+LBi i/2+n/2+nr r/2/2 6.3.1选择运算（选择运算（4）v复杂条件的选择复杂条件的选择合取：合取：1 2 n（r）析取：析取：1 2 n（r）方法：利用一个索引进行合取选择。方法：利用一个索引进行合取选择。利用组合索引进行合取选择。利用组合索引进行合取选择。利用多维索引进行合取选择。利用多维索引进行合取选择。通过标识符的交集进行合取选择。通过标识符的交集进行合取选择。通过标识符的并集进行析取选择。通过标识符的并集进行析取选择。6.3.2排序运算排序运算排序运算在数据库中的重要意义：排序运算在数据库中的重要意义：SQL查询可能要求有序的查询结果。查询可能要求有序的查询结果。事事先先对对于于作作为为运运算算对对象象的的关关系系进进行行排排序序，可可以以提提高某些关系运算（例如连接）的执行效率。高某些关系运算（例如连接）的执行效率。内内排排序序：文文件件较较小小，整整个个排排序序过过程程都都能能在在内内存存中进行。中进行。外排序：文件较大，排序过程需要使用外存。外排序：文件较大，排序过程需要使用外存。6.3.2排序运算（排序运算（2）v外部排序外部排序-归并算法：归并算法：（设内存中用于排序的缓冲区页面数为（设内存中用于排序的缓冲区页面数为M）第一阶段，建立多个已排序的子表。第一阶段，建立多个已排序的子表。每次读入每次读入M块，进行内排序，将长度为块，进行内排序，将长度为M块的已块的已排序子表（共排序子表（共 br/M 个）写到外存中。个）写到外存中。第二阶段，对已排序子表进行归并（可能需第二阶段，对已排序子表进行归并（可能需进行若干趟）。进行若干趟）。6.3.2排序运算（排序运算（3）第二阶段，对已排序子表进行归并。第二阶段，对已排序子表进行归并。第第一一趟趟：将将头头M-1个个已已排排序序子子表表的的各各块块逐逐步步读读入入内内存存，归归并并并并输出。输出。将将下下M-1个个已已排排序序子子表表的的各各块块逐逐步步读读入入内内存存，归归并并并输出。并输出。已排序子表数目减少到原来的已排序子表数目减少到原来的1/1/（M-1M-1）第二趟：以第一趟的输出作为输入，重复过程。第二趟：以第一趟的输出作为输入，重复过程。第三趟：以第二趟的输出作为输入，重复归并过程第三趟：以第二趟的输出作为输入，重复归并过程直至归并为一个已排序文件。直至归并为一个已排序文件。6.3.2排序运算（排序运算（4）第二阶段第一趟：第二阶段第一趟：将头将头M-1M-1个已排序子表的每一个的第一块读入内存的一个缓冲页个已排序子表的每一个的第一块读入内存的一个缓冲页 repeatrepeat在所有缓冲页中的第一个元组中挑选排序码值最小的元组；在所有缓冲页中的第一个元组中挑选排序码值最小的元组；把该元组写到第把该元组写到第M M个缓冲页，并将其从原缓冲页中删除；个缓冲页，并将其从原缓冲页中删除；if if 任何一个归并段文件任何一个归并段文件R Ri i的缓冲页为空并且没有到达的缓冲页为空并且没有到达R Ri i末尾末尾 then then 读入读入R Ri i的下一块到相应的缓冲页；的下一块到相应的缓冲页；if if 第第M M个缓冲页满个缓冲页满 then then 将第将第M M个缓冲页写到磁盘，并清空该缓冲页；个缓冲页写到磁盘，并清空该缓冲页；untiluntil所有的缓冲页均空所有的缓冲页均空将下将下M-1M-1个已排序子表的每一个的第一块读入内存，归并。个已排序子表的每一个的第一块读入内存，归并。.6.3.2排序运算（排序运算（5）初始关系初始关系 归并段文件归并段文件 归并段文件归并段文件 排序结果排序结果 第一阶段第一阶段 第二阶段第二阶段 第二阶段第二阶段 创建归并段文件创建归并段文件 第一趟归并第一趟归并 第二趟归并第二趟归并6.3.2排序运算（排序运算（6）代价估算：代价估算：趟数趟数=logM-1(br/M)E=bE=br r(2(2 loglogM-1M-1(b(br r/M)/M)+1)+1)6.3.3连接运算连接运算v二元运算，涉及两个关系。二元运算，涉及两个关系。r|s重要的运算，多种不同的实现算法。重要的运算，多种不同的实现算法。6.3.3连接运算（连接运算（2）自然连接结果集大小的估计：自然连接结果集大小的估计：基于主码、外码连接的情况：结果集的元组数等于基于主码、外码连接的情况：结果集的元组数等于外码所在关系的元组数。外码所在关系的元组数。一一般般情情况况：（假假设设连连接接属属性性A的的每每个个值值在在关关系系的的元元组组中等概率出现），中等概率出现），结果集的元组数为：结果集的元组数为：vnr*(ns/V(A,s)v或或ns*(nr/V(A,r)说明：说明：当当V(A,s)V(A,s)与与V(A,r)V(A,r)不同时，取两个估计值中较小者。不同时，取两个估计值中较小者。若两个关系中的元组在连接属性上的取值能匹配上的很少时，若两个关系中的元组在连接属性上的取值能匹配上的很少时，上述估计值太高。但实际上这种情况很少发生。上述估计值太高。但实际上这种情况很少发生。6.3.3连接运算（连接运算（3）v嵌套循环连接嵌套循环连接v块嵌套循环连接块嵌套循环连接v索引嵌套循环连接索引嵌套循环连接v排序排序-归并连接归并连接 v散列连接散列连接 v复杂连接的实现复杂连接的实现 6.3.3连接运算（连接运算（4）v嵌套循环连接嵌套循环连接foreach元组元组trinrdobeginforeach元组元组tsinsdobegin测试元组对测试元组对(tr,ts)是否满足连接条件是否满足连接条件如果满足，把如果满足，把tr ts加到结果中加到结果中endend6.3.3连接运算（连接运算（5）v嵌套循环连接（续）嵌套循环连接（续）优点：对参加运算的关系没有要求，优点：对参加运算的关系没有要求，适合于任何连接条件。适合于任何连接条件。代价：代价：最最坏坏情情况况（缓缓冲冲区区只只能能够够容容纳纳每每个个关关系系的的一一个个块）：块）：nr bs+br或或ns br+bs最好情况（内层关系最好情况（内层关系s能完全放在内存中）：能完全放在内存中）：bs+br 6.3.3连接运算（连接运算（6）v块块嵌嵌套套循循环环连连接接：以以块块的的方方式式循循环环，以以减减少少块块读读写次数。写次数。foreach块块Brofrdobeginforeach块块Bsofsdobeginforeach元组元组trinBrdobeginforeach元组元组tsinBsdo begin测试元组对测试元组对(tr,ts)是否满足连接条件是否满足连接条件如果满足，把如果满足，把tr ts加到结果中加到结果中endendendend6.3.3连接运算（连接运算（7）v块嵌套循环连接（续）块嵌套循环连接（续）优点：对参加运算的关系没有要求，优点：对参加运算的关系没有要求，适合于任何连接条件。适合于任何连接条件。代价：代价：最最坏坏情情况况（缓缓冲冲区区只只能能够够容容纳纳每每个个关关系系的的一一个个块）：块）：br*bs+br或或bs*br+bs最好情况（内层关系最好情况（内层关系s能完全放在内存中）：能完全放在内存中）：bs+br 6.3.3连接运算（连接运算（8）v块嵌套循环连接（续）块嵌套循环连接（续）一些改进：一些改进：连连接接属属性性是是内内层层关关系系的的码码时时，内内层层循循环环可可中中途途跳跳出。出。内内层层循循环环轮轮流流做做正正、反反向向扫扫描描，重重用用缓缓冲冲区区中中的数据，以减少磁盘读取。的数据，以减少磁盘读取。内层循环利用索引。内层循环利用索引。6.3.3连接运算（连接运算（9）v索引嵌套循环连接：在内层循环中利用连接索引嵌套循环连接：在内层循环中利用连接属性上的索引。属性上的索引。foreach元组元组trinrdobeginforeach与元组与元组tr满足连接条件的索引项满足连接条件的索引项ins关系在连接属性上的索引关系在连接属性上的索引dobegin利用索引取到相应的利用索引取到相应的ts把把tr ts加到结果中加到结果中endend 6.3.3连接运算（连接运算（10）v索引嵌套循环连接（续）索引嵌套循环连接（续）代价：代价：最最坏坏情情况况（缓缓冲冲区区只只能能够够容容纳纳关关系系r的的一一个个块和索引的一个块）：块和索引的一个块）：br+nr*c或或bs+ns*c最好情况不必考虑，因为不必采用索引嵌套最好情况不必考虑，因为不必采用索引嵌套循环连接方法。循环连接方法。对关系S使用连接条件利用索引进行选择操作的代价6.3.3连接运算（连接运算（11）v排序排序-归并连接归并连接 类似于外排序的归并算法的思路，进行连接运算。类似于外排序的归并算法的思路，进行连接运算。前提：两个关系的元组都已按连接属性排好序。前提：两个关系的元组都已按连接属性排好序。适用于自然连接和等值连接。适用于自然连接和等值连接。a3b1d8d13f7m5q6aAaGcLdNmB r sa1a2a1a3在归并连接中使用的已排序关系在归并连接中使用的已排序关系rs6.3.3连接运算（连接运算（12）pr:=r的第一个元组的地址的第一个元组的地址ps:=s的第一个元组的地址；的第一个元组的地址；while(psnullandprnull)dobegints:=ps所指向的元组；所指向的元组；Ss:=ts；让让ps指向关系指向关系s的下一个元组；的下一个元组；done:=false;while(notdoneandpsnull)dobegints:=ps所指向的元组；所指向的元组；if(tsJoinAttrs=tsJoinAttrs)thenbeginSs:=Ss ts；让让ps指向关系指向关系s的下一个元组；的下一个元组；endelsedone:=true；end在连接属性上具有相同值的在连接属性上具有相同值的S S元组被加入到了元组被加入到了S Ss s中。中。PsPs指向在连接属性上具有另指向在连接属性上具有另一个值的一个值的S S元组。元组。6.3.3连接运算（连接运算（13）tr:=pr所指向的元组；所指向的元组；while(prnullandtrJoinAttrsM2时，关系的划分不可能一趟完成，需要递归划分。时，关系的划分不可能一趟完成，需要递归划分。当当对对于于某某个个i，Hsi中中的的元元组组数数大大于于内内存存容容量量时时，需需要要进进行行溢溢出处理，想办法使出处理，想办法使Hsi变小。变小。改进：混合散列连接改进：混合散列连接当当M2bs时，充分利用内存空间，减少磁盘时，充分利用内存空间，减少磁盘I/O的方法。的方法。前提：读每个关系一遍就能完成散列划分，构造用输入关系的每一个分划都能完全放入内存。6.3.3连接运算（连接运算（23）v复杂连接的实现复杂连接的实现 合取式：合取式：r|r|r|q1计计算算r-R(q1)，在在s对对应应的的分分量量填填上上空空值，加到值，加到q1中。中。6.3.4其他运算（其他运算（4）v外连接（续）外连接（续）修改连接算法修改连接算法v修改嵌套循环连接算法进行左外连接、右外连接。修改嵌套循环连接算法进行左外连接、右外连接。v修修改改排排序序-归归并并连连接接算算法法进进行行全全外外连连接接、左左外外连连接接、右外连接。右外连接。v修修改改散散列列连连接接算算法法进进行行全全外外连连接接、左左外外连连接接、右右外外连接。连接。6.3.4其他运算（其他运算（5）v聚集聚集排序的方法排序的方法散列的方法散列的方法6.4表达式计算表达式计算例例customer_name（balance|customer）customer_namebalance 1000 (branch|customer-name(branch-city=”Brooklyn”balance1000 (branch|customer-name(branch_city=”Brooklyn”balance1000 (branch|1000(branch|customer-name(branch-city=”Brooklyn”(branch)|1000(account)|customer-name(account-number(branch-city=”Brooklyn”(branch)|1000(account)|1000andexists(select*from depositor where depositor.customer-name=borrower.customer-name and account-number 1000)=createtablet1asselectdistinctcustomer-namefromdepositorwhere account-number 1000andt1.customer-name=borrower.customer-name6.6.3嵌套子查询的优化（嵌套子查询的优化（6）当嵌套子查询使用聚集、或嵌套子查询的结当嵌套子查询使用聚集、或嵌套子查询的结果用于等值测试、或嵌套子查询与外部查询果用于等值测试、或嵌套子查询与外部查询的关联条件是的关联条件是not existsnot exists时，去除相关操作时，去除相关操作会更复杂。会更复杂。课程实习课程实习目的：目的：1.了了解解数数据据库库管管理理系系统统底底层层的的存存储储管管理理与与数数据据管管理部件，它所提供的接口。理部件，它所提供的接口。2.进行查询处理系统设计与实现的实际训练。进行查询处理系统设计与实现的实际训练。任务：任务：1.设设计计与与实实现现一一个个简简化化的的查查询询处处理理系系统统，对对SQL语句进行分析处理，优化，产生执行结果。语句进行分析处理，优化，产生执行结果。2.分析、比较不同的查询执行计划的执行性能。分析、比较不同的查询执行计划的执行性能。课程实习（课程实习（2）基础环境：基础环境：COBASE核心核心存储管理和数据管理子系统存储管理和数据管理子系统SQL语言翻译处理存储管理与数据管理单元组接口SQL语句课程实习（课程实习（3）说明：说明：1二至三人一组，自由结合。二至三人一组，自由结合。2适适当当控控制制系系统统的的规规模模和和难难度度，只只处处理理有有限形式的限形式的SQL查询。查询。3集集中中做做与与查查询询处处理理密密切切相相关关的的工工作作，简简化其他部分。化其他部分。4注意中间结果，和比较、分析结果的输注意中间结果，和比较、分析结果的输出，充分展示你的工作的特色。出，充分展示你的工作的特色。课程实习（课程实习（4）提交：提交：1查询处理系统规格定义查询处理系统规格定义2设计说明书设计说明书3使用说明书使用说明书4比较分析和总结报告比较分析和总结报告5可运行的系统可运行的系统