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