第九章关系查询处理和查询优化

AnIntroductiontoDatabaseSystem上海第二工业大学计算机与信息学院数据库系统概论AnIntroductiontoDatabaseSystem第九章关系查询处理和查询优化AnIntroductiontoDatabaseSystem第九章

关系查询处理和查询优化9.1关系数据库的查询处理9.2关系数据库系统的查询优化9.3代数优化9.4物理优化AnIntroductiontoDatabaseSystem9.1关系数据库的查询处理9.1.1查询处理的步骤查询分析：对查询语句进行语法和词法分析查询检查：检查语义：语句中使用的对象的存在性和有效性用户权限和和完整性检查检查通过后，把查询语句转换成等价的关系代数表达式（查询树即语法分析树）AnIntroductiontoDatabaseSystem语法分析树：结果project(Sname)

select(SC.Cno=2)

join(Student.Sno=SC.Sno)

StudentSCAnIntroductiontoDatabaseSystem查询优化：选择一个高效的查询处理策略，方法有代数优化、物理优化，选择的依据有基于规则、基于代价或基于语义执行查询：依据优化器得到的策略生成查询计划，由代码生成器生成可执行代码。AnIntroductiontoDatabaseSystem9.1.2实现查询操作的算法示例1.选择操作的常用算法全表扫描，选出符合条件的元组使用索引可快速获取符合选择条件的元组指针，如sage=20或sage>20。组合条件如：sage>20andsdept=‘CS’方法1：分别选出符合sage>20条件的元组指针和符合sdept=‘CS’条件的元组指针，然后求它们的交集方法2：先选出符合sage>20条件的元组指针，然后对选出的元组判断是否符合sdept=‘CS’条件。第一种方法在sage和sdept上均有索引的情况下比较有效，第二种方法应该优先选出选择条件中有索引的元组。AnIntroductiontoDatabaseSystem2.连接操作的常用算法（假定为等值连接）：

Selecta.sno,a.sname,o,b.gradefromstudenta,scbwherea.sno=b.sno连接的总体思路：扫描student，对每一元组的sno，扫描grade的sno，把相同值的元组和student对应元组进行连接后输出。AnIntroductiontoDatabaseSystem循环嵌套方法：嵌套扫描两个表，总循环次数为两个元组个数的乘积。排序-合并方法：根据两个表的sno进行排序，两个循环均不必进行全表扫描。效率大大提高。索引连接方法：对sc关于sno建立索引，内层循环中由于sc建立的索引，所以不必全表扫描。AnIntroductiontoDatabaseSystemHashjoin方法：适用大表和小表的连接1依据Hash函数把小表数据放入内存（可保留少量数据在临时表空间中）（小表数据的一次扫描）2每读取大表的一条记录（大表数据的一次扫描），就和小表中内存中的数据进行比较（有了hash函数，比较就不需要扫描小表），如果符合，则立即输出数据。而如果大表的数据与小表中临时表空间的数据相符合，先不输出，而等大表的所有数据都读取完毕，才一起输出（减少读取硬盘的次数）。

3.HashJoin方法只需要对两个表进行一次扫描，并且极大地降低了读取硬盘的次数。AnIntroductiontoDatabaseSystem9.2.1查询优化概述查询效率是衡量RDBMS重要性能指标。RDBMS通过查询优化提升查询效率。关系的结构化查询语言SQL高级别的语义（只需指出做什么而不必给出怎么做），使RDBMS进行查询优化成为可能。RDBMS的查询优化，使用户不必考虑如何最好地表达查询以获得较好的效率。AnIntroductiontoDatabaseSystem系统进行优化较用户优化的优势：优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息。如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划而不必重写程序。优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。优化器中包括了很多复杂的优化技术。AnIntroductiontoDatabaseSystem查询优化目标查询优化的总目标选择有效策略，求得给定关系代数表达式的值（关系），使得查询代价最小。查询执行策略的代价构成：

总代价=I/O代价+CPU代价+内存代价+通信代价

AnIntroductiontoDatabaseSystem9.2.2查询优化的必要性例：求选修了课程Ｃ2的学生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';以下考察不同的执行策略对数据读写上需要的时间AnIntroductiontoDatabaseSystem查询优化的必要性（续）假设：1：Student:1000条，SC:10000条，选修2号课程:50条2：一个内存块可存放元组:10个Student，或100个SC，内存容量可以存放:5块Student元组、

1块SC元组和若干块连接结果元组3：读写速度：20块/秒4：连接方法：基于数据块的嵌套循环法

AnIntroductiontoDatabaseSystem执行策略1:笛卡尔积、选择、投影Q1＝sname(бStudent.Sno=SC.Sno∧SC.Cno='2'

(Student×SC))

①Student×SC：读取总块数=读Student表块数+读SC表遍数*每遍块数

=1000/10+(1000/(10×5))×(10000/100)=100+20×100=2100

读数据时间=2100/20=105秒每次可读student的10X5个元组，然后以块为单位读入全部SC，产生笛卡尔积AnIntroductiontoDatabaseSystem中间结果大小=1000*10000=107

写中间结果时间=10000000/10/20=50000秒

（假设每个内存块可存放10个元组的中间结果）②б

读数据时间=50000秒

③П总时间=105＋50000＋50000秒=100105秒

=27.8小时AnIntroductiontoDatabaseSystem执行策略2：自然连接、选择、投影2.Ｑ2＝ПＳname(бSC.Cno='2'(StudentSC))①

读取总块数=2100块

读数据时间=2100/20=105秒

中间结果大小=10000（减少1000倍）

写中间结果时间=10000/10/20=50秒

②б

读数据时间=50秒

③П

时间＝105＋50＋50秒＝205秒=3.4分

AnIntroductiontoDatabaseSystem执行策略3：选择、自然连接、投影3.Ｑ3＝ПSname(StudentбSC.Cno='2'(SC))

①б

读SC表总块数=10000/100=100块 读数据时间=100/20=5秒

中间结果大小=50条不必写入外存

② 读Student表总块数=1000/10=100块 读数据时间=100/20=5秒

③П

总时间＝5＋5秒＝10秒AnIntroductiontoDatabaseSystem9.3代数优化关系代数表达式：关系代数运算符经过有限次复合后得到的式子，其值仍为关系。（P60）关系代数表达式等价：即关系代数表达式E1和E2中代入相同的关系，其结果相同，记为：E1≡E2。AnIntroductiontoDatabaseSystem9.3.1关系代数表达式等价变换规则设E1、E2等是关系代数表达式，F是条件表达式l.连接、笛卡尔积交换律

E1×E2≡E2×E1 E1E2≡E2E1 E1FE2≡E2FE1

AnIntroductiontoDatabaseSystem关系代数等价变换规则（续）

2.连接、笛卡尔积的结合律

(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)

F1

F2

F1

F2AnIntroductiontoDatabaseSystem关系代数等价变换规则（续）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}的子集AnIntroductiontoDatabaseSystem关系代数等价变换规则（续）4.选择的串接定律

бF1

（б

F2（E））≡бF1∧F2(E)选择的串接律说明选择条件可以合并这样一次就可检查全部条件。AnIntroductiontoDatabaseSystem关系代数等价变换规则（续）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)))AnIntroductiontoDatabaseSystem关系代数等价变换规则（续）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)

AnIntroductiontoDatabaseSystem关系代数等价变换规则（续）(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)AnIntroductiontoDatabaseSystem关系代数等价变换规则（续）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)AnIntroductiontoDatabaseSystem关系代数等价变换规则（续）l0.投影与并的交换 假设：E1和E2有相同的属性名：

πA1,A2,…,An(E1∪E2)≡ πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)AnIntroductiontoDatabaseSystem小结1-2:连接、笛卡尔积的交换律、结合律3：合并或分解投影运算4：合并或分解选择运算5-8：选择运算与其他运算交换5，9，10：投影运算与其他运算交换AnIntroductiontoDatabaseSystem9.3.2关系代数的启发式的优化算法选择运算应尽可能先做：选择运算减小了中间关系中元组数量在执行连接操作前对关系适当进行预处理按连接属性排序在连接属性上建立索引

投影运算和选择运算同时做：在扫描关系时同时进行投影运算和选择运算，避免重复扫描关系将投影运算与其前面或后面的双目运算(关系代数的运算符除投影和选择外均为双目运算符)一起做。AnIntroductiontoDatabaseSystem某些选择运算同它前面要执行的笛卡尔积结合起来成为连接运算，连接运算比产生笛卡尔后进行选择运算要快的多提取公共子表达式：可把满足公共子表达式的关系（不太大的情况下）读入内存以提高查询效率。AnIntroductiontoDatabaseSystem遵循启发式规则，运用等价变换规则优化关系表达式的算法：算法：关系代数表达式的优化算法输入：依据一个关系表达式的查询树。算法输出：优化的查询树方法：（1）分解选择运算 利用规则4把形如бF1∧F2∧…∧Fn(E)变换为

бF1(бF2(…(бFn(E))…))，为（2）做准备。AnIntroductiontoDatabaseSystem关系代数表达式的优化算法

(续)（2）对每一个选择运算，利用规则4～8尽可能把它移到树的叶端。（选择优先）（3）对每一个投影运算，利用规则3，5，l0，11中的一般形式尽可能把它移向树的叶端。（投影优先）选择和投影运算均能减少中间结果，具体哪个更优先，取决于具体关系中行和列哪个数据量更大。AnIntroductiontoDatabaseSystem（4）利用等价变化3-5，合并串接的选择运算成一个选择运算和合并串接的投影运算成一个投影运算，以便能在一次扫描中完成运算，如：

бA<3(бA<5(E))бA<3(E)

πA1(πA1,A2(E))πA1(E)AnIntroductiontoDatabaseSystem关系代数表达式的优化算法

(续)（5）对内结点（除叶结点外的所有结点）分组：每一双目运算(×，，∪，-)和它所有的直接祖先为一组(这些直接祖先是б，π运算)，如下例第1，3组；如果其后代直到叶子全是单目运算，则也将它们并入该组。如下例第1组。当双目运算是笛卡尔积(×)，而且其后的选择不能与它结合为等值连接时，可把这些单目运算单独分为一组。

如下例中注释部分。每组结点对应计算程序中的一步，各步程序的顺序可任意，但任何一组的计算必须在它的父代组之前计算。如下例中第1和第2组结果必须在第3组计算之间产生。AnIntroductiontoDatabaseSystem分组实例：查询男同学选课学分大于4分的姓名和课程名studentcoursescббπ第1组π第3组第2组π若为“X”，则下面可分成两组ssex=‘男’Sno,cnosname,cnoCcredit>4Sname,cnameπsno,sname,ssexAnIntroductiontoDatabaseSystem9.4物理优化物理优化指存取路径和底层操作算法的选择，主要研究根据查询的不同特点，选择操作和连接操作中对9.1.2中各种算法的选择。有基于启发式、基于代价估算和两者结合的优化方法。AnIntroductiontoDatabaseSystem基于启发式的优化：一.选择操作的优化规则对于小关系，不论是否有索引，均使用全表扫描。下面规则则对大关系而言。包含主码等值的查询，一定使用主码索引。包含非主属性等值查询，若有关于该非主属性的索引，则估算查询结果的元组数量，与整个元组数量比例大的话，使用全表扫描，否则使用索引扫描。AnIntroductiontoDatabaseSystem对and连接的条件，若有相应的组合索引，则使用索引扫描；若部分有索引，则先使用索引扫描，选出符合部分条件的元组，在其中再选出符合其他条件的元组。对or连接的条件，一般使用全表扫描。例如关于A,B有索引，（notA）or（notB）可优化为not(AandB)，事实上一些DBMS也会作此优化(前者若使用索引，必须两次全表扫描，而后者一次全表，一次在前一次结果上再扫描)。……

AnIntroductiontoDatabaseSystem二.连接操作的优化规则连接属性均排序，使用排序-合并方法仅一个表的连接属性有索引，使用索引连接方法。上述条件均不满足，若一个表较小，则可以选用Hashjoin方法嵌套循环方法不需要任何前提条件，但较小的表的扫描应作为外循环，可减少读块的次数。（极端情况下，小表只要读一次）AnIntroductiontoDatabaseSystem基于代价估算的优化根据数据库的状态计算各种操作算法的执行代价，选择代价最小的算法。执行代价的计算方法：在数据字典中存放优化器所需要的统计信息，如表的元组数，元组长度、列值个数、最大、最小值、列上是否有索引等。根据以上的统计信息，计算各种算法的代价估值。AnIntroductiontoDatabaseSystem优化的一般步骤(续)（1）把查询转换成某种内部表示 例：求选修了课程Ｃ2的学生姓名

SELECTStudent.Sname FROMStudent,SC WHEREStudent.Sno=SC.Sno ANDSC.Cno='2';AnIntroductiontoDatabaseSystem（1）把查询转换成某种内部表示语法树结果project(Sname)

select(SC.Cno=2)

join(Student.Sno=SC.Sno)

StudentSCAnIntroductiontoDatabaseSystem关系代数