最近,由于工作需求去了解一下Query是如何在MongoDB内部进行处理,从而丢给存储引擎的。里面涉及了Query执行计划和优化器的相关代码,MongoDB整体思路设计的干净利落,有些地方深入挖一下其实还是能有些优化点的。本文会涉及一条Query被parse之后一路走到引擎之前,都做了那些事情,分析基于MongoDB v3.4.6代码。由于篇幅过长,文章分为上下两篇,分别介绍执行计划 & 优化器和Query具体的执行器。 名词定义: 下图主要描述了Query在执行层的逻辑,其他模块的逻辑进行了精简: 在此流程中: 本文后续以MongoDB find命令为基础,介绍执行计划。update和delete也需要执行计划,生成原理类似。 下面是一个标准的find查询协议包,红框内是涉及查询的基本算子如:过滤条件filter算子、sort排序算子、投影算子等等,其他是查询的一些属性,MongoDB查询区别于SQL,没有那么复杂的语法和语义解析,各个算子被结构化的存储到协议标准里面,所以普通的查询也直接可以取出。 。 上述Query中各个算子使用bson结构表示的逻辑表达式,这里会被先标准化成CanonicalQuery。主要涉及和的生成。collator是用户可以自定义的除了ByteComparator(逐字节比较排序)之外的比较方法,比如内置的比较。collator需要和filter里的逻辑表达式相关联(比如$gt大于运算)。 ,构成一个表达式tree结构,顶层root是一个AndMatchExpression,如果含有AND、OR、NOR,tree的深度就+1. 这个表达式tree会用做以后过滤记录。 normalizeTree 简化AND、OR、NOT表达式: Find/Update/Delete通过.explain()函数可以打印Query生成的执行计划, explain("executionStats")会打印更多的统计信息。 上图中比较关键的信息: winningPlan : 最后生成的唯一的plan或者经过Optimizer选择最优的 在生成执行计划之前,这里有一些。针对Oplog扫描场景(oplogReplay)和_id主键查询做了特例化,如果是oplogReplay则直接生成按ts字段的CollectionScan。如果是主键等值查询,则生成IDHack,直接查询主键。生成执行的过程, 这里选取索引有个规则: 1). 如果查询带_id主键索引,这直接选主键索引 2). 优先走,即查询条件带该索引,并且projection算子下只选择该field的数据(不用二次fetch数据) 3). 如果既有唯一索引和普通索引,则优先使用该唯一索引(此处猜测应该是唯一索引命中概率更高,因为同一条记录只出现一次) 4). 如果都是唯一索引,则first win(此处测试应该是按index name做了排序) 5). 如果都是普通索引或者索引之间有覆盖,则会根据多个索引生成多个执行路径,并生成多个执行计划。 所以生成执行计划其实就是 匹配各个索引,然后按照这个索引的访问方式,生成访问数据的各个步骤,最终得到数据 。如果最终生成了多个Plan,则让Optimizer去选。 优化器是一个很大的话题,各个传统数据库和NewSQL在这个地方都下了不少功夫,甚至说优化器的好坏直接决定了查询性能。本文不在这里介绍过多的优化器知识,涵盖太广。(同类型的还有RBO和HBO)。但和传统的MySQL的CBO有些不太一样,MySQL会采集一些引擎层索引的stats信息,如条数、cardinality(稀疏度)等,然后根据stats估算执行计划代驾。MongoDB Optimizer在评估时会touch数据,获得一个运行时信息再去结合估算,进行Plan的打分,得分最高的就是最优的。 Optimizer分为logical逻辑优化和physical物理优化,逻辑优化在上面CanonicalQuery时已经做了,这里只涉及物理优化。Optimizer会把所有的Plan都执行一小部分数据,在执行终会统计扫描次数、获得结果次数等stats指标,然后根据该指标进行score计算,核心的几个步骤如下: 所以最后score为: 选出的Plan会进入PlanCache下次同样QueryShape的语句,会命中cache。这里cache即使命中了,也不是完全无代价,是要去碰数据再去evaluate一次,如果猜测准确,则继续使用cached plan。 网上有篇文章分享了由于不正确的PlanCache导致慢查的case有兴趣可以看下 http://mongoing.com/archives/5624 1). Optimizer采用touch数据的方式,默认配置下,最少扫描100次结果,最大扫描max(10000, colletion_total_records * 0.3)次索引,。虽然后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的开销。 喜欢撸代码的朋友可以根据下图只接索引代码,有针对性的去看细节: 橙色的是Optimizer相关的,绿色是执行计划相关的,蓝色时执行器相关的(后面文章会介绍)
(图片来自于网络)
创客课程开发的每个主题课程需要基于现实情景,设置学习探究任务,通过问题研究、任务...
创客空间建设 能够给人们分享各种乐趣,通过电脑,技术,科学,艺术结合,设计创造一...
在了解创客教育之前,我们首先了解下何为创客。创客是一群喜欢或享受创新的人。创客跨...
STEAM教育是对传统教育的提升,它是基于自然学校方式的功能性框架,可以适合各类...