关系系统及其查询优化

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,关系系统及其查询优化,第,4,章,关系系统的定义,关系系统的分类,关系系统的查询优化,关系系统及其查询优化,查询优化的一般准则,关系代数等价变换规则,关系代数表达式的优化算法,优化的一般步骤,2024/9/21,1,4.1,关系系统,支持关系模型的关系数据库管理系统简称关系系统。,下述关系的,DBMS,不能称为关系系统,不支持关系数据结构的系统,支持关系数据结构，但无,、,、,运算功能的系统,支持关系数据结构，有,、,、,运算，但要求定义物理,存取路径的系统,可称为关系系统的,DBMS,，当且仅当,1,）支持关系数据结构（关系数据库）,2,）支持,、,、 运算，且不要求用户定义任何物理存取路径,4.1.1,关系系统的定义,2024/9/21,2,4.1.2,关系系统的分类,4,全关系系统：,支持关系模型的所有特征。在关系完备系统的基础上，进一步支持实体完整性和参照完整性等。,DB,ORACLE,SYBASE, ,已接近这个目标。目前尚无全关系系统。,1,表式系统,：,仅支持关系数据结构，不支持集合级的操作。,（不能算关系系统）,2,（最小）关系系统：,支持关系数据结构，支持,、,、 运算，且不定义物理路径。,3,关系完备系统：,支持关系数据结构和所有关系代数操作（或功能上与关系代数等价）。,DB,ORACLE,SYBASE,属于这一类。,2024/9/21,3,关系系统分类,2024/9/21,4,4.2,关系数据库系统的查询优化,4.2.1,关系系统及其查询优化,查询处理的过程,查询语句,查询输出,关系代数表达式,执行计划,语法分析与翻译,执行引擎,优化器,有关数据的统计信息,数据,2024/9/21,5,系统优化,优化器可以从数据字典中获取许多统计信息，从而选择有效的执行计划；,如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划；,优化器可以考虑数百种不同的执行计划；,优化器中包括了很多复杂的优化技术。,2024/9/21,6,实际系统的查询优化步骤,1.,将查询转换成某种内部表示，通常是语法树,2.,根据一定的等价变换规则把语法树转换成标准（优化）形式,3.,选择低层的操作算法,对于语法树中的每一个操作,根据存取路径、数据的尺寸、数据的存储分布、存储数据的聚簇等信息来计算各种执行算法的执行代价,选择代价小的执行算法,4.,生成查询计划,(,查询执行方案,),2024/9/21,7,常用查询优化技术,用启发式规则来缩减查询计划的搜索空间,利用统计信息估算执行代价,基于代价（目前商品化,RDBMS,大都采用）,代价模型,集中式数据库,单用户系统：总代价,= I/O,代价,+ CPU,代价,多用户系统：总代价,= I/O,代价,+ CPU,代价,+,内存代价,分布式数据库,总代价,= I/O,代价,+ CPU,代价,+,内存代价, +,通信代价,2024/9/21,8,4.2.2,一个实例,例,.,求选,2,号课程的学生姓名,SELECT,Student.Sname,FROM,Student,，,SC,WHERE,Student.Sno = SC.Sno,AND,Cno = 2,；,数据量：,Student:1000,条；,SC:10000,条；选修,2,号课程,:50,条,一个内存块装元组,:10,个,Student,或,100,个,SC,，内存中可以,存放,:5,块,Student,元组和,1,块,SC,元组,读写速度：,20,块,/,秒,假设：,2024/9/21,9,1.,1,Sname,(,Student.Sno=SC.Sno SC.Cno=c2,(StudentSC),计算广义笛卡尔积,(,StudentSC,),读取总块数,=,读,Student,表块数,+,读,SC,表遍数 * 每遍块数,= 1000/10+(1000/(105) (10000/100) = 2100,读数据时间,=2100/20=105,秒,中间结果大小,= 1000*10000 = 10,7,(1,千万条元组,),写中间结果时间,= 10000000/10/20 = 50000,秒, 选择操作,(,),读数据时间,= 50000,秒, 投影,(,),总时间,=105,50000,50000,秒,= 100105,秒,= 27.8,小时,2024/9/21,10,2.,2,name,(,SC.Cno= 2,(Student SC),自然连接,( ),读取总块数,= 2100,块,读数据时间,=2100/20=105,秒,中间结果大小,=10000,（即,SC,表中记录条数，减少,1000,倍）,写中间结果时间,=10000/10/20=50,秒,选择操作,(,),读数据时间,=50,秒,投影,(,),总时间,105,50,50,秒,205,秒,=3.4,分,2024/9/21,11,3.,2,Sname,(Student ,SC.Cno= 2,(SC),选择操作,(,),读,SC,表总块数,= 10000/100=100,块,读数据时间,=100/20=5,秒,中间结果大小,=50,条 （不必使用中间文件）,自然连接（ ）,读,Student,表总块数,= 1000/10=100,块,读数据时间,=100/20=5,秒, 投影,(,),总时间,5,5,秒,10,秒,2024/9/21,12,4.2.3,查询优化的一般准则,选择运算应尽可能先做,在执行连接操作前对关系适当进行预处理,（索引连接方法和排序合并连接方法）,投影运算和选择运算同时做,将投影运算与其前后的双目运算结合（连接、并、差、交等）,选择运算和笛卡尔积运算结合（等值连接比笛卡儿积省时间）,提取公共子表达式（例如，定义视图的表达式）,2024/9/21,13,4.2.4,关系代数等价变换规则,l.,连接、笛卡尔积交换律,2.,连接、笛卡尔积的结合律,3.,投影的串接定律,4.,选择的串接定律,5.,选择与投影的交换律,6.,选择与笛卡尔积的交换律,7.,选择与并的交换,8.,选择与差运算的交换,9.,投影与笛卡尔积的交换,l0.,投影与并的交换,2024/9/21,14,4.2.5,关系代数表达式的优化算法,分解选择运算,通过交换选择运算，将其尽可能移到叶端,通过交换投影运算，将其尽可能移到叶端,合并串接的选择和投影，以便能同时执行或在一次扫描中完成,对内结点分组,生成程序,2024/9/21,15,4.2.6,优化的一般步骤,1,把查询转换成某种内部表示,2,代数优化：把语法树转换成标准（优化）形式,3,物理优化：选择低层的存取路径,4,生成查询计划，选择代价最小的,2024/9/21,16,Student,SC,Join(Student.Sno=SC.Sno),Select(SC.Cno=2),Project(Sname),结 果,Student.Sno=Sc.Sno,Sc.Sno,=2,Student SC,Sname,Student.Sno=Sc.Sno,Sc.Sno=2,Sname,SC,Student,2024/9/21,17,小 结,关系系统,关系系统的定义,关系系统的分类,关系系统的查询优化,关系系统及其查询优化,查询优化的一般准则,关系代数等价变换规则,关系代数表达式的优化算法,优化的一般步骤,2024/9/21,18,