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