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

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

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

查詢優(yōu)化的可能性關系數據語言的級別很高，使DBMS可以從關系表達式中分析查詢語義。查性優(yōu)化必要性例：找出學生張明所選修的課程和成績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)化的必要性假設1：外存： S:n1條,SC:n2條假設2：一個內存塊裝元組:B1個Student,或B2個SC, 內存共有K塊，存放:K-1塊S元組,1塊SC元組假設3：連接方法：基于數據塊的嵌套循環(huán)法

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

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

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

關系代數等價變換規(guī)則

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

F

F

F

F關系代數等價變換規(guī)則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}的子集關系代數等價變換規(guī)則4.選擇的串接定律

бF1（б

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

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

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

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

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

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

8.選擇與差運算的交換 假設：E1與E2有相同的屬性名 бF(E1-E2)≡бF(E1)-бF(E2)關系代數等價變換規(guī)則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)關系代數等價變換規(guī)則l0.投影與并的交換

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

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

R1.A1)7.4分解查詢的優(yōu)化方法E．Wong等人提出在關系數據庫INGRES中，對關系數據庫語言QUEL的查詢處理就采用這種優(yōu)化方法對復雜的查詢表達式進行分解、化簡，變換成一系列較為簡單的查詢，同時在分解過程中執(zhí)行簡單查詢，以便于再分解在INGRES中把多元查詢優(yōu)化的分解方法分成兩部分，它們是分解處理與結局處理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條規(guī)則。根據這3條規(guī)則進行分解處理未必是最優(yōu)的，但一般的說是能夠得到好處的。3條規(guī)則是：1．抽取并處理每一個可提取的一元子查詢。2．只要有可能就進行化簡。3．如果不進行元組代入，則查詢處理無法再繼續(xù)進行下去，選擇元組數最少的關系做元組代入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))選擇的替換