第7章查询优化

数据库原理及应用ThePrincipleofDatabaseandapplications第七章查询优化第七章

查询优化7.1查询优化概述7.2查询优化的一般策略7.3基于关系代数表达式的优化算法7.4分解查询的优化方法7.5连接运算的优化7.6代价估算优化7.1查询优化概述查询优化的必要性查询优化极大地影响RDBMS的性能。

查询优化的可能性关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义。查性优化必要性例：找出学生张明所选修的课程和成绩T1=πCNO,GR（бS.SNO=SC.SNO

S.SN=‘张明’（S

SC）)T2=πCNO,GR（бSN=‘张明’（S

SC）)T3=πCNO,GR（（бSN=‘张明’（S）

SC）查询优化的必要性假设1：外存： S:n1条,SC:n2条假设2：一个内存块装元组:B1个Student,或B2个SC, 内存共有K块，存放:K-1块S元组,1块SC元组假设3：连接方法：基于数据块的嵌套循环法

查询优化的必要性对于表达式T1，总共要存取的块数是：设n1=n2=10000，B1=B2=10，K=100，则共存取11000块。若每秒存取10块，则需要18分钟查询优化的必要性对于表达式T3，由于先做选择运算，则所存取的块数是：假设各项参数同上，则共存取2000块，这时则大约需要3分钟查询优化查询优化的思想要完成同样的查询任务可能有若干条查询路径，从这些查询路径中选择最佳路径查询优化代数优化物理优化规则优化代价估算优化由DBMS进行查询优化的好处系统可以比用户程序的优化做得更好优化器从数据字典中获取更多的信息如属性值的分布情况，优化器根据这些信息选择有效的执行计划如果物理统计信息丢失，系统可以自动优化查询以选择相适应的执行计划优化器可以考虑数百种不同的执行计划优化器包含了许多复杂的优化技术，这些技术只有最好的程序员才能掌握7.2查询优化的一般策略限制运算尽早进行合并笛卡儿乘积与其后的限制运算为连接运算把投影运算和限制运算同时进行投影运算与其后的其他运算同时进行，以避免重复多次扫描文件事先处理文件存储公用的子表达式7.3基于关系代数表达式的优化算法7.3.1关系代数表达式的等价变换规则关系代数表达式等价指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的上面的优化策略大部分都涉及到代数表达式的变换

常用的等价变换规则

设E1、E2等是关系代数表达式，F是条件表达式 l.连接、笛卡尔积交换律 E1×E2≡E2×E1 E1E2≡E2E1 E1FE2≡E2FE1

关系代数等价变换规则

2.连接、笛卡尔积的结合律(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)

F

F

F

F关系代数等价变换规则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)5.选择与投影的交换律бF(πA1,A2,

,An(E))≡πA1,A2,

,An(бF(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)

关系代数等价变换规则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)7.3.2关系代数表达式的优化步骤【例7.1】设有S(供应商)，P(零件)，SP(供应关系)S(SNUM，SNAME，CITY)P(PNUM，PNAME，WEIGHT，SIZE)SP(SNUM，PNUM，EDEPT，QUAN)设有查询Q: SELECTSNAME FROM S，P，SP WHERES.SUNM=SP.SNUM AND SP.PNUM=P.PNUM AND S.CITY=’NANJING’ AND P.PNAME=’BOLT’ AND SP.QUAN>10000;关系代数表达式的优化步骤优化过程见图7-1，7-2，7-3，7-4，7-5关系代数表达式的优化步骤代数优化的基本步骤和规则：1.以SELECT子句对应投影操作，以FROM子句对应笛卡儿乘积，以WHERE子句对应选择操作，生成原始查询树2．应用变换原则（2）、（6）、（7）、（9），尽可能将选择条件移向树叶方向关系代数表达式的优化步骤3．应用连接、苗卡尔乘积的结合律，按照小关系先做的原则，重新安排连接（笛卡儿乘积）的次序4．如果笛卡儿乘积后还须按连接条件进行选择操作，可将两者组合成连接操作。5．对每个叶结点加必要的投影操作，以消除对查询无用的属性。关系代数表达式的优化步骤嵌套查询SELECTA1FROM R1WHERER1.A2

CONST1AND R1.A3IN(SELECT A4 FROMR2 WHERE R2.A5

R1.A1)7.4分解查询的优化方法E．Wong等人提出在关系数据库INGRES中，对关系数据库语言QUEL的查询处理就采用这种优化方法对复杂的查询表达式进行分解、化简，变换成一系列较为简单的查询，同时在分解过程中执行简单查询，以便于再分解在INGRES中把多元查询优化的分解方法分成两部分，它们是分解处理与结局处理7.4.1分解处理查询处理的分解过程包括3个部分：一元子查询的提取化简元组代入。分解处理例：设关系数据库中包括下列关系SUPPLIER(SNO，SNAME，CITY) (供应者关系)PART(PNO，PNAME，SIZE) (零件关系)PROJECT(JNO，JNAME．CITY) (工程项目关系)INVENTORY(SN0，PNO，QOH) (库存关系)SUPPPLY(SNO，JNO，PNO，QTY) (供应关系)条件是：该供应者必须将零件6号螺丝提供给在同一城市的某个工程项目，并且其供应量（QTY）大余1000；以及库存量要大于供应量。分解处理RANGEOFSISSUPPLIERRANGEOFPISPARTRANGEOFJISPROJECTRANGEOFVISINVENTORYRANGEOFYISSUPPLYRETRIEVE(S．SNAME)WHERE(S．SNO＝V．SNO)AND(S．SNO＝Y．SNO)AND(S．CITY＝J．CITY)AND(P．PN0＝Y．PNO)AND(J．JNO)＝Y．JNO)AND(V．QOH＞Y．QTY)AND(P．PNAME＝“DOLTS”)AND(P．SIZE＝6)AND(Y．QTY＞1000)见图7-6

SUPPLIER

PROJECT

SUPPLY

INVENTORY

PART

SNAME

SON

PNO

QTY>1000

QOH>QTY

CITY

PNO

SNO

JNO

PNAME=

‘

BOLTS

’

PNO

SIZE=6图7-6查询的图示分解处理一元子查询的提取例如，图7-6的查询中，有两个一元子查询可以提取出来RETRIEVEINTOPARTl(P．PNO)WHERE(P．PNAME＝“BOLTS”)AND(P．SIZE＝6)和RETRIEVEINTOSUPPLYl(S．SNO，Y．JNO，Y．PNO，Y．QTY)WHEREY．QTY＞1000分解处理在对查询进行语义等价交换时，利用下面的传递性(a＝b)AND(b＝c)

a＝c(a＞b)AND(b＞c)

a＞c可以通过V．QOH＞Y．QTY和Y．QTY＞1000导出Y．QOH＞1000。由于S．SNO＝V．SNO和S．SNO＝Y．SN0可以导出V．SNO＝Y．SNO。由于V．SNO＝Y．SNO和Y．SNO＝S．SNO隐含了V．SNO＝S．SNO，所以V．SNO＝S．SNO可以从图7-6中去掉，变成了图7-7的形式图7-7一元子查询提取后的形势

SUPPLIER

PROJECT

SUPPLY1

INVENTORY1

PART1

SNAME

PNO

QOH>QTY

CITY

PNO

SNO

JNO

PNO.SNO

PART

SUPPLY

INVENTORY

PNAME=

“BOLTS”

PART1

SIZE=6

QTY>1000

SUPLY1

QOH>1000

INVENTORY1

（a）

（b）

分解处理化简一元子查询提取后，则可以进行化简处理。化简是用两个至少是二元的，并且有一个公共的元组变量的查询代替原来多元查询的过程。即Q(T1，T2，…，Tn)

Q1(T1，T2，…，Ti)和Q2(Ti+1，Ti+2，…，Tn)其中，Ti(i＝1，2，…，n)是元组变量，Q、Q1、Q2均为查询表达式。对图7-7中的（b）进行化简，可以得到如图7-8所示的查询图7-8分解处理INGRES对分解处理给出了3条规则。根据这3条规则进行分解处理未必是最优的，但一般的说是能够得到好处的。3条规则是：1．抽取并处理每一个可提取的一元子查询。2．只要有可能就进行化简。3．如果不进行元组代入，则查询处理无法再继续进行下去，选择元组数最少的关系做元组代入7.4.2结局处理INGRES对复杂的多元查询分成两步来进行分解处理：一个复杂的多元查询经过分解处理、查询逐步变成一系列的简单查询，如图7-9所示。结局处理：当查询变成二元的或二元以下的简单查询时、存储结构对存取效率的影响逐步变得清晰，这时就要求根据数据的存储结构来最有效的处理这些简单的查询结局处理在INGRES中，对数据的实际存取是在处理一元查询时进行的，因此在结局处理中需要考虑以下两个问题：1．如果结局处理中存在一元查询，那么该一元查询是否要分解之前处理；2．处理二元查询必须选一个变量进行元组代入，那么应该选哪个变量呢？结局处理中先要处理一元查询的分解。结局处理INGRES中的二元查询的一般形式是：RANGEOFrISRRANGEOFsISSRETRIEVEINTORESULT(TL(r，s))WHEREC1(r)ANDC2(s)ANDC3(r，s)其中，TL(r，s)是所需查找的数据，C1(r)和C2(s)是可以分解的一元查询C3(r，s)是二元查询。结局处理通常，一元查询的分解，往往可以减少查询处理的开销，但也有例外。例如，R对于查询C1(r)没有聚集索引，而对于每一个元组S，R对于C3(r，s)是有聚集索引，那么对于R的存取应该延迟到元组替换后再进行。因为当S被替换后，通过C3(r，s)和C1(r)一起来存取R要比单独通过C1(r)来存取R要快得多。结局处理后阶段处理中的第二个问题是要解决元组替换的变量选择。设有二元查询Q(r，s)，假定|R|和|S|分别表示关系R和S的基数，并且假定选择元组变量r作为代入变量，那么我们得到|R|个对关系S的一元查询。其处理开销由下面公式给出：

COST(代入r)＝|R|十|R|

P(S，Q)其中，P(S，Q)表示对于每一个替换元组r，处理查询将存取页的平均数。开销公式是采用页的存取数来度量的。结局处理因此二元查询元组替换的最小开销是：COSTmin=MIN(|R|+|R|

P(S，Q)，|S|+|S|

P(P，Q))选择的替换