06第四章 关系查询处理和查询优化.ppt

1、查询分析 从语法的角度对一条SQL语句进行分析，判断其是否 符合SQL的语法规则。 2、查询检查 从逻辑的角度对合法的SQL语句检查，同时进行安全 性和完整性检查。 3、查询优化 同一个查询有多种实现途径，从中选择出一种效率最 高的算法进行优化。包括代数优化和物理优化。 4、查询执行 依据优化结果执行查询，由代码生成器生成执行这个 查询的代码，得到查询结果。 一、选择操作的实现 二、连接操作的实现 语法树 关系代数语法树 * 第四章 关系查询处理和查询优化 关系数据库系统的查询处理 1 关系数据库系统的查询优化 2 代数优化 3 优化实例 4 4.1 关系数据库系统的查询处理 查询分析 查询检查 查询优化 查询执行 查询语句 词法分析 语法分析 语义分析 符号名转换 安全性检查 完整性检查 查询树(query tree) 代数优化 物理优化等 执行策略描述 代码生成 查询计划的执行代码 数据库 数据字典 4.1.1 查询处理步骤 4.1.2 实现查询操作的算法示例 SELECT * FROM student WHERE 条件表达式 假设条件表达式 可选择： C1: 无条件; C2: Sno = ‘009’; C3: Sage 17; C4: Sdept = ‘CS’ and Sage 17; 4.1.2 实现查询操作的算法示例 全表扫描 对查询的基本表进行顺序的逐行扫描，逐一检查元 组是否满足条件，把满足条件的元组作为结果输出。 （简单有效，适合小表，对大表费时） 索引扫描 通过索引找到满足条件的元组指针（物理地址）， 再通过指针直接找到元组。 4.1.2 实现查询操作的算法示例 例1：对C2条件表达式: Sno = ‘009’ 地址Ox00154 地址Ox00147 Sno Sname Ssex Sage Sdept 001 007 008 009 地址Ox00186 地址Ox00257 001 007 008 009 Sno Ox00147 Ox00154 Ox00186 Ox00257 元组指针 例2：C3条件表达式: Sage 17 Sno Sname Ssex Sage Sdept 001 007 008 009 17 18 20 21 Sage Ox00865 Ox00875 Ox00885 Ox00895 元组指针 4.1.2 实现查询操作的算法示例 SELECT * FROM Student，SC WHERE Student.Sno= SC.Sno 嵌套循环法 对外层(student)的每个元组，检索内层(SC)元组，判断 连接字段是否相等，满足条件则输出。 排序合并法 对待连接的两个表按照连接字段排序，然后进行连接，满 足条件则输出。 索引连接法 用索引进行元组查找，进行连接。 第四章 关系查询处理和查询优化 关系数据库系统的查询处理 1 关系数据库系统的查询优化 2 代数优化 3 优化实例 4 4.2.1 查询优化的概述 查询优化的必要性 查询优化极大地影响RDBMS的性能。 查询优化的可能性 关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义。 由DBMS执行查询优化的好处 —用户不必考虑如何最好地表达查询以获得较好的效率。 —系统可以比用户程序的优化做得更好 优化器可以从数据字典中获取许多统计信息，而用户程序则 难以获得这些信息。 (2) 如果数据库的物理统计信息改变了，系统可以自动对查询重 新优化以选择相适应的执行计划。 在非关系系统中必须重写程序，在实际应用中代价太大。 (3) 优化器可以考虑数百种不同的执行计划，而程序员一般只能 考虑有限的几种可能性。（关系代数） (4) 优化器中包括了很多复杂的优化技术，综合考虑软硬件条 件，分析查询代价。 总代价= I/O代价 + CPU代价+ 内存代价 + 通信代价 查询优化的总目标： 选择有效策略，使得总代价表达式的值最小。 4.2.1 查询优化的概述 查询优化一般步骤 1．把查询转换成某种内部表示（关系代数） 2．代数优化： 把语法树转换成标准（优化）形式。 3．物理优化： 选择低层的存取路径，索引利用方式。 4．生成查询计划，选择代价最小的。 4.2.1 查询优化的概述 4.2.2 实例 例：求选修了2号课程的学生姓名? SELECT Student.Sname FROM Student, SC WHE