查詢策略

對於一個給定的查詢,通常會有多種不同的查詢策略(Query strategies),即是查詢的不同方法。查詢最佳化就是從這些策略中找出最有效查詢計畫的一種過程。一個好的查詢策略往往比一個壞的查詢策略在執行效率(基於執行時間)上高几個數量級。

查詢策略選擇的重要性

由於不同的查詢策略通信時間相差很大,達數個量級,因此查詢策略的選擇尤為重要。一個好的查詢策略應該使數據的傳輸量和通信次數量少,以減少數據傳輸和通信的時間,從而減少查詢的總代價。我們通過關係account來討論選擇查詢策略的重要性。

關係account的模式為:

Account一schema=(account一number, branchname, blance)。

考慮一個極其簡單的查詢:“找出account關係中的所有元組”。雖然這個查詢很簡單,但對它的處理卻不是微不足道的,因為在分散式資料庫中account關係可能被分片,被複製,也可能既分片又複製。如果account關係被複製,我們就需要對副本進行選擇。如果所有的副本都沒有被分片,我們就選擇使傳輸代價最小的那個副本;但是,如果副本被分片了,進行選擇就不那么容易,因為我們需要進行一些連線運算來重構account關係。這種情況下,我們這個簡單例子的執行策略可能會很多。這時,通過窮舉所有可能的策略來對查詢進行最佳化是不可能的。顯然,我們需要根據不同查詢要求來選擇不同的查詢策略,以減少查詢的總代價。

簡單的連線處理

選擇查詢策略的一個主要方面就是選擇連線策略。考慮下面的關係代數表達式:

accountc depositorc branch·

假設這三個關係既沒有被複製,也沒有被分片,且account存儲在站點S1上,depositor存儲在站點S2上,branch存儲在站點S3上。設S1表示提出查詢的站點。系統需要在站S1點產生結果。下面是處理這個查詢可採取策略中的幾個:

1)將三個關係的副本都送到站點SI,使用集中式的查詢處理技術,在站點SI上選擇一個本地處理整個查詢的策略。

2)將關係account的一個副本送到站點S2,在S2上計算temp1=account deposit。將temp1從S2送到S3,在S3上計算temp2= temp1 branch。最後將結果temp2送到S1。

3)設計與上一個策略類似的策略,只是交換S1, S2, S3的角色。

沒有一個策略總是最好的。我們需要考慮的因素中包括運送的數據量、在一對站點間傳輸數據塊的代價以及各站點上處理的相對速度。考慮上面列出的前兩個策略。如果我們將三個關係都送到站點S1,並且在這些關係上存在索引,我們可能需要在S1上重新創建索引。重新創建索引帶來了額外的處理開銷和額外的磁碟訪問。然而,第二種策略也存在缺點,那就是一個可能很大的關係( customer account)必須從S2送到S3。此關係中,客戶每擁有一個賬戶,其地址就要重複一次。因此同第一種策略相比,第二種策略可能導致額外的網路傳輸。

查詢最佳化

查詢最佳化就是從這些策略中找出最有效查詢計畫的一種過程。一個好的查詢策略往往比一個壞的查詢策略在執行效率(基於執行時間)上高几個數量級。以關係資料庫系統為例,查詢最佳化處理是關係資料庫系統的基本優勢所在。關係資料庫的查詢使用SQL語句實現,對於同一個用SQL表達的查詢要求,通常可以有多個不同形式但相互“等價”的關係代數表達式。對於描述同一個查詢要求但形式不同的關係代數表達式來說,由於存取路徑不同,相應的查詢效率就會產生差異,有時這種差異可以相當巨大。在關係資料庫中,為了提高查詢效率需要對一個查詢要求尋求“好的”查詢路徑(查詢計畫),或者說“好的”、等效的關係代數表達式。這種“查詢最佳化”是關係資料庫的關鍵技術,也是其巨大的優勢。

在關係資料庫中,用戶使用的查詢語句主要表達查詢條件和查詢結果,而查詢的具體實施過程及其查詢策略選擇都由資料庫管理系統負責完成,因此查詢具有非過程性的突出特徵。

數據查詢是資料庫中最基本、最常用和1最複雜的數據操作,從實際套用角度來看,必須考察系統用於數據查詢處理的開銷代價。查詢處理的代價通常取決於查詢過程對磁碟的訪問。磁碟訪問速度相對於記憶體速度要慢得多。在資料庫系統中,用戶查詢通過相應的查詢語句提交給資料庫管理系統執行。一般而言,相同的查詢要求和結果存在著不同的實現策略,系統在執行這些查詢策略時所付出的開銷通常有很大差別,甚至可能相差好幾個數量級。實際上,對於任何一個資料庫系統來說,這種“擇優”的過程就是“查詢處理過程中的最佳化”,簡稱為查詢最佳化。

查詢最佳化技術

查詢最佳化的基本方式可分為用戶手動最佳化和系統自動最佳化兩類。手動最佳化還是自動最佳化,在技術實現上取決於相應表達式語義層面的高低。

在基於格式化數據模型的層次和網路資料庫系統中,由於用戶通常使用較低層面上的語義表述查詢要求,系統難以自動完成查詢策略的選擇,只能由用戶自己完成,由此可能導致的問題有二:其一,當用戶做出了明顯的錯誤查詢決策時,系統對此無能為力;其二,用戶必須相當熟悉有關編程問題,這樣就加重了用戶的負擔,妨礙了資料庫的廣泛使用。關係資料庫的查詢語言是高級語言,具有更高層面上的語義特徵,有可能完成查詢計畫的自動選擇。

與手動最佳化比較,系統自動最佳化有如下的明顯優勢:

(1)能夠從數據字典中獲取統計信息,根據這些信息選擇有效的執行計畫。用戶手工最佳化時的程式則難以得到這些信息。

(2)當資料庫物理統計信息改變時,系統可以自動進行重新最佳化以選擇相適應的執行計畫,而手工最佳化必須重新編寫程式。

(3)可以從多種(如數百種)不同的執行計畫中進行選擇;而手工最佳化時.程式設計師一般只能考慮數種可能性。

(4)最佳化過程可能包含相當複雜的各種最佳化技術,這需要受過良好訓練的專業人員才能掌握,而系統的自動最佳化使每個資料庫使用人員(包括不具有專業訓練的普通用戶)都能擁有相應的最佳化技術。

一個“好”的資料庫系統,其中的查詢最佳化應當是自動的,即由系統的資料庫管理系統自動完成查詢最佳化過程。

查詢最佳化器

查詢最佳化器和三類最佳化技術

自動進行查詢最佳化是資料庫管理系統的關鍵技術。由資料庫管理系統自動生成若干候選查詢計畫並且從中選取較“優”的查詢計畫的程式稱為查詢最佳化器。

查詢最佳化器所使用的技術可以分為三類。

(1)規則最佳化技術

如果查詢僅僅涉及查詢語句本身,根據某些啟發式規則,例如“先選擇、投影和後連線”等就可以完成最佳化,稱之為規則最佳化。這類最佳化的特點是對查詢的關係代數表達式進行等價變換,以減少執行開銷,所以也稱為代數最佳化。

(2)物理最佳化技術

如果最佳化與數據的物理組織和訪問路徑有關,例如,在已經組織了基於查詢的專門索引或者排序檔案的情況下,就需要對如何選擇實現策略進行必要的考慮,諸如此類的問題就是物理最佳化。

(3)代價估算最佳化技術

對於多個候選策略逐個進行執行代價估算,從中選擇代價最小的作為執行策略,就稱為代價估算最佳化。

物理最佳化涉及數據檔案的組織方法,代價估算最佳化開銷較大,因此它們都只適用於一定的場合。

關係查詢最佳化的可行性

我們已經知道,查詢表達式具語義層面的高低決定查詢最佳化是否自動。關係數據模型本質上基於集合論,從而使得關係數據的自動查詢最佳化具有了必要的理論基礎。相應的關係查詢語言是一種高級語言,具有很高層面上的語義表現,從而又使由機器處理查詢最佳化具有可實現的技術基礎。因此,在關係資料庫系統中進行自動查詢最佳化是可行的。

當關係查詢語言表示的查詢操作基於集合運算時,可稱其為關係代數語言;而基於關係演算時,可稱其為關係演算語言。這兩種語言本身是有過程性的,但由於所依據理論本身不同義各有差異。

關係代數具有5種基本運算,這些運算自身和相互間滿足一定的運算定律,例如,結合律、交換律、分配率和串接率等,這就意味著不同的關係代數表達式可以得到同一結果,因此用關係代數語言進行的查詢就有進行最佳化的可能。

關係演算中需要使用“存在”和“任意”兩個量詞,這兩個量詞也有自身的演算規則,例如,兩個量詞之間的先後順序,只不過這裡的涉及面較窄,運算規則較為整齊,在“等價”的關係演

相關詞條

熱門詞條

聯絡我們