一條查詢SQL到執行的完整流程
整體流程如下：
用一條SQL舉例如下：下面是一個簡單的嵌套查詢的SQL.
第一步：會把這條 SQL 轉換為一棵AST抽象文法樹：
第二步：會把這個AST抽象文法樹轉換為關系代數表達的邏輯計劃：
第三步：對邏輯計劃進行優化：
上面是把StarsIn表與子表做了一個笛卡爾積，但是其實是可以做Join的，是以可以變換為如下查詢計劃（這裡其實就是對邏輯計劃進行優化）：
第四步：需要評估資料表的資料量大小，子查詢的資料量大小，以及最後結果資料量大小（主要是根據中繼資料統計資訊進行估算）:
第五步：需要根據上一步的統計資訊選擇把邏輯計劃轉換為很多實體計劃，例如的join政策（Hash Join還是嵌套循環），掃描的方式（分段掃描還是索引掃描），如下可以轉換為很多中實體計劃；
實體計劃1:
實體計劃2:
實體計劃3:
第六步：需要評估每一種實體計劃的成本，然後選擇代價最小的實體計劃：
第七步：有了實體執行計劃，應該怎麼執行實體計劃：
目前主要有三種方法：
- 解釋疊代的執行方式：核心思想就是把SQL 的每個操作算子化，然後通過疊代的方式順序執行每一步進而達到最後結果；
- 向量化的執行方式：核心思想就是通過把SQL 的操作算子批量運作的方式進行；
- 通過代碼編譯的方式：核心思想就是把SQL 的執行的邏輯通過編譯器直接自動編譯成可執行的代碼；
：
上面的SQL語句可以分為兩部分，一個是productId=75的SELECT算子，一個是quantity*price的表達式算子；
定義好接口和算子：主要分為兩種，一種是Operator,例如表掃描算子，SELECT算子，投射（PROJECTION）算子；一種是表達式Expression,例如取出字段的Atribute,計算乘法的Times,計算相等的Equals;
Expression的具體實作例子如下：Attribute主要是擷取具體的字段；Times主要是計算乘法；
Operator的具體實作例子：例如TableScan主要是資料擷取每一行資料；Project主要是通過parent Operator中擷取資訊，然後通過執行Expression中的計算方法；
接下來就可以把上面例子SQL通過如下的方式表達出來，最後生成一個Project算子，通過疊代調用算子的計算方法執行最後得到結果；
這種方法的優點是簡單，但是每次執行一個算子，比較慢；是以可以通過保留上面的算子，但是執行的時候可以批量一次執行，這就引出下第二種方法；
這三種方法的使用情況：
- 傳統關系型資料庫例如MySQL:主要使用第一種逐條解釋執行的方式；
- 大資料分析架構例如Spark SQL:主要使用第二種向量批量執行的方法，同時也會采用第三種編譯生成運作代碼的方式；
- 機器學習相關架構如TensorFlow:主要使用第二種向量批量執行的方法，同時也會采用第三種編譯生成運作代碼的方式；
我們能優化什麼
主要分為三個地方進行優化：
- SQL算子圖：選擇什麼樣的算子，以及執行的順序；
- SQL底層算子的實作方式：例如Join有很多實作方式，如Hash Join還是Sort Merge Join等，我們可以根據實際情況選擇不同的實作方式；
- 通路路徑：怎麼讀取資料表，是全表掃描、索引掃描還是索引分段掃描等等資料通路的路徑方式；
基于規則的優化
提前定義好一些規則，當查詢計劃中滿足這些規則的時候就可以通過這些規則進行優化，例如當我們判斷到一個SQL中的表達式有expr OR TRUE的時候，我們可以直接改寫為TRUE,進而避免無意義的計算。
如何實作每一個Rule其實就是一個函數，通過搜尋整個Query Plan，如果滿足條件就做轉換；
一般Rules都是在優化過程中的一個階段分組好了的 ，每一個階段跑所有的Rule直到全部應用了Rule:
1.簡單化select,project中的表達式：如上例提到的Boolean表達式；一些計算表達式；字元串表達式等；很多重複的表達式也可以簡化；
2.選擇通路路徑和操作實作的Rule:
- 索引列的判斷：如果是索引列，就走索引掃描；
- 小表判斷：如果是小表就可以走hash join;
- 少量資料基于列的聚合：可以用記憶體hash table的方式；
3.過濾條件下推：
例子1：從兩個表的笛卡爾積完了後再根據R表篩選滿足p過濾條件的查詢，可以直接優化為先篩選出R表的p再與S進行笛卡爾積，這樣能減少資料量傳輸和計算量；
4.查詢字段裁剪：
例子1：如果最終傳回資料中有X的列，可以先在表R上進行X列和p過濾條件中的列形成一個全集傳回，然後再查詢需要的X列，這樣就避免了第一步的時候把所有列資料傳回，裁剪了查詢字段，減少了資料的傳輸量；
基于規則優化的缺陷這種完全基于模式的優化Rule不一定完全達到理想的優化效果，是以需要進一步基于資料統計和成本模型的方式進行優化；
資料統計資訊
T(R):表示R表有多少行；
S(R):表示一行資料的總位元組數；
B(R):表需要實體存儲的塊數；
V(R，A):A列的基數：也就是A列的distinct數目；
資料統計資訊計算方法
磁盤上實體資料表的統計資訊很容易擷取，但是對于一個查詢計劃中間表的資料統計資訊應該怎麼計算呢？
一個完美的計算算法應該滿足如下條件：
- 能夠精确評估統計資訊；
- 低成本消耗；
- 幂等性：也就是對于同樣的中間過程多次評估都是一樣的結果；
事實上幾乎不可能同時滿足上面的要求。
例子1:評估兩個表笛卡爾積後的表的統計資訊：W=R1*R2
S(W) = S(R1) + S(R2):計算W表一行資料的位元組數，可以把兩個表各自每行位元組數加起來；
T(W) = T(R1) * T(R2):計算W表所有的行數。
例子2:評估select * from R where Z=val中間表W的統計資訊，可以基于不同的假設進行估算：
假設Z字段的分布全是一緻的：
也就是W表的行數=R表總行數/Z列的基數
假設Z字段是基于給定一個值均勻分布的：
如圖：如果給定所有列的一個領域值是10，那麼對于任何列的行數可以計算為總行數/這個領域值；
例子3:對于評估select * from R where Z>=val中間表W的統計資訊:
假設都是分布均勻的，可以根據比例計算W表的條數；
例子4:評估Join中間結果的統計資訊：W=R1 join R2
Case1:如果R1與R2沒有相同字段，那與笛卡爾積沒什麼差別；
Case2:如果有相同字段A,且V(R1,A)<=V(R2,A):即在R1表的A列數值是R2表A列數值的子集；
也就是總的行數=R1的行數*A列在R2表中的平均數。
Case3:如果有相同字段A,且V(R1,A)>=V(R2,A):即在R2表的A列數值是R1表A列數值的子集；
基于成本模型
我們怎麼去衡量一個查詢計劃的成本呢？下面是通常的一些名額參數：
- 磁盤IO數量；
- 計算循環的次數；
- 執行的時間消耗；
- 記憶體使用情況；傳輸資料量大小；cpu使用消耗；
本文隻專注在磁盤IO數量上。
例1: select * from table where p 中間表R走索引 vs 全表掃描的IO數
全表掃描IO次數=T(R)*S(R)/block size b=行數*每行位元組數/一個塊的位元組數
走索引所描IO次數：首先做p條件篩選假設進行了L次IO;
Join的順序以及實作算法的選擇常常非常影響運算的效率。
上面例子中選擇什麼樣的順序會影響執行效率。
一些常見的Join算法：
- 嵌套循環Join:也就是小表驅動大表。
2.Merge Join:核心思想就是先排序，再比較。
核心算法如下：
Cost如下：
3.基于索引的Join:
4.Hash Join(基于Ram)
5.基于磁盤的Hash Join
對于Join算法可以有如下結論：
- 如果索引存在就走索引Join;
- 如果至少有一個表是排序過的，就走Merge Join;
- 如果所有表沒有排序，就走Hash Join;
基于CBO的優化
為了解決RBO的缺陷，是以提出了基于CBO的思想，通過基于統計資訊對Plan Cost的計算進而進行優化，整個流程如下：
第一步：Generage Plans：生成Plans;
第二步：進行剪枝；
第三步：評估Cost,并選擇Cost最小的進行執行。
怎麼樣生成Plans:一種最簡單的方式就是疊代搜尋并窮舉每一種可能：
如上圖，但是搜尋空間會非常大，是以很多DBMS簡單的考慮左子樹深度Join的方式減少複雜度，如下圖：
一種辦法是通過疊代的方式，如果沒有比目前最好的要好就丢棄；
另一個辦法是通過一種貪心算法，找到局部優化的方式，這樣能夠很大程度的進行剪枝；
記憶體記錄的方式以及使用動态規劃在Plan的搜尋過程中，許多子查詢會重複出現，就需要記錄統計資訊和cost評估這樣減少計算量；
這樣就能記錄好子查詢最優的政策，這也就是動态規劃的思想。
參考
1. cs245.stanford.edu: Query Optimization 1/2
2. 詳細可以再參考文章：https://io-meter.com/2018/11/01/sql-query-optimization-volcano/