3.3 關系代數表達式的優化

在層次模型和網狀模型中，用戶使用過程化的語言表達查詢要求、執行何種記錄級的操作，以及操作的序列等，所以用戶必須了解存取路徑，系統要提供用戶選擇存取路徑的手段，這樣，查詢效率便由用戶的存取策略決定。在這兩種模型中，要求用戶有較高的數據庫技術和程序設計水平。而在關系模型中，關系系統的查詢優化都是由數據庫管理系統來實現的，用戶不必考慮如何表達查詢以獲得較好的效率，只要告訴系統“干什么”就可以了，因為系統可以比用戶程序的“優化”做得更好。

由數據庫管理系統來實現查詢優化的優勢如下。

1）優化器可以從數據字典中獲取許多統計信息，例如關系中的元組數、關系中每個屬性值的分布情況等。優化器可以根據這些信息選擇有效的執行計劃，而用戶程序則難以獲得這些信息。

2）如果數據庫的物理統計信息改變了，系統可以自動對查詢進行重新優化以選擇相適應的執行計劃。在非關系系統中必須重寫程序，而重寫程序在實際應用中往往是不太可能的。

3）優化器可以考慮數百種不同的執行計劃，而程序員一般只能考慮有限的幾種可能性。

4）優化器中包括了很多復雜的優化技術，這些優化技術往往只有最好的程序員才能掌握。系統的自動優化相當于使得所有人都擁有這些優化技術。

實際系統對查詢優化的具體實現不盡相同，但一般來說，可以歸納為四個步驟。

1）將查詢轉換成某種內部表示，通常是語法樹。

2）根據一定的等價變換規則把語法樹轉換成標準（優化）形式。

3）選擇低層的操作算法。對于語法樹中的每一個操作都需要根據存取路徑、數據的存儲分布、存儲數據的聚簇等信息來選擇具體的執行算法。

4）生成查詢計劃。查詢計劃也稱查詢執行方案，是由一系列內部操作組成的。這些內部操作按一定的次序構成查詢的一個執行方案。通常這樣的執行方案有多個，需要對每個執行計劃計算代價，從中選擇代價最小的一個。

總之，關系數據庫查詢優化的總目標是：選擇有效的策略，求得給定關系表達式的值，達到提高DBMS系統效率的目標。