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

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

2．2 查詢代價分析
    從優(yōu)化的角度考慮，規(guī)則1與規(guī)則2等價變換前后的中間結果規(guī)模幾乎不發(fā)生變化，因此無需考慮優(yōu)化問題。但規(guī)則3～規(guī)則10變換前后中間結果規(guī)模會發(fā)生變化，例如規(guī)則3若選取的條件F只與E1有關，那么先進行E1的條件選取，再與E2笛卡爾積的時間代價將大大減少，下面通過例子進行查詢代價分析。
    假設關系E1有106個元組，關系E2有103個元組。那么執(zhí)行E1xE2，則有109個元組。若條件F只與E1有關，且滿足F的選擇性為0．1％，則意味著只有103個元組滿足條件，而另外的1O9-103個元組都不滿足條件。因此將σF(E1xE2)等價變換為σF(E1)xE2后，其中間結果σF (E1)的規(guī)模僅103元組。若1個物理塊可允許存放100個E1元組，10個E2元組，而主存中可允許存放10塊E1元組，1塊E2元組，以下估計分析等價變換前后的查詢代價。
2．2．1 等價變換前查詢代價估計分析
    等價變換前查詢代價是指采用σF(E1)xE2方式所需花費的查詢代價。下面分別從E1×E2和σF兩個方面分析：
    (1)E1×E2代價估計E1xE2代價估計主要是從磁盤讀塊和中間結果寫盤的時間考慮，而對主存中數(shù)據(jù)的處理時間忽略不計。
    E1xE2讀塊總數(shù)=E1的塊數(shù)+E2的塊數(shù)×讀E2的遍數(shù)=104+100x103=110 000塊。若每秒可以讀50塊，讀塊時間為2 200 s(約0．6 h)。連接后的元組數(shù)為109，若每塊可存放10個元組，那么寫中間結果需要的時間是108/50=2x1 06 s。故E1xE2花費的時間為2×106 s+2．2×103s≈556．2 h。
    (2)σF代價估計 σF運算時需將E1xE2的中間結果依次讀入內存進行運算，兇此需要108／50=2×106s；滿足條件的103個元組，共需100個塊寫回磁盤，需2 s。故σF花費的時間為2x106s+2．2x103s≈556．2 h。
2．2．2 等價變換后查詢代價估計分析
    等價變換后查詢代價是指采用σF(E1)xE2方式所需花費的查詢代價。σF(E1)代價估計約為200 s，讀E2的時間為2 s。又由于讀E1進行選擇的同時將滿足條件的元組與E2連接，形成的中間結果有103全部可以放在主存，故無需寫盤時間。從分析可知，等價變換后查詢代價約為202 s。
2．3 關系代數(shù)表達式的優(yōu)化規(guī)則
    由上述分析可知，一個關系代數(shù)表達式可以有多種查詢方案，每個方案的代價相差幾個數(shù)量級，特別是當查詢非常復雜的時候。因此生成一個好的查詢方案非常重要。
    但需要看到，生成每個可能的方案和測算代價需花費大量的時間，而生成的卻可能是即將被拋棄的方案。解決辦法是定義一般的優(yōu)化規(guī)則，從而避免DBMS查詢優(yōu)化器枚舉出一些差的方案。針對給定的查詢問題，通常有以下優(yōu)化規(guī)則：
    規(guī)則1：盡量將選擇和投影運算提前，以減少元組數(shù)和關系大小。
    規(guī)則2：把某些選擇運算和笛卡爾積相結合，即將選擇運算附加在連接運算上，可減少中間結果保存以備后用的時間代價。
    規(guī)則3：對同一關系上的多個選擇和投影運算同時進行，以避免重復掃描同一關系。
    規(guī)則4：把投影操作和連接運算結合起來執(zhí)行。

3 SQL查詢優(yōu)化
    查詢優(yōu)化是為查詢選擇最有效的查詢計劃過程。查詢優(yōu)化一方面是在關系代數(shù)級進行優(yōu)化，目的是力圖找出與給定查詢等價，但執(zhí)行效率更高的一個表達式。
3．1 等價變換策略
    查詢優(yōu)化的另一方面涉及查詢語句處理的詳細策略的選擇，例如選擇執(zhí)行運算所采用的具體算法以及將使用的特定索引等。事實RDBMS優(yōu)化器的查詢優(yōu)化從給定的SQL查詢開始，轉換查詢形式，直至所得到的形式依據(jù)某些規(guī)則是最優(yōu)的。選擇與投影等價變換策略有：
    策略1：對同一關系的多個選擇可以轉換為一個用and連接的選擇操作。例如：Select A1，…，AnFrom E where F1=
(Select A1 From E where F2)XXXXXXXXXXXXXXXXXXXXXSelect A1，…，AnFrom E where F1and F2。原始的查詢意味著要對E進行2次掃描，而變換后只需要1次。
    策略2：對同一關系連續(xù)的多個投影可轉換為僅含最后一個投影的操作。例如：Select A1，…AnFrom E(Select B1，…，Bm From E)XXXXXXXXXXXXXXXXXXXXXSelectA1，…，AnFrom E。因為A1，…，An∈B1，…，Bm，所以根據(jù)表1規(guī)則9等價于直接對子集A1,…，An投影。
    策略3：投影后的選擇操作可轉換為選擇操作后的投影操作，例如：Select A1,A2 From E1 Where A1=(Select B1 From E2Where B2>F2)等價于A1,A2 From E1E2Where A1=B1 And B2>F2。
    經等價變換使得條件A1=B1 And B2>F2滿足時再進行投影，這樣可減少中間結果的規(guī)模。
    策略4：投影操作在并操作、交操作和連接操作上滿足分配律。例如：σF(E1∪E2)=σF(E1)∪σF(E2)等價于Select A1，A2From E1 Where F union Select B1，B2 From E2 Where F。對于E1，E2若在不同的服務器上，先進行本地服務器上的選擇再進行并行運算將減少查詢代價。
    策略5：并操作和交操作滿足吸收律，即：E1∪(E1∩E2)=E1或E1 ∩(E1 UE2)=E1。例如：Select*From E1 union(Select*E1 From insersect Select* From E2)等價于Select *From E1。等價變換前對E1掃描2次，E2掃描1次，但等價變換后僅對E1掃描1次。
3．2 成本最小的查詢計劃
    數(shù)據(jù)庫查詢優(yōu)化器是關系數(shù)據(jù)庫服務器的一個組成部分。基于成本的數(shù)據(jù)庫查詢優(yōu)化器的任務是通過產生可供選擇的查詢計劃，找到最低估算成本的查詢計劃來優(yōu)化一條SQL語句，其過程如圖1所示。查詢計劃對SQL語句性能十分重要。當一條SQL 語句被送人RDBMS服務器，將被解析并提交給數(shù)據(jù)庫查詢優(yōu)化器。查詢優(yōu)化器進行查詢等價變換，并對查詢表達式進行評估，以產生若干可供選擇的查詢計劃。估計每個待選的查詢計劃的成本，選用成本最小的查詢計劃，最終生成可執(zhí)行的SQL語句。

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