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

An Introduction to Database System 上海第二工业大学计算机与信息学院数据库系统概论 An Introduction to Database System 第九章关系查询处理和查询优化 An Introduction to Database System 第九章关系查询处理和查询优化 关系数据库的查询处理 关系数据库系统的查询优化 代数优化 物理优化 An Introduction to Database System 关系数据库的查询处理 查询处理的步骤?查询分析:对查询语句进行语法和词法分析?查询检查: ?检查语义:语句中使用的对象的存在性和有效性?用户权限和和完整性检查?检查通过后,把查询语句转换成等价的关系代数表达式(查询树即语法分析树) An Introduction to Database System 语法分析树: 结果 project(Sname) select(o= ?2?) join(=) Student SC An Introduction to Database System ?查询优化:选择一个高效的查询处理策略,方法有代数优化、物理优化,选择的依据有基于规则、基于代价或基于语义?执行查询:依据优化器得到的策略生成查询计划,由代码生成器生成可执行代码。 An Introduction to Database System 实现查询操作的算法示例 ?全表扫描,选出符合条件的元组?使用索引可快速获取符合选择条件的元组指针,如 sage=20 或 sage>20 。?组合条件如: sage>20 and sdept= ‘ CS ’?方法 1 :分别选出符合 sage>20 条件的元组指针和符合 sdept= ‘ CS ’条件的元组指针,然后求它们的交集?方法 2 :先选出符合 sage>20 条件的元组指针,然后对选出的元组判断是否符合 sdept= ‘ CS ’条件。?第一种方法在 sage 和 sdept 上均有索引的情况下比较有效,第二种方法应该优先选出选择条件中有索引的元组。 An Introduction to Database System (假定为等值连接): Select ,,o, from student a,sc b where = ●连接的总体思路:扫描 student ,对每一元组的 sno ,扫描 grade 的 sno ,把相同值的元组和 student 对应元组进行连接后输出。 An Introduction to Database System ●循环嵌套方法:嵌套扫描两个表,总循环次数为两个元组个数的乘积。●排序- 合并方法:根据两个表的 sno 进行排序, 两个循环均不必进行全表扫描。效率大大提高。●索引连接方法:对 sc 关于 sno 建立索引,内层循环中由于 sc建立的索引,所以不必全表扫描。 An Introduction to Database System ● Hash join 方法:适用大表和小表的连接 1 依据 Hash 函数把小表数据放入内存(可保留少量数据在临时表空间中)(小表数据的一次扫描) 2 每读取大表的一条记录(大表数据的一次扫描) ,就和小表中内存中的数据进行比较(有了 hash 函数,比较就不需要扫描小表),如果符合,则立即输出数据。而如果大表的数据与小表中临时表空间的数据相符合,先不输出,而等大表的所有数据都读取完毕,才一起输出(减少读取硬盘的次数)。 Join 方法只需要对两个表进行一次扫描,并且极大地降低了读取硬盘的次数。 An Introduction to Database System 查询优化概述?查询效率是衡量 RDBMS 重要性能指标。? RDBMS 通过查询优化提升查询效率。?关系的结构化查询语言 SQL 高级别的语义(只需指出做什么而不必给出怎么做), 使 RDBMS 进行查询优化成为可能。? RDBMS 的查询优化,使用户不必考虑如何最好地表达查询以获得较好的效率。