5第4章关系系统及其查询优化

1数据库原理及应用数据库原理及应用PrincipleandApplicationofDatabase第四章关系系统及其查询优化2数据库原理及应用学习目标掌握关系系统的定义和分类掌握关系系统查询优化的总目标和步骤理解关系系统查询优化的一般准则3数据库原理及应用关系模型的三要素：关系数据结构：域及域上定义的关系。关系操作：并、交、差、广义笛卡尔积、选择、投影、连接和除。关系完整性：实体完整性、参照完整性、用户自定义完整性。4.1关系系统4数据库原理及应用关系系统的定义一个系统可定义为关系系统，当且仅当它至少：(1)支持关系数据库(关系数据结构)。从用户观点看，数据库由表构成，并且只有表这种结构。(2)支持选择、投影和(自然)连接运算。对这些运算不必要求定义任何物理存取路径。4.1关系系统5数据库原理及应用关系系统定义的三个问题为什么关系系统除了要支持关系数据结构外，还必须支持选择、投影和连接运算呢？为什么要求这三种运算不能依赖于物理存取路径呢？为什么要求关系系统支持这三种最重要的运算而不是关系代数的全部运算功能呢？6数据库原理及应用关系系统的分类按照E.F.CODD的思想，依据系统支持关系模型的程度，可分成四类：表式系统：仅支持关系(即表)数据结构，不支持集合级的操作，如倒排表列系统，它不能算作关系系统。(最小)关系系统：如前面定义所述，支持关系数据结构和选择、投影、连接三种关系操作，如FoxBASE、FoxPro等。7数据库原理及应用关系完备的系统：支持关系数据结构和所有的关系代数操作。如Oracle7.X、SybaseSQLSERVER10等90年代的许多RDBMS。全关系系统：支持关系模型的所有特征。如目前大多数主流关系系统产品：Oracle9i/10g/11i、SybaseAdaptiveServer12、MicroSoftSQLSERVER2003/2005等已不同程度上接近或达到了这个目标。8数据库原理及应用查询优化概述：关系查询优化是影响RDBMS性能的关键因素，由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性。查询优化的优点：用户不必考虑如何最好地表达查询就可以获得较好的效率，系统优化比用户程序优化做得更好，这是因为：优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息。如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。优化器中包括了很多复杂的优化技术。4.2关系系统的查询优化9数据库原理及应用查询优化的目标：选择有效策略，求得给定关系表达式的值。实际系统查询优化的步骤将查询转换成某种内部表示，通常是语法树。根据一定的等价变换规则把语法树转换成标准(优化)形式。选择低层的操作算法。对于语法树中的每一个操作，计算各种执行算法的执行代价，选择代价小的执行算法。生成查询计划(查询执行方案)：由一系列内部操作组成的。代价模型集中式数据库：单用户系统的总代价=I/O代价+CPU代价；多用户系统的总代价=I/O代价+CPU代价+内存代价分布式数据库：总代价=I/O代价+CPU代价[+内存代价]+通信代价10数据库原理及应用查询优化的必要性一个实例：求选修2号课程的学生姓名，用SQL语言表达为：SELECTStudent.SnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno='2';假设学生～课程数据库有1000个Student记录、10000个SC记录，其中选修2号课程的选课记录为50条。对于上述SQL查询，DBMS可以转化为如下几种等价的关系代数表达式：执行策略1：ПＳname(бStudent.Sno=SC.Sno∧SC.Cno='2'(Student×SC))执行策略2：ПＳname(бSC.Cno='2'(StudentSC))执行策略3：ПSname(StudentбSC.Cno='2'(SC))执行策略4：ПＳname(StudentбSC.Cno=‘2’(SC))，假设SC表在Cno上有索引，Student表在Sno上有索引。由于执行策略不同，查询的时间相差很大。11数据库原理及应用执行策略1：ПＳname(бStudent.Sno=SC.Sno∧SC.Cno='2'(Student×SC))计算广义笛卡尔积：把Student和SC的每个元组连接起来。方法是：在内存中尽可能多地装入某个表(如Student表)的若干块元组，留出一块存放另一个表(如SC表)的元组。然后把SC中的每个元组和Student中每个元组连接，连接后的元组装满一块后就写到中间文件上，再从SC中读入一块和内存中的Student元组连接，直到SC表处理完。再次读入若干块Student元组，读入一块SC元组，重复上述处理过程至Student表处理完假设一个内存块能装10个Student元组或100个SC元组，内存中一次可以存放5块Student元组和1块SC元组及若干块连接结果元组，则读取总块数=读Student表块数+读SC表遍数×每遍块数=1000/10+(1000/(10×5))×(10000/100)=2100若每秒读写20块，则读块总计时间=2100/20=105秒。连接后的元组数为1000*10000=107，设每块能装10个这样的元组，则写出这些块总计时间=107/10/20=50000秒。作选择操作：忽略内存处理时间，这一步共计时间同写中间文件50000秒作投影操作：时间可以忽略结论：查询总时间=(105＋50000＋50000)秒=100105秒=27.8小时。12数据库原理及应用执行策略2：ПＳname(бSC.Cno='2'(StudentSC))作自然连接为了执行自然连接，读取Student和SC表的策略不变，读取总块数2100，共计时间105秒。但自然连接的结果为10000，比策略1大大减少了，写出这些元组时间为10000/10/20=50秒。作选择操作读取中间文件块，作选择运算共计时间50秒。作投影操作时间可以忽略。结论：查询总时间＝(105＋50＋50)秒＝205秒=3.4分钟。13数据库原理及应用执行策略3：ПSname(StudentбSC.Cno='2'(SC))作选择操作只需读一遍SC表，读块总数=10000/100=100块，共计时间=100/20=5秒。因为满足条件的元组只有50个，不必使用中间文件写入外存。作自然连接读取Student表，把读入的Student元组和内存中的SC元组作连接，只需读一遍Student表，读块总数=1000/10=100块，共计时间=100/20=5秒。作投影操作时间可以忽略。结论：总时间＝(5＋5)秒＝10秒。14数据库原理及应用执行策略4：ПＳname(StudentбSC.Cno=‘2’(SC))，假设SC表在Cno上有索引，Student表在Sno上有索引。作选择操作根据SC表索引读取SC表总块数=50/1001块，共计时间1/20秒。因满足条件的元组只有50个，不必使用中间文件写入外存作自然连接根据Student表索引，读Student表总块数=50/10=5块，共计时间=5/20秒。作投影操作时间可以忽略。结论：查询总时间1秒。15数据库原理及应用查询优化的一般准则选择运算尽可能先做。这是最重要一条，目的是减小中间关系在执行连接操作前对关系适当进行预处理。预处理有两方法：索引连接法(在连接属性上建立索引，然后执行连接)、排序合并法(对关系排序，然后执行连接)。投影运算和选择运算同时进行。如有若干投影和选择运算，且它们都对同一关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系。将投影运算与其前面或后面的双目运算结合。目的是减少扫描关系的遍数。把某些选择与在其前要执行的笛卡尔积结合成为一个连接运算例：бStudent.Sno=SC.Sno(Student×SC)StudentSC提取公共子表达式。16数据库原理及应用关系代数等价变换规则：关系代数表达式的优化是查询优化的基本课题，而研究关系代数表达的优化又是从关系代数表达式的等价变换规则开始的。所谓关系代数表达式的等价是指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的。两个关系表达式E1和E2是等价的，记为E1≡E2。常用等价变换规则：设E1、E2等是关系代数表达式，F是条件连接、笛卡尔积的交换律E1×E2≡E2×E1E1E2≡E2E1E1FE2≡E2FE1连接、笛卡尔积的结合律(E1×E2)×E3≡E2×(E2×E3)(E1E2)E3≡E1(E2E3)(E1F1E2)F2E3≡E1F1(E2F2E3)17数据库原理及应用投影的串接定律：设E是关系代数表达式，Ai(i=1,2,…,n)、Bj(j=l,2,…,m)是属性名，{A1,A2,…,An}为{Bl,B2,…,Bm}的子集πA1,A2,,An(πB1,B2,,Bm(E))≡πA1,A2,,An(E)选择的串接定律：设E是关系代数表达式，F1、F2是条件。бF1(бF2(E))≡бF1∧F2(E)该定律说明选择条件可以合并，一次就可检查全部条件。选择与投影的交换律若选择条件F只涉及属性A1,…,An，则бF(πA1,A2,,An(E))≡πA1,A2,,An(бF(E))若F中有不属于A1,…,An的属性B1,…,Bm，则πA1,A2,,An(бF(E))≡πA1,A2,,An(бF(πA1,A2,,An,B1,B2,,Bm(E)))18数据库原理及应用选择与笛卡尔积的交换律若F中涉及的属性都是E1中的属性，则бF(E1×E2)≡бF(E1)×E2若F=F1∧F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则由上面的等价变换规则1，4，6可推出：бF(E1×E2)≡бF1(E1)×бF2(E2)若F=F1∧F2，F1只涉及E1中的属性，F2涉及E1和E2两者的属性，则бF(E1×E2)≡бF2(бF1(E1)×E2)它使部分选择在笛卡尔积前先做。选择与并的交换：设E=E1∪E2，E1、E2有相同的属性名，则бF(E1∪E2)≡бF(E1)∪бF(E2)19数据库原理及应用选择与差运算的交换：设E1与E2有相同的属性名，则бF(E1-E2)≡бF(E1)-бF(E2)投影与笛卡尔积的交换：设E1和E2是两个关系表达式，A1,…,An是E1的属性，B1,…,Bm是E2的属性，则πA1,A2,…,An,B1,B2,…,Bm(E1×E2)≡πA1,A2,…,An(E1)×πB1,B2,…,Bm(E2)投影与并的交换：设E1和E2有相同的属性名，则πA1,A2,…,An(E1∪E2)≡πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)小结：上述等价变换规则1～2为连接、笛卡尔积的交换律、结合律，3为合并或分解投影运算，4为合并或分解选择运算，5～8为选择运算与其他运算交换，5、9、10为投影运算与其他运算交换。20数据库原理及应用关系代数表达式的优化算法：输入一个关系表达式的语法树，输出计算该表达式的程序。具体方法是：分解选择运算：利用规则4把形如бF1∧F2∧…∧Fn(E)变换为бF1(бF2(…(бFn(E))…))通过交换选择运算，将其尽可能移到叶端：对每一个选择，利用规则4～8尽可能把它移到树的叶端。通过交换投影运算，将其尽可能移到叶端：对每一个投影利用规则3，9，l0，5中的一般形式尽可能把它移向树的叶端。合并串接的选择和投影，以便能同时执行或在一次扫描中完成利用规则3～5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影，使多个选择或投影能同时执行，或在一次扫描中全部完成。尽管这种变换似乎违背投影尽可能早做的原则，但这样做效率更高。21数据库原理及应用对内结点分组：每一双