第15讲数据库查询处理与优化.

第15讲关系查询与优化1第15讲关系查询与优化第15讲关系查询与优化2实例•应用实例–假设学生-课程数据库中有1000个学生，10000个选课记录，其中选修“c02”课程的记录为50个。–一个磁盘块能存储10个S元组，或100个SC元组。•用SQL语句表达查询：选修了“c02”课程的学生姓名。•用多种等价的关系代数表达式来完成这一查询。•分析该查询在不同存储结构和索引结构的磁盘I/O次数。第15讲关系查询与优化3实例【例】查询选修了“c02”课程的学生姓名Q1:SELECTSNFROMS，SCWHERES.Sno=SC.SnoANDSC.Cno='c02';Q2:SELECTSNFROMSWHERESnoIN（SELECTSnoFROMSCWHERECno=‘c02’）；第15讲关系查询与优化4实例【例】查询选修了“c02”课程的学生姓名πSn(бS.Sno=SC.Sno∧SC.Cno='2'(S×SC))πSn(бSC.Cno='2'(S⋈SC))πSn(S⋈бSC.Cno='2'(SC))第15讲关系查询与优化5关系查询与优化•查询处理步骤•查询优化技术–代数优化–物理优化第15讲关系查询与优化6查询语句查询解析器查询分析查询预处理器关系代数查询树查询优化器查询计划的执行代码执行引擎执行结果查询预处理查询优化查询执行数据字典数据库系统的查询处理步骤SELECTSnFROMS，SCWHERES.Sno=SC.SnoANDSC.Cno='c02';语法分析树关系代数优化查询树查询代码生成器生成执行代码查询处理器的组成和查询处理的典型步骤第15讲关系查询与优化7查询分析与预处理•查询分析–接受类似SQL这样的高级查询语言表示的查询，并进行词法分析和语法分析。第15讲关系查询与优化8【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。查询分析与预处理Q1:SELECTSNFROMS，SCWHERES.Sno=SC.SnoANDSC.Cno='c02';Q2:SELECTSNFROMSWHERESnoIN（SELECTSnoFROMSCWHERECno=‘c02’）第15讲关系查询与优化9【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。查询分析与预处理用查询语句Q1实现两个关系的连接查询的语法分析树QuerySELECTSelListFROMFromListWHEREConditionAttributeRelNameANDS.SNSConditionAttribute=ValueSC.CNO‘c02’FromListRelNameSC,ConditionAttribute=AttributeS.SNOSC.SNO第15讲关系查询与优化10【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。查询分析与预处理用查询语句Q2实现两个关系的嵌套查询的语法分析树QuerySELECTSelListFROMFromListWHEREConditionAttributeRelNameAttributeIN()SNSSNOQuerySELECTSelListFROMFromListWHEREConditionAttributeRelNameAttribute=SNOSCCNO‘c02’Value第15讲关系查询与优化11查询分析与预处理•查询有效性检查–根据数据字典对合法的查询语句进行语义检查。•检查语句中的数据库对象在所查询的特定数据库模式中是否为有效且有语义含义的名字。•检查所有属性的类型是否与其使用相对应，以及根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查。第15讲关系查询与优化12查询分析与预处理•生成关系代数初始查询树–查询预处理器采用一些相应的规则，用一个或多个关系代数运算符替换语法树上的结点与结构，生成一个对应于SQL查询的关系代数初始查询树。•关系代数查询树是一个树数据结构，在查询树中，查询的输入关系表示为叶结点，关系代数操作表示为内部结点，一元关系操作符只有一个子结点，二元关系操作符有两个子结点。第15讲关系查询与优化13查询分析与预处理每个内部节点用关系操作符来标记，每个叶子结点用关系名来标记。一元关系操作符只有一个孩子，二元操作符有两个孩子。Q1查询的关系代数查询树【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'(S×SC))第15讲关系查询与优化14查询分析与预处理Q2查询的关系代数查询树【例】在“学生-课程”数据库中查询选修了课程号为“c02”课程的学生姓名。Q2：πSN(S⋈πSno(бSC.Cno='c02'(SC)))第15讲关系查询与优化15查询语句查询解析器查询预处理器关系代数查询树查询优化器查询计划的执行代码执行引擎执行结果数据字典查询分析与预处理SELECTSnFROMS，SCWHERES.Sno=SC.SnoANDSC.Cno='c02';语法分析树关系代数优化查询树查询代码生成器πSn(бS.Sno=SC.Sno∧SC.Cno='c02'(S×SC))QuerySELECTSelListFROMFromListWHEREConditionAttributeRelNameANDS.SNSConditionAttribute=ValueSC.CNO‘c02’FromListRelNameSC,ConditionAttribute=AttributeS.SNOSC.SNO第15讲关系查询与优化16•由查询优化器将查询预处理器所生成的关系代数初始查询树转换成一个预期所需执行时间较小的等价的关系代数查询树，得到一个可被转换成最有效的物理查询计划的一个“优化”的逻辑查询计划。代数优化第15讲关系查询与优化17•代数优化的必要性代数优化【例】分析实现“查询选修了课程号为‘c02’课程的学生姓名”的两种关系代数查询树的执行效率。Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'(S×SC))Q2：πSN(S⋈πSno(бSC.Cno='c02'(SC)))第15讲关系查询与优化18•代数优化的必要性代数优化在衡量代价时，需要使用如下一些参数：–操作符使用的内存大小M。•假设内存被分成缓冲区，缓冲区的大小与磁盘块的大小相同。M表示一个特定的操作符执行时可以获得的内存缓冲区的数目。–关系R所占磁盘块的大小B(R)•通常假设R聚集存储在B个块或近似B个块中。–关系R中元组的数目T(R)•一个块中能容纳的R的元组数可表示为T/B。–关系R的一个属性列上不同值的数目V(R,a)。第15讲关系查询与优化19代数优化【例】分析实现“查询选修了课程号为‘c02’课程的学生姓名”的两种关系代数查询树的执行效率。（1）T(S)=1000，T(SC)=10000。选修“c02”课程的元组为50个。（2）假设数据记录均为定长记录，一个磁盘块能存储10个S元组记录，或100个SC元组记录。则B(S)=100，B(SC)=100。（3）对关系S和关系SC的连接采用嵌套循环方法，选择关系S作为外循环关系。内存的磁盘缓冲区M=7，可同时容纳5块关系S的磁盘块、1块关系SC的磁盘块，1块用于存放中间结果。（4）关系S和SC的运算结果装满一个缓冲区块后需及时地由缓冲区存储到磁盘上的中间文件中，一个缓冲区块能存储10个运算结果记录。（5）假设缓冲区管理器每秒读写20个磁盘块。•代数优化的必要性第15讲关系查询与优化201.计算广义笛卡尔积S×SC代数优化Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'(S×SC))第15讲关系查询与优化21…10个S元组……100个SC元组……10个SC×S元组……10个S元组…100个SC元组…10个SC×S元组…磁盘B(S)=100块B(SC)=100块T(S)*T(SC)/105块1块1块内存20次100次106次代数优化第15讲关系查询与优化221.计算广义笛卡尔积S×SC读取关系S和关系SC的总的磁盘块数=读取关系S的磁盘块数+读取关系SC的遍数×每遍读取的关系SC的磁盘块数=B(S)+(100/5)×B(SC)=100+20×100=2100（块）读数据时间=2100/20=105秒运算中间结果元组数=1000*10000=107运算中间结果需占用的磁盘块数=107/10=106（块）运算中间结果写入磁盘时间=107/10/20=5×104秒代数优化Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'(S×SC))第15讲关系查询与优化232.选择操作бS.Sno=SC.Sno∧SC.Cno='c02'选择操作执行时间=中间结果文件读取时间=运算中间结果写入磁盘时间=5×104（s）运算结果只有50条记录，可驻留内存。3.投影操作πSN对内存的50条记录进行操作，忽略不计。查询Q1所需总时间=105＋5×104＋5×104=100105（s）≈27.8（h）代数优化Q1：πSN(бS.Sno=SC.Sno∧SC.Cno='c02'(S×SC))第15讲关系查询与优化241.读SC作选择和投影πSno(бSC.Cno='c02'(SC))读取关系SC的磁盘块数=B(SC)=100（块）读数据时间=100/20=5（s）在内存中，对读取的数据进行选择和投影操作，时间忽略不计。满足条件的中间结果元组数=50，驻留内存，不必用中间文件。2.读S作连接和投影πSN(S⋈πSno(бSC.Cno='c02'(SC)))读取关系S的磁盘块数=B(S)=100（块）读数据时间=100/20=5（s）在内存中，对读取的S元组与50个选课元组进行连接操作后投影，时间忽略不计。查询Q2所需总时间=5＋5=10（s）代数优化≈Q2：πSN(S⋈πSno(бSC.Cno='c02'(SC)))第15讲关系查询与优化25•代数优化的必要性–对于实现同一查询的不同的关系代数表达式（查询树），其操作的次序不同，查询效率不同，查询时间相差很大。–有必要对查询预处理器产生的关系代数初始查询树进行优化，得到较优的逻辑查询计划，而不管用户书写的SQL查询是什么形式。代数优化如何改变关系代数表达式的操作次序，提高其查询效率？第15讲关系查询与优化26•代数优化–关系代数表达式（查询树）的优化就是指按照一定的规则，改变关系代数表达式中操作的次序和组合，将其转换为一个可以更高效执行的关系代数表达式（查询树）。•基于代数等价的启发式优化代数优化第15讲关系查询与优化27•基于代数等价的启发式优化–通过利用一些启发式规则，将一个代数表达式转换为另一个不同的但等价的代数表达式，产生可被进一步优化的查询执行计划。•关系代数表达式等价：指用相同的关系实例代替两个表达式中相应的关系所得到的结果是相同的。代数优化第15讲关系查询与优化28•基于代数等价的启发式优化–常用的等价变换规则设E、E1、E2等是关系代数表达式，F、F1、F2是条件表达式1.连接、笛卡尔积交换律E1×E2≡E2×E1E1⋈E2≡E2⋈E1E1⋈FE2≡E2⋈FE12.连接、笛卡尔积的结合律(E1×E2)×E3≡E1×(E2×E3)(E1⋈E2)⋈E3≡E1⋈(E2⋈E3)(E1⋈F1E2)⋈F2E3≡E1⋈F1(E2⋈F2E3)代数优化第15讲关系查询与优化29•基于代数等价的启发式优化–常用的等价变换规则3.投影的串接定律πA1,A2,…,An(πB1,B2,…,Bm(E))≡πA1,A2,…,An(E){A1,A2,…,An}构成{B1，B2，…，Bm}的子集4.选择的串接定律бF1(бF2(E))≡бF1∧F2(E)代数优化第15讲关系查询与优化30•基于代数等价的启发式优化–常用的