關(guān)系代數(shù)與SQL查詢優(yōu)化的研究

1 引言
    隨著各個(gè)應(yīng)用領(lǐng)域信息化程度日益提高，數(shù)據(jù)庫中的數(shù)據(jù)量迅猛增長，導(dǎo)致數(shù)據(jù)庫系統(tǒng)的查詢性能下降。但是一個(gè)數(shù)據(jù)庫應(yīng)用系統(tǒng)的查詢性能直接影響到系統(tǒng)的推廣和應(yīng)用，因此數(shù)據(jù)庫系統(tǒng)性能和查詢優(yōu)化成為數(shù)據(jù)庫應(yīng)用領(lǐng)域備受關(guān)注的熱點(diǎn)問題。
    影響數(shù)據(jù)庫系統(tǒng)性能的因素很多，包括數(shù)據(jù)庫連接方式、應(yīng)用系統(tǒng)架構(gòu)、數(shù)據(jù)庫設(shè)計(jì)、管理等。其中最本質(zhì)又至關(guān)重要的是數(shù)據(jù)庫管理系統(tǒng)本身的查詢優(yōu)化技術(shù)。在數(shù)據(jù)庫系統(tǒng)開發(fā)中，用戶業(yè)務(wù)邏輯必須轉(zhuǎn)換成數(shù)據(jù)庫查詢語言執(zhí)行，或?qū)?shù)據(jù)庫查詢語言嵌入在宿主語言程序中執(zhí)行。通過分析關(guān)系代數(shù)表達(dá)式的等價(jià)變換準(zhǔn)則及查詢代價(jià)，于給定的SQL查詢與關(guān)系代數(shù)表達(dá)式對(duì)應(yīng)關(guān)系，研究并分析基于關(guān)系代數(shù)等價(jià)變換規(guī)則的SQL查詢優(yōu)化。

2 關(guān)系代數(shù)表達(dá)式的等價(jià)變換規(guī)則
    數(shù)據(jù)庫查詢是指從數(shù)據(jù)庫中提取數(shù)據(jù)的一系列活動(dòng)，包括：將高級(jí)數(shù)據(jù)庫語言表示的查詢語句翻譯為能在文件系統(tǒng)這一物理層次上實(shí)現(xiàn)的表達(dá)式，為優(yōu)化查詢進(jìn)行各種轉(zhuǎn)換，生成可供執(zhí)行的查詢計(jì)劃。對(duì)于數(shù)據(jù)庫的查詢要求可通過關(guān)系代數(shù)的運(yùn)算(操作)表達(dá)，而在SQL語言中通過SELECT語句實(shí)現(xiàn)查詢要求。南于關(guān)系代數(shù)運(yùn)算與SELECT語句描述之間存在著對(duì)應(yīng)關(guān)系，兇此可將數(shù)據(jù)庫查詢轉(zhuǎn)換成關(guān)系代數(shù)運(yùn)算，并利用關(guān)系代數(shù)等價(jià)變換規(guī)則生成優(yōu)化SOL的查詢計(jì)劃。
2．1 關(guān)系代數(shù)等價(jià)變換規(guī)則
    設(shè)E、E1、E2和E3是關(guān)系代數(shù)表達(dá)式，A1,…，An和B1，…，Bm是屬性名，且A1,…，An是B1，…，Bm的子集，F(xiàn)、F1、F2和F3是條件表達(dá)式。則有常用的等價(jià)變換規(guī)則如表1所示。

2．2 查詢代價(jià)分析
    從優(yōu)化的角度考慮，規(guī)則1與規(guī)則2等價(jià)變換前后的中間結(jié)果規(guī)模幾乎不發(fā)生變化，因此無需考慮優(yōu)化問題。但規(guī)則3～規(guī)則10變換前后中間結(jié)果規(guī)模會(huì)發(fā)生變化，例如規(guī)則3若選取的條件F只與E1有關(guān)，那么先進(jìn)行E1的條件選取，再與E2笛卡爾積的時(shí)間代價(jià)將大大減少，下面通過例子進(jìn)行查詢代價(jià)分析。
    假設(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è)可能的方案和測(cè)算代價(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í)行。

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次。
    策略2：對(duì)同一關(guān)系連續(xù)的多個(gè)投影可轉(zhuǎn)換為僅含最后一個(gè)投影的操作。例如：Select A1，…AnFrom E(Select B1，…，Bm From E)XXXXXXXXXXXXXXXXXXXXXSelectA1，…，AnFrom E。因?yàn)锳1，…，An∈B1，…，Bm，所以根據(jù)表1規(guī)則9等價(jià)于直接對(duì)子集A1,…，An投影。
    策略3：投影后的選擇操作可轉(zhuǎn)換為選擇操作后的投影操作，例如：Select A1,A2 From E1 Where A1=(Select B1 From E2Where B2>F2)等價(jià)于A1,A2 From E1E2Where A1=B1 And B2>F2。
    經(jīng)等價(jià)變換使得條件A1=B1 And B2>F2滿足時(shí)再進(jìn)行投影，這樣可減少中間結(jié)果的規(guī)模。
    策略4：投影操作在并操作、交操作和連接操作上滿足分配律。例如：σF(E1∪E2)=σF(E1)∪σF(E2)等價(jià)于Select A1，A2From E1 Where F union Select B1，B2 From E2 Where F。對(duì)于E1，E2若在不同的服務(wù)器上，先進(jìn)行本地服務(wù)器上的選擇再進(jìn)行并行運(yùn)算將減少查詢代價(jià)。
    策略5：并操作和交操作滿足吸收律，即：E1∪(E1∩E2)=E1或E1 ∩(E1 UE2)=E1。例如：Select*From E1 union(Select*E1 From insersect Select* From E2)等價(jià)于Select *From E1。等價(jià)變換前對(duì)E1掃描2次，E2掃描1次，但等價(jià)變換后僅對(duì)E1掃描1次。
3．2 成本最小的查詢計(jì)劃
    數(shù)據(jù)庫查詢優(yōu)化器是關(guān)系數(shù)據(jù)庫服務(wù)器的一個(gè)組成部分?；诔杀镜臄?shù)據(jù)庫查詢優(yōu)化器的任務(wù)是通過產(chǎn)生可供選擇的查詢計(jì)劃，找到最低估算成本的查詢計(jì)劃來優(yōu)化一條SQL語句，其過程如圖1所示。查詢計(jì)劃對(duì)SQL語句性能十分重要。當(dāng)一條SQL 語句被送人RDBMS服務(wù)器，將被解析并提交給數(shù)據(jù)庫查詢優(yōu)化器。查詢優(yōu)化器進(jìn)行查詢等價(jià)變換，并對(duì)查詢表達(dá)式進(jìn)行評(píng)估，以產(chǎn)生若干可供選擇的查詢計(jì)劃。估計(jì)每個(gè)待選的查詢計(jì)劃的成本，選用成本最小的查詢計(jì)劃，最終生成可執(zhí)行的SQL語句。

4 結(jié)束語
    數(shù)據(jù)庫查詢優(yōu)化器生成查詢計(jì)劃存在2個(gè)問題：第一，無法產(chǎn)生全部可能的、并可供選擇的查詢計(jì)劃；第二，無法準(zhǔn)確地估計(jì)查詢成本。另外，查詢處理的代價(jià)通常取決于磁盤的訪問，因?yàn)榇疟P的訪問比內(nèi)存訪問速度慢得多，就所需的磁盤訪問次數(shù)而言，策略好壞差別很大，甚至相差幾個(gè)數(shù)量級(jí)。所以，對(duì)于一個(gè)給定的查詢，查詢優(yōu)化器系統(tǒng)如何快速選擇一個(gè)生成成本相對(duì)較小的查詢計(jì)劃很值得研究。