代數優化改變查詢語句中操作的次序和組合，不涉及底層的存取路徑
對於一個查詢語句有許多存取方案，它們的執行效率不同， 僅僅進行代數優化是不夠的
物理優化就是要選擇高效合理的操作算法或存取路徑，求得優化的查詢計劃
一、 選擇操作的啟發式規則:
對於小關系，使用全表順序掃描，即使選擇列上有索引
對於大關系，啟發式規則有：
對於選擇條件是主碼＝值的查詢
查詢結果最多是一個元組，可以選擇主碼索引
一般的RDBMS會自動建立主碼索引。
對於選擇條件是非主屬性＝值的查詢，並且選擇列上有索引
要估算查詢結果的元組數目
如果比例較小(<10%)可以使用索引掃描方法
否則還是使用全表順序掃描
對於選擇條件是屬性上的非等值查詢或者范圍查詢，並且選擇列上有索引
要估算查詢結果的元組數目
如果比例較小(<10%)可以使用索引掃描方法
否則還是使用全表順序掃描
對於用AND連接的合取選擇條件
如果有涉及這些屬性的組合索引
優先采用組合索引掃描方法
如果某些屬性上有一般的索引
則可以用［例1-C4］中介紹的索引掃描方法
否則使用全表順序掃描。
對於用OR連接的析取選擇條件，一般使用全表順序掃描
二、 連接操作的啟發式規則：
1. 如果2個表都已經按照連接屬性排序
選用排序-合並方法
2. 如果一個表在連接屬性上有索引
選用索引連接方法
3. 如果上面2個規則都不適用，其中一個表較小
選用Hash join方法
. 可以選用嵌套循環方法，並選擇其中較小的表，確切地講是占用的塊數(b)較少的表，作為外表(外循環的表) 。
理由：
設連接表R與S分別占用的塊數為Br與Bs
連接操作使用的內存緩沖區塊數為K
分配K-1塊給外表
如果R為外表，則嵌套循環法存取的塊數為:
Br+ (Br/(K-1)) *Bs
顯然應該選塊數小的表作為外表
一、 統計信息
基於代價的優化方法要計算各種操作算法的執行代價，與數據庫的狀態密切相關
數據字典中存儲的優化器需要的統計信息：
1. 對每個基本表
該表的元組總數(N)
元組長度(l)
占用的塊數(B)
占用的溢出塊數(BO)
2. 對基表的每個列
該列不同值的個數(m)
選擇率(f)
如果不同值的分布是均勻的，f＝1/m
如果不同值的分布不均勻，則每個值的選擇率＝具有該值的元組數/N
該列最大值
該列最小值
該列上是否已經建立了索引
索引類型(B+樹索引、Hash索引、聚集索引)
3. 對索引(如B+樹索引)
索引的層數(L)
不同索引值的個數
索引的選擇基數S(有S個元組具有某個索引值)
索引的葉結點數(Y)
二、 代價估算示例
全表掃描算法的代價估算公式
如果基本表大小為B塊，全表掃描算法的代價 cost＝B
如果選擇條件是碼＝值，那麼平均搜索代價 cost＝B/2
索引掃描算法的代價估算公式如果比較條件是＞，＞＝，＜，＜＝操作
假設有一半的元組滿足條件就要存取一半的葉結點
通過索引訪問一半的表存儲塊cost=L+Y/2+B/2
嵌套循環連接算法的代價估算公式
9.4.1中已經討論過了嵌套循環連接算法的代價 cost＝Br+(Br/(K-1))*Bs
如果需要把連接結果寫回磁盤，
cost＝Br+(Br/(K-1))*Bs +(Frs*Nr*Ns)/Mrs
其中Frs為連接選擇性(join selectivity)，表示連接結果元組數的比例
Mrs是存放連接結果的塊因子，表示每塊中可以存放的結果元組數目。
排序-合並連接算法的代價估算公式
如果連接表已經按照連接屬性排好序，則 cost＝Br+Bs+(Frs*Nr*Ns)/Mrs。
如果必須對文件排序
需要在代價函數中加上排序的代價
對於包含B個塊的文件排序的代價大約是(2*B)+(2*B*log2B)
比較復雜的查詢，尤其是涉及連接和嵌套的查詢
不要把優化的任務全部放在RDBMS上
應該找出RDBMS的優化規律，以寫出適合RDBMS自動優化的SQL語句
了解具體的查詢計劃表示，分析查詢的實際執行策略
