9-1-0

数据库系统概论AnIntroductiontoDatabaseSystem第九章关系查询处理和查询优化第九章关系系统及其查询优化9.1关系数据库系统的查询处理9.2关系数据库系统的查询优化9.3代数优化9.4物理优化9.1.1查询处理步骤9.1关系数据库系统的查询处理•依据优化器得到的执行策略生成查询计划•代码生成器(codegenerator)生成执行查询计划的代码•查询优化：选择一个高效执行的查询处理策略•查询优化分类：–代数优化：指关系代数表达式的优化–物理优化：指存取路径和底层操作算法的选择•查询优化方法选择的依据：–基于规则(rulebased)–基于代价(costbased)–基于语义(semanticbased)•根据数据字典对合法的查询语句进行语义检查•根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查•检查通过后把SQL查询语句转换成等价的关系代数表达式•RDBMS一般都用查询树(语法分析树)来表示扩展的关系代数表达式•对查询语句进行扫描、词法分析和语法分析•从查询语句中识别出语言符号•进行语法检查和语法分析一、选择操作的实现•［例1］Select*fromstudentwhere条件表达式；考虑条件表达式的几种情况：C1：无条件；C2：Sno＝'200215121'；C3：Sage20；C4：Sdept＝'CS'ANDSage20；9.1.2实现查询操作的算法示例•选择操作典型实现方法：–1.简单的全表扫描方法对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出适合小表，不适合大表–2.索引(或散列)扫描方法适合选择条件中的属性上有索引通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组•［例1-C2］以C2为例，Sno＝‘200215121’，并且Sno上有索引(或Sno是散列码)•［例1-C3］以C3为例，Sage20，并且Sage上有B+树索引•［例1-C4］以C4为例，Sdept＝‘CS’ANDSage20，如果Sdept和Sage上都有索引：–算法一：分别用上面两种方法分别找到Sdept＝‘CS’的一组元组指针和Sage20的另一组元组指针,求这2组指针的交集,到student表中检索。–算法二：找到Sdept＝‘CS’的一组元组指针，通过这些元组指针到student表中检索，对得到的元组检查另一些选择条件(如Sage20)是否满足。二、连接操作的实现•连接操作是查询处理中最耗时的操作之一•本节只讨论等值连接(或自然连接)最常用的实现算法•［例2］SELECT*FROMStudent，SCWHEREStudent.Sno=SC.Sno；•1.嵌套循环方法•2.排序-合并方法•3.索引连接方法•4.HashJoin方法–对外层循环(Student)的每一个元组(s)，检索内层循环(SC)中的每一个元组(sc)–检查这两个元组在连接属性(sno)上是否相等–如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止取Student表中第一个Sno，依次扫描SC表中具有相同Sno的元组当扫描到Sno不相同的第一个SC元组时，返回Student表扫描它的下一个元组，再扫描SC表中具有相同Sno的元组，把它们连接起来重复上述步骤直到Student表扫描完在SC表上建立属性Sno的索引对Student中每一个元组，由Sno值通过SC的索引查找相应的SC元组把这些SC元组和Student元组连接起来循环执行②③，直到Student表中的元组处理完为止–把连接属性作为hash码，用同一个hash函数把R和S中的元组散列到同一个hash文件中•划分阶段–对包含较少元组的表(比如R)进行一遍处理–把它的元组按hash函数分散到hash表的桶中•连接阶段–对另一个表(S)进行一遍处理–把S的元组散列到适当的hash桶中–把元组与桶中所有来自R并与之相匹配的元组连接起来9.2关系数据库系统的查询优化9.2.1查询优化概述•关系查询优化是影响RDBMS性能的关键因素。它减轻了用户选择存取路径的负担。•优点：用户不必考虑如何最好的表达查询以获得较好的效率。关系系统具有查询优化功能，而非关系系统不具备。关系系统带有优化器，自动优化，用户只需提出“干什么”，不必提出“怎么干”。•查询优化目标：选择有效的策略，求得给定的关系表达式的值，使得查询代价最小(实际上是较小)系统优化器的基本功能•优化器可以从数据字典中获取许多统计信息，根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。•如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序。•优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。•优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。系统对查询优化的具体实现步骤•将查询转换成某种内部表示，通常是语法树。•根据一定的等价变换规则把语法树转换成标准（优化）形式。•选择低层的操作算法。•生成查询计划。系统查询的执行开销•在集中式数据库中：总代价=I/O代价+CPU代价•在多用户环境下：总代价=I/O代价+CPU代价+内存代价9.2.2查询优化的必要性•例求选修2号课程的学生姓名用SQL语言表达：selectStudent.SnamefromStudent,SCwhereStudent.Sno=SC.SnoandSC.Cno=’2’;用等价的关系代数表达式表示如下：Q1=Sname(Studnet.Sno=SC.SnoSC.Cno=’2’(Studnet×SC))Q2=Sname(SC.Cno=’2’(StudentSC))Q3=Sname(StudentSC.Cno=’2’(SC))三种查询用时比较假定学生-课程数据库中有l000个学生记录,l0000个选课记录，其中选修2号课程的选课记录为50个。若内存缓冲区一块能装10个Student记录或装100个SC记录。5块用于Studnet记录，一块用于SC记录，则读取总块数：按20块/秒的读写速度表示，则第①种方法需用查询时间为：105秒第②种方法需用查询时间为：205秒第③种仅需用10秒.这个简单的例子充分说明了查询优化的必要性.有索引的情况假如SC表在Cno字段上有索引，第l步就不必读取所有的SC元组，而只需读取Cno=‘2’的那些元组(50个)。存取的索引块和SC中满足条件的数据块大约总共3~4块。若student表在Sno上也有索引，则第2步也不必读取所有的student元组，因为满足条件的SC记录仅50个，涉及最多50个student记录，因此读取student表的块数也可大大减少。总的存取时间将进一步减少到数秒。9.3代数优化9.3.1关系代数表达式等价变换规则•代数优化策略：通过对关系代数表达式的等价变换来提高查询效率•关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的•两个关系表达式E1和E2是等价的，可记为E1≡E2常用的等价变换规则•定义：两个关系表达式E1，E2等价E1与E2的结果关系相同，用E1≡E2表示E1与E2等价。①连接、笛卡儿积的交换律E1×E2≡E2×E1E1E2≡E2E1E1E2≡E2E1其中F为连接运算条件②、×的结合律(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)FFF1F2F1F2③投影串接定律：A1,A2,…,An(B11,B22,…,Bn(E))≡A1,A2,…,An(E)其中{A1,A2,…An}{B1,B2,…Bn}④选择串接定律F1(F2(E))≡F1∧F2(E)⑤选择与投影的交换律F(A1,A2,…,An(E))≡A1,A2,…,An(F(E))其中{A1,A2,…An}包含F中涉及的属性。若F中有属性∈{B1,B2,…Bn}{A1,A2,…An},则有一般规则：A1,A2,…,An(F(E))≡A1,A2,…,An(F(A1,A2,…,An,B1,B2,…,Bm(E)))⑥与笛卡尔积的交换律10.若F中只涉及E1中的属性，则F(E1×E2)=F(E1)×E220.若F=F1∧F2，且F1E1，F2E2而Fi只涉及Ei中的属性，则F(E1×E2)=F1(E1)×F2(E2)30.若F1∈E1,F2∈E1∧E2,且F=F1∧F2F(E1×E2)=F2(F1(E1)×(E2))使部分选择在笛卡儿积前先做。⑦与∪的交换律设E=E1∪E2,且E1与E2有相同的属性名，则F(E1∪E2)≡F(E1)∪F(E2)⑧与差的交换律若E1与E2有相同的属性名，则F(E1-E2)≡F(E1)-F(E2)⑨与的交换律设E1和E2是两个关系表达式，A1，…An是E1的属性,B1,…,Bm是E2的属性,则A1,…An,B1,…Bm(E1E2)≡A1,…An(E1)B1,…Bm(E2)⑩与∪的交换律设E1与E2有相同的属性名，则A1,…An(E1∪E2)≡A1,…An(E1)∪A1,…An(E2)9.3.2查询树的启发式优化l.选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条。2.在执行连接运算之前应建立索引或排序(分类)3.投影与选择同时进行(变两个扫描为一次扫描)4.把投影同其前后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系。5.把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。6.找出公共子表达式。关系代数表达式的优化算法•优化思想：选择、投影尽早做，即把它们移到表达式语法树的下部。•优化工具：关系代数等价变换规则。•优化算法：关系表达式的优化输入----语法树描述输出----程序实现一般优化方法(1)利用规则④把形如F1∧F2,…,∧Fn(E)变换为F1(F2((Fn(E))))（2）对每个选择，利用规则④---⑧,尽可能把它移到树的叶端。（3）对每一个投影，利用规则③，⑨，⑩，⑤,把它尽可能移到叶端。（4）利用规则③---⑤,把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。（5）把上述得到的语法树的内结点分组。每一双目运算（×,,∪,－）和它所有的直接祖先为一组（这些直接祖先是，运算）。（6）生成一个程序，每组结点的计算是程序的一步。各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算。查询优化的一般步骤1.将要求查询转换成语法树（关系代数的内部表示）2.把语法树转化成优化形式--标准型。根据关系代数变换规则进行算法优化。3.选择低层优化路径。要充分考虑索引、数据的存储分布等存取路径。4.生成选择代价最小的查询计划。例：求选修了2号课程的学生姓名。SELECTStudent.SnameFROMStudent，SCWHEREStudent.Sno=SC.SnoANDSC.Cno='2'；1.将查询转换成语法树（关系代数的内部表示）内部表示的语法树关系代数语法树Project(Sname)Restrict(SC.Cno=’2’)限制join(Student.Sno=SC.Sno)SCStudentSC.Cno=’2’Student.Sno=SC.SnoSnameSCStudent2.把语法树转化成优化形式--标准型SC.Cno=’2’SnameSCStudentSC.Cno=’2’Student.Sno=SC.SnoSnameSCStudent根据关系代数变换规则进行算法优化。将上面语法树中的选择SC.Cno=’2’移到叶端，生成一棵新的语法树：3.选择低层优化路径。扫描SC表是