华科数据库系统原理第九章研讨.pptx

第9章关系查询处理和查询优化9.1问题的提出非过程化，无需显示指明存取路经。查询操作的多解性：同一个查询操作可能存在多种实现途径（算法不同、存取方法不同）。代数优化——优化关系代数表达式物理优化——优化存取路径和底层操作算法，可进一步分为基于规则的（rulebased）、基于代价的（costbased）和基于语义的（semanticbased）。12基于规则的基于代价的基于语义的关系代数等价变换规则查询处理步骤基本概念1查询分析（词法、语法、语义、符号名）查询树（querytree）语法分析树（syntaxtree）执行树执行计划3实例设有如下关系：学生（学号，姓名，性别，出生日期，所在系）课程（课号，名称，学分）成绩（学号，课号，成绩）要求查询选修了2号课程的学生姓名。可用如下等价的代数表达式来完成这一查询：Q1＝π姓名（σ学生.学号=成绩.学号∧课号=’2’（学生×成绩））Q2＝π姓名（σ课号=’2’(学生成绩））Q3＝π姓名（学生σ课号=’2’（成绩））由于查询执行的策略不同,查询时间相差很大。4统计量：学生记录——1000条；成绩记录——10000条；选修了2号课程的记录——50条。一个物理块（页面）能容纳：10条学生记录或100条成绩记录。内存仅提供7个存储页面，其中5页存放学生记录，1页存放成绩记录，1页存放中间结果。磁盘每秒钟读/写20块数据记录。采用嵌套循环实现方式。5外表:学生表内表:成绩表第一种情况：Q1＝π姓名（σ学生.学号=成绩.学号∧课号=’2’（学生×成绩））1．计算：学生×成绩读取的总块数为：1000/10+1000/(10×5)×10000/100=2100(块)所需时T1=2100/20=105(秒)笛卡儿集的元组个数为103×104＝107，设每块能装10个元组，则写出这些块所需的时间T2=106/20=5×104(秒)6注意:写出!2．作选择σ依次读入连接后的结果，选择满足条件的记录，假定内存处理时间忽略不计，则读取中间结果的时间T3与T2相等，即T3=5×104(秒)，满足条件的记录仅有50条，结果直接驻留内存。3．作投影π将内存中的结果在“姓名”上作投影，得最终结果，因此第一种情况下执行查询的总时间为：T=T1+T2+T3≈105(秒)（总时间约28小时）7第二种情况Q2＝π姓名（σ课号=’2’(学生成绩））1．计算自然连接读取学生表和成绩表的策略不变，总的读取时间仍105秒，但自然连接的结果比第一种情况大大减少，为104条，因此，写出这些元组所需时间为104/10/20＝50（秒）。2．作选择读取中间结果所需的时间仍为50（秒），符合条件的记录为50条。3．作投影将中间结果投影输出。第二种情况总的执行时间为：105＋50＋50＝205（秒）810000条成绩记录第三种情况Q3＝π姓名（学生σ课号=’2’（成绩））1．先对成绩表作选择运算，只读取一遍成绩表，存取花费时间为5秒，因满足条件的记录为50条，不必使用中间文件。2．读取学生表并与内存中的成绩记录作连接，花费时间5秒。3．输出投影结果。第三种情况总的执行时间为10秒。上例充分说明查询优化的必要性，同时给出一些查询优化方法的基本思想（避免笛卡儿积,尽量让选择运算在连接运算之前执行）。91000/10/20基本概念2选择运算的实现方法：全表扫描索引扫描连接运算的实现方法：嵌套循环连接（nestedloop）排序—合并连接（sort-mergejoin）Hash连接（hashjoin）索引连接（indexjoin）10两个关系是否只扫描一次？如果两个关系的连接属性均存在重复值又会如何？HASH连接9.2查询优化的任务：提高速度（DBMS）9.3查询优化的目标1、减少中间关系规模2、减少I/O关系代数表达式的等价变换规则（课本269～271页）SQL查询的代数处理过程（课本272页，图9.3~9.5）9.4一般策略（查询树的启发式优化）1、“选择”尽可能提前执行；最基本一条，因为“选择”使中间结果变小。2、索引和排序特别是对连接运算，连接前“先排序”或“建立”索引，提高速度。11例如：对Borrower与Loans进行自然联接计算时：①对loans按card-no建立索引；②对Borrower每一元组的card-no值：·通过loans索引查元组·Borrower元组与相应元组连接起来③无需反复扫描loans3、“投影”和“选择”同时进行，（避免多次扫描关系，否则投影选择各扫描一次）。前提是两种运算对同一关系运算才成立。124、（某些）选择与选择前的笛卡尔积结合扫描得到的元组立即与参与计算的另一元组做匹配条件过滤，将这种笛卡尔积转变为连接运算。连接运算（特别是等值连接运算）比笛卡尔积快。5、投影与其前后的其它双目运算同时进行，避免重复扫