第7章查詢優(yōu)化

數(shù)據(jù)庫原理及應(yīng)用ThePrincipleofDatabaseandapplications第七章查詢優(yōu)化第七章

查詢優(yōu)化7.1查詢優(yōu)化概述7.2查詢優(yōu)化的一般策略7.3基于關(guān)系代數(shù)表達(dá)式的優(yōu)化算法7.4分解查詢的優(yōu)化方法7.5連接運(yùn)算的優(yōu)化7.6代價(jià)估算優(yōu)化7.1查詢優(yōu)化概述查詢優(yōu)化的必要性查詢優(yōu)化極大地影響RDBMS的性能。

查詢優(yōu)化的可能性關(guān)系數(shù)據(jù)語言的級(jí)別很高，使DBMS可以從關(guān)系表達(dá)式中分析查詢語義。查性優(yōu)化必要性例：找出學(xué)生張明所選修的課程和成績T1=πCNO,GR（бS.SNO=SC.SNO

S.SN=‘張明’（S

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

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

SC）查詢優(yōu)化的必要性假設(shè)1：外存： S:n1條,SC:n2條假設(shè)2：一個(gè)內(nèi)存塊裝元組:B1個(gè)Student,或B2個(gè)SC, 內(nèi)存共有K塊，存放:K-1塊S元組,1塊SC元組假設(shè)3：連接方法：基于數(shù)據(jù)塊的嵌套循環(huán)法

查詢優(yōu)化的必要性對(duì)于表達(dá)式T1，總共要存取的塊數(shù)是：設(shè)n1=n2=10000，B1=B2=10，K=100，則共存取11000塊。若每秒存取10塊，則需要18分鐘查詢優(yōu)化的必要性對(duì)于表達(dá)式T3，由于先做選擇運(yùn)算，則所存取的塊數(shù)是：假設(shè)各項(xiàng)參數(shù)同上，則共存取2000塊，這時(shí)則大約需要3分鐘查詢優(yōu)化查詢優(yōu)化的思想要完成同樣的查詢?nèi)蝿?wù)可能有若干條查詢路徑，從這些查詢路徑中選擇最佳路徑查詢優(yōu)化代數(shù)優(yōu)化物理優(yōu)化規(guī)則優(yōu)化代價(jià)估算優(yōu)化由DBMS進(jìn)行查詢優(yōu)化的好處系統(tǒng)可以比用戶程序的優(yōu)化做得更好優(yōu)化器從數(shù)據(jù)字典中獲取更多的信息如屬性值的分布情況，優(yōu)化器根據(jù)這些信息選擇有效的執(zhí)行計(jì)劃如果物理統(tǒng)計(jì)信息丟失，系統(tǒng)可以自動(dòng)優(yōu)化查詢以選擇相適應(yīng)的執(zhí)行計(jì)劃優(yōu)化器可以考慮數(shù)百種不同的執(zhí)行計(jì)劃優(yōu)化器包含了許多復(fù)雜的優(yōu)化技術(shù)，這些技術(shù)只有最好的程序員才能掌握7.2查詢優(yōu)化的一般策略限制運(yùn)算盡早進(jìn)行合并笛卡兒乘積與其后的限制運(yùn)算為連接運(yùn)算把投影運(yùn)算和限制運(yùn)算同時(shí)進(jìn)行投影運(yùn)算與其后的其他運(yùn)算同時(shí)進(jìn)行，以避免重復(fù)多次掃描文件事先處理文件存儲(chǔ)公用的子表達(dá)式7.3基于關(guān)系代數(shù)表達(dá)式的優(yōu)化算法7.3.1關(guān)系代數(shù)表達(dá)式的等價(jià)變換規(guī)則關(guān)系代數(shù)表達(dá)式等價(jià)指用相同的關(guān)系代替兩個(gè)表達(dá)式中相應(yīng)的關(guān)系所得到的結(jié)果是相同的上面的優(yōu)化策略大部分都涉及到代數(shù)表達(dá)式的變換

常用的等價(jià)變換規(guī)則

設(shè)E1、E2等是關(guān)系代數(shù)表達(dá)式，F(xiàn)是條件表達(dá)式 l.連接、笛卡爾積交換律 E1×E2≡E2×E1 E1E2≡E2E1 E1FE2≡E2FE1

關(guān)系代數(shù)等價(jià)變換規(guī)則

2.連接、笛卡爾積的結(jié)合律(E1×E2)×E3≡E1×(E2×E3)(E1E2)E3≡E1(E2E3)(E1E2)E3≡E1(E2E3)

F

F

F

F關(guān)系代數(shù)等價(jià)變換規(guī)則3.投影的串接定律

π

A1,A2,

,An(π

B1,B2,

,Bm(E))≡π

A1,A2,

,An(E)假設(shè)：1) E是關(guān)系代數(shù)表達(dá)式2) Ai(i=1，2，…，n),Bj(j=l，2，…，m)是屬性名3){A1,A2,…,An}構(gòu)成{Bl，B2，…，Bm}的子集關(guān)系代數(shù)等價(jià)變換規(guī)則4.選擇的串接定律

бF1（б

F2（E））≡бF1∧F2(E)5.選擇與投影的交換律бF(πA1,A2,

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

,An(бF(E))關(guān)系代數(shù)等價(jià)變換規(guī)則6.選擇與笛卡爾積的交換律(1)假設(shè)：F中涉及的屬性都是E1中的屬性 бF(E1×E2)≡бF(E1)×E2

(2)假設(shè)：F=F1∧F2，并且F1只涉及E1中的屬性，

F2只涉及E2中的屬性 則由上面的等價(jià)變換規(guī)則1，4，6可推出： бF(E1×E2)≡бF1(E1)×бF2(E2)

關(guān)系代數(shù)等價(jià)變換規(guī)則7.選擇與并的交換 假設(shè)：E=E1∪E2，E1，E2有相同的屬性名 бF(E1∪E2)≡бF(E1)∪бF(E2)

8.選擇與差運(yùn)算的交換 假設(shè)：E1與E2有相同的屬性名 бF(E1-E2)≡бF(E1)-бF(E2)關(guān)系代數(shù)等價(jià)變換規(guī)則9.投影與笛卡爾積的交換

假設(shè)：E1和E2是兩個(gè)關(guān)系表達(dá)式，

A1，…，An是E1的屬性，

B1，…，Bm是E2的屬性πA1,A2,…,An,B1,B2,…,Bm（E1×E2)≡ πA1,A2,…,An（E1)×πB1,B2,…,Bm(E2)關(guān)系代數(shù)等價(jià)變換規(guī)則l0.投影與并的交換

假設(shè)：E1和E2有相同的屬性名 πA1,A2,…,An(E1∪E2)≡ πA1,A2,…,An(E1)∪πA1,A2,…,An(E2)7.3.2關(guān)系代數(shù)表達(dá)式的優(yōu)化步驟【例7.1】設(shè)有S(供應(yīng)商)，P(零件)，SP(供應(yīng)關(guān)系)S(SNUM，SNAME，CITY)P(PNUM，PNAME，WEIGHT，SIZE)SP(SNUM，PNUM，EDEPT，QUAN)設(shè)有查詢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;關(guān)系代數(shù)表達(dá)式的優(yōu)化步驟優(yōu)化過程見圖7-1，7-2，7-3，7-4，7-5關(guān)系代數(shù)表達(dá)式的優(yōu)化步驟代數(shù)優(yōu)化的基本步驟和規(guī)則：1.以SELECT子句對(duì)應(yīng)投影操作，以FROM子句對(duì)應(yīng)笛卡兒乘積，以WHERE子句對(duì)應(yīng)選擇操作，生成原始查詢樹2．應(yīng)用變換原則（2）、（6）、（7）、（9），盡可能將選擇條件移向樹葉方向關(guān)系代數(shù)表達(dá)式的優(yōu)化步驟3．應(yīng)用連接、苗卡爾乘積的結(jié)合律，按照小關(guān)系先做的原則，重新安排連接（笛卡兒乘積）的次序4．如果笛卡兒乘積后還須按連接條件進(jìn)行選擇操作，可將兩者組合成連接操作。5．對(duì)每個(gè)葉結(jié)點(diǎn)加必要的投影操作，以消除對(duì)查詢無用的屬性。關(guān)系代數(shù)表達(dá)式的優(yōu)化步驟嵌套查詢SELECTA1FROM R1WHERER1.A2

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

R1.A1)7.4分解查詢的優(yōu)化方法E．Wong等人提出在關(guān)系數(shù)據(jù)庫INGRES中，對(duì)關(guān)系數(shù)據(jù)庫語言QUEL的查詢處理就采用這種優(yōu)化方法對(duì)復(fù)雜的查詢表達(dá)式進(jìn)行分解、化簡，變換成一系列較為簡單的查詢，同時(shí)在分解過程中執(zhí)行簡單查詢，以便于再分解在INGRES中把多元查詢優(yōu)化的分解方法分成兩部分，它們是分解處理與結(jié)局處理7.4.1分解處理查詢處理的分解過程包括3個(gè)部分：一元子查詢的提取化簡元組代入。分解處理例：設(shè)關(guān)系數(shù)據(jù)庫中包括下列關(guān)系SUPPLIER(SNO，SNAME，CITY) (供應(yīng)者關(guān)系)PART(PNO，PNAME，SIZE) (零件關(guān)系)PROJECT(JNO，JNAME．CITY) (工程項(xiàng)目關(guān)系)INVENTORY(SN0，PNO，QOH) (庫存關(guān)系)SUPPPLY(SNO，JNO，PNO，QTY) (供應(yīng)關(guān)系)條件是：該供應(yīng)者必須將零件6號(hào)螺絲提供給在同一城市的某個(gè)工程項(xiàng)目，并且其供應(yīng)量（QTY）大余1000；以及庫存量要大于供應(yīng)量。分解處理RANGEOFSISSUPPLIERRANGEOFPISPARTRANGEOFJISPROJECTRANGEOFVISINVENTORYRANGEOFYISSUPPLYRETRIEVE(S．SNAME)WHERE(S．SNO＝V．SNO)AND(S．SNO＝Y(jié)．SNO)AND(S．CITY＝J．CITY)AND(P．PN0＝Y(jié)．PNO)AND(J．JNO)＝Y(jié)．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的查詢中，有兩個(gè)一元子查詢可以提取出來RETRIEVEINTOPARTl(P．PNO)WHERE(P．PNAME＝“BOLTS”)AND(P．SIZE＝6)和RETRIEVEINTOSUPPLYl(S．SNO，Y．JNO，Y．PNO，Y．QTY)WHEREY．QTY＞1000分解處理在對(duì)查詢進(jìn)行語義等價(jià)交換時(shí)，利用下面的傳遞性(a＝b)AND(b＝c)

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

a＞c可以通過V．QOH＞Y．QTY和Y．QTY＞1000導(dǎo)出Y．QOH＞1000。由于S．SNO＝V．SNO和S．SNO＝Y(jié)．SN0可以導(dǎo)出V．SNO＝Y(jié)．SNO。由于V．SNO＝Y(jié)．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）

分解處理化簡一元子查詢提取后，則可以進(jìn)行化簡處理?；喪怯脙蓚€(gè)至少是二元的，并且有一個(gè)公共的元組變量的查詢代替原來多元查詢的過程。即Q(T1，T2，…，Tn)

Q1(T1，T2，…，Ti)和Q2(Ti+1，Ti+2，…，Tn)其中，Ti(i＝1，2，…，n)是元組變量，Q、Q1、Q2均為查詢表達(dá)式。對(duì)圖7-7中的（b）進(jìn)行化簡，可以得到如圖7-8所示的查詢圖7-8分解處理INGRES對(duì)分解處理給出了3條規(guī)則。根據(jù)這3條規(guī)則進(jìn)行分解處理未必是最優(yōu)的，但一般的說是能夠得到好處的。3條規(guī)則是：1．抽取并處理每一個(gè)可提取的一元子查詢。2．只要有可能就進(jìn)行化簡。3．如果不進(jìn)行元組代入，則查詢處理無法再繼續(xù)進(jìn)行下去，選擇元組數(shù)最少的關(guān)系做元組代入7.4.2結(jié)局處理INGRES對(duì)復(fù)雜的多元查詢分成兩步來進(jìn)行分解處理：一個(gè)復(fù)雜的多元查詢經(jīng)過分解處理、查詢逐步變成一系列的簡單查詢，如圖7-9所示。結(jié)局處理：當(dāng)查詢變成二元的或二元以下的簡單查詢時(shí)、存儲(chǔ)結(jié)構(gòu)對(duì)存取效率的影響逐步變得清晰，這時(shí)就要求根據(jù)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)來最有效的處理這些簡單的查詢結(jié)局處理在INGRES中，對(duì)數(shù)據(jù)的實(shí)際存取是在處理一元查詢時(shí)進(jìn)行的，因此在結(jié)局處理中需要考慮以下兩個(gè)問題：1．如果結(jié)局處理中存在一元查詢，那么該一元查詢是否要分解之前處理；2．處理二元查詢必須選一個(gè)變量進(jìn)行元組代入，那么應(yīng)該選哪個(gè)變量呢？結(jié)局處理中先要處理一元查詢的分解。結(jié)局處理INGRES中的二元查詢的一般形式是：RANGEOFrISRRANGEOFsISSRETRIEVEINTORESULT(TL(r，s))WHEREC1(r)ANDC2(s)ANDC3(r，s)其中，TL(r，s)是所需查找的數(shù)據(jù)，C1(r)和C2(s)是可以分解的一元查詢C3(r，s)是二元查詢。結(jié)局處理通常，一元查詢的分解，往往可以減少查詢處理的開銷，但也有例外。例如，R對(duì)于查詢C1(r)沒有聚集索引，而對(duì)于每一個(gè)元組S，R對(duì)于C3(r，s)是有聚集索引，那么對(duì)于R的存取應(yīng)該延遲到元組替換后再進(jìn)行。因?yàn)楫?dāng)S被替換后，通過C3(r，s)和C1(r)一起來存取R要比單獨(dú)通過C1(r)來存取R要快得多。結(jié)局處理后階段處理中的第二個(gè)問題是要解決元組替換的變量選擇。設(shè)有二元查詢Q(r，s)，假定|R|和|S|分別表示關(guān)系R和S的基數(shù)，并且假定選擇元組變量r作為代入變量，那么我們得到|R|個(gè)對(duì)關(guān)系S的一元查詢。其處理開銷由下面公式給出：

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

P(S，Q)其中，P(S，Q)表示對(duì)于每一個(gè)替換元組r，處理查詢將存取頁的平均數(shù)。開銷公式是采用頁的存取數(shù)來度量的。結(jié)局處理因此二元查詢元組替換的最小開銷是：COSTmin=MIN(|R|+|R|

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

P(P，Q))選擇的替換