《第15讲数据库查询处理与优化资料》由会员分享，可在线阅读，更多相关《第15讲数据库查询处理与优化资料（83页珍藏版）》请在金锄头文库上搜索。
1、1,第15讲 关系查询与优化,2,实例,应用实例 假设学生-课程数据库中有1000个学生，10000个选课记录，其中选修“c02”课程的记录为50个。 一个磁盘块能存储10个S元组，或100个SC 元组。 用SQL语句表达查询：选修了“c02”课程的学生姓名。 用多种等价的关系代数表达式来完成这一查询。 分析该查询在不同存储结构和索引结构的磁盘I/O次数。,3,实例,【例】查询选修了“c02”课程的学生姓名 Q1: SELECT SN FROM S，SC WHERE S.Sno=SC.Sno AND SC.Cno= c02 ;,Q2: SELECT SN FROM S WHERE Sno IN
2、 （SELECT Sno FROM SC WHERE Cno=c02）；,4,实例,【例】查询选修了“c02”课程的学生姓名, Sn (S.Sno=SC.Sno SC.Cno=2 (SSC) Sn (SC.Cno= 2 (S SC) Sn (S SC.Cno= 2 (SC),5,关系查询与优化,查询处理步骤 查询优化技术 代数优化 物理优化,6,查询语句,查询解析器,查询分析,查询预处理器,关系代数查询树,查询优化器,查询计划的执行代码,执行引擎,执行结果,查询预处理,查询优化,查询执行,数据字典,数据库系统的查询处理步骤,SELECT Sn FROM S，SC WHERE S.Sno=SC.
3、Sno AND SC.Cno= c02 ;,语法分析树,关系代数优化查询树,查询代码生成器,生成执行代码,查询处理器的组成和查询处理的典型步骤,7,查询分析与预处理,查询分析 接受类似SQL这样的高级查询语言表示的查询，并进行词法分析和语法分析。,8,【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。,查询分析与预处理,Q1: SELECT SN FROM S，SC WHERE S.Sno=SC.Sno AND SC.Cno= c02 ; Q2: SELECT SN FROM S WHERE Sno IN （SELECT Sno FROM SC WHERE Cno=c0
4、2）,9,【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。,查询分析与预处理,用查询语句Q1实现两个关系的连接查询的语法分析树,10,【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。,查询分析与预处理,用查询语句Q2实现两个关系的嵌套查询的语法分析树,11,查询分析与预处理,查询有效性检查 根据数据字典对合法的查询语句进行语义检查。 检查语句中的数据库对象在所查询的特定数据库模式中是否为有效且有语义含义的名字。 检查所有属性的类型是否与其使用相对应，以及根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查。,12,查询分析与预处理
5、,生成关系代数初始查询树 查询预处理器采用一些相应的规则，用一个或多个关系代数运算符替换语法树上的结点与结构，生成一个对应于SQL查询的关系代数初始查询树。 关系代数查询树是一个树数据结构，在查询树中，查询的输入关系表示为叶结点，关系代数操作表示为内部结点，一元关系操作符只有一个子结点，二元关系操作符有两个子结点。,13,查询分析与预处理,每个内部节点用关系操作符来标记，每个叶子结点用关系名来标记。一元关系操作符只有一个孩子，二元操作符有两个孩子。,Q1查询的关系代数查询树,【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。,Q1：SN (S.Sno=SC.Sno SC
6、.Cno=c02 (SSC),14,查询分析与预处理,Q2查询的关系代数查询树,【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。,Q2：SN (S Sno(SC.Cno= c02 (SC) ),15,查询语句,查询解析器,查询预处理器,关系代数查询树,查询优化器,查询计划的执行代码,执行引擎,执行结果,数据字典,查询分析与预处理,SELECT Sn FROM S，SC WHERE S.Sno=SC.Sno AND SC.Cno= c02 ;,语法分析树,关系代数优化查询树,查询代码生成器,Sn (S.Sno=SC.Sno SC.Cno= c02 (SSC),16,由查
7、询优化器将查询预处理器所生成的关系代数初始查询树转换成一个预期所需执行时间较小的等价的关系代数查询树，得到一个可被转换成最有效的物理查询计划的一个“优化”的逻辑查询计划。,代数优化,17,代数优化的必要性,代数优化,【例】分析实现“查询选修了课程号为c02课程的学生姓名”的两种关系代数查询树的执行效率。,Q1：SN (S.Sno=SC.Sno SC.Cno=c02 (SSC),Q2：SN (S Sno(SC.Cno= c02 (SC) ),18,代数优化的必要性,代数优化,在衡量代价时，需要使用如下一些参数： 操作符使用的内存大小M。 假设内存被分成缓冲区，缓冲区的大小与磁盘块的大小相同。M表
8、示一个特定的操作符执行时可以获得的内存缓冲区的数目。 关系R所占磁盘块的大小B(R) 通常假设R聚集存储在B个块或近似B个块中。 关系R中元组的数目T(R) 一个块中能容纳的R 的元组数可表示为T/B。 关系R的一个属性列上不同值的数目V(R,a)。,19,代数优化,【例】分析实现“查询选修了课程号为c02课程的学生姓名”的两种关系代数查询树的执行效率。 （1）T(S)=1000，T(SC)=10000。选修“c02” 课程的元组为50个。 （2）假设数据记录均为定长记录，一个磁盘块能存储10个S元组记录，或100个SC 元组记录。则B(S)=100， B(SC)=100。 （3）对关系S和关
9、系SC的连接采用嵌套循环方法，选择关系S作为外循环关系。内存的磁盘缓冲区M=7，可同时容纳5块关系S的磁盘块、1块关系SC的磁盘块，1块用于存放中间结果。 （4）关系S和SC的运算结果装满一个缓冲区块后需及时地由缓冲区存储到磁盘上的中间文件中，一个缓冲区块能存储10个运算结果记录。 （5）假设缓冲区管理器每秒读写20个磁盘块。,代数优化的必要性,20,1.计算广义笛卡尔积 SSC,代数优化,Q1：SN (S.Sno=SC.Sno SC.Cno=c02 (SSC),21,磁盘,B(S)=100块,B(SC)=100块,T(S)*T(SC)/10,5块,1块,1块,内存,20次,100次,106次
10、,代数优化,22,1.计算广义笛卡尔积 SSC 读取关系S和关系SC的总的磁盘块数 =读取关系S的磁盘块数+ 读取关系SC的遍数 每遍读取的关系SC的磁盘块数 =B(S)+ (100/5) B(SC) =100+20100=2100（块） 读数据时间=2100/20=105秒 运算中间结果元组数= 1000*10000 = 107 运算中间结果需占用的磁盘块数=107 /10=106（块） 运算中间结果写入磁盘时间 = 107 /10/20 = 5104秒,代数优化,Q1：SN (S.Sno=SC.Sno SC.Cno=c02 (SSC),23,2. 选择操作S.Sno=SC.Sno SC.C
11、no= c02 选择操作执行时间 =中间结果文件读取时间 =运算中间结果写入磁盘时间 =5104（s） 运算结果只有50条记录，可驻留内存。 3.投影操作SN 对内存的50条记录进行操作，忽略不计。 查询Q1所需总时间 =105 5104 5104 =100105（s） 27.8（h）,代数优化,Q1：SN (S.Sno=SC.Sno SC.Cno=c02 (SSC),24,1.读SC作选择和投影Sno(SC.Cno= c02 (SC) ) 读取关系SC的磁盘块数= B(SC)=100（块） 读数据时间=100/20=5（s） 在内存中，对读取的数据进行选择和投影操作，时间忽略不计。 满足条件
12、的中间结果元组数=50，驻留内存，不必用中间文件。 2.读S作连接和投影SN (S Sno(SC.Cno= c02 (SC) ) 读取关系S的磁盘块数= B(S)=100（块） 读数据时间=100/20=5（s） 在内存中，对读取的S元组与50个选课元组进行连接操作后投影， 时间忽略不计。 查询Q2所需总时间 = 55=10（s）,代数优化,Q2：SN (S Sno(SC.Cno= c02 (SC) ),25,代数优化的必要性 对于实现同一查询的不同的关系代数表达式（查询树），其操作的次序不同，查询效率不同，查询时间相差很大。 有必要对查询预处理器产生的关系代数初始查询树进行优化，得到较优的逻
13、辑查询计划，而不管用户书写的SQL查询是什么形式。,代数优化,如何改变关系代数表达式的操作次序，提高其查询效率？,26,代数优化 关系代数表达式（查询树）的优化就是指按照一定的规则，改变关系代数表达式中操作的次序和组合，将其转换为一个可以更高效执行的关系代数表达式（查询树）。 基于代数等价的启发式优化,代数优化,27,基于代数等价的启发式优化 通过利用一些启发式规则，将一个代数表达式转换为另一个不同的但等价的代数表达式，产生可被进一步优化的查询执行计划。 关系代数表达式等价：指用相同的关系实例代替两个表达式中相应的关系所得到的结果是相同的。,代数优化,28,基于代数等价的启发式优化 常用的等价
14、变换规则 设E、E1、E2等是关系代数表达式，F、F1、F2是条件表达式 1.连接、笛卡尔积交换律 E1 E2 E2E1 E1 E2 E2 E1 E1 F E2 E2 F E1 2. 连接、笛卡尔积的结合律 (E1E2) E3 E1 (E2E3) (E1 E2) E3 E1 (E2 E3) (E1 F1 E2) F2 E3 E1 F1 (E2 F2 E3),代数优化,29,基于代数等价的启发式优化 常用的等价变换规则 3. 投影的串接定律 A1,A2, ,An(B1,B2,Bm(E) A1,A2, ,An (E) A1, A2, , An构成B1，B2，Bm的子集 4. 选择的串接定律 F1
15、(F2(E ) ) F1 F2(E),代数优化,30,基于代数等价的启发式优化 常用的等价变换规则 5. 选择与投影的交换律 F (A1,A2,An(E) A1,A2,An(F(E) F只涉及属性A1，An A1,A2, ,An ( F(E) A1,A2,An (F (A1,A2, ,An,B1,B2, ,Bm(E) F中有不属于A1, ,An的属性B1,Bm,代数优化,31,基于代数等价的启发式优化 常用的等价变换规则 6. 选择与笛卡尔积的交换律 F (E1E2) F (E1)E2 F中涉及的属性都是E1中的属性 F(E1E2) F1(E1)F2 (E2) F=F1F2，并且F1只涉及E1中的属性， F2只涉及E2中的属性 F(E1E2) F2(F1(E1)E2) F=F1F2，F1只涉及E1中的属性，F2涉及E1和E2两者的属性,代数优化,32,基于代数等价的启发式优化 常用的等价变换规则 7. 选择对自然连接的分配律 F(E
