【精选】18_关系查询处理和查询优化.ppt

关系查询处理和查询优化 单世民 查询处理 查询处理是指从数据库中提取数据所涉及的一系列活动，包括： 将用高层数据库语言表示的查询语句（如：SQL）翻译成能在文件系统这一物理层次上实现的表达式（如关系代数）； 为优化查询而进行的各种转换； 查询的实际执行。 查询处理过程 查询的代价 可以通过查询对各种资源的使用状况测量查询处理的代价，这些资源包括：磁盘存取、查询在CPU的执行时间、通信开销、所需的内存量。 总代价=I/O代价+CPU代价+内存代价+通信代价 在大型的数据库系统中，磁盘的访问时间（10ms/次）通常是整个查询中的主要部分。因此，一般用磁盘的存取时间来衡量查询执行计划的好坏。 查询的代价 集中式数据库 单用户系统总代价 = I/O代价 + CPU代价 多用户系统总代价 = I/O代价 + CPU代价 + 内存代价 分布式数据库总代价 = I/O代价 + CPU代价[+ 内存代价] + 通信代价 查询的代价 磁盘存取代价可以用磁盘块传输数来度量 为了简化磁盘存取时间代价的计算： 假定所有块传送的代价相同。该假定忽略了： 旋转等待时间：等待所需要的数据（扇区）旋转到读写头下的时间延迟。 寻道时间（有哪些信誉好的足球投注网站时间）：将磁头移动到所期望的磁道或柱面的时间； 忽略了将查询的最终结果写回到磁盘的代价。 查询的代价 由于磁盘缓冲区的影响，不知道所需的磁盘块是否在内存，所以只能假设是最坏的情况。假定所有数据块都在磁盘上，没有读入内存。 在估计代价时要考虑的因素 关系的元组数、磁盘块数、一个磁盘能存放的元组数、元组的大小、属性上不同取值的元组数… 树形索引的平均扇出系数、层数、最底层索引的块数… 查询处理 基本查询操作的实现方法： 选择 条件表达式condition的几种情况 C1:无条件 C2:等值比较（Sno C3:范围比较（Sage25） C4:组合条件（Sdept=‘CS’ AND Sage25） 查询处理 基本查询操作的实现方法： 连接 几种实现方法 1.嵌套循环方法（nested loop） 2.排序合并方法（sort-merge join） 3.索引连接方法（index join） 4.Hash Join方法 查询优化 查询优化的必要性查询优化极大地影响RDBMS的性能。 查询优化的可能性关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义。 由DBMS进行查询优化的好处 用户不必考虑如何最好地表达查询以获得较好的效率系统可以比用户程序的优化做得更好 优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息 如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。 优化器中包括了很多复杂的优化技术 查询优化目标 查询优化的总目标 选择有效策略，求得给定关系表达式的值 实际系统的查询优化步骤 1. 将查询转换成某种内部表示，通常是语法树 2. 根据一定的等价变换规则把语法树转换成标准（优化）形式 3. 选择低层的操作算法。对于语法树中的每一个操作计算各种执行算法的执行代价，选择代价小的执行算法 4. 生成查询计划(查询执行方案)。查询计划是由一系列内部操作组成的。 优化必要性实例 求选修了2号课程的学生姓名 写出可行的关系代数表达式 优化必要性实例 假设1：Student:1000条,SC:10000条, 选修2号课程:50条 假设2：一个内存块装:10个Student元组, 或100个SC元组内存中一次可以存放: 5块Student元组,1块SC元组和若干块连接结果元组 假设3：读写速度：20块/秒 假设4：连接方法：基于数据块的嵌套循环法 策略1 ① Student×SC读取总块数= 读Student表块数 + 读SC表遍数*每遍块数 =1000/10+(1000/(10×5)) ×(10000/100) =100+20×100=2100（块）读数据时间=2100/20=105秒中间结果大小 = 1000*10000 = 107 (1千万条元组)写中间结果时间 =10/20 = 50000秒? ②б 读数据时间 = 50000秒? ③П 总时间 =105＋50000＋50000秒 = 100105秒 = 27.8小时 策略2 ①连接操作读取总块数= 2100块读数据时间=2100/20=105秒中间结果大小=10000 （减少1000倍）写中间结果时间=10000/10/20=5