数据库原理与技术PPT课件

6.1 查询处理概述查询处理概述查询处理是指从数据库中提取数据的一系列活动。主要包括：查询处理是指从数据库中提取数据的一系列活动。主要包括： 将用高层数据库语言表示的查询语句翻译为能在文件系统这一物理层次上实现的表将用高层数据库语言表示的查询语句翻译为能在文件系统这一物理层次上实现的表达式达式 为优化查询而进行各种转换为优化查询而进行各种转换 查询的实际执行查询的实际执行 输入：输入：SQL语句语句输出：满足查询条件的数据输出：满足查询条件的数据 第1页/共87页6.1 查询处理概述（查询处理概述（2）查询处理的基本步骤：查询处理的基本步骤： 1 语法分析与翻译语法分析与翻译 2 优化优化 3 执行执行语法分析与翻译关系代数表达式执行计划优化器查询语句执行引擎查询结果有关数据的统计值数据第2页/共87页6.1 查询处理概述（查询处理概述（3）查询优化是为关系代数表达式的计算选择最有效的查询计划的过程。查询优化是为关系代数表达式的计算选择最有效的查询计划的过程。查询执行计划查询执行计划：用于计算一个查询的原语序列。用于计算一个查询的原语序列。 执行原语：加了执行原语：加了“如何执行如何执行”注释的关系代数运算。注释的关系代数运算。第3页/共87页6.1 查询处理概述（查询处理概述（4）查询优化的过程：查询优化的过程： 代数优化：力图找出与给定关系代数表达式等价的但执行效率更高的一个表达式。代数优化：力图找出与给定关系代数表达式等价的但执行效率更高的一个表达式。 查询语句处理的详细策略的选择，例如选择执行运算所采用的具体算法，选择将使用的特定索引等等。查询语句处理的详细策略的选择，例如选择执行运算所采用的具体算法，选择将使用的特定索引等等。 第4页/共87页6.1 查询处理概述（查询处理概述（5）对于关系数据库系统，查询优化是：对于关系数据库系统，查询优化是： 挑战：必须进行好的优化，才有可接受的性能挑战：必须进行好的优化，才有可接受的性能 机会：关系表达式的语义层次高，提供了优化的可能性。机会：关系表达式的语义层次高，提供了优化的可能性。优化器有理由比程序员做得更好：优化器有理由比程序员做得更好：优化器具有丰富的可使用的信息优化器具有丰富的可使用的信息 当数据库发生变化时优化器容易再次进行优化当数据库发生变化时优化器容易再次进行优化优化器能够对多种实现策略逐一进行考虑优化器能够对多种实现策略逐一进行考虑 优化器集中了最优秀的程序员的智慧和经验优化器集中了最优秀的程序员的智慧和经验 第5页/共87页6.2 代价估算代价估算 6.2.1 用于估计代价的目录信息用于估计代价的目录信息 6.2.2 查询代价的度量查询代价的度量 第6页/共87页 6.2.1 用于估计代价的目录信息用于估计代价的目录信息 有关关系的统计信息有关关系的统计信息 nr：关系：关系r中的元组数目中的元组数目 br：含有关系：含有关系r的元组的块数目的元组的块数目 sr ：关系：关系r中一个元组的大小中一个元组的大小 fr ：关系：关系r的块因子，即一个块中能存放的关系的块因子，即一个块中能存放的关系r的元组数的元组数若假定关系若假定关系r的元组物理上存于同一文件中，则：的元组物理上存于同一文件中，则： br = nr / fr 第7页/共87页 6.2.1 用于估计代价的目录信息用于估计代价的目录信息（2） 有关关系的统计信息（续）有关关系的统计信息（续） V(A,r) ：关系：关系r中属性中属性A所具有的不同值的数目。所具有的不同值的数目。 V(A,r)等于等于 A（r）的大小）的大小 若若A为关系为关系r的码，则的码，则V(A,r) = nr SC(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可以是属性组。可以是属性组。第8页/共87页6.2.1 用于估计代价的目录信息（用于估计代价的目录信息（3） 有关索引的统计信息：有关索引的统计信息： fi ：树形结构：树形结构(如如B树树)索引索引i的内部结点的平均扇出。的内部结点的平均扇出。 HTi ：索引：索引i的层数。的层数。 对于关系对于关系r的属性的属性A上所建的平衡树索引（如上所建的平衡树索引（如B树），树），HTi logfi(V(A,r) 对于散列索引，HTHTi i1 1 LBi ：索引：索引i中最低层索引块数目，即索引叶层的块数。中最低层索引块数目，即索引叶层的块数。 对于散列索引，对于散列索引，Lbi就是索引中的块数。就是索引中的块数。 算法算法A的代价估计记为的代价估计记为EA。 第9页/共87页6.2.2 查询代价的度量查询代价的度量查询代价：查询处理对各种资源的使用情况查询代价：查询处理对各种资源的使用情况 磁盘存取磁盘存取 （简化为磁盘块传送数）（简化为磁盘块传送数） CPU时间时间 通信开销通信开销 一个重要的影响因素：主存中缓冲区的大小一个重要的影响因素：主存中缓冲区的大小M M最好的情形，所有的数据可以读入到缓冲区中最好的情形，所有的数据可以读入到缓冲区中最坏的情形，缓冲区只能容纳数目不多的数据块最坏的情形，缓冲区只能容纳数目不多的数据块大约每个关系一块。大约每个关系一块。 第10页/共87页6.3 基本运算的实现基本运算的实现 每一个基本的代数运算都有多种不同的实现算法。每一个基本的代数运算都有多种不同的实现算法。 适用于不同的情况适用于不同的情况 等值条件，范围条件等值条件，范围条件 数据是聚集的，数据是非聚集的数据是聚集的，数据是非聚集的 相关属性上有索引，相关属性上没有索相关属性上有索引，相关属性上没有索引引 执行代价不同执行代价不同 第11页/共87页6.3 基本运算的实现（基本运算的实现（2）选择运算选择运算 排序运算排序运算 连接运算连接运算 其他运算其他运算 第12页/共87页选择运算选择运算 全表扫描全表扫描 方法：依次访问表的每一个块，对于每一个元组，测试它是否满足选择条件。方法：依次访问表的每一个块，对于每一个元组，测试它是否满足选择条件。 代价：代价：E = br 缺点：缺点： 效率低效率低 优点：优点： 对关系的存储方式没有要求，不需要索引。对关系的存储方式没有要求，不需要索引。 适用于任何选择条件。适用于任何选择条件。 第13页/共87页选择运算（选择运算（2） 索引扫描索引扫描 条件：表在选择条件的属性上建有索引。条件：表在选择条件的属性上建有索引。 方法：访问索引，根据索引项的指示去访问数据元组。方法：访问索引，根据索引项的指示去访问数据元组。 无序索引：访问满足等值条件的元组无序索引：访问满足等值条件的元组 有序索引：访问满足范围查找条件的一系列元组。有序索引：访问满足范围查找条件的一系列元组。 第14页/共87页选择运算选择运算.（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 第15页/共87页选择运算（选择运算（4） 复杂条件的选择复杂条件的选择 合取：合取：12n（r） 析取：析取：12n（r） 方法：利用一个索引进行合取选择。方法：利用一个索引进行合取选择。 利用组合索引进行合取选择。利用组合索引进行合取选择。 利用多维索引进行合取选择。利用多维索引进行合取选择。 通过标识符的交集进行合取选择。通过标识符的交集进行合取选择。 通过标识符的并集进行析取选择。通过标识符的并集进行析取选择。 第16页/共87页排序运算排序运算排序运算在数据库中的重要意义：排序运算在数据库中的重要意义： SQL查询可能要求有序的查询结果。查询可能要求有序的查询结果。 事先对于作为运算对象的关系进行排序，可以提高某些关系运算（例如连接）事先对于作为运算对象的关系进行排序，可以提高某些关系运算（例如连接）的执行效率。的执行效率。 内排序：文件较小，整个排序过程都能在内存中进行。内排序：文件较小，整个排序过程都能在内存中进行。 外排序：文件较大，排序过程需要使用外存。外排序：文件较大，排序过程需要使用外存。 第17页/共87页排序运算（排序运算（2） 外部排序外部排序-归并算法：归并算法： （设内存中用于排序的缓冲区页面数为（设内存中用于排序的缓冲区页面数为M） 第一阶段，建立多个已排序的子表。第一阶段，建立多个已排序的子表。 每次读入每次读入M块，进行内排序，将长度为块，进行内排序，将长度为M块的块的已排序子表（共已排序子表（共 br /M 个）写到外存中。个）写到外存中。 第二阶段，对已排序子表进行归并（可能需进行若干趟）。第二阶段，对已排序子表进行归并（可能需进行若干趟）。第18页/共87页排序运算（排序运算（3）第二阶段，对已排序子表进行归并。第二阶段，对已排序子表进行归并。 第一趟：将头第一趟：将头M-1个已排序子表的各块逐步读入内存，归个已排序子表的各块逐步读入内存，归并并输出。并并输出。 将下将下M-1个已排序子表的各块逐步读入内存，个已排序子表的各块逐步读入内存，归并并输出。归并并输出。 已排序子表数目减少到原来的已排序子表数目减少到原来的1/1/（M-1M-1） 第二趟：以第一趟的输出作为输入，重复过程。第二趟：以第一趟的输出作为输入，重复过程。 第三趟：以第二趟的输出作为输入，重复归并过程第三趟：以第二趟的输出作为输入，重复归并过程 直至归并为一个已排序文件。直至归并为一个已排序文件。第19页/共87页排序运算（排序运算（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个已排序子表的每一个的第一块读入内存，归并。个已排序子表的每一个的第一块读入内存，归并。 . .第20页/共87页排序运算（排序运算（5） 初始关系 归并段文件 归并段文件 排序结果 第一阶段 第二阶段 第二阶段 创建归并段文件 第一趟归并 第二趟归并第21页/共87页排序运算（排序运算（6）代价估算：代价估算：趟数趟数 = logM-1( br /M ) E = bE = br r ( 2 ( 2 loglogM-1M-1( b( br r /M ) /M ) + 1 ) + 1 ) 第22页/共87页连接运算连接运算 二元运算，涉及两个关系。二元运算，涉及两个关系。 r | s 重要的运算，多种不同的实现算法。重要的运算，多种不同的实现算法。 第23页/共87页连接运算（连接运算（2） 自然连接结果集大小的估计：自然连接结果集大小的估计： 基于主码、外码连接的情况：结果集的元组数等于外码所在关系的元组数。基于主码、外码连接的情况：结果集的元组数等于外码所在关系的元组数。 一般情况：（假设连接属性一般情况：（假设连接属性A的每个值在关系的元组中等概率出现），的每个值在关系的元组中等概率出现）， 结果集的元结果集的元组数为：组数为： nr *(ns /V(A,s) 或或 ns *( nr /V(A,r)说明：说明： 当当V(A,s)V(A,s)与与V(A,r)V(A,r)不同时，取两个估计值中较小者。不同时，取两个估计值中较小者。若两个关系中的元组在连接属性上的取值能匹配上的很少时，若两个关系中的元组在连接属性上的取值能匹配上的很少时，上述估计值太高。但实际上这种情况很少发生。上述估计值太高。但实际上这种情况很少发生。第24页/共87页连接运算（连接运算（3） 嵌套循环连接嵌套循环连接 块嵌套循环连接块嵌套循环连接 索引嵌套循环连接索引嵌套循环连接 排序排序- -归并连接归并连接 散列连接散列连接 复杂连接的实现复杂连接的实现 第25页/共87页连接运算（连接运算（4） 嵌套循环连接嵌套循环连接 for each元组元组tr in r do begin for each元组元组ts in s do begin 测试元组对测试元组对(tr,ts)是否满足连接条件是否满足连接条件 如果满足，把如果满足，把tr ts加到结果中加到结果中 end end第26页/共87页连接运算（连接运算（5） 嵌套循环连接（续）嵌套循环连接（续）优点：对参加运算的关系没有要求，优点：对参加运算的关系没有要求， 适合于任何连接条件。适合于任何连接条件。代价：代价： 最坏情况（缓冲区只能够容纳每个关系的一个块）：最坏情况（缓冲区只能够容纳每个关系的一个块）： nr bs + br 或或 ns br + bs 最好情况（内层关系最好情况（内层关系s能完全放在内存中）：能完全放在内存中）： bs + br 第27页/共87页连接运算（连接运算（6） 块嵌套循环连接：以块的方式循环，以减少块读写次数。块嵌套循环连接：以块的方式循环，以减少块读写次数。 for each块块Br of r do begin for each块块Bs of s do begin for each元组元组tr in Br do begin for each元组元组ts in Bs do begin 测试元组对测试元组对(tr,ts)是否满是否满足连接条件足连接条件 如果满足，把如果满足，把tr ts加到结加到结果中果中 end end end end第28页/共87页连接运算（连接运算（7） 块嵌套循环连接（续）块嵌套循环连接（续） 优点：对参加运算的关系没有要求，优点：对参加运算的关系没有要求， 适合于任何连接条件。适合于任何连接条件。 代价：代价： 最坏情况（缓冲区只能够容纳每个关系的一个块）：最坏情况（缓冲区只能够容纳每个关系的一个块）： br * bs + br 或或 bs * br + bs 最好情况（内层关系最好情况（内层关系s能完全放在内存中）：能完全放在内存中）： bs + br 第29页/共87页连接运算（连接运算（8） 块嵌套循环连接（续）块嵌套循环连接（续） 一些改进：一些改进： 连接属性是内层关系的码时，内层循环可中途跳出。连接属性是内层关系的码时，内层循环可中途跳出。 内层循环轮流做正、反向扫描，重用缓冲区中的数据，以减少磁盘读取。内层循环轮流做正、反向扫描，重用缓冲区中的数据，以减少磁盘读取。 内层循环利用索引。内层循环利用索引。 第30页/共87页连接运算（连接运算（9） 索引嵌套循环连接：在内层循环中利用连接属性上的索引。索引嵌套循环连接：在内层循环中利用连接属性上的索引。 for each 元组元组 tr in r do begin for each与元组与元组tr满足连接条件的满足连接条件的索引项索引项 in s关系在连接属性上的索关系在连接属性上的索引引do begin 利用索引取到相应的利用索引取到相应的ts 把把tr ts加到结果中加到结果中 end end 第31页/共87页连接运算（连接运算（10） 索引嵌套循环连接（续）索引嵌套循环连接（续）代价：代价： 最坏情况（缓冲区只能够容纳关系最坏情况（缓冲区只能够容纳关系r的一个块和索引的一个块）：的一个块和索引的一个块）： br + nr * c 或或 bs + ns * c 最好情况不必考虑，因为不必采用索引嵌套循环连接方法。最好情况不必考虑，因为不必采用索引嵌套循环连接方法。 对关系S使用连接条件利用索引进行选择操作的代价第32页/共87页连接运算（连接运算（11） 排序排序- -归并连接归并连接 类似于外排序的归并算法的思路，进行连接运算。类似于外排序的归并算法的思路，进行连接运算。前提：两个关系的元组都已按连接属性排好序。前提：两个关系的元组都已按连接属性排好序。适用于自然连接和等值连接。适用于自然连接和等值连接。a3b1d8d13f7m5q6aAaGcLdNmB r sa1a2a1a3在归并连接中使用的已排序关系rs第33页/共87页连接运算（连接运算（12）pr := r的第一个元组的地址的第一个元组的地址ps := s的第一个元组的地址；的第一个元组的地址；while (psnull and prnull) dobegin ts := ps所指向的元组；所指向的元组； Ss := ts ； 让让ps指向关系指向关系s的下一个元组；的下一个元组； done := false; while (not done and psnull) do begin ts:= ps所指向的元组；所指向的元组； if (tsJoinAttrs = tsJoinAttrs) then begin Ss := Ss ts； 让让ps指向关系指向关系s的下的下一个元组；一个元组； end else done := true； end在连接属性上具有相同值在连接属性上具有相同值的的S S元组被加入到了元组被加入到了S Ss s中。中。PsPs指向在连接属性上具有指向在连接属性上具有另一个值的另一个值的S S元组。元组。第34页/共87页连接运算（连接运算（13） tr := pr所指向的元组；所指向的元组；w h i l e ( p r n u l l a n d tr J o i n At t r s M2时，关系的划分不可能一趟完成，需要递归划时，关系的划分不可能一趟完成，需要递归划分。分。 当对于某个当对于某个i， Hsi中的元组数大于内存容量时，需要进中的元组数大于内存容量时，需要进行溢出处理，想办法使行溢出处理，想办法使Hsi变小。变小。 改进：混合散列连接改进：混合散列连接 当当M 2 bs时，充分利用内存空间，减少磁盘时，充分利用内存空间，减少磁盘I/O的方的方法。法。 前提：读每个关系一遍就能完成散列划分，构造用输入关系的每一个分划都能完全放入内存。第44页/共87页连接运算（连接运算（23） 复杂连接的实现复杂连接的实现 合取式：合取式：r | r | r | q1 计算计算 r - R(q1)，在，在s对应的分量填上空值，加到对应的分量填上空值，加到q1中。中。 第48页/共87页其他运算（其他运算（4） 外连接（续）外连接（续） 修改连接算法修改连接算法 修改嵌套循环连接算法进行左外连接、右外连接。修改嵌套循环连接算法进行左外连接、右外连接。 修改排序修改排序-归并连接算法进行全外连接、左外连接、右外连接。归并连接算法进行全外连接、左外连接、右外连接。 修改散列连接算法进行全外连接、左外连接、右外连接。修改散列连接算法进行全外连接、左外连接、右外连接。第49页/共87页其他运算（其他运算（5） 聚集聚集 排序的方法排序的方法 散列的方法散列的方法第50页/共87页6.4 表达式计算表达式计算 例例 customer_name（balance |customer） customer_name balance 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) | 1000 and exists ( select * from depositor where depositor.customer-name = borrower.customer-name and account-number 1000)=create table t1 as select distinct customer-name from depositor where account-number 1000 and t1.customer-name = borrower.customer-name 第81页/共87页嵌套子查询的优化（嵌套子查询的优化（6） 当嵌套子查询使用聚集、或嵌套子查询的结果用于等值测试、或嵌套子查询与外部查询的关联条件是当嵌套子查询使用聚集、或嵌套子查询的结果用于等值测试、或嵌套子查询与外部查询的关联条件是not not existsexists时，去除相关操作会更复杂。时，去除相关操作会更复杂。 第82页/共87页课程实习课程实习目的：目的： 1. 了解数据库管理系统底层的存储管理与数了解数据库管理系统底层的存储管理与数据管理部件，它所提供的接口。据管理部件，它所提供的接口。 2. 进行查询处理系统设计与实现的实际训练。进行查询处理系统设计与实现的实际训练。任务：任务： 1. 设计与实现一个简化的查询处理系统，对设计与实现一个简化的查询处理系统，对SQL语句进行分析处理，优化，产生执行结果。语句进行分析处理，优化，产生执行结果。 2. 分析、比较不同的查询执行计划的执行性分析、比较不同的查询执行计划的执行性能。能。 第83页/共87页课程实习（课程实习（2）基础环境：基础环境：COBASE核心核心 存储管理和数据管理子系统存储管理和数据管理子系统SQL语言翻译处理存储管理与数据管理单元组接口SQL语句第84页/共87页课程实习（课程实习（3）说明：说明： 1二至三人一组，自由结合。二至三人一组，自由结合。 2适当控制系统的规模和难度，只处理有限形式的适当控制系统的规模和难度，只处理有限形式的SQL查询。查询。 3集中做与查询处理密切相关的工作，简化其他部分。集中做与查询处理密切相关的工作，简化其他部分。 4注意中间结果，和比较、分析结果的输出，充分展示你的工作的特色。注意中间结果，和比较、分析结果的输出，充分展示你的工作的特色。 第85页/共87页课程实习（课程实习（4）提交：提交： 1查询处理系统规格定义查询处理系统规格定义 2设计说明书设计说明书 3使用说明书使用说明书 4比较分析和总结报告比较分析和总结报告 5可运行的系统可运行的系统第86页/共87页感谢您的观看！第87页/共87页