补充查询处理和查询优化.ppt

1,本章内容：,1 关系数据库系统的查询处理,2 关系数据库系统的查询优化,3 代数优化,4 物理优化,第九章 关系查询处理和查询优化,2,1、了解查询处理的一般步骤 2、了解为什么必须进行查询优化？ 3、掌握关系代数的等价变换规则 4、掌握代数优化的算法和优化的一般步骤 5、了解物理优化的内容和方法,本章要求：,3,一、查询处理步骤 查询处理分为4个阶段，在处理过程中，一旦发现问题，则报告错误，中止处理。,1 关系数据库系统的查询处理,查询处理的任务： 将用户提交给RDBMS的查询语句转换为高效的执行计划（方案）。,4,词法分析：识别出语句中的SQL关键字、属性名、关系名、运算符、常量等语言符号。 语法分析：检查语句是否符合SQL语法规则。,(1) 查询分析,5,语义检查：根据数据字典，检查语句中的数据库对象，如属性名、关系名等，是否有效。 符号名转换：将外部名转换为内部名。 安全性检查：检查用户是否有请求的存取权限。 完整性检查：检查是否违反完整性约束。 查询树转换：用基于关系代数的查询树来表示查询，查询树也叫语法分析树。,(2) 查询检查,6,(3) 查询优化 从多个可能的执行方案中选择一个执行效率较高的方案。 分为两个层次。,7,(4) 查询执行 依据查询优化得到的结果，生成执行代码，执行之。,代数优化：按照一定的规则，改变代数表达式中关系操作的次序和组合，使执行效率更高，又称逻辑优化。 物理优化：依据事先确定的策略，选择底层存取路径和算法。,8,二、实现查询操作的算法举例,1. 选择操作的实现 Select * from student where ； 考虑的几种情况：,C1: 无条件； C2: Sno=200215121； C3：Sage20; C4: Sdept=CS AND Sage20;,9,二、实现查询操作的算法举例,1. 选择操作的实现 (1) 简单的全表扫描方法 对查询基本表顺序扫描，逐一检查每个元组是否满足选择的条件，对满足条件的元组作为结果输出。对于小表，简单有效。对于大表，费时。,(2) 索引或散列扫描方法 如果选择条件中的属性上有索引（B+树索引或Hash索引），可以用索引扫描方法。通过索引先找到满足条件的元组的主码或元组指针，再通过元组指针直接在查询的基本表中找到元组。,10,二、实现查询操作的算法举例,2. 连接操作的实现 Select * from Student, Sc Where Student.Sno=SC.sno (1) 嵌套循环方法,对于外层循环(Student)的每个元组(s),检索内层循环(SC)中的每个元组(sc)，并检查这两个元组在连接属性(sno)上是否相等。如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止。,11,二、实现查询操作的算法举例,(2) 排序-合并方法,如果连接的表没有排好序，则将Student和SC表按连接属性Sno排序； 取Student表中的第一个Sno，依次扫描SC表中具有相同Sno的元组，把它们连接起来； 当扫描到Sno不相同的第一个SC元组时，返回Student表扫描下一个元组，再扫描SC表中具有相同Sno的元组，把它们连接起来。 重复上述步骤直到Student表扫描完。,12,二、实现查询操作的算法举例,(3) 索引连接方法,在SC表上建立属性Sno的索引，如果原来没有的话； 对Student表中的每一个元组，由Sno的值通过SC的索引查找相应的SC元组； 把这些SC元组和Student元组连接起来。 循环执行、 ；直到Student表中的元组处理完为止。,13,二、实现查询操作的算法举例,(4) Hash Join方法,把连接属性作为hash码，用同一个hash函数把R和S中的元组散列到同一个hash文件中。 划分阶段：对包含较少元组的表(比如R)进行一遍处理，把它的元组按hash函数分散到hash表的桶中； 试探阶段：对另一个表(S)进行一遍处理，把S的元组散列到适当的hash桶中，并将元组与桶中所有来自R并与之匹配的元组连接起来。,14,2 关系数据库系统的查询优化,关系数据语言只需用户提出“做什么”，不必指出“怎么做”，为什么能做到这一点？ 一个重要原因就是系统能自动进行查询优化。系统自动优化比用户自己优化会做得更好，见P267。 在集中式数据库中，查询执行的总代价(开销)为： 总代价 = I/O代价 + CPU代价 + 内存代价 三者中，I/O代价是最主要的。,查询优化的总目标： 选择有效的策略，求得给定的关系表达式的值，使得查询代价较小。,15,例：求选修了2号课程的学生姓名。其SQL语句为：,SELECT 姓名 FROM Student, SC WHERE Student.学号 = SC.学号 AND 课号 = 2;,为什么要进行查询优化？,也可用SQL语言如下实现:,SELECT 姓名 FROM Student WHERE 学号 IN (SELECT 学号 FROM SC WHERE 课号 = 2 ) ;,16,对于一个复杂的查询，不同用户可能会写出各种不同的查询方法。这些方法有的简单，有的复杂。它们的执行结果是一样的，但执行效率可能是不一样的。系统能解决这一问题吗？,17,对这一查询，可以考虑下面几种实现方式： 1、先求Student和SC的笛卡尔积，然后从中选出两学号字段值相等、课程号为2的元组，再投影姓名。,Q1 = 姓名 ( Student.学号=SC.学号课号=2( StudentSC ) ),2、先做Student和SC的自然连接，然后从中选出课程号为2的元组，再投影姓名。,Q2 = 姓名（课号=2 （Student SC）,3、先从SC中选出课程号为2的元组，然后将该结果与Student 连接，再投影姓名。,Q3 = 姓名（Student 课号=2 （SC）,18,分析三种实现策略的执行时间： 设有1000个学生记录，10000个选课记录，选修2号课程的学生有50名。,1、第一种策略：,Q1 = 姓名 ( Student.学号=SC.学号课号=2( StudentSC ) ),（1）计算广义笛卡尔积 StudentSC： 执行方式：读Student若干块和SC的1块到内存，然后执行连接，结果装满1块后就立即写入磁盘的临时文件中，当内存中的Student记录与SC记录全部连接后，再读入SC的下一块，继续连接，直到SC的所有记录与内存中的Student都连接，再读入Student的另若干块，重复上面的过程。,19,设一块能装10个Student记录或100个SC记录。 则Student的总块数为 1000/10 = 100 块，SC的总块数为 10000/100 = 100 块 若每次在内存中装入5块Student记录和1块SC的记录，则Student被读取1遍，SC被读取 100 / 5 = 20 遍。读取两表的总块数为 100 + 10020 = 2100块 连接结果为1000*10000 = 1000 0000个记录，若每块可装10个结果记录，共需写入磁盘1000 0000 / 10 = 100 0000块。 若每秒可读写20块，则读、写总时间分别为： 2100 /20 = 105 秒 100 0000 / 20 = 50000 秒,20,（2）依次读入Student SC的记录，然后执行选择。 读的时间：100 0000 / 20 = 50000秒 满足条件的记录为50个，全部放入内存，不再临时存储。 （3）在上步基础上执行投影得最终结果（此步时间不计）。,第一种策略的总时间为： 105 + 50000 + 50000 10万秒（近28小时）,21,2、第二种策略,（1）计算自然连接 读取Student表和SC表的策略不变，执行时间还是2100 / 20 = 105秒。 因为SC表中的每一个学号都在Student表中出现，而Student表中无重复学号，故连接后的结果和SC表的行数一样，为10000行，将它们临时存入盘中需（10000 / 10）块 / 20块/秒 = 50秒,计算自然连接需时：105 + 50 = 155秒,Q2 = 姓名（课号=2 （Student SC）,22,（2）执行选择运算 将存储在磁盘上临时文件中的自然连接结果，读入内存进行选择，结果为50个记录，不再临时存储。,主要为读取自然连接结果的时间：为50秒,（3）把上一步结果投影，时间忽略不计,第二种策略的总时间为： 155 + 50 = 205秒,23,3、第三种策略,（1）先对SC表作选择 只需读一遍SC表，需时 100块 / 20块/秒 = 5秒 中间结果只有50个记录，不需使用中间文件,（2）作自然连接 只需读一遍Student表，边读边和内存中的中间结果连接，结果仍为50个元组，需时 5 秒,Q3 = 姓名（Student 课号=2 （SC）,（3）把上一步结果投影，时间忽略不计,第三种策略的总时间为： 5 + 5 = 10 秒,结论：不同的查询策略其执行时间可能差别很大,24,说明： 刚才使用的是全表扫描的方法，比较费时，如果在选择字段和连接字段上建立了适当的索引，就可以减少记录的读取量，从而降低查询开销。这就是存取路径选择问题，由物理优化解决。,25,总结： 通过刚才的例子可知，前两种策略的中间结果集（笛卡尔积和自然连接）包含了许多对查询结果无用的记录，造成结果集太大，不得不进行磁盘缓存处理，从而使得花费时间较多。 由此启发我们，在查询处理时，应尽可能早地去掉对查询结果没有用的数据（记录或字段），以降低中间结果集的规模，这可通过优先执行一元运算（选择和投影）来实现，象第三种策略那样。,26,3 代数优化,一、关系代数表达式等价变换规则,设E1、E2是关系代数表达式。若用相同的关系代替E1、E2中相应的关系所得到的结果相同，则称E1、E2等价，记作 E1 E2。,1、投影的串接定律（幂等律）, A1,A2,An ( B1,B2,Bm ( E ) ) A1,A2,An ( E ) 其中A1,A2,An B1,B2,Bm,例： 姓名 ( 学号，姓名 ( Student ) ) 姓名 ( Student ),27,2、选择的串接定律（幂等律）, F1 （ F2 （E） F1F2 （E）,性别=男 (年龄20(Student)性别=男 年龄20 (Student),28,3、连接、笛卡尔积的交换律,笛卡尔积：E1 E2 E2 E1 自然连接：E1 E2 E2 E1,4、连接、笛卡尔积的结合律,笛卡尔积：(E1 E2 ) E3 E1 ( E2 E3 ) 自然连接：(E1 E2 ) E3 E1 ( E2 E3 ),29,5、选择与投影的交换律,F ( A1,A2,An ( E ) ) A1,A2,An ( F ( E ) ) 其中F只涉及A1,A2,An中的属性,例： 性别=男 ( 学号，姓名，性别 ( Student ) ) 学号，姓名，性别 ( 性别=男 (Student ) ),若F中有不属于A1,A2,An的属性B1,B2,Bm， 则 A1,A2,An ( F ( E ) ) A1,A2,An ( A1,A2,An,B1,B2,Bm ( F ( E ) ) ) A1,A2,An ( F ( A1,A2,An,B1,B2,Bm ( E ) ) ),30,例： 学号，姓名 ( 性别=男 (Student ) ) 学号，姓名 性别=男 ( 学号，姓名，性别 ( Student ) ),31,6、选择与笛卡尔积的交换律（分配律）,设F=F1F2F3，其中F1只涉及E1中的属性，F2只涉及E2中的属性，F3涉及E1和E2两者中的属性， 则 F ( E1 E2 ) F3 ( F1 E1 F2 E2 ),如果某个Fi不存在，则去掉相应的Fi。,例： Student.学号=SC.学号成绩60 ( Student SC ) Student.学号=SC.学号( Student 成绩60 SC ),32,7、选择对自然连接的分配律,设F=F1F2，其中F1只涉及E1的属性，F2只涉及E2的属性，则 F (E1 E2) F1 E1 F2 E2,例： 性别=男成绩=90 (Student SC) 性别=男 Student 成绩=90 SC,8、选择对并、交、差的分配律,F (E1 E2) F E1 F E2 F (E1 E2) F E1 F E2 F (E1 - E2) F E1 - F E2,33,9、投影对笛卡尔积的分配律,设A1,A2,，An是E1的属性， B1,B2,，Bm是E2的属性，则 A1,A2,An,B1,B2,Bm(E1 E2) A1,A2,An E1 B1,B2,Bm E2,10、投影对并、交、差的分配律,A(E1 E2) A E1 A E2 A(E1 E2) A E1 A E2 A(E1 - E2) A E1 - A E2,34,二、查询树的启发式优化,1、启发式规则 （1）一元运算应尽可能先做。这样可及时丢掉对查询结果无用的记录或字段，极大地减小中间结果集。 （2）将选择、投影及其前后的笛卡尔积、连接运算同时进行。这样可减少对关系的扫描遍数和中间结果的存储量。 （3）找出公共子表达式，将计算结果临时保存，再遇到该表达式时，不再计算，直接使用保存的结果。,35,2、关系代数语法树 用来表示关系代数表达式的一棵树，其内结点表示一种运算，叶结点表示一个关系。如： SELECT 姓名 FROM Student，SC WHERE Student.学号=SC.学号 AND 课号=2；,方法：将目标列转换为投影，将WHERE中的条件转换为选择，将FROM后的表用笛卡尔积连接起来。,也可转换为自然连接。,课号=2,36,3、关系代数表达式的优化算法,输入：一棵关系代数表达式的语法树 输出：优化的语法树,利用选择的串接定律，把形如 F1F2Fn （E）的式子变换为 F1 ( F2 ( ( Fn ( E ) ) ),（1）分解选择,37,对每一个选择，利用“选择的串接定律、选择与投影的交换律、选择对笛卡尔积的分配律、选择对自然连接的分配律、选择对并、交、差的分配律”尽可能把它移到树的叶端。,（2）选择下移,38,对每一个投影，利用“投影的串接定律、选择与投影的交换律、投影对笛卡尔积的分配律、投影对并、交、差的分配律”尽可能把它移到树的叶端。,（3）投影下移,（1）分解选择,（2）选择下移,39,利用“投影的串接定律、选择的串接定律、选择与投影的交换律”把选择和投影合并成单个选择、单个投影、或选择后跟投影等三种情况，使多个选择和 / 或投影能同时执行、或在一次扫描中完成。,（4）选择、投影合并,（3）投影下移,（1）分解选择,（2）选择下移,40,把上面得到的语法树分组： 每个二元运算和它的 一元直接祖先 为一组。若它的后代直到叶子全是一元运算，则也将它们并入该组。,（5）按点分组（每组只有一个二元运算）,不超过别的 二元运算结点,但对于笛卡尔积，若后面（父结点）是不能与它结合为等值连接的选择运算时，其一直到叶子的一元运算结点需单独算一组。,41,例：考虑由以下关系组成的图书馆数据库,BOOKS（书名，作者，出版社，编号） BORROWERS（姓名，单位，证号） LOANS（证号，编号，借阅日期）,找出2007年12月01日前借出书籍的书名和借阅人姓名。,用SQL 语言可表达如下： SELECT 书名，姓名 FROM BOOKS，BORROWERS，LOANS WHERE BOOKS.编号=LOANS.编号 AND BORROWERS.证号=LOANS.证号 AND 借阅日期 2007-12-01;,42,上述SQL语句可转化为如下关系代数表达式：,书名，姓名 ( 借阅日期2007-12-01 (BOOKS （ BORROWERS LOANS ) ) ),或 书名，姓名 ( 借阅日期2007-12-01 BOOKS.编号=LOANS.编号 BORROWERS.证号=LOANS.证号 (BOOKS ( BORROWERS LOANS ) ) ),通常先转化为后一种形式，在优化的后期会将笛卡尔积转换为自然连接。,43,书名，姓名,借阅日期2007-12-01 BOOKS.编号=LOANS.编号 BORROWERS.证号=LOANS.证号,上述表达式的语法树,LOANS,BOOKS,BORROWERS,根据算法第1步， 分解该选择,44,第1步优化（分解选择）后的语法树,书名，姓名,LOANS,BOOKS,BORROWERS,借阅日期2005-10-01 BOOKS.编号=LOANS.编号 BORROWERS.证号=LOANS.证号,借阅日期2007-12-01, BOOKS.编号=LOANS.编号, BORROWERS.证号=LOANS.证号,分解之后,根据算法第2步， 该选择可下移,45,书名，姓名,LOANS,BOOKS,BORROWERS,借阅日期2007-12-01, BOOKS.编号=LOANS.编号, BORROWERS.证号=LOANS.证号,46,书名，姓名,LOANS,BOOKS,BORROWERS,借阅日期2007-12-01, BOOKS.编号=LOANS.编号, BORROWERS.证号=LOANS.证号,该选择已不能下移,该选择也不能下移,将该选择下移,交换,47,书名，姓名,LOANS,BOOKS,BORROWERS,借阅日期2007-12-01, BOOKS.编号=LOANS.编号, BORROWERS.证号=LOANS.证号,继续下移,48,书名，姓名,LOANS,BOOKS,BORROWERS,借阅日期2007-12-01, BOOKS.编号=LOANS.编号, BORROWERS.证号=LOANS.证号,交换,49,书名，姓名,LOANS,BOOKS,BORROWERS,借阅日期2007-12-01, BOOKS.编号=LOANS.编号, BORROWERS.证号=LOANS.证号,继续下移,50,书名，姓名,LOANS,BOOKS,BORROWERS,借阅日期2007-12-01, BOOKS.编号=LOANS.编号, BORROWERS.证号=LOANS.证号,OK,第2步优化（选择下移）后的语法树,该投影能否与选择交换？,不能！,怎么办？,利用投影的幂等律插入一个投影,算法第3步，投影下移,51,书名，姓名,LOANS,BOOKS,BORROWERS,借阅日期2007-12-01, BOOKS.编号=LOANS.编号, BORROWERS.证号=LOANS.证号,书名，姓名，BOOKS.编号，LOANS.编号,交换,52,书名，姓名,LOANS,BOOKS,BORROWERS,借阅日期2007-12-01, BOOKS.编号=LOANS.编号, BORROWERS.证号=LOANS.证号,书名，姓名，BOOKS.编号，LOANS.编号,对笛卡尔分配,53,书名， BOOKS.编号,书名，姓名,LOANS,BOOKS,BORROWERS,借阅日期2007-12-01, BOOKS.编号=LOANS.编号, BORROWERS.证号=LOANS.证号,姓名，LOANS.编号,OK,还需下移,54,书名， BOOKS.编号,书名，姓名,LOANS,BOOKS,BORROWERS,借阅日期2007-12-01, BOOKS.编号=LOANS.编号, BORROWERS.证号=LOANS.证号,姓名，LOANS.编号,插入一个投影,姓名，LOANS.编号， BORROWERS.证号，LOANS.证号,下移,55,书名， BOOKS.编号,书名，姓名,LOANS,BOOKS,BORROWERS,借阅日期2007-12-01, BOOKS.编号=LOANS.编号, BORROWERS.证号=LOANS.证号,姓名，LOANS.编号,姓名，LOANS.编号， BORROWERS.证号，LOANS.证号,对笛卡尔分配,56,LOANS.编号， LOANS.证号,姓名， BORROWERS.证号,书名， BOOKS.编号,书名，姓名,LOANS,BOOKS,BORROWERS,借阅日期2007-12-01, BOOKS.编号=LOAN