? 所謂查詢優(yōu)化，目標(biāo)是關(guān)系數(shù)據(jù)庫(kù)下或者 newSQL 的 SQL Server 層對(duì) SQL 語(yǔ)句進(jìn)行優(yōu)化，在不改變期望結(jié)果的情況下使得數(shù)據(jù)庫(kù)引擎計(jì)劃執(zhí)行時(shí)間最短。狹義的查詢優(yōu)化技術(shù)是指邏輯優(yōu)化與物理優(yōu)化（在后面會(huì)細(xì)講），廣義上的查詢優(yōu)化技術(shù)包括從 SQL 語(yǔ)句輸入開始，對(duì) SQL 語(yǔ)句的重寫，內(nèi)部執(zhí)行算法的優(yōu)化，并行優(yōu)化及分布式條件下的優(yōu)化，還包括了外部緩存機(jī)制對(duì)于查詢計(jì)劃及查詢結(jié)果的重用。
? 查詢優(yōu)化技術(shù)是數(shù)據(jù)庫(kù)領(lǐng)域十分重要的技術(shù)，尤其在當(dāng)前業(yè)務(wù)數(shù)據(jù)及業(yè)務(wù)請(qǐng)求規(guī)模不斷增長(zhǎng)的情況下顯得尤為重要。這里從狹義的查詢優(yōu)化技術(shù)入手，從宏觀上講述查詢優(yōu)化器的架構(gòu)及各個(gè)模塊實(shí)現(xiàn)的主要功能任務(wù)，希望能夠?qū)Υ蠹伊私饧袄斫獠樵儍?yōu)化器有所幫助。

架構(gòu)

? SQL 語(yǔ)句經(jīng)過(guò)語(yǔ)法分析器生成語(yǔ)法分析樹，再通過(guò)查詢優(yōu)化器生成查詢樹及查詢計(jì)劃，最后交由執(zhí)行器執(zhí)行。

架構(gòu)圖

語(yǔ)法分析器

語(yǔ)法分析

? 語(yǔ)法分析是指對(duì)用戶輸入的 SQL 語(yǔ)句進(jìn)行判斷，糾正拼寫錯(cuò)誤及語(yǔ)法錯(cuò)誤。如：

Select name, class_name
from student S, course C, sc SC
where S.sno = SC.sno and C.cno = SC.cno and C.cno = 22;

?如果關(guān)鍵詞如 Select 拼寫錯(cuò)誤，或者語(yǔ)句不符合 Select_From_Where 語(yǔ)法規(guī)范，將在此步驟檢測(cè)出來(lái)。

語(yǔ)義檢查

? 語(yǔ)義檢測(cè)負(fù)責(zé)判斷 SQL 語(yǔ)句中涉及的表及表中的屬性列是否存在，如果 SQL 所操作的目標(biāo)表或者屬性列完全不存在那么后期的優(yōu)化也是徒勞無(wú)果的。比如在上面的 SQL 例子中，將會(huì)判斷以下存儲(chǔ)對(duì)象或元數(shù)據(jù)是否存在。

屬性列： name, class_name
相關(guān)表： student, course, sc

查詢優(yōu)化器

邏輯優(yōu)化

? 邏輯優(yōu)化簡(jiǎn)單來(lái)說(shuō)就是根據(jù)關(guān)系代數(shù)的等價(jià)變換規(guī)則進(jìn)行查詢重寫。首先傳統(tǒng)關(guān)系代數(shù)運(yùn)算符有并、交、差、積，對(duì)于 SQL 語(yǔ)句來(lái)說(shuō)，專有運(yùn)算符有選擇、投影、連接、除。首先傳統(tǒng)運(yùn)算符在 SQL 語(yǔ)句中的體現(xiàn)為：

• 并 - union

Select * from R union Select * from S

• 交 - not in(not in)

Select * from R where kr not in (
Select kr from R where kr not in (
Select ks from S))

• 差 - not in

Select * from R where kr not in (Select ks from S)

• 積 - 無(wú)條件join

Select R.* , S.* from R , S

專有運(yùn)算符的 SQL 表現(xiàn)：

• 選擇 - condition

Select * from R where condition

• 投影 - 屬性列

Select col_1,col_2+2 from R

• 連接 - condition 中 join 或者等值連接

Select r.col_1,s.col_2 from R,S where condition

• 除 - not exists(not exists)

Select Distinct r1.x from R,r1 where not exists (
Select S.y from S Where not exists (
Select * from R r2 where r2.x=r1.x and r2.y=S.y))

? 有了上述的運(yùn)算符對(duì)應(yīng)關(guān)系， SQL 語(yǔ)句就可以使用關(guān)系代數(shù)的等價(jià)變換進(jìn)行優(yōu)化。這里有一些例子：

邏輯優(yōu)化舉例

物理優(yōu)化

? 物理優(yōu)化是與實(shí)際存儲(chǔ)相關(guān)的優(yōu)化階段。簡(jiǎn)單來(lái)說(shuō)就是通過(guò)代價(jià)模型對(duì)表級(jí)操作算法的選擇。
? 首先介紹代價(jià)模型，學(xué)過(guò)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的同學(xué)都知道，衡量計(jì)算機(jī)性能的重要指標(biāo)就是相同任務(wù)或者指令的執(zhí)行時(shí)間。那么與之相似，一個(gè)執(zhí)行計(jì)劃的優(yōu)劣程度也可以使用時(shí)間來(lái)衡量。當(dāng)然，數(shù)據(jù)庫(kù)查詢優(yōu)化的目標(biāo)也是在盡可能短的時(shí)間返回期望的結(jié)果。所以代價(jià)模型的宏觀表達(dá)式為：總代價(jià) = IO代價(jià) + CPU代價(jià)

? 說(shuō)回表級(jí)操作算法，這里有以下3類：

• 單表 ---> 掃描方式 ： 全表掃描、索引掃描
• 兩表 ---> 連接方式 ： 嵌套循環(huán)連接、歸并連接、哈希連接
• 多表 ---> 連接順序 ： 動(dòng)態(tài)規(guī)劃、啟發(fā)式、貪心、System R、遺傳算法

單表掃描

? 單表掃描的選擇主要通過(guò)選擇率來(lái)判斷，也就是滿足條件的元組數(shù)（表中一行數(shù)據(jù)）占總元組數(shù)的比例。同時(shí)在許多文章中，這里滿足條件的元祖數(shù)也稱為基數(shù)，有: 選擇率 = 基數(shù) / 總元組數(shù)。
? 比如在條件篩選過(guò)后可能只有 1/1000 的元組被選到，那么通過(guò)索引掃描的方式訪問(wèn)整個(gè)表是很快的，但如果有 999/1000 的數(shù)據(jù)將會(huì)被篩選出來(lái)，那么通過(guò)全表掃描的方式或許更加有效。

兩表連接

? 傳統(tǒng)的兩表連接方法有嵌套循環(huán)連接、歸并連接及哈希連接。

• 嵌套循環(huán)連接 ： 相當(dāng)于兩個(gè)for循環(huán)，使用 A 表的一個(gè)元組去匹配 B 表的每一個(gè)元組，直到 A 表的所有元組都被訪問(wèn)完全。
• 歸并連接 ： 先將 B 表按照匹配的屬性列排序，然后使用 A 表的每一個(gè)元組匹配 B 表的元組，一旦出現(xiàn)不匹配的情況下那么直接開始下一輪循環(huán)匹配（因?yàn)榕胚^(guò)序，后續(xù)的元組也將不匹配）。
• 哈希連接 ： 先將 A 表所有元組對(duì)應(yīng)屬性列 hash ，然后將 B 表的每個(gè)元組對(duì)應(yīng)屬性列使用相同的散列方法 hash，若值相等則匹配。

多表連接順序

? 多表下是對(duì)各個(gè)表的連接順序進(jìn)行選擇，比如 A、B、C 三個(gè)表，A、B 較大，C 較小，那么 AB 先連接可能產(chǎn)生的中間結(jié)果會(huì)比較大， 采用 BC-A 的連接順序可能先得到的中間結(jié)果就會(huì)比較小，既節(jié)省計(jì)算資源又節(jié)省存儲(chǔ)空間。常見的多表連接順序的選擇算法有動(dòng)態(tài)規(guī)劃、啟發(fā)式、貪心、System R、遺傳算法。PostgreSQl 中使用的算法為動(dòng)態(tài)規(guī)劃及遺傳算法。

分布式查詢優(yōu)化

? 與單機(jī)的查詢優(yōu)化不同，分布式情況下目標(biāo)數(shù)據(jù)可能分布在不同的節(jié)點(diǎn)上。因此對(duì)于代價(jià)模型來(lái)說(shuō)，還需要加上數(shù)據(jù)傳輸的代價(jià)。同時(shí)由于分布式環(huán)境的復(fù)雜性，還要考慮到數(shù)據(jù)副本及底層數(shù)據(jù)庫(kù)引擎異構(gòu)（如關(guān)系型與 NoSQL ）和異制（數(shù)據(jù)模型及數(shù)據(jù)結(jié)構(gòu)不相同，比如文件型及 KV）的問(wèn)題。

? 分布式環(huán)境下如果兩個(gè)要連接的表（A、B）在不同的節(jié)點(diǎn)上，這樣的情況下有兩種基本的連接算法：

• 直接連接：直接將 B 表整個(gè)傳輸?shù)?A 表所在節(jié)點(diǎn)進(jìn)行連接計(jì)算
• 半連接：只是將 B 表要連接的屬性列傳輸?shù)?A 表所在節(jié)點(diǎn)進(jìn)行連接計(jì)算，計(jì)算完畢后傳輸回 B 表的節(jié)點(diǎn)篩選出匹配完成的元組

?很明顯，直接連接不適合目標(biāo)表非常大的情況，但是半連接傳輸?shù)拇螖?shù)較多。

最后

? 以上旨在幫助大家宏觀認(rèn)識(shí)數(shù)據(jù)庫(kù)查詢優(yōu)化器，對(duì)查詢優(yōu)化器架構(gòu)及各個(gè)模塊功能有大體認(rèn)識(shí)。
? 以下是幾篇相關(guān)的經(jīng)典論文：

• The Volcano optimizer generator: extensibility and efficient search
• Eddies: Continuously Adaptive Query Processing
• Ripple Joins for Online Aggregation