在關系數據庫系統中有著非常重要的地位
關系查詢優化是影響RDBMS性能的關鍵因素
由於關系表達式的語義級別很高，使關系系統可以從關系表達式中分析查詢語義，提供了執行查詢優化的可能性
查詢優化的優點不僅在於用戶不必考慮如何最好地表達查詢以獲得較好的效率，而且在於系統可以比用戶程序的“優化”做得更好
(1) 優化器可以從數據字典中獲取許多統計信息，而用戶程序則難以獲得這些信息
(2)如果數據庫的物理統計信息改變了，系統可以自動對查詢重新優化以選擇相適應的執行計劃。在非關系系統中必須重寫程序，而重寫程序在實際應用中往往是不太可能的。
(3)優化器可以考慮數百種不同的執行計劃，程序員一般只能考慮有限的幾種可能性。
(4)優化器中包括了很多復雜的優化技術，這些優化技術往往只有最好的程序員才能掌握。系統的自動優化相當於使得所有人都擁有這些優化技術
RDBMS通過某種代價模型計算出各種查詢執行策略的執行代價，然後選取代價最小的執行方案
集中式數據庫
執行開銷主要包括：
磁盤存取塊數(I/O代價)
處理機時間(CPU代價)
查詢的內存開銷
I/O代價是最主要的
分布式數據庫
總代價=I/O代價+CPU代價+內存代價＋通信代價
查詢優化的總目標：
選擇有效的策略
求得給定關系表達式的值
使得查詢代價最小(實際上是較小) [例3] 求選修了2號課程的學生姓名。用SQL表達：
SELECT Student.Sname
FROM Student，SC
WHERE Student.Sno=SC.Sno AND SC.Cno=‘2’；
假定學生-課程數據庫中有1000個學生記錄，10000個選課記錄
其中選修2號課程的選課記錄為50個
系統可以用多種等價的關系代數表達式來完成這一查詢
Q1=πSname(σStudent.Sno=SC.Sno∧Sc.Cno='2' (Student×SC))
Q2=πSname(σSc.Cno='2' (Student SC))
Q3=πSname(Student σSc.Cno='2'(SC))
一、第一種情況
Q1=πSname(σStudent.Sno=SC.Sno∧Sc.Cno=’2’ (Student×SC))
1. 計算廣義笛卡爾積
把Student和SC的每個元組連接起來的做法：
在內存中盡可能多地裝入某個表(如Student表)的若干塊，留出一塊存放另一個表(如SC表)的元組。
把SC中的每個元組和Student中每個元組連接，連接後的元組裝滿一塊後就寫到中間文件上
從SC中讀入一塊和內存中的Student元組連接，直到SC表處理完。
再讀入若干塊Student元組，讀入一塊SC元組
重復上述處理過程，直到把Student表處理完
2. 作選擇操作
依次讀入連接後的元組，按照選擇條件選取滿足要求的記錄
假定內存處理時間忽略。讀取中間文件花費的時間(同寫中間文件一樣)需5×104s
滿足條件的元組假設僅50個，均可放在內存
3. 作投影操作
把第2步的結果在Sname上作投影輸出，得到最終結果
第一種情況下執行查詢的總時間≈105+2×5×104≈105s
所有內存處理時間均忽略不計
二、 第二種情況
Q2=πSname(σSc.Cno=’2’ (Student SC))
1. 計算自然連接
執行自然連接，讀取Student和SC表的策略不變，總的讀取塊數仍為2100塊花費105 s
自然連接的結果比第一種情況大大減少，為104個
寫出這些元組時間為104/10/20=50s，為第一種情況的千分之一
2. 讀取中間文件塊，執行選擇運算，花費時間也為50s。
3. 把第2步結果投影輸出。
第二種情況總的執行時間≈105+50+50≈205s
三、 第三種情況
Q3=πSname(Student σSc.Cno=’2’(SC))
1. 先對SC表作選擇運算，只需讀一遍SC表，存取100塊花費時間為5s，因為滿足條件的元組僅50個，不必使用中間文件。
2. 讀取Student表，把讀入的Student元組和內存中的SC元組作連接。也只需讀一遍Student表共100塊，花費時間為5s。
3. 把連接結果投影輸出
第三種情況總的執行時間≈5+5≈10s
假如SC表的Cno字段上有索引
第一步就不必讀取所有的SC元組而只需讀取Cno=‘2’的那些元組(50個)
存取的索引塊和SC中滿足條件的數據塊大約總共3～4塊
若Student表在Sno上也有索引
第二步也不必讀取所有的Student元組
因為滿足條件的SC記錄僅50個，涉及最多50個Student記錄
讀取Student表的塊數也可大大減少
總的存取時間將進一步減少到數秒
把代數表達式Q1變換為Q2、 Q3，
即有選擇和連接操作時，先做選擇操作，這樣參加連接的元組就可以大大減少，這是代數優化
在Q3中
SC表的選擇操作算法有全表掃描和索引掃描2種方法，經過初步估算，索引掃描方法較優
對於Student和SC表的連接，利用Student表上的索引，采用index join代價也較小，這就是物理優化
：通過對關系代數表達式的等價變換來提高查詢效率
關系代數表達式的等價：指用相同的關系代替兩個表達式中相應的關系所得到的結果是相同的
兩個關系表達式E1和E2是等價的，可記為E1≡E2
常用的等價變換規則：
1. 連接、笛卡爾積交換律
設E1和E2是關系代數表達式，F是連接運算的條件，則有
E1 × E2≡E2 × E1
E1 E2≡E2 E1
E1 E2≡E2 E1
2. 連接、笛卡爾積的結合律
設E1，E2，E3是關系代數表達式，F1和F2是連接運算的條件，則有
(E1 × E2) × E3≡E1 × (E2 × E3)
(E1 E2) E3≡E1 (E2 E3)
(E1 E2) E3≡E1 (E2 E3)
3. 投影的串接定律
( (E))≡ (E)
這裡，E是關系代數表達式，Ai(i=1，2，…，n)，Bj(j=1，2，…，m)是屬性名且{A1，A2，…，An}構成{B1，B2，…，Bm}的子集。
4. 選擇的串接定律
( (E))≡ (E)
這裡，E是關系代數表達式，F1、F2是選擇條件。
選擇的串接律說明選擇條件可以合並。這樣一次就可檢查全部條件
5. 選擇與投影操作的交換律
σF( (E))≡ (σF(E))
選擇條件F只涉及屬性A1，…，An。
若F中有不屬於A1，…，An的屬性B1，…，Bm則有更一般的規則：
(σF(E))≡ (σF( (E)))
6. 選擇與笛卡爾積的交換律
如果F中涉及的屬性都是E1中的屬性，則
(E1×E2)≡ (E1)×E2
如果F=F1∧F2，並且F1只涉及E1中的屬性，F2只涉及E2中的屬性，則由上面的等價變換規則1，4，6可推出：
(E1×E2)≡ (E1)× (E2)
若F1只涉及E1中的屬性，F2涉及E1和E2兩者的屬性，則仍有
(E1×E2)≡ ( (E1)×E2)
它使部分選擇在笛卡爾積前先做。
7. 選擇與並的分配律
設E=E1∪E2，E1，E2有相同的屬性名，則
σF(E1∪E2)≡σF(E1)∪σF(E2)
8. 選擇與差運算的分配律
若E1與E2有相同的屬性名，則
σF(E1-E2)≡σF(E1)-σF(E2)
9. 選擇對自然連接的分配律
σF(E1 E2)≡σF(E1) σF(E2)
F只涉及E1與E2的公共屬性
10. 投影與笛卡爾積的分配律
設E1和E2是兩個關系表達式，A1，…，An是E1的屬性，B1，…，Bm是E2的屬性，則
(E1×E2)≡ (E1)× (E2)
11. 投影與並的分配律
設E1和E2有相同的屬性名，則
(E1∪E2)≡ (E1)∪ (E2)
典型的啟發式規則：
1. 選擇運算應盡可能先做。在優化策略中這是最重要、最基本的一條
2. 把投影運算和選擇運算同時進行（pipelining技術）
如有若干投影和選擇運算，並且它們都對同一個關系操作，則可以在掃描此關系的同時完成所有的這些運算以避免重復掃描關系，也避免存儲中間關系
3. 把投影同其前或其後的雙目運算結合起來執行（pipelining技術）
4. 把某些選擇同在它前面要執行的笛卡爾積結合起來成為一個連接運算
5. 找出公共子表達式
如果這種重復出現的子表達式的結果不是很大的關系並且從外存中讀入這個關系比計算該子表達式的時間少得多，則先計算一次公共子表達式並把結果寫入中間文件是合算的
當查詢的是視圖時，定義視圖的表達式就是公共子表達式的情況
遵循這些啟發式規則，應用9.3.1的等價變換公式來優化關系表達式的算法。
算法：關系表達式的優化
輸入：一個關系表達式的查詢樹
輸出：優化的查詢樹
方法：
(1) 利用等價變換規則4把形如σF1∧F2∧…∧Fn(E)變換為σF1(σF2(…(σFn(E))…))。
(2) 對每一個選擇，利用等價變換規則4～9盡可能把它移到樹的葉端。
(3) 對每一個投影利用等價變換規則3，5，10，11中的一般形式盡可能把它移向樹的葉端。
注意：
等價變換規則3使一些投影消失
規則5把一個投影分裂為兩個，其中一個有可能被移向樹的葉端
(4) 利用等價變換規則3～5把選擇和投影的串接合並成單個選擇、單個投影或一個選擇後跟一個投影。使多個選擇或投影能同時執行，或在一次掃描中全部完成
(5) 把上述得到的語法樹的內節點分組。每一雙目運算(×， ，∪，-)和它所有的直接祖先為一組(這些直接祖先是(σ，π運算)。
如果其後代直到葉子全是單目運算，則也將它們並入該組
但當雙目運算是笛卡爾積(×)，而且後面不是與它組成等值連接的選擇時，則不能把選擇與這個雙目運算組成同一組，把這些單目運算單獨分為一組
例[5] 查詢語句：檢索學習課程名為MATH的女學生學號和姓名。
該查詢語句的關系代數表達式如下：
πS#，SNAME(σCNAME=’MATH’∧SEX=’F’(C SC S))
上式中， 符號用π、σ、×操作表示，可得下式
πS#，SNAME(σCNAME=’MATH’∧SEX=’F’(πL
(σC.C# = SC.C#∧SC.S# = S.S#(C×SC×S))))
此處L是C、SC、S中全部屬性,去除重復屬性。
