關(guān)系代數(shù)與SQL查詢優(yōu)化的研究
加入技術(shù)交流群
假設(shè)關(guān)系E1有106個(gè)元組，關(guān)系E2有103個(gè)元組。那么執(zhí)行E1xE2，則有109個(gè)元組。若條件F只與E1有關(guān)，且滿足F的選擇性為0．1％，則意味著只有103個(gè)元組滿足條件，而另外的1O9-103個(gè)元組都不滿足條件。因此將σF(E1xE2)等價(jià)變換為σF(E1)xE2后，其中間結(jié)果σF (E1)的規(guī)模僅103元組。若1個(gè)物理塊可允許存放100個(gè)E1元組，10個(gè)E2元組，而主存中可允許存放10塊E1元組，1塊E2元組，以下估計(jì)分析等價(jià)變換前后的查詢代價(jià)。
2．2．1 等價(jià)變換前查詢代價(jià)估計(jì)分析
等價(jià)變換前查詢代價(jià)是指采用σF(E1)xE2方式所需花費(fèi)的查詢代價(jià)。下面分別從E1×E2和σF兩個(gè)方面分析：
(1)E1×E2代價(jià)估計(jì)E1xE2代價(jià)估計(jì)主要是從磁盤讀塊和中間結(jié)果寫盤的時(shí)間考慮，而對(duì)主存中數(shù)據(jù)的處理時(shí)間忽略不計(jì)。
E1xE2讀塊總數(shù)=E1的塊數(shù)+E2的塊數(shù)×讀E2的遍數(shù)=104+100x103=110 000塊。若每秒可以讀50塊，讀塊時(shí)間為2 200 s(約0．6 h)。連接后的元組數(shù)為109，若每塊可存放10個(gè)元組，那么寫中間結(jié)果需要的時(shí)間是108/50=2x1 06 s。故E1xE2花費(fèi)的時(shí)間為2×106 s+2．2×103s≈556．2 h。
(2)σF代價(jià)估計(jì) σF運(yùn)算時(shí)需將E1xE2的中間結(jié)果依次讀入內(nèi)存進(jìn)行運(yùn)算，兇此需要108／50=2×106s；滿足條件的103個(gè)元組，共需100個(gè)塊寫回磁盤，需2 s。故σF花費(fèi)的時(shí)間為2x106s+2．2x103s≈556．2 h。
2．2．2 等價(jià)變換后查詢代價(jià)估計(jì)分析
等價(jià)變換后查詢代價(jià)是指采用σF(E1)xE2方式所需花費(fèi)的查詢代價(jià)。σF(E1)代價(jià)估計(jì)約為200 s，讀E2的時(shí)間為2 s。又由于讀E1進(jìn)行選擇的同時(shí)將滿足條件的元組與E2連接，形成的中間結(jié)果有103全部可以放在主存，故無需寫盤時(shí)間。從分析可知，等價(jià)變換后查詢代價(jià)約為202 s。
2．3 關(guān)系代數(shù)表達(dá)式的優(yōu)化規(guī)則
由上述分析可知，一個(gè)關(guān)系代數(shù)表達(dá)式可以有多種查詢方案，每個(gè)方案的代價(jià)相差幾個(gè)數(shù)量級(jí)，特別是當(dāng)查詢非常復(fù)雜的時(shí)候。因此生成一個(gè)好的查詢方案非常重要。
但需要看到，生成每個(gè)可能的方案和測算代價(jià)需花費(fèi)大量的時(shí)間，而生成的卻可能是即將被拋棄的方案。解決辦法是定義一般的優(yōu)化規(guī)則，從而避免DBMS查詢優(yōu)化器枚舉出一些差的方案。針對(duì)給定的查詢問題，通常有以下優(yōu)化規(guī)則：
規(guī)則1：盡量將選擇和投影運(yùn)算提前，以減少元組數(shù)和關(guān)系大小。
規(guī)則2：把某些選擇運(yùn)算和笛卡爾積相結(jié)合，即將選擇運(yùn)算附加在連接運(yùn)算上，可減少中間結(jié)果保存以備后用的時(shí)間代價(jià)。
規(guī)則3：對(duì)同一關(guān)系上的多個(gè)選擇和投影運(yùn)算同時(shí)進(jìn)行，以避免重復(fù)掃描同一關(guān)系。
規(guī)則4：把投影操作和連接運(yùn)算結(jié)合起來執(zhí)行。本文引用地址：http://m.butianyuan.cn/article/202639.htm
3 SQL查詢優(yōu)化
查詢優(yōu)化是為查詢選擇最有效的查詢計(jì)劃過程。查詢優(yōu)化一方面是在關(guān)系代數(shù)級(jí)進(jìn)行優(yōu)化，目的是力圖找出與給定查詢等價(jià)，但執(zhí)行效率更高的一個(gè)表達(dá)式。
3．1 等價(jià)變換策略
查詢優(yōu)化的另一方面涉及查詢語句處理的詳細(xì)策略的選擇，例如選擇執(zhí)行運(yùn)算所采用的具體算法以及將使用的特定索引等。事實(shí)RDBMS優(yōu)化器的查詢優(yōu)化從給定的SQL查詢開始，轉(zhuǎn)換查詢形式，直至所得到的形式依據(jù)某些規(guī)則是最優(yōu)的。選擇與投影等價(jià)變換策略有：
策略1：對(duì)同一關(guān)系的多個(gè)選擇可以轉(zhuǎn)換為一個(gè)用and連接的選擇操作。例如：Select A1，…，AnFrom E where F1=
(Select A1 From E where F2)XXXXXXXXXXXXXXXXXXXXXSelect A1，…，AnFrom E where F1and F2。原始的查詢意味著要對(duì)E進(jìn)行2次掃描，而變換后只需要1次。
評(píng)論