西华师范大学计算机学院第四章第四章 关系系统及其查询优化关系系统及其查询优化 第四章 关系系统及其查询优化4.1 关系系统4.2 关系系统的查询优化4.3 小结 关系系统•能够在一定程度上支持关系模型的数据库管理系统是关系系统•由于关系模型中并非每一部分都是同等重要的•并不苛求一个实际的关系系统必须完全支持关系模型 关系模型•关系数据结构–域及域上定义的关系•关系操作–并、交、差、广义笛卡尔积、选择、投影、连接、除等 •关系完整性–实体完整性、参照完整性、用户自己定义的完整性 关系系统的定义 一个数据库管理系统可定义为关系系统，当且仅当它至少支持：1. 关系数据库（即关系数据结构）在用户眼里,数据库是由表,并且只有表构成的2. 支持选择、投影和（自然）连接运算 对这些运算不要求用户定义任何物理存取路径对关系系统的最低要求 关系系统的定义 ●不支持关系数据结构的系统显然不能称为关系系统●仅支持关系数据结构，但没有选择、投影和连接运算功能的系统仍不能算作关系系统–原因：选择、投影、连接运算是最有用的运算，有了这三种运算功能就能解决绝大部分的实际问题，提高用户的生产率•支持选择、投影和连接运算，但要求定义物理存取路径，这种系统也不能算作真正的关系系统–原因：降低或丧失了数据的物理独立性–因此,关系系统必须能自动选择路径,必须能查询优化,这是关系系统的关键技术。
4.1.2 关系系统的分类 •分类依据：支持关系模型的程度•分类⒈ 表式系统：支持关系数据结构(即表)，它不是关系系统 (a) (最小)关系系统； (b) 关系完备的系统； (c) 全关系系统一个关系数据模型（圆）由三部分组成： 结构S、完整性I和数据操纵M 每一部分中阴影的大小,表示支持该内容的程度 4.1.2 关系系统的分类 ⒉ (最小)关系系统：支持关系数据结构及选择、投影、连接关系操作，如FoxBASE和FoxPro ⒊ 关系完备的系统：支持关系数据结构及所有的关系代数操作⒋ 全关系系统：支持关系模型的所有特征，特别支持数据结构中域的概念, 支持实体完整性和参照完整性 目前,很多关系系统已接近了此目标 关系系统的分类 （续） 数据结构数据结构数据操作数据操作完整性完整性表式系统表式系统表表 (最小最小)关系系统关系系统表表选选择择、、投投影影、、连接连接 关系完备的系统关系完备的系统表表 全关系系统全关系系统 第四章 关系系统及其查询优化4.1 关系系统4.2 关系系统的查询优化4.3 小结 4.2 关系系统的查询优化 4.2.1 查询优化概述4.2.2 查询优化的必要性4.2.3 查询优化的一般准则4.2.4 关系代数等价变换规则4.2.5 关系代数表达式的优化算法4.2.6 优化的一般步骤 4.2.1 查询优化概述•查询优化的必要性–为了达到所需的性能要求，数据库系统必须使用查询优化技术。
•查询优化的可能性–关系表达式具有高度语义层次，使DBMS可以从关系表达式中分析查询语义 由DBMS进行查询优化的好处•自动优化系统中用户不必考虑如何最好地表达查询以获得较好的效率•优化器可以比用户程序的优化做得更好(1) 优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息，例如：每个基表中元组的数目、每个域中值的个数等因此优化器可以对给定查询的执行策略作出更为精确的计算，从而更有可能选择最高效的执行方案 由DBMS进行查询优化的好处(2)如果数据库的物理统计信息改变了，优化器可以自动对查询重新优化（即重新处理一遍原来的查询请求）以选择相适应的执行计划而在非关系系统中必须重写程序，这在实际应用中往往是不太可能的3)优化器可以考虑一个给定查询的成百上千种不同的执行计划，而程序员一般只能考虑有限的几种可能性4)优化器可以认为是包含着最优秀程序员的技巧和服务的程序 也即,优化器可以根据变化了的当前信息,自动选择一个对当时情况较有利的执行计划 但用户程序是不可能有此性能的,用户程序的执行计划是不会随系统当时的实际情况而变化的 查询优化目标•查询优化的目标选择有效策略,等价变换给定的关系表达式,使结果表达式求解（程序）的代价较小•实际系统的查询优化步骤1. 将查询转换成某种内部表示，通常是语法树2. 根据一定的等价变换规则把语法树转换成标准 （优化）形式 实际系统的查询优化步骤3. 选择低层的操作算法，根据存取路径、 数据的存储分布情况等，对于语法树中的每一个操作，计算各种执行算法的执行代价以选择代价小的执行算法4. 生成查询计划(查询执行方案)由以上三条最后生成了一系列的内部操作。
根据这些内部操作要求的执行次序,确定一个执行方案 代价模型•集中式数据库•单用户系统总代价 = I/O代价 + CPU代价•多用户系统总代价 = I/O代价 + CPU代价 + 内存代价•分布式数据库 总代价 = I/O代价 + CPU代价[+ 内存代价] + 通信代价 4.2.2 查询优化的必要性 关系代数和关系演算具有等价性， 同一个问题用同一种方法有不同的解决途径， 这些方法结果相同， 但执行效率有较大差别 下面先看一个实例， 说明查询优化的一般问题例：求选修了课程Ｃ2的学生姓名 SELECT Student.SnameFROM Student, SCWHERE Student.Sno=SC.SnoAND SC.Cno='2'; 查询优化的必要性（续） 假设1：外存：Student:1000条,SC:10000条, 选修2号课程:50条假设2：一个内存块装元组:10个Student, 或100个SC, 内存中一次可以存放: 5块Student元组, 1块SC元组和若干块连接结果元组假设3：读写速度：20块/秒假设4：连接方法：基于数据块的嵌套循环法 执行策略1Ｑ1＝ ПＳname(бStudent.Sno=SC.Sno ∧SC.Cno='2' (Student×SC)) ① Student×SC一般的做法是： 在内存中尽可能多地装入某个表（如s表）的若干块元组， 留出一块存放另一个表（如sc表）的元组， 然后把内存中sc的每个元组和s的每个元组连接， 连接后的元组装满一块后就写到中间文件上， 再从sc表中读入一块和内存中的s元组连接， 直到sc表处理完。
这时再一次读入若干块s元组， 读入一块sc元组， 重复上述处理过程， 直到把s表处理完在笛卡尔积操作中，表s的每个元组只装入内存一次，而sc的每个元组却要反复多次装入内存 读取总块数= 读Student表块数 + 读SC表遍数 *每遍块数 =1000/10+(1000/(10×5)) ×(10000/100) =100+20×100=2100 读数据时间=2100/20=105秒 不同的执行策略,考虑I/O时间中间结果大小 = 1000*10000 = 107 (1千万条元组)写中间结果时间 = 10000000/10/20 = 50000秒 ②б•假定内存处理时间不计， 这一步读取中间文件花费的时间需5×104秒（同写中间文件一样） ③П总时间 =105＋50000＋50000秒 = 100105秒 = 27.8小时 查询优化的必要性（续） 2. Ｑ2＝ ПＳname(бSC.Cno=' 2' (Student SC)) ①读取总块数= 2100块读数据时间=2100/20=105秒中间结果大小=10000 （减少1000倍）写中间结果时间=10000/10/20=50秒 ②б读取中间文件， 执行选择运算 读数据时间=50秒 ③П 总时间＝105＋50＋50秒＝205秒=3.4分 查询优化的必要性（续） 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秒 查询优化的必要性（续） 4. Ｑ2＝ ПＳname(Student бSC.Cno='2' (SC))假设SC表在Cno上有索引，Student表在Sno上有索引 ①б 读SC表索引=读SC表总块数= 50/100<1块读数据时间 中间结果大小=50条 不必写入外存 查询优化的必要性（续） ② 读Student表索引=读Student表总块数= 50/10=5块读数据时间 ③ П总时间<10秒 4.2.3 查询优化的一般准则 查询优化主要是合理安排操作的顺序，使系统效率较高。
优化是相对的， 变换后的表达式不一定是所有等价表达式中执行时间最少的 因此， 优化没有一个特定的模式， 常根据经验， 运用下列策略来完成•选择运算应尽可能先做 –在查询优化中，这是最重要、 最基本的一条 选择运算使中间结果显著变小，减少运算量和从外存读块的次数，从而使执行时间成数量级地减少•在执行连接操作前对关系适当进行预处理–按连接属性排序或在连接属性上建立索引，提高存取效率–例如,对两个表进行自然连接操作,则可先对两表建立有关索引,然后,只要对两表进行一遍扫描即可完成自然连接操作 提高了连接的速度 4.2.3 查询优化的一般准则（续） •同一关系的投影运算和选择运算同时进行 这样做可避免重复扫描关系，从而达到缩短时间的目的•将投影运算与其前面或后面的双目运算结合–目的：减少扫描关系的遍数 查询优化的一般准则 （续）•某些选择运算＋在其前面执行的笛卡尔积 ===> 连接运算 ，避免选择操作是在笛卡尔积运算完的一个较大关系上进行，减少时间和空间的开销 例：бStudent.Sno=SC.Sno (Student×SC) Student SC•找出公共子表达式,并把运算结果存于外存。
需要时,再从外存读入，以免重复计算 4.2.4 关系代数等价变换规则 •关系代数是关系数据理论的基础， 关系演算、SQL语言等都可以转化为关系代数去实现 所以关系代数表达式的优化是查询优化的基本课题•关系代数表达式等价–指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的,两个关系代数表达式E1和E2等价， 一般表示为： E1≡E2，例如R∩S≡R –(R-S) –上面的优化策略大部分都涉及到代数表达式的变换 常用的等价变换规则设E1、E2等是关系代数表达式，F是条件表达式 l. 连接、笛卡尔积交换律E1× E2≡ E2×E1E1 E2≡E2 E1 E1 F E2≡E2 F E1 关系代数等价变换规则（续） 2. 连接、笛卡尔积的结合律 (E1×E2) × E3 ≡ E1 × (E2×E3) (E1 E2) E3 ≡ E1 (E2 E3) (E1 E2) E3 ≡ E1 (E2 E3) F1 F2 F1 F2 关系代数等价变换规则（续） 3. 投影的串接定律 π A1,A2, ,An(π B1,B2, ,Bm(E))≡ π A1,A2, ,An (E)假设：1)E是关系代数表达式2)Ai(i=1，2，…，n), Bj(j=l，2，…，m)是属性名3){A1, A2, …, An}构成{Bl，B2，…，Bm}的子集 即：对同一关系连续的多个投影可以转换为仅含最少属性的投影操作。
关系代数等价变换规则（续） 4. 选择的串接定律 бF1 （ б F2（E））≡ бF1∧ F2(E)–选择的串接律说明 对同一关系连续的多个选择可以转换为一个用AND连接的选择操作–这样一次就可检查全部条件 关系代数等价变换规则（续） 5. 选择与投影的交换律(1)假设: 选择条件F只涉及属性A1，…，An бF (πA1,A2, ,An(E))≡ πA1,A2, ,An(бF(E)) (2)假设: F中有不属于A1, …,An的属性B1,…,Bm π A1,A2, ,An ( бF(E))≡ πA1,A2, ,An(бF (πA1,A2, ,An,B1,B2, ,Bm(E))) 关系代数等价变换规则（续） 6. 选择与笛卡尔积的交换律(1) 假设：F中涉及的属性都是E1中的属性 бF (E1×E2)≡бF (E1)×E2 (2) 假设：F=F1∧F2，并且F1只涉及E1中的属性， F2只涉及E2中的属性 则由上面的等价变换规则1，4，6可推出： бF(E1×E2) ≡б F1(E1)×бF2 (E2) 关系代数等价变换规则（续） (3) 假设： F=F1∧F2， F1只涉及E1中的属性， F2涉及E1和E2两者的属性 бF(E1×E2)≡б F2(бF1(E1)×E2) 它使部分选择在笛卡尔积前先做 关系代数等价变换规则（续） 7. 选择与并的交换假设：E=E1∪E2，E1，E2有相同的属性名бF(E1∪E2)≡ бF(E1)∪ бF(E2) 8. 选择与差运算的交换假设：E1与E2有相同的属性名бF(E1-E2)≡ бF(E1) - бF(E2) 关系代数等价变换规则（续） 9. 投影与笛卡尔积的交换假设：E1和E2是两个关系表达式， A1，…，An是E1的属性， B1，…，Bm是E2的属性 π A1,A2, …,An,B1,B2, …,Bm （E1×E2)≡π A1,A2, …,An（E1)× π B1,B2, …,Bm(E2) 关系代数等价变换规则（续） l0. 投影与并的交换假设：E1和E2 有相同的属性名 π A1,A2, …,An(E1∪E2)≡ π A1,A2, …,An(E1)∪ π A1,A2, …,An(E2) 小结1-2: 连接、笛卡尔积的交换律、结合律3： 合并或分解投影运算4： 合并或分解选择运算5-8： 选择运算与其他运算交换5，9，10： 投影运算与其他运算交换 4.2 关系系统的查询优化 4.2.1 查询优化概述4.2.2 查询优化的必要性4.2.3 查询优化的一般准则4.2.4 关系代数等价变换规则4.2.5 关系代数表达式的优化算法4.2.6 优化的一般步骤 4.2.5 关系代数表达式的优化算法 算法：关系表达式的优化输入：一个关系表达式的语法树。
输出：计算该表达式的程序方法：（1）分解选择运算 利用规则4把形如бF1 ∧F2 ∧ … ∧ Fn (E)变换为 бF1 (бF2(… (бFn(E))… )) 关系代数表达式的优化算法 (续)（2）通过交换选择运算，将其尽可能移到叶端 对每一个选择，利用规则4～8尽可能把它移到树的叶端 （3）通过交换投影运算，将其尽可能移到叶端对每一个投影利用规则3，9，l0，5中的一般形式尽可能把它移向树的叶端 关系代数表达式的优化算法 (续)（4）合并串接的选择和投影，以便能同时执行或在一次扫描中完成–利用规则3～5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影–使多个选择或投影能同时执行，或在一次扫描中全部完成–尽管这种变换似乎违背“投影尽可能早做”的原则，但这样做效率更高 关系代数表达式的优化算法 (续)（5）对内结点分组–把上述得到的语法树的内节点分组–每一双目运算(×， ，∪，-)和它所有的直接祖先为一组(这些直接祖先是б，π运算)–如果其后代直到叶子全是单目运算，则也将它们并入该组，但当双目运算是笛卡尔积(×)，而且其后的选择不能与它结合为等值连接时除外。
把这些单目运算单独分为一组 关系代数表达式的优化算法 (续)（6）生成程序–生成一个程序，每组结点的计算是程序中的一步–各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算 4.2 关系系统的查询优化 4.2.1 查询优化概述4.2.2 查询优化的必要性4.2.3 查询优化的一般准则4.2.4 关系代数等价变换规则4.2.5 关系代数表达式的优化算法4.2.6 优化的一般步骤 4.2.6 优化的一般步骤 1．把查询转换成某种内部表示2．代数优化：把语法树转换成标准（优化） 形式3．物理优化：选择低层的存取路径4．生成查询计划，选择代价最小的 优化的一般步骤 (续)（1）把查询转换成某种内部表示例：求选修了课程Ｃ2的学生姓名SELECT Student.SnameFROM Student, SCWHERE Student.Sno=SC.SnoAND SC.Cno='2'; （1）把查询转换成某种内部表示语法树 结果结果project(Sname) select(SC.Cno= 2 ) join(Student.Sno=SC.Sno) StudentSC 关系代数语法树πSname SC.Cno=’2’ Student.Sno=SC.Sno × StudentSC （2）代数优化利用优化算法把语法树转换成标准（优化）形式 πSname Student.Sno=SC.Sno SC.Cno= 2 × StudentSC （3）物理优化：选择低层的存取路径- 优化器查找数据字典获得当前数据库状态信息•选择字段上是否有索引•连接的两个表是否有序•连接字段上是否有索引–然后根据一定的优化规则选择存取路径 如本例中若SC表上建有Cno的索引，则应该利用这个索引，而不必顺序扫描SC表。
（4）生成查询计划，选择代价最小的–在作连接运算时，若两个表(设为R1，R2)均无序，连接属性上也没有索引，则可以有下面几种查询计划： • 对两个表作排序预处理• 对R1在连接属性上建索引• 对R2在连接属性上建索引• 在R1，R2的连接属性上均建索引–对不同的查询计划计算代价，选择代价最小的一个–在计算代价时主要考虑磁盘读写的I/O数，内存CPU处理时间在粗略计算时可不考虑 【例】 有职工和部门构成的关系数据库： EMP（编号E＃，姓名EN，性别SEX，年龄AGE，工资SAL，部门D＃）, DEPT（部门号D＃，部门名DN，管理者号MGR，地址ADD） 求出管理者号为18所在部门的职工姓名， 且他们的工资不超过500元 解： 依据题意可写出如下查询： Q1： πEN（（EMP σMGR=′18′（DEPT））－（σSAL>′500′（EMP） σMGR=′18′（DEPT）））•对应的查询树如下图(a)所示 其优化过程从合并树叶EMP和DEPT开始， 然后依据各种等价变换规则， 进行一系列变换， 最后形成图(f) 这一查询对有经验的读者可直接写出优化结果： Q2： πEN（πEN， D＃（σNOT SAL>′50０′（EMP）） πD＃（σMGR=′18′（DEPT））） 图 查询优化过程示意图 查询优化过程示意图 查询优化过程示意图 第四章 关系系统及其查询优化4.1 关系系统4.2 关系系统的查询优化4.3 小结 4.3 小结 •关系系统–关系系统的定义一个数据库管理系统可定义为关系系统，当且仅当它至少支持：1． 关系数据库（即关系数据结构）2． 支持选择、投影和（自然）连接运算， 且不要求用户定义任何物理存取路径 小结 （续）–关系系统的分类•表式系统•(最小)关系系统•关系完备系统•全关系系统 关系系统的分类 （续） 数据结构数据结构数据操作数据操作完整性完整性表式系统表式系统表表 (最小最小)关系系统关系系统表表选选择择、、投投影影、、连接连接 关系完备的系统关系完备的系统表表 全关系系统全关系系统 小结 （续）•关系系统的查询优化 –代数优化：关系代数表达式的优化•关系代数等价变换规则•关系代数表达式的优化算法 –物理优化：存取路径和低层操作算法的选择 。