? 所謂查詢優(yōu)化璧瞬，目標是關(guān)系數(shù)據(jù)庫下或者 newSQL 的 SQL Server 層對 SQL 語句進行優(yōu)化栈暇，在不改變期望結(jié)果的情況下使得數(shù)據(jù)庫引擎計劃執(zhí)行時間最短麻裁。狹義的查詢優(yōu)化技術(shù)是指邏輯優(yōu)化與物理優(yōu)化（在后面會細講），廣義上的查詢優(yōu)化技術(shù)包括從 SQL 語句輸入開始瞻鹏，對 SQL 語句的重寫悲立，內(nèi)部執(zhí)行算法的優(yōu)化鹿寨，并行優(yōu)化及分布式條件下的優(yōu)化新博，還包括了外部緩存機制對于查詢計劃及查詢結(jié)果的重用。
? 查詢優(yōu)化技術(shù)是數(shù)據(jù)庫領(lǐng)域十分重要的技術(shù)脚草，尤其在當前業(yè)務(wù)數(shù)據(jù)及業(yè)務(wù)請求規(guī)模不斷增長的情況下顯得尤為重要赫悄。這里從狹義的查詢優(yōu)化技術(shù)入手，從宏觀上講述查詢優(yōu)化器的架構(gòu)及各個模塊實現(xiàn)的主要功能任務(wù)馏慨，希望能夠?qū)Υ蠹伊私饧袄斫獠樵儍?yōu)化器有所幫助埂淮。
架構(gòu)
? SQL 語句經(jīng)過語法分析器生成語法分析樹，再通過查詢優(yōu)化器生成查詢樹及查詢計劃写隶，最后交由執(zhí)行器執(zhí)行倔撞。
語法分析器
語法分析
? 語法分析是指對用戶輸入的 SQL 語句進行判斷，糾正拼寫錯誤及語法錯誤慕趴。如：
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 拼寫錯誤痪蝇，或者語句不符合 Select_From_Where 語法規(guī)范，將在此步驟檢測出來冕房。
語義檢查
? 語義檢測負責判斷 SQL 語句中涉及的表及表中的屬性列是否存在躏啰，如果 SQL 所操作的目標表或者屬性列完全不存在那么后期的優(yōu)化也是徒勞無果的。比如在上面的 SQL 例子中耙册，將會判斷以下存儲對象或元數(shù)據(jù)是否存在给僵。
屬性列： name, class_name
相關(guān)表： student, course, sc
查詢優(yōu)化器
邏輯優(yōu)化
? 邏輯優(yōu)化簡單來說就是根據(jù)關(guān)系代數(shù)的等價變換規(guī)則進行查詢重寫。首先傳統(tǒng)關(guān)系代數(shù)運算符有并详拙、交帝际、差蔓同、積，對于 SQL 語句來說蹲诀，專有運算符有選擇牌柄、投影、連接侧甫、除珊佣。首先傳統(tǒng)運算符在 SQL 語句中的體現(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)
- 積 - 無條件join
Select R.* , S.* from R , S
專有運算符的 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īng)關(guān)系， SQL 語句就可以使用關(guān)系代數(shù)的等價變換進行優(yōu)化披粟。這里有一些例子：
物理優(yōu)化
? 物理優(yōu)化是與實際存儲相關(guān)的優(yōu)化階段咒锻。簡單來說就是通過代價模型對表級操作算法的選擇。
? 首先介紹代價模型守屉，學(xué)過計算機系統(tǒng)結(jié)構(gòu)的同學(xué)都知道惑艇，衡量計算機性能的重要指標就是相同任務(wù)或者指令的執(zhí)行時間。那么與之相似拇泛，一個執(zhí)行計劃的優(yōu)劣程度也可以使用時間來衡量滨巴。當然，數(shù)據(jù)庫查詢優(yōu)化的目標也是在盡可能短的時間返回期望的結(jié)果俺叭。所以代價模型的宏觀表達式為：總代價 = IO代價 + CPU代價
? 說回表級操作算法恭取，這里有以下3類：
- 單表 ---> 掃描方式 ： 全表掃描、索引掃描
- 兩表 ---> 連接方式 ： 嵌套循環(huán)連接熄守、歸并連接蜈垮、哈希連接
- 多表 ---> 連接順序 ： 動態(tài)規(guī)劃、啟發(fā)式裕照、貪心攒发、System R、遺傳算法
單表掃描
? 單表掃描的選擇主要通過選擇率來判斷晋南，也就是滿足條件的元組數(shù)（表中一行數(shù)據(jù)）占總元組數(shù)的比例惠猿。同時在許多文章中，這里滿足條件的元祖數(shù)也稱為基數(shù)负间，有: 選擇率 = 基數(shù) / 總元組數(shù)偶妖。
? 比如在條件篩選過后可能只有 1/1000 的元組被選到，那么通過索引掃描的方式訪問整個表是很快的唉擂，但如果有 999/1000 的數(shù)據(jù)將會被篩選出來餐屎，那么通過全表掃描的方式或許更加有效。
兩表連接
? 傳統(tǒng)的兩表連接方法有嵌套循環(huán)連接玩祟、歸并連接及哈希連接腹缩。
- 嵌套循環(huán)連接 ： 相當于兩個for循環(huán)，使用 A 表的一個元組去匹配 B 表的每一個元組，直到 A 表的所有元組都被訪問完全藏鹊。
- 歸并連接 ： 先將 B 表按照匹配的屬性列排序润讥，然后使用 A 表的每一個元組匹配 B 表的元組，一旦出現(xiàn)不匹配的情況下那么直接開始下一輪循環(huán)匹配（因為排過序盘寡，后續(xù)的元組也將不匹配）楚殿。
- 哈希連接 ： 先將 A 表所有元組對應(yīng)屬性列 hash ，然后將 B 表的每個元組對應(yīng)屬性列使用相同的散列方法 hash竿痰，若值相等則匹配脆粥。
多表連接順序
? 多表下是對各個表的連接順序進行選擇，比如 A影涉、B变隔、C 三個表，A蟹倾、B 較大匣缘，C 較小，那么 AB 先連接可能產(chǎn)生的中間結(jié)果會比較大鲜棠， 采用 BC-A 的連接順序可能先得到的中間結(jié)果就會比較小肌厨，既節(jié)省計算資源又節(jié)省存儲空間。常見的多表連接順序的選擇算法有動態(tài)規(guī)劃豁陆、啟發(fā)式柑爸、貪心、System R献联、遺傳算法竖配。PostgreSQl 中使用的算法為動態(tài)規(guī)劃及遺傳算法何址。
分布式查詢優(yōu)化
? 與單機的查詢優(yōu)化不同里逆，分布式情況下目標數(shù)據(jù)可能分布在不同的節(jié)點上。因此對于代價模型來說用爪，還需要加上數(shù)據(jù)傳輸的代價原押。同時由于分布式環(huán)境的復(fù)雜性，還要考慮到數(shù)據(jù)副本及底層數(shù)據(jù)庫引擎異構(gòu)（如關(guān)系型與 NoSQL ）和異制（數(shù)據(jù)模型及數(shù)據(jù)結(jié)構(gòu)不相同偎血，比如文件型及 KV）的問題诸衔。
? 分布式環(huán)境下如果兩個要連接的表（A、B）在不同的節(jié)點上颇玷，這樣的情況下有兩種基本的連接算法：
- 直接連接：直接將 B 表整個傳輸?shù)?A 表所在節(jié)點進行連接計算
- 半連接：只是將 B 表要連接的屬性列傳輸?shù)?A 表所在節(jié)點進行連接計算笨农，計算完畢后傳輸回 B 表的節(jié)點篩選出匹配完成的元組
?很明顯，直接連接不適合目標表非常大的情況帖渠，但是半連接傳輸?shù)拇螖?shù)較多谒亦。
最后
? 以上旨在幫助大家宏觀認識數(shù)據(jù)庫查詢優(yōu)化器，對查詢優(yōu)化器架構(gòu)及各個模塊功能有大體認識。
? 以下是幾篇相關(guān)的經(jīng)典論文：
