上篇圖文，從SQL引擎概述和SQL解析兩方面進行了詳細論述，本篇將接著從SQL引擎的查詢優化展開介紹，完整版內容請查看CSDN·Gauss松鼠會專欄博客，以下內容為章節試讀：三、查詢優化
數據庫的查詢優化過程功能比較明晰，從源代碼組織的角度來看，相關代碼分布在不同的目錄下，如表1所示。表1查詢優化模塊說明
模塊
目錄
說明
查詢重寫
src///prep
主要包括子查詢優化、謂詞化簡及正則化、謂詞傳遞閉包等查詢重寫優化技術
統計信息
src////.cpp
生成各種類型的統計信息，供選擇率估算、行數估算、代價估算使用
代價估算
src///utils/adt/.///path/.cpp
進行選擇率估算、行數估算、代價估算
物理路徑
src///path
生成物理路徑
動態規劃
src///plan
通過動態規劃方法對物理路徑進行搜索
遺傳算法
src///geqo
通過遺傳算法對物理路徑進行搜索
（一）查詢重寫
SQL語言是豐富多樣的，非常的靈活，不同的開發人員依據經驗的不同，手寫的SQL語句也是各式各樣，另外還可以通過工具自動生成。SQL語言是一種描述性語言，數據庫的使用者只是描述了想要的結果，而不關心數據的具體獲取方式，輸入數據庫的SQL語言很難做到是以最優形式表示的，往往隱含了一些冗余信息，這些信息可以被挖掘用來生成更加高效的SQL語句。查詢重寫就是把用戶輸入的SQL語句轉換為更高效的等價SQL，查詢重寫遵循兩個基本原則。
（1） 等價性：原語句和重寫后的語句c 連接數據庫代碼，輸出結果相同。（2） 高效性：重寫后的語句，比原語句在執行時間和資源使用上更高效。查詢重寫主要是基于關系代數式的等價變換，關系代數的變換通常滿足交換律、結合律、分配率、串接率等，如表2所示。表2關系代數等價變換
等價變換
內容
交換律
A × B == B × AA ?B == B ? AA ?FB == B ?FA ……其中F是連接條件Πp(σF(B)) ==σF(Πp(B)) ……其中F∈p
結合律
(A × B) × C==A × (B × C)(A ?B) ?C==A ?(B ?C)(A ?F1B) ?F2C==A ?F1(B ?F2C) …… F1和F2是連接條件
分配律
σF(A × B) ==σF(A) × B …… 其中F∈ AσF(A × B) ==σF1(A) ×σF2(B)…… 其中F = F1 ∪ F2，F1∈A, F2 ∈BσF(A × B) ==σFX(σF1(A) ×σF2(B))…… 其中F = F1∪F2∪FX，F1∈A, F2 ∈BΠp,q(A × B) == Πp(A) × Πq(B) …… 其中p∈A，q∈BσF(A × B) ==σF1(A) ×σF2(B)…… 其中F = F1 ∪ F2，F1∈A, F2 ∈BσF(A × B) ==σFx(σF1(A) ×σF2(B))…… 其中F = F1∪F2∪Fx，F1∈A, F2 ∈B
串接律
ΠP=p1,p2,…pn(ΠQ=q1,q2,…qn(A)) == ΠP=p1,p2,…pn(A)……其中P?QσF1(σF2(A)) ==σF1∧F2(A)
查詢重寫優化既可以基于關系代數的理論進行優化，例如謂詞下推、子查詢優化等，也可以基于啟發式規則進行優化，例如Outer Join消除、表連接消除等。另外還有一些基于特定的優化規則和實際執行過程相關的優化c 連接數據庫代碼，例如在并行掃描的基礎上，可以考慮對算子分階段進行，通過將劃分成不同的階段，可以提升執行的效率。
從另一個角度來看，查詢重寫是基于優化規則的等價變換，屬于邏輯優化，也可以稱為基于規則的優化，那么怎么衡量對一個SQL語句進行查詢重寫之后，它的性能一定是提升的呢？這時基于代價對查詢重寫進行評估就非常重要了，因此查詢重寫不只是基于經驗的查詢重寫，還可以是基于代價的查詢重寫。
以謂詞傳遞閉包和謂詞下推為例，謂詞的下推能夠極大的降低上層算子的計算量，從而達到優化的效果，如果謂詞條件有存在等值操作，那么還可以借助等值操作的特性來實現等價推理，從而獲得新的選擇條件。
例如，假設有兩個表t1、t2分別包含[1,2,3,..100]共100行數據，那么查詢語句 t1.c1, t2.c1 FROM t1 JOIN t2 ON t1.c1=t2.c1 WHERE t1.c1=1則可以通過選擇下推和等價推理進行優化，如圖1所示。
圖1查詢重寫前后對比圖
如圖1（1）所示，t1、t2表都需要全表掃描100行數據，然后再做join，生成100行數據的中間結果，最后再做選擇操作，最終結果只有1行數據。如果利用等價推理，可以得到{t1.c1, t2.c1, 1}的是互相等價的，從而推導出新的t2.c1=1的選擇條件，并把這個條件下推到t2上，從而得到圖1（4）重寫之后的邏輯計劃。可以看到，重寫之后的邏輯計劃，只需要從基表上面獲取1條數據即可，join時內、外表的數據也只有1條，同時省去了在最終結果上的過濾條件，性能大幅提升。
在代碼層面，查詢重寫的架構大致如圖2所示。
圖2查詢重寫的架構
（1） 提升子查詢：子查詢出現在中，它存儲的是一個子查詢樹，若子查詢不被提升，則經過查詢優化之后形成一個子執行計劃，上層執行計劃和子查詢計劃做嵌套循環得到最終結果。在該過程中，查詢優化模塊對這個子查詢所能做的優化選擇較少。若該子查詢被提升，轉換成與上層的join，由查詢優化模塊常數替換等式：由于常數引用速度更快，故將可以求值的變量求出來，并用求得的常數替換它，實現函數為ams。（2） 子查詢替換CTE：理論上CTE（ table ，通用表達式）與子查詢性能相同，但對子查詢可以進行進一步的提升重寫優化，故嘗試用子查詢替換CTE，實現函數為。（3） multi count()替換為多條子查詢：如果出現該類查詢，則將多個count()查詢分別替換為多條子查詢，其中每條子查詢中包含一個count()表達式，實現函數為。