优化器内幕

╰+哭是因爲堅強的太久メ 2022-12-22 01:00 131阅读 0赞

我记得我还在上一家公司的时候，有一次和主管一起做1：1，主管问我，将来你的技术方向是什么，我说我想往HA方向发展，因为是我的强项。主管问我还有别的吗？我犹豫地说，我也想做优化器方向，但是智商不够。主管大笑，说如果有兴趣可以钻研看看。

现在想想，优化器确实比HA好玩多了。HA只是数据库的一个理念，实现这个理念的一些手段方式而已。而优化器则是算法实现，是关系型数据库的整体实现方式。借此来了解图灵奖得主James Gray的遗作，就算学不会，也可以吹吹这位传奇人物的神秘去世故事

## 上篇 ##

1.  什么是执行计划？ 怎么生成执行计划？
2.  数据访问的基本操作：Scan, Seek, bookmark lookup
3.  表连接的三种基本操作： Nested Loop join, Merge Join, Hash Join

后续计划中的坑

1.  子查询的种种
2.  并发线程和我们的hybrid 并发
3.  隔离级别 Isolation的实现
4.  其他杂七杂八的待定

先挖好坑，逐步来填。

## 1. 什么是执行计划？ 怎么生成执行计划？ ##

**1.1 执行计划的基本单位 Operator**

在说执行计划之前，我们要知道执行计划的基本单位。 SQL Server中，一个执行计划的基本单位是iterator(迭代器)或者叫 operator，iterator主要做一件事，就是从input，可能是一个表，可能是一个计算结果集，读入数据，然后进行一定操作之后，返回结果集给他的父节点。  
在SQL Server的图形执行计划中，每一个小图标，就是一个operator

![4d5e5363f287cd6a104f2a2d15f5e3a3.png][]

**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。

![97ec65f7c0276443826bf0d016d4e1dd.png][]

那么为什么需要Estimated EP呢 ，有些大语句跑一次要一个小时甚至更多，没法获得Actual EP，这个时候我们就需要 Estimated EP。

生成Estimated EP的方法非常简单，SQL Server中，点击这个按钮“Display Estimated Execution Plan”，或者使用showplan语句。

![8f4f513c5d34c4e60272f8eb967ffcf3.png][]

**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

![1d61a51af99babe64b016279836412d6.png][]

第二种到目录检索（有个有序指引）里快速查到，这个就叫SEEK。在树形结构中，SEEK的IO接近于2.

![dbac97da48c939f1ded28f892804228d.png][]

当然，就像你翻字典一样，如果你知道，你在翻得这个字是唯一的，当你翻到第一个的时候，你就不会继续往后翻了。数据库在操作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'

第一个查询就是大家熟悉的覆盖索引，第二个查询就是大家口中的回表。

![d08b7608ea8a6a53e20d0a4b556e3dfb.png][]

第一个非常简单，走了索引 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时代广为流传的“回表”一词的来源。

下图非常好的再现了这个逻辑

![869fa6c109a0f3226bf24a4495012ce0.png][]

这里必须要补充一下，bookmark lookup可不是什么廉价的操作.

上图非常好的看见，non-clustered index seek是一个连续读，而lookup的时候，回到clustered index中，变成了随机读（random pickup），这是非常昂贵的。如果seek的结果是20，回表操作就是20次random IO。

所以，当回表操作非常大的时候，还不如直接走clustered index，眼尖的同学一定看见，我在上述例子中使用了index hint强迫他走了索引，实际上，优化器默认会聪明地调整到clustered index scan

![43db88799348043ff81d5701638e1b97.png][]

**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)

![01092855387a96777de29288770552ec.png][]

**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就是这样执行的。

![318f4aa1a9213df17c3b38ba704198f1.png][]

这里提一句，如果是索引里面seek走的谓词，叫做seek predicate，如果是scan走的，就是predicate。  
  
ICP的好处就是，在回表之前，先过滤第三个条件，减少回表量，确保每个回表数据就是要进output list的。因为我们说了，回表是非常expensive的操作。

当执行计划里，Extra写了Using Index Condition,就表示ICP（Index Condition Pushdown）.

![6566d1329d93464c2015de5771f5871a.png][]

## 3.表连接的三种基本操作： Nested Loop join, Merge Join, Hash Join ##

掌握了数据的访问方式，我们终于可以来探讨表（数据集）的连接（join）的基本形态了。  
  
**3.1 先说Join**

Join本身是一个关键字，并不是一个operator。

Join基本分类就是inner join（默认）和outer join。inner join就是找交集的过程。而outer join则可以参考下面这个表格

![b8dae79c83d2b9b876321bba41364949.png][]

除此之外，还有半连接（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的执行计划

![e524a5d411e1dcdf419d7ae93cbaaa6a.png][]

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 并不快。

![911cca1e1737b1ec3a1bc905360c06f3.png][]

让我们看下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之后得到的执行计划。

![f064af02193775807618561b85315232.png][]

我们可以看下merge join 和 hash join 在大量有序结果集的性能差别。

![894c53fec48a8bf736296df1476fbdf6.png][]

**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

![6f752e244d32919d04c68b5ecc438488.png][]

算法上，左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 小结**

知道你们喜欢这种总结表格，一劳永逸。但是请不要忘记，懂得过程，比懂得结果更有意义。

![a481a1a164a77b26097b147e1d07e5c9.png][]

[4d5e5363f287cd6a104f2a2d15f5e3a3.png]: /images/20221120/8f37cd19ad0e408ca9c5b694e4367a0d.png
[97ec65f7c0276443826bf0d016d4e1dd.png]: /images/20221120/baf87aef5ab04c47bffd55ec55c26d6d.png
[8f4f513c5d34c4e60272f8eb967ffcf3.png]: /images/20221120/e70a6d5e245e4251a8862a051d6f6bdd.png
[1d61a51af99babe64b016279836412d6.png]: /images/20221120/4c9cd1ad1ef14f5781db28836108ecad.png
[dbac97da48c939f1ded28f892804228d.png]: /images/20221120/60947ef314f8485baedc356b6f35238c.png
[d08b7608ea8a6a53e20d0a4b556e3dfb.png]: /images/20221120/ed9ddf447cb94d55822977f0fee3e4eb.png
[869fa6c109a0f3226bf24a4495012ce0.png]: /images/20221120/e5dc70a2314642fa9d08b627e34bb73b.png
[43db88799348043ff81d5701638e1b97.png]: /images/20221120/976026eb032848a79495df726aac9f17.png
[01092855387a96777de29288770552ec.png]: /images/20221120/96f7354b55ad4238b4a9232bb33a2ce4.png
[318f4aa1a9213df17c3b38ba704198f1.png]: /images/20221120/d973664f64e248579cca56a6dc688f7c.png
[6566d1329d93464c2015de5771f5871a.png]: /images/20221120/631a7b139cf848dbbaa6a9e38567697a.png
[b8dae79c83d2b9b876321bba41364949.png]: /images/20221120/97c54824537b43678bdd01a655a64f5a.png
[e524a5d411e1dcdf419d7ae93cbaaa6a.png]: /images/20221120/9318ade52e8a43aaa7193aa70b8f6e2e.png
[911cca1e1737b1ec3a1bc905360c06f3.png]: /images/20221120/3d439cd1590540ea81f876b5735c6d1b.png
[f064af02193775807618561b85315232.png]: /images/20221120/999c960edbc749368018abba537d4556.png
[894c53fec48a8bf736296df1476fbdf6.png]: /images/20221120/6e5f06e161da421abb2b48cbe80d4436.png
[6f752e244d32919d04c68b5ecc438488.png]: /images/20221120/428bf92e217c41d88d96a9210182518f.png
[a481a1a164a77b26097b147e1d07e5c9.png]: /images/20221120/ae85e6b180f643ad93b88a20fc7829c5.png