作者：马弓手三菜
我记得我还在上一家公司的时候，有一次和主管一起做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 小结
知道你们喜欢这种总结表格，一劳永逸。但是请不要忘记，懂得过程，比懂得结果更有意义。
因为篇幅原因，方便大家阅读，所以先写一个上篇，聊一些基础的。
后续会逐步聊一些更上层的东西。毕竟优化器是数据库中最核心也是最难实现的部分。需要足够的毅力和能力，去理解它。