An Introduction to Database System上海第二工业大学上海第二工业大学 计算机与信息学院计算机与信息学院数据库系统概论数据库系统概论An Introduction to Database System第九章第九章 关系查询处理和查询优化关系查询处理和查询优化An Introduction to Database System第九章第九章 关系查询处理和查询优化关系查询处理和查询优化9.1 关系数据库的查询处理9.2 关系数据库系统的查询优化9.3 代数优化9.4 物理优化An Introduction to Database System9.1 关系数据库的查询处理关系数据库的查询处理9.1.1 查询处理的步骤n查询分析：对查询语句进行语法和词法分析n查询检查：n检查语义：语句中使用的对象的存在性和有效性n用户权限和和完整性检查n检查通过后，把查询语句转换成等价的关系代数表达式（查询树即语法分析树）An Introduction to Database System语法分析树：语法分析树：结果结果project(Sname)select(SC.Cno= 2 ) join(Student.Sno=SC.Sno)StudentSCAn Introduction to Database Systemn查询优化：选择一个高效的查询处理策略，方法有代数优化、物理优化，选择的依据有基于规则、基于代价或基于语义n执行查询：依据优化器得到的策略生成查询计划，由代码生成器生成可执行代码。An Introduction to Database System9.1.2 实现查询操作的算法示例实现查询操作的算法示例1.选择操作的常用算法n全表扫描，选出符合条件的元组n使用索引可快速获取符合选择条件的元组指针，如sage=20或sage20。n组合条件如：sage20 and sdept=CSn方 法 1： 分 别 选 出 符 合 sage20条 件 的 元 组 指 针 和 符 合sdept=CS条件的元组指针，然后求它们的交集n方法2：先选出符合sage20条件的元组指针，然后对选出的元组判断是否符合sdept=CS条件。n第一种方法在sage和sdept上均有索引的情况下比较有效，第二种方法应该优先选出选择条件中有索引的元组。An Introduction to Database System2.连接操作的常用算法（假定为等值连接）：Select a.sno,a.sname,b.cno,b.grade from student a,sc b where a.sno=b.sno连接的总体思路：扫描student，对每一元组的sno，扫描grade的sno，把相同值的元组和student对应元组进行连接后输出。An Introduction to Database System循环嵌套方法：嵌套扫描两个表，总循环次数为两个元组个数的乘积。排序-合并方法：根据两个表的sno进行排序，两个循环均不必进行全表扫描。效率大大提高。索引连接方法：对sc关于sno建立索引，内层循环中由于sc建立的索引，所以不必全表扫描。An Introduction to Database SystemHash join方法：适用大表和小表的连接1 依据Hash函数把小表数据放入内存（可保留少量数据在临时表空间中）（小表数据的一次扫描） 2 每读取大表的一条记录（大表数据的一次扫描） ，就和小表中内存中的数据进行比较（有了hash函数，比较就不需要扫描小表），如果符合，则立即输出数据。而如果大表的数据与小表中临时表空间的数据相符合，先不输出，而等大表的所有数据都读取完毕，才一起输出（减少读取硬盘的次数）。 3.Hash Join方法只需要对两个表进行一次扫描，并且极大地降低了读取硬盘的次数。An Introduction to Database System9.2.1 查询优化概述查询优化概述n查询效率是衡量RDBMS重要性能指标。nRDBMS通过查询优化提升查询效率。n关系的结构化查询语言SQL高级别的语义（只需指出做什么而不必给出怎么做），使RDBMS进行查询优化成为可能。nRDBMS的查询优化，使用户不必考虑如何最好地表达查询以获得较好的效率。An Introduction to Database System系统进行优化较用户优化的优势：系统进行优化较用户优化的优势：n优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息。n如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划而不必重写程序。n优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。n优化器中包括了很多复杂的优化技术。An Introduction to Database System查询优化目标查询优化目标n查询优化的总目标 选择有效策略，求得给定关系代数表达式的值（关系），使得查询代价最小。n查询执行策略的代价构成：总代价=I/O代价 + CPU代价 + 内存代价 + 通信代价 An Introduction to Database System9.2.2 查询优化的必要性查询优化的必要性 例：求选修了课程2的学生姓名 SELECT Student.SnameFROM Student, SCWHERE Student.Sno=SC.SnoAND SC.Cno=2; n以下考察不同的执行策略对数据读写上需要的时间An Introduction to Database System查询优化的必要性（续）查询优化的必要性（续） 假设：1：Student:1000条，SC:10000条， 选修2号课程:50条2：一个内存块可存放元组:10个Student，或100个SC，内存容量可以存放: 5块Student元组、 1块SC元组和若干块连接结果元组3：读写速度：20块/秒4：连接方法：基于数据块的嵌套循环法 An Introduction to Database System执行策略执行策略1:笛卡尔积、选择、投影笛卡尔积、选择、投影Q1sname(Student.Sno=SC.SnoSC.Cno=2 (StudentSC) StudentSC： 读取总块数= 读Student表块数 + 读SC表遍数 *每遍块数=1000/10+(1000/(105) (10000/100) =100+20100=2100 读数据时间=2100/20=105秒每次可读student的10X5个元组，然后以块为单位读入全部SC，产生笛卡尔积An Introduction to Database System中间结果大小 = 1000*10000 = 107 写中间结果时间 = 10000000/10/20 = 50000秒（假设每个内存块可存放10个元组的中间结果）读数据时间 = 50000秒总时间 =1055000050000秒 = 100105秒 = 27.8小时An Introduction to Database System执行策略执行策略2：自然连接、选择、投影：自然连接、选择、投影2. 2 name(SC.Cno= 2 (Student SC)读取总块数= 2100块读数据时间=2100/20=105秒中间结果大小=10000 （减少1000倍）写中间结果时间=10000/10/20=50秒读数据时间=50秒时间1055050秒205秒=3.4分An Introduction to Database System执行策略执行策略3：选择、自然连接、投影：选择、自然连接、投影3. 3 Sname(Student SC.Cno= 2 (SC)读SC表总块数= 10000/100=100块读数据时间=100/20=5秒中间结果大小=50条 不必写入外存读Student表总块数= 1000/10=100块读数据时间=100/20=5秒 总时间55秒10秒 An Introduction to Database System9.3 代数优化代数优化n关系代数表达式：关系代数运算符经过有限次复合后得到的式子，其值仍为关系。（P60）n关系代数表达式等价：即关系代数表达式E1和E2中代入相同的关系，其结果相同，记为：E1E2。An Introduction to Database System9.3.1 关系代数表达式等价变换规则关系代数表达式等价变换规则设E1、E2等是关系代数表达式，F是条件表达式l. 连接、笛卡尔积交换律E1 E2 E2E1E1 E2E2 E1 E1 F E2E2 F E1 An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续） 2. 连接、笛卡尔积的结合律 (E1E2) E3 E1 (E2E3) (E1 E2) E3 E1 (E2 E3) (E1 E2) E3 E1 (E2 E3) F1 F2 F1 F2An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续） 3. 投影的串接定律 A1,A2, ,An( B1,B2, ,Bm(E) A1,A2, ,An (E)假设：1)E是关系代数表达式2)Ai(i=1，2，n), Bj(j=l，2，m)是属性名3)A1, A2, , An构成Bl，B2，Bm的子集 An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续） 4. 选择的串接定律 F1 （ F2（E） F1 F2(E)n选择的串接律说明选择条件可以合并n这样一次就可检查全部条件。 An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续） 5. 选择与投影的交换律(1)假设: 选择条件F只涉及属性A1，An F (A1,A2, ,An(E) A1,A2, ,An(F(E)(2)假设: F中有不属于A1, ,An的属性B1,Bm A1,A2, ,An ( F (E) A1,A2, ,An(F (A1,A2,An,B1,B2, ,Bm(E)An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续） 6. 选择与笛卡尔积的交换律(1) 假设：F中涉及的属性都是E1中的属性 F (E1E2)F (E1)E2(2) 假 设 ： F=F1F2， 并 且 F1只 涉 及 E1中 的 属 性 ， F2只涉及E2中的属性，则由上面的等价变换规则1，4，6可推出： F(E1E2) F1(E1)F2 (E2)An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续） (3) 假设： F=F1F2，F1只涉及E1中的属性，F2涉及E1和E2两者的属性，则： F(E1E2) F2(F1(E1)E2)7. 选择与并的交换假设：E=E1E2，E1，E2有相同的属性名F(E1E2) F(E1) F(E2)8. 选择与差运算的交换假设：E1与E2有相同的属性名F(E1-E2) F(E1) - F(E2) An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续） 9. 投影与笛卡尔积的交换假设：E1和E2是两个关系表达式， A1，An是E1的属性， B1，Bm是E2的属性 A1,A2, ,An,B1,B2, ,Bm （E1E2) A1,A2, ,An（E1) B1,B2, ,Bm(E2)An Introduction to Database System关系代数等价变换规则（续）关系代数等价变换规则（续） l0. 投影与并的交换假设：E1和E2 有相同的属性名： A1,A2, ,An(E1E2) A1,A2, ,An(E1) A1,A2, ,An(E2) An Introduction to Database System小结小结1-2: 连接、笛卡尔积的交换律、结合律3： 合并或分解投影运算4： 合并或分解选择运算5-8： 选择运算与其他运算交换5，9，10： 投影运算与其他运算交换 An Introduction to Database System9.3.2 关系代数的启发式的优化算法关系代数的启发式的优化算法n选择运算应尽可能先做：选择运算减小了中间关系中元组数量n在执行连接操作前对关系适当进行预处理n按连接属性排序n在连接属性上建立索引n投影运算和选择运算同时做：在扫描关系时同时进行投影运算和选择运算，避免重复扫描关系n将投影运算与其前面或后面的双目运算(关系代数的运算符除投影和选择外均为双目运算符)一起做。An Introduction to Database Systemn某些选择运算同它前面要执行的笛卡尔积结合起来成为连接运算，连接运算比产生笛卡尔后进行选择运算要快的多n提取公共子表达式：可把满足公共子表达式的关系（不太大的情况下）读入内存以提高查询效率。An Introduction to Database System遵循启发式规则，运用等价变换规则优化关遵循启发式规则，运用等价变换规则优化关系表达式的算法：系表达式的算法：算法：关系代数表达式的优化算法输入：依据一个关系表达式的查询树。算法输出：优化的查询树方法：（1）分解选择运算利用规则4把形如F1 F2 Fn (E)变换为 F1 (F2( (Fn(E) ) ，为（2）做准备。An Introduction to Database System关系代数表达式的优化算法关系代数表达式的优化算法 (续续)（2）对每一个选择运算，利用规则48尽可能把它移到树的叶端。（选择优先）（3）对每一个投影运算，利用规则3，5，l0，11中的一般形式尽可能把它移向树的叶端。（投影优先）n选择和投影运算均能减少中间结果，具体哪个更优先，取决于具体关系中行和列哪个数据量更大。An Introduction to Database System（4）利用等价变化3-5，合并串接的选择运算成一个选择运算和合并串接的投影运算成一个投影运算，以便能在一次扫描中完成运算，如：A3 (A5(E) ) A4Sname,cnamesno,sname,ssexAn Introduction to Database System9.4 物理优化物理优化n物理优化指存取路径和底层操作算法的选择，主要研究根据查询的不同特点，选择操作和连接操作中对9.1.2中各种算法的选择。n有基于启发式、基于代价估算和两者结合的优化方法。An Introduction to Database System基于启发式的优化：基于启发式的优化：一.选择操作的优化规则n对于小关系，不论是否有索引，均使用全表扫描。下面规则则对大关系而言。n包含主码等值的查询，一定使用主码索引。n包含非主属性等值查询，若有关于该非主属性的索引，则估算查询结果的元组数量，与整个元组数量比例大的话，使用全表扫描，否则使用索引扫描。An Introduction to Database Systemn对and连接的条件，若有相应的组合索引，则使用索引扫描；若部分有索引，则先使用索引扫描，选出符合部分条件的元组，在其中再选出符合其他条件的元组。n对or连接的条件，一般使用全表扫描。例如关于A,B有索引，（not A） or （not B）可优化为not (A and B)，事实上一些DBMS也会作此优化(前者若使用索引，必须两次全表扫描，而后者一次全表，一次在前一次结果上再扫描)。n An Introduction to Database System二二.连接操作的优化规则连接操作的优化规则n连接属性均排序，使用排序-合并方法n仅一个表的连接属性有索引，使用索引连接方法。n上述条件均不满足，若一个表较小，则可以选用Hash join方法n嵌套循环方法不需要任何前提条件，但较小的表的扫描应作为外循环，可减少读块的次数。（极端情况下，小表只要读一次）An Introduction to Database System基于代价估算的优化基于代价估算的优化n根据数据库的状态计算各种操作算法的执行代价，选择代价最小的算法。n执行代价的计算方法：n在数据字典中存放优化器所需要的统计信息，如表的元组数，元组长度、列值个数、最大、最小值、列上是否有索引等。n根据以上的统计信息，计算各种算法的代价估值。An Introduction to Database System优化的一般步骤优化的一般步骤 (续续)（1）把查询转换成某种内部表示例：求选修了课程2的学生姓名SELECT Student.SnameFROM Student, SCWHERE Student.Sno=SC.SnoAND SC.Cno=2; An Introduction to Database System（1）把查询转换成某种内部表示）把查询转换成某种内部表示语法树 结果结果project(Sname)select(SC.Cno= 2 ) join(Student.Sno=SC.Sno)StudentSCAn Introduction to Database System关系代数语法树关系代数语法树Sname SC.Cno=2 Student.Sno=SC.S StudentSCAn Introduction to Database System（2）代数优化）代数优化利用优化算法把语法树转换成标准（优化）形式Sname Student.Sno=SC.Sno SC.Cno= 2 StudentSCAn Introduction to Database System（3）物理优化：选择低层的存取路径）物理优化：选择低层的存取路径- 优化器查找数据字典获得当前数据库状态信息选择字段上是否有索引连接的两个表是否有序连接字段上是否有索引然后根据一定的优化规则选择存取路径 如本例中若SC表上建有Cno的索引，则应该利用这个索引，而不必顺序扫描SC表。 An Introduction to Database System（4）生成查询计划，选择代价最小的）生成查询计划，选择代价最小的在作连接运算时，若两个表(设为R1，R2)均无序，连接属性上也没有索引，则可以有下面几种查询计划： 对两个表作排序预处理 对R1在连接属性上建索引 对R2在连接属性上建索引 在R1，R2的连接属性上均建索引对不同的查询计划计算代价，选择代价最小的一个。在计算代价时主要考虑磁盘读写的I/O数，内存CPU处理时间在粗略计算时可不考虑。 同结果查询语句效率存在较大差异的实例同结果查询语句效率存在较大差异的实例(在对在对datadate索引下，后者执行效率高很多索引下，后者执行效率高很多)nselect * from datedata a where datadate=all (select datadate from datedata b where a.stockid=b.stockid and datadate2014-1-1)nselect * from datedata a where datadate= (select max(datadate) from datedata b where a.stockid=b.stockid and datadate2014-1-1)An Introduction to Database System