数据库查询处理与优化.ppt

《数据库查询处理与优化.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第15讲关系查询与优化1实例应用实例假设学生-课程数据库中有1000个学生，10000个选课记录，其中选修“c02”课程的记录为50个。一个磁盘块能存储10个S元组，或100个SC元组。用SQL语句表达查询：选修了“c02”课程的学生姓名。用多种等价的关系代数表达式来完成这一查询。分析该查询在不同存储结构和索引结构的磁盘I/O次数。2实例【例】查询选修了“c02”课程的学生姓名Q1:SELECTSNFROMS，SCWHERES.Sno=SC.SnoANDSC.Cno='c02';Q2:SELECTS

2、NFROMSWHERESnoIN（SELECTSnoFROMSCWHERECno=‘c02’）；3实例【例】查询选修了“c02”课程的学生姓名πSn(бS.Sno=SC.Sno∧SC.Cno='2'(S×SC))πSn(бSC.Cno='2'(S⋈SC))πSn(S⋈бSC.Cno='2'(SC))4关系查询与优化查询处理步骤查询优化技术代数优化物理优化5查询语句查询解析器查询分析查询预处理器关系代数查询树查询优化器查询计划的执行代码执行引擎执行结果查询预处理查询优化查询执行数据字典数据库系统的查询

3、处理步骤SELECTSnFROMS，SCWHERES.Sno=SC.SnoANDSC.Cno='c02';语法分析树关系代数优化查询树查询代码生成器生成执行代码查询处理器的组成和查询处理的典型步骤6查询分析与预处理查询分析接受类似SQL这样的高级查询语言表示的查询，并进行词法分析和语法分析。7【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。查询分析与预处理Q1:SELECTSNFROMS，SCWHERES.Sno=SC.SnoANDSC.Cno='c02';Q2:SELEC

4、TSNFROMSWHERESnoIN（SELECTSnoFROMSCWHERECno=‘c02’）8【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。查询分析与预处理用查询语句Q1实现两个关系的连接查询的语法分析树9【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。查询分析与预处理用查询语句Q2实现两个关系的嵌套查询的语法分析树10查询分析与预处理查询有效性检查根据数据字典对合法的查询语句进行语义检查。检查语句中的数据库对象在所查询的特定数据库模式中是

5、否为有效且有语义含义的名字。检查所有属性的类型是否与其使用相对应，以及根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查。11查询分析与预处理生成关系代数初始查询树查询预处理器采用一些相应的规则，用一个或多个关系代数运算符替换语法树上的结点与结构，生成一个对应于SQL查询的关系代数初始查询树。关系代数查询树是一个树数据结构，在查询树中，查询的输入关系表示为叶结点，关系代数操作表示为内部结点，一元关系操作符只有一个子结点，二元关系操作符有两个子结点。12查询分析与预处理每个内部节点用关系

6、操作符来标记，每个叶子结点用关系名来标记。一元关系操作符只有一个孩子，二元操作符有两个孩子。Q1查询的关系代数查询树【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'(S×SC))13查询分析与预处理Q2查询的关系代数查询树【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。Q2：πSN(S⋈πSno(бSC.Cno='c02'(SC)))14查询语句查询解析器查询预处理器关系代数查询树查

7、询优化器查询计划的执行代码执行引擎执行结果数据字典查询分析与预处理SELECTSnFROMS，SCWHERES.Sno=SC.SnoANDSC.Cno='c02';语法分析树关系代数优化查询树查询代码生成器πSn(бS.Sno=SC.Sno∧SC.Cno='c02'(S×SC))15由查询优化器将查询预处理器所生成的关系代数初始查询树转换成一个预期所需执行时间较小的等价的关系代数查询树，得到一个可被转换成最有效的物理查询计划的一个“优化”的逻辑查询计划。代数优化16代数优化的必要性代数优化【例】分析

8、实现“查询选修了课程号为‘c02’课程的学生姓名”的两种关系代数查询树的执行效率。Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'(S×SC))Q2：πSN(S⋈πSno(бSC.Cno='c02'(SC)))17代数优化的必要性代数优化在衡量代价时，需要使用如下一些参数：操作符使用的内存大小M。假设内存被分成缓冲区，缓冲区的大小与磁盘块的大小相同。M表示一个特定的操作符执行时可以获得的内存缓冲区的数目。关系R所占磁盘块的大小B(R)通常假设R聚集存