作者：馬弓手三菜
我記得我還在上一家公司的時候，有一次和主管一起做1：1，主管問我，将來你的技術方向是什麼，我說我想往HA方向發展，因為是我的強項。主管問我還有别的嗎？我猶豫地說，我也想做優化器方向，但是智商不夠。主管大笑，說如果有興趣可以鑽研看看。
現在想想，優化器确實比HA好玩多了。HA隻是資料庫的一個理念，實作這個理念的一些手段方式而已。而優化器則是算法實作，是關系型資料庫的整體實作方式。借此來了解圖靈獎得主James Gray的遺作，就算學不會，也可以吹吹這位傳奇人物的神秘去世故事
上篇
什麼是執行計劃？ 怎麼生成執行計劃？
資料通路的基本操作：Scan, Seek, bookmark lookup
表連接配接的三種基本操作： Nested Loop join, Merge Join, Hash Join
後續計劃中的坑
子查詢的種種
并發線程和我們的hybrid 并發
隔離級别 Isolation的實作
其他雜七雜八的待定
先挖好坑，逐漸來填。
1. 什麼是執行計劃？ 怎麼生成執行計劃？
1.1 執行計劃的基本機關 Operator
在說執行計劃之前，我們要知道執行計劃的基本機關。 SQL Server中，一個執行計劃的基本機關是iterator(疊代器)或者叫 operator，iterator主要做一件事，就是從input，可能是一個表，可能是一個計算結果集，讀入資料，然後進行一定操作之後，傳回結果集給他的父節點。
在SQL Server的圖形執行計劃中，每一個小圖示，就是一個operator
1.2 怎麼生成執行計劃
SQL Server有兩個執行計劃，一個是Estimated EP, 一個是 Actual EP。
所謂Estimated EP，就是指，在真正執行SQL語句之前，解析一次語句，看看可能生成的執行計劃時什麼
而Actual EP則是一條SQL語句執行時真正采用的執行計劃。 在SQL Server和 Oracle中，兩者往往因為種種原因（比如統計資訊不準）會和estimated EP不一樣，也是商業資料庫經常優化的一個點。
Actual EP 相比于 Estimated EP，每個operator上會多一些統計結果，包括，這個operator實際執行了幾次，傳回了多少行？這和estimated的是否一緻，是我們調優的一個重要點，statistics是否準确。
下圖左邊是AEP，右邊是EEP。
那麼為什麼需要Estimated EP呢 ，有些大語句跑一次要一個小時甚至更多，沒法獲得Actual EP，這個時候我們就需要 Estimated EP.
生成Estimated EP的方法非常簡單，SQL Server中，點選這個按鈕“Display Estimated Execution Plan”，或者使用showplan語句。
1.3 operator的三屬性
是以這下我們知道了，如果要想讀懂一個執行計劃，最關鍵的是讀懂operator。這也是為什麼我一開始說，mysql的執行計劃看上去簡單，容易了解，實際上，沒法深入閱讀。對于學習優化器，是一個天然壁壘。
1.3.1 記憶體
每一個operator，都需要使用一定的記憶體來完成執行動作。是以通常情況，資料庫引擎會預留一些記憶體給他們。但有些操作，需要消耗大量記憶體， 是以會出現使用tempdb（sqlserver） 來彌補記憶體的不足。
1.3.2 阻塞式和互動式
有些operator必須執行完成，才能傳回結果，這種稱之為阻塞式，比如排序，hash操作，和一些組合函數，max,min,count等，都是在執行完成才傳回結果。
有些operator，可以一邊執行，一邊傳回結果。一個非常好的例子就是top(sql server) 和 limit(mysql), 一個億級别的表，也可以很快取到top 5 行。 當然，如果之後有sort條件，就另當别論了。
1.3.3 動态遊标（cursor）
并不是所有資料結果都是可以順序/倒序讀取的，一個好的例子就是索引檢索，索引掃描的本質就是一個可以正過來倒過去的遊标。是以合适的索引非常重要，如果是一個堆（heap），operator就沒法支援cursor。
MySQL中預設會解決掉heap結構，這點和SQL server很像，和Oracle不一樣。Oracle的索引組織表并不那麼常用，且葉節點也和我們的clustered index有些許不同。
好了，以上就是基礎中的基礎。不論你是初學者還是高玩，相信都能從上述總結對比中，有所收獲。
2. 資料通路的基本操作：Scan, Seek, bookmark lookup
2.1 幾個基本概念
Predicate，謂詞。 一個SQL語句中，where條件之後的列，通常我們叫過濾條件，它的學名叫做謂詞。
output list, 傳回列。一個SQL語句中， select 之後 from之前的那些列，真正需要展示給客戶的列。
select id,name from table_a where id =3;
這個例子中， id就是謂詞， 同時output list是 id 和 name 兩個列。
2.2 Scan 和 Seek
一條簡單的語句
select * from test where id=2
想要找到id為2的所有記錄，這就像在字典中翻一個字，你有兩種翻法：
第一種，逐頁翻，從第一頁翻到最後一頁，這個就叫SCAN
第二種到目錄檢索（有個有序指引）裡快速查到，這個就叫SEEK。在樹形結構中，SEEK的IO接近于2.
當然，就像你翻字典一樣，如果你知道，你在翻得這個字是唯一的，當你翻到第一個的時候，你就不會繼續往後翻了。資料庫在操作unique key的時候，也是這樣，是以常說，哲學指導世界。
在商業資料庫裡，堆表（heap）和叢集索引（clustered index）構成了兩種資料組織結構，前者無序，是以隻能做scan（table scan）操作，後者有序，可以做scan(clustred index scan)和seek(clustered index seek)操作。如果你單獨建立了某（幾）個列的索引，它也可以做(non-clustered)index scan和(non-clustered)index seek
MySQL預設都會有clustered index，SQL Server也十分強調建立clustered index，Oracle則不同。是以我們SQL Server所有的調優都基于clustered index這個優秀的前提。
2.3 Bookmark Lookup
如果你隻接觸過mysql, 這可能是你第一次聽說這個詞，在Oracle和SQL Server中，它有一個簡單的中文名： 回表。 當然，這個名字并不準确。
考慮下如下這兩個簡單查詢，執行計劃會有什麼不同：
select lastname from test where lastname='Simth'
select id,lastname,firstname,other from test where lastname='Simth'
第一個查詢就是大家熟悉的覆寫索引，第二個查詢就是大家口中的回表。
第一個非常簡單，走了索引 idx_l，predicate（謂詞）是 lastname, output list（輸出列） 也是 lastname，當output list完全從索引中就能取出，俗稱覆寫索引查詢。
第二個就不一樣了， 先走了索引 idx_l, predicate 是 lastname， 因為這個索引隻有3個列，是以output list 隻有, 、lastname, firstname， id（clustered index的列會在所有索引裡）， 沒有other列，是以要根據 clustered index的id, 回到 clustered index，拿到對應的other。
如果沒有clustered index，就是根據row ID 回表，這就是Oracle時代廣為流傳的“回表”一詞的來源。
下圖非常好的再現了這個邏輯
這裡必須要補充一下，bookmark lookup可不是什麼廉價的操作.
上圖非常好的看見，non-clustered index seek是一個連續讀，而lookup的時候，回到clustered index中，變成了随機讀（random pickup），這是非常昂貴的。如果seek的結果是20，回表操作就是20次random IO。
是以，當回表操作非常大的時候，還不如直接走clustered index，眼尖的同學一定看見，我在上述例子中使用了index hint強迫他走了索引，實際上，優化器預設會聰明地調整到clustered index scan
2.4 Seek Predicate
并不是所有情況，所有謂詞都能輕而易舉的走到索引，尤其是在組合索引的時候。這也是網上經常能看到的零散知識點總結，大家着迷一般分享着神秘的索引判斷條件，而忽視了整個優化器架構。
這裡我就不太多贅述，
2.4.1 單列索引
下述條件可以走
a = 3
a > 100
a between 0 and 99
a like ‘abc%’
a in (2, 3, 5, 7)
下述條件不可以走
ABS(a) = 1
a + 1 = 9
a like ‘%abc’
2.4.2 組合索引
下列條件可以走，前者等值查詢，後者範圍查詢
a = 3 and b = ‘pi’
a = ‘xyzzy’ and b <= 0
2.4.3 一個例子
從網上找了一個例子，非常好的說明了索引和cover的列的多少。具體資料存儲，以後我們再開文章來說。
下述文法中，include是SQL Server特有，mysql可以忽略。
create table T_clu (a int, b int, c int, d int, e int, f int)
create unique clustered index T_clu_a on T_clu (a) -- mysql 中不允許單獨建立，等價于主鍵如果加上非空的話
create index T_clu_b on T_clu (b)
create index T_clu_ac on T_clu (a, c)
create index T_clu_d on T_clu (d) include (e) -- SQL Server特有
create unique index T_clu_f on T_clu (f)
| T_clu_a | a | a, b, c, d, e |
|---|---|---|
| T_clu_b | b, a | a, b |
| T_clu_ac | a, c | |
| T_clu_d | d, a | a, d, e |
| T_clu_f | f | a, f |
2.5 MySQL 索引下推
不得不說，MySQL在有些場景下是充滿創造力的，MySQL的索引下推，就是一個非常好的例子。這點，SQL Server還需要不斷進步。在學習SQL Server的道路上，還要對友商的先進之處，保持技術敏感。
考慮下這個語句的執行計劃
select * from test where lastname = 'Smith' and firstname > 'Goe' and other < 'abc';
現在，有了SCAN, SEEK和bookmark lookup的基礎，我們知道，這個語句，前兩個判斷條件可以走一次索引的seek, 之後會對結果集進行bookmark lookup, 回表後，再進行第三個判斷條件過濾。 比如SQL Server就是這樣執行的。
這裡提一句，如果是索引裡面seek走的謂詞，叫做seek predicate，如果是scan走的，就是predicate。
ICP的好處就是，在回表之前，先過濾第三個條件，減少回表量，確定每個回表資料就是要進output list的。因為我們說了，回表是非常expensive的操作
當執行計劃裡，Extra寫了Using Index Condition,就表示ICP（Index Condition Pushdown）.
3.表連接配接的三種基本操作： Nested Loop join, Merge Join, Hash Join
掌握了資料的通路方式，我們終于可以來探讨表（資料集）的連接配接（join）的基本形态了。
3.1 先說Join
Join本身是一個關鍵字，并不是一個operator。
Join基本分類就是inner join（預設）和outer join。inner join就是找交集的過程。而outer join則可以參考下面這個表格
| Join | 結果集 … |
|---|---|
| A left outer join B | all A rows |
| A right outer join B | all B rows |
| A full outer join B -- MySQL沒有 | all A and B rows |
除此之外，還有半連接配接（semi-join） 。這和我們之前說的unique key的半掃描很像，就是找到第一個就會退出目前循環，比如帶exists的連接配接。
select a.id from test a where exists ( select 1 from test2 b where a.id = b.id);
3.2 Nested Loop
考慮下這個查詢會怎麼走
select a.id,a.lastname,b.firstname from test a join test2 b on a.id=b.id;
id是主鍵， (lastname,firstname)組成組合索引。
我們來看下SQL Server的執行計劃
Nested Loop 的算法僞代碼如下
for each row R1 in the outer table
for each row R2 in the inner table
if R1 joins with R2
return (R1, R2)
可以看見這是一個典型的雙層循環，想想學C語言時肯定會舉得例子，記憶體循環（inner table） 外層循環（outer table）整個效率就取決于内層循環每次的執行速度。
是以這個模型往往需要一個小的驅動表，驅動表上有索引，每次快速掃描一次。外循環是大表，一共掃描一次，這是比較理想的情況。
當我們把test2表撐到10萬行，并且和test表大量重複，這個時候，Nested Loop就不太适用了。有一個誤區，大部分人會認為，大量資料的等值查詢會使用hash join，那麼事實上，并不完全是這樣的。
3.3 Merge Join
在MySQL中并沒有這種join 方式，是以，我們可以認為Merge Join是在一些特殊場景提高join性能的一種方法。 大部分場景Merge Join 并不快。
讓我們看下merge join的算法僞代碼。
get first row R1 from input 1
get first row R2 from input 2
while not at the end of either input
begin
if R1 joins with R2
begin
return (R1, R2)
get next row R2 from input 2
end
else if R1 < R2
get next row R1 from input 1
else
get next row R2 from input 2
end
什麼時候會走merge join呢？ 當兩個結果集做有序列map的時候，merge是按順序讀取并合并。而如果是兩個無序結果，則效率會比較差。
有序結果的merge join肯定比hash要廉價，因為hash join的時間複雜度是o(1)，結果集越大，join 成本越高。此例中我強制使用hash之後得到的執行計劃。
我們可以看下merge join 和 hash join 在大量有序結果集的性能差别。
3.4 Hash Join
Hash 算法是一個通用算法，在計算機領域大量使用。還記得我們前面說過，阻塞式查詢和互動式查詢嗎？ Nested Loop 和 Merge Join 是互動式，而Hash是阻塞式，必須等待Hash結果全部做完，才會傳回資料。MySQL目前也沒有這個join方法。
hash join的算法 僞代碼如下
for each row R1 in the build table
begin
calculate hash value on R1 join key(s)
insert R1 into the appropriate hash bucket
end
for each row R2 in the probe table
begin
calculate hash value on R2 join key(s)
for each row R1 in the corresponding hash bucket
if R1 joins with R2
return (R1, R2)
end
在Hash Join執行之前，資料庫引擎會根據表的Cardinality (mysql) / Cardinality Estimate(CE, SQLServer) 來估算大概需要多少記憶體。如果是多表hash join，引擎會選擇最小的兩個表進行Hash，進而減小記憶體的使用。
hash中有兩個基本概念，一個是probe，一個是buckets list。
如上述僞代碼所描述的，hash join分兩個階段，第一個階段叫做build，就是建立buckets list，這是一個維護在記憶體的hash table, 如果記憶體不夠大，會溢出到tempdb上。
第二個階段叫probe，就是用第二個表生成好的hash 結果來對應第一階段的buckets list。
但是hash都有一個問題，就是hash 沖突（collision），是以在實作的時候，引擎在buckets size上是需要計算的，細節的部分，我們将來在in-memory OLTP 中再細聊。
再多說一句左hash和右hash
算法上，左hash是指，表1表2生成出第一個hash結果HJ1，而表3是下一個probe，在生成完下一個HJ2之後，HJ1已經沒用了， 可以釋放掉。是以左hash是一個有阻塞的，但是記憶體開銷較小的算法，記憶體開銷是 max(hj1 + hj2, hj2 +hj3)
右hash是指，表1表2生成的HJ1是下一個probe，會參與到表3的probe，是以沒有阻塞，并且記憶體不能釋放，記憶體開銷是（hj1+hj2+hj3）,但速度更好
3.5 Join 小結
知道你們喜歡這種總結表格，一勞永逸。但是請不要忘記，懂得過程，比懂得結果更有意義。
因為篇幅原因，友善大家閱讀，是以先寫一個上篇，聊一些基礎的。
後續會逐漸聊一些更上層的東西。畢竟優化器是資料庫中最核心也是最難實作的部分。需要足夠的毅力和能力，去了解它。