MongoDB 执行计划 & 优化器简介 (上)，mongodb执行计划
最近，由于工作需求去了解一下Query是如何在MongoDB内部进行处理，从而丢给存储引擎的。里面涉及了Query执行计划和优化器的相关代码，MongoDB整体思路设计的干净利落，有些地方深入挖一下其实还是能有些优化点的。本文会涉及一条Query被parse之后一路走到引擎之前，都做了那些事情，分析基于MongoDB v3.4.6代码。由于篇幅过长，文章分为上下两篇，分别介绍执行计划 & 优化器和Query具体的执行器。
1. 一条Query语句都做了什么
名词定义：
-
QuerySolution执行计划， 本文也称Plan -
QueryPlaner生成执行计划模块 -
PlanExecutor运行执行计划模块，同时充当优化器(Optimizer)的角色
下图主要描述了Query在执行层的逻辑，其他模块的逻辑进行了精简：
- 1). Client按照MongoDB的网络协议，请求建立连接，并友单独新建的thread处理所有请求。
- 2). 有些Query(如insert)，本身不需要执行计划和优化，这直接通过接口和引擎交互(通过RecordStore写表)
- 3). Query会进行简单的处理(标准化)，并构造一些上下文数据结构变成CanonicalQuery(标准化Query)。
- 4). Plan模块会负责生成该Query的多个执行计划，然后丢给Optimizer去选择最优的，丢给PlanExecutor。
- 5). PlanExecutor按照执行计划一步一步迭代，获得最终的数据(或执行update修改数据)。
在此流程中：
Plan如果只关联到单个或零个索引，这只生成一个执行计划，如果发现有多个索引或者索引有重叠，这可能生成多个执行计划。Optimizer只在多个执行计划时，才会介入。
2. QuerySolution 执行计划
本文后续以MongoDB find命令为基础，介绍执行计划。update和delete也需要执行计划，生成原理类似。
下面是一个标准的find查询协议包，红框内是涉及查询的基本算子如：过滤条件filter算子、sort排序算子、投影算子等等，其他是查询的一些属性，MongoDB查询区别于SQL，没有那么复杂的语法和语义解析，各个算子被结构化的存储到协议标准里面，所以普通的查询也直接可以取出。
- filter : 查询过滤条件，类比SQL的where表达式
- projection : 投影，选择取出的fields，类比SQL的select
- hint : 手工指定索引，可以强制指定使用某个索引
后续Plan会在这些算子上做逻辑处理、优化再连接各个算子，并生成一颗可以执行的树状数据结构。
2.1 CanonicalQuery
上述Query中各个算子使用bson结构表示的逻辑表达式，这里会被先标准化成CanonicalQuery。主要涉及collator和MatchExpression的生成。collator是用户可以自定义的除了ByteComparator(逐字节比较排序)之外的比较方法，比如内置的中文比较。collator需要和filter里的逻辑表达式相关联(比如$gt大于运算)。
MatchExpression是将filter算子里每个逻辑运算转换成各个类型的表达式(GT,ET,LT,AND,OR...)，构成一个表达式tree结构，顶层root是一个AndMatchExpression，如果含有AND、OR、NOR，tree的深度就+1. 这个表达式tree会用做以后过滤记录。
着这个过程里会做一些简单的等价代换的优化:
-
normalizeTree 简化AND、OR、NOT表达式:
- 如$AND:[{$AND:{}}]简化成$AND:[{}]
- 如$AND:[{$AND:[], $AND:[]}]简化成$AND:[{},{},{}...]
- 如$NOT:{$NOT:{}}，简化成{}
(图片来自于网络)
- sortTree : 将AND、OR表达式简化排序，并且擦除相同逻辑表达式
- 这里有个点待确认，MatchExpression后会做常量替换，比如a>2+(3*4)转换成a>14，具体代码没有定位 ？？
2.2 生成执行计划 Plan
Find/Update/Delete通过.explain()函数可以打印Query生成的执行计划, explain("executionStats")会打印更多的统计信息。
上图中比较关键的信息：
- parsedQuery : 对应filter过滤条件
-
winningPlan : 最后生成的唯一的plan或者经过Optimizer选择最优的
- stage : 执行计划中每一个操作，后续会介绍。
- keyPattern : 用到的索引和基本属性等
- indexBounds : 要扫描索引的边界，这里是等值。
- rejectedPlans : 被Optimizer放弃的执行计划，结构和上述类似。
在生成执行计划之前，这里有一些短路的优化。针对Oplog扫描场景(oplogReplay)和_id主键查询做了特例化，如果是oplogReplay则直接生成按ts字段的CollectionScan。如果是主键等值查询，则生成IDHack，直接查询主键。生成执行的过程，本质上是通过Query的查询条件去匹配对应collection上的索引，然后根据相关性生成不同索引组合的不同执行路径，每一个索引规则都可能对应一个执行计划，或者是全表扫描CollectionScan 这里选取索引有个规则：
1). 如果查询带_id主键索引，这直接选主键索引
2). 优先走覆盖索引，即查询条件带该索引，并且projection算子下只选择该field的数据(不用二次fetch数据)
3). 如果既有唯一索引和普通索引，则优先使用该唯一索引(此处猜测应该是唯一索引命中概率更高，因为同一条记录只出现一次)
4). 如果都是唯一索引，则first win(此处测试应该是按index name做了排序)
5). 如果都是普通索引或者索引之间有覆盖，则会根据多个索引生成多个执行路径，并生成多个执行计划。
所以生成执行计划其实就是 匹配各个索引，然后按照这个索引的访问方式，生成访问数据的各个步骤，最终得到数据 。如果最终生成了多个Plan，则让Optimizer去选。
3 Plan Optimizer
优化器是一个很大的话题，各个传统数据库和NewSQL在这个地方都下了不少功夫，甚至说优化器的好坏直接决定了查询性能。本文不在这里介绍过多的优化器知识，涵盖太广。MongoDB使用了一种类似CBO(cost based optimizer)的优化策略(同类型的还有RBO和HBO)。但和传统的MySQL的CBO有些不太一样，MySQL会采集一些引擎层索引的stats信息，如条数、cardinality(稀疏度)等，然后根据stats估算执行计划代驾。MongoDB Optimizer在评估时会touch数据，获得一个运行时信息再去结合估算，进行Plan的打分，得分最高的就是最优的。
Optimizer分为logical逻辑优化和physical物理优化，逻辑优化在上面CanonicalQuery时已经做了，这里只涉及物理优化。Optimizer会把所有的Plan都执行一小部分数据，在执行终会统计扫描次数、获得结果次数等stats指标，然后根据该指标进行score计算，核心的几个步骤如下：
- 如果执行过程中遇到了IS_EOF(Exector的一个表示，表示该步骤结束了，没有数据量)，则score变成一个很大的值。
- 如果执行的算子里面不包含PROJECTION、AND_HASH、FETCH、SORT等高阶操作，则增加少量
Bounes加分。 - 计算productivity，该值由
fetched/workUnits得来是一个小于1的百分比，即获得有效的记录数/总共扫描的记录数。意义就是扫了一部分数据之后，有效数据的占比。占比越大，证明索引被读取的价值就越高。
所以最后score为：
score = 1 + productivity + noFetchBonus + noSortBonus + noIxisectBonus + isEOFBonus
选出的Plan会进入PlanCache下次同样QueryShape的语句，会命中cache。这里cache即使命中了，也不是完全无代价，是要去碰数据再去evaluate一次，如果猜测准确，则继续使用cached plan。
网上有篇文章分享了由于不正确的PlanCache导致慢查的case有兴趣可以看下 http://mongoing.com/archives/5624
4. 优化器的一点想法
1). Optimizer采用touch数据的方式，默认配置下，最少扫描100次结果，最大扫描max(10000, colletion_total_records * 0.3)次索引，在某些命中率很低的场景下，对IO和数据量的影响还是很大。虽然后PlanCache能减少同一QueryShape的开销，但是PlanCache逻辑中本身同样也要touch小部分数据，开销还是有的。而且如果PlanCache的结果有可能已经不在适合当前查询，比如数据的分布已经有了不小的变化，这时候是需要等到触发replan的条件或者DDL的invalidate cache。
当然这么做也有自己的道理，实现相对简单，存储引擎和server之间不用互访Index的分布数据，也省去了维护cardinality准确性的代价。
2). 现在优化器score机制本质上还是Produtivity影响最大，该指标反应的Index扫描和Index读取效率方面。其实还有很多方面可以考虑，比如Index 的内存占用开销，扫描时btree遍历比较的cpu开销(int类型一定比string类型小，不过Mongo的Index是无类型的)，也应该计算在读取开销内。或者是类似MySQL 8 的新机制，如果page在buffer pool已经存在，则优先选，这样可以选择尽量都在内存里已经存在的Index，减少IO的开销。
One More Thing~
喜欢撸代码的朋友可以根据下图只接索引代码，有针对性的去看细节：
橙色的是Optimizer相关的，绿色是执行计划相关的，蓝色时执行器相关的(后面文章会介绍)
