MongoDB 查询优化器中的 MatchExpression 启发式改写：从 normalize 到布尔简化的源码级解析

MongoDB 查询优化器中的 MatchExpression 启发式改写从 normalize 到布尔简化的源码级解析【免费下载链接】mongoThe MongoDB Database项目地址: https://gitcode.com/GitHub_Trending/mo/mongo本文基于 MongoDB 源码仓库中的 src/mongo/db/matcher/README.md系统讲解 find 查询过滤器与聚合$match阶段中MatchExpression树的启发式改写heuristic rewrites机制。读完本文你将理解MatchExpression::normalize()/optimize()的整体流水线、表达式特化优化如$or转$in、$expr索引化改写与布尔简化bitset 树、DNF、Quine-McCluskey、吸收律、Petrick 最小覆盖各自的职责与触发条件并能结合 src/mongo/db/query/compiler/rewrites/matcher/expression_optimizer.cpp 等当前源码位置定位实现、用 failpoint 做语义正确性验证。一、什么是启发式改写查询规范化阶段的逻辑模型变换一条查询首先被解析为逻辑模型logical model以结构化形式表达查询语义。随后该逻辑模型会经历规范化normalization、变换transformation与优化optimization使其更便于高效执行。这些改写基于预定义规则即启发式heuristics。之所以称之为heuristic rewrites是因为系统并不确定改写后的结果一定优于原始形式它只是做出一个最佳猜测best guess。逻辑模型优化完成后查询规划器会生成多个候选物理计划表示并由 classic runtime planner 选出最高效的执行计划。需要明确本文及其源 README的边界覆盖范围find 查询的MatchExpression部分以及聚合管道中$match阶段的MatchExpression不覆盖范围后续阶段stage builders即查询编译过程。聚合管道层面的改写请参阅 src/mongo/db/pipeline/README.md。从源码结构看MatchExpression的优化发生在查询**规范化canonicalization**阶段这是本文所有改写规则的统一前置阶段。二、优化入口与整体流水线源 README 描述的入口是MatchExpression::optimize()由MatchExpression::normalize()在MatchExpression树根上调用。optimize()对树结构做不改变语义的简化变换返回值有三种可能原始的、未被修改的MatchExpression被原地修改mutated的原始MatchExpression一个全新的MatchExpression。在当前仓库中这一逻辑位于 src/mongo/db/query/compiler/rewrites/matcher/expression_optimizer.cpp。optimizeMatchExpression()L772-L809按matchType()从matchExpressionOptimizersMap查表取出对应的ExpressionOptimizerFunc执行改写normalizeMatchExpression()L824-L832在优化后还调用sortMatchExpressionTree()对子节点做稳定排序保证树的可复现顺序。整个流程与源 README 中的流程图一致MatchExpression优化包含两个过程后文分别展开表达式特化优化Expression-specific Optimizations每个具体MatchExpression子类如LeafMatchExpression、ArrayMatchExpression自带针对自身的优化逻辑布尔简化Boolean Simplification简化含$and、$or、$nor、$not等布尔运算符的MatchExpression的逻辑结构。附注如何关闭优化用于测试验证新改写规则语义正确性时你可能想关闭优化将优化前后的查询结果做对比。此时可以切换disableMatchExpressionOptimizationfailpointdb.adminCommand({configureFailPoint: disableMatchExpressionOptimization, mode: alwaysOn})该 failpoint 在 expression_optimizer.cpp L778 被检查启用后直接返回未修改的表达式。值得注意的是从源码结构看该 failpoint 还有一个联动效果src/mongo/db/query/plan_enumerator/plan_enumerator.h 显示当它被设置时 OR-pushdown 同样会被禁用src/mongo/db/query/plan_enumerator/plan_enumerator.cpp L831 也有对应的防御性断言——因为 OR-pushdown 依赖优化后的表达式形态。测试侧的使用可参考 src/mongo/db/query/query_tester/testfile.cpp L289 与 src/mongo/db/query/query_planner_tree_test.cpp L455。三、表达式特化优化Expression-specific Optimizations代表不同类型的MatchExpression子类通过重写优化器README 中称为MatchExpression::getOptimizer()定义特化优化行为它接收一个输入的MatchExpression并将同一个MatchExpression传递给得到的ExpressionOptimizerFunc。如果子类持有子MatchExpression它就负责返回一个会对这些子节点递归调用MatchExpression::optimize()的ExpressionOptimizerFunc。在当前仓库中这一注册—查表机制落在 src/mongo/db/query/compiler/rewrites/matcher/expression_optimizer.cpp L752-L768通过REGISTER_MATCH_EXPRESSION_OPTIMIZER宏为各MatchType注册优化函数例如EXPRESSION类型注册exprOptimizer、MATCH_IN注册inOptimizer、INTERNAL_SCHEMA_XOR复用listOfOptimizer。优化逻辑表示一般采用自底向上的方式先处理子树必要时消去冗余子节点可避免在父层做无用功。但这一约定并非强制——实现可以先优化自身例如裁剪子表达式再去优化子节点。例 1ListOfMatchExpression$and/$or考察 src/mongo/db/matcher/expression_tree.h 中的ListOfMatchExpression类型$and、$or等如何被改写。考虑如下查询{ // Root $and: [ // Child 0 { $or: [ { age: { $eq: 50 } }, { age: { $eq: 30 } } ] }, // Child 1 { $and: [ { $alwaysTrue: 1 }, { $and: [ {status: { $eq: active }}, {name: { $eq: John }} ] } ] } ] }顶层AndMatchExpression有两个子节点Child 0 是OrMatchExpressionChild 1 是AndMatchExpression。Child 0 的改写Child 0 是一个对同一路径使用 EQ 条件的 OR可被改写为InMatchExpression改写后的 AND 只剩一个操作数因此把表达式简化为该操作数本身。// Child 0 after rewrites { age: { $in: [ 50, 30 ] } }Child 1 的改写它是一棵包含平凡真trivially true谓词与嵌套AndMatchExpression的AndMatchExpression。AND 满足结合律AND 会吸收其子节点中任何 AND 的子节点因此嵌套谓词被提升到顶层所有平凡为真的子节点从 AND 中删除。// Child 1 after rewrites { $and: [ { status: { $eq: active } }, { name: { $eq: John } } ] }最后根节点处 Child 1 中的 AND 可被最外层 AND 吸收最终改写后的查询变得精简可以进入后续查询规划阶段{ $and: [ { age: { $in: [ 50, 30 ] } } { status: { $eq: active } }, { name: { $eq: John } } ] }例 2InMatchExpression针对 src/mongo/db/matcher/expression_leaf.h 中的InMatchExpression执行如下优化仅含一个正则的 IN 变成RegexMatchExpression仅含一个相等值的 IN 变成EqualityMatchExpression空 IN 变成$alwaysFalse。// 1 { field: { $in: [/^abc/] } } -- { field: { $regex: ^abc } } // 2 { field: { $in: [xyz] } } -- { field: xyz } // 3 { field: { $in: [] } } -- { $alwaysFalse: 1 }例 3ExprMatchExpression把$expr变得可走索引还存在一类改写让原本无法利用索引的表达式变得可索引化。$expr表达式本身不可走索引但它可能包含能够借助索引产生预期结果的超集的子表达式从而尽量减少需要过滤的文档数量。系统尝试把它们改写为内部MatchExpression的合取conjunction使查询规划器有可能生成索引扫描。我们将改写如下$expr{ $expr: { $and: [ { $eq: [$x, 1] }, { $eq: [$y, $z] } ] } }改写为{ $and: [ { x: { $_internalExprEq: 1 } } { $expr: { $and: [ { $eq: [$x, 1] }, { $eq: [$y, $z] } ] } } ] }注意{ $eq: [$x, 1] }可以表示为MatchExpression而{ $eq: [$y, $z] }比较的是两个字段路径引用需要从每份输入文档中取值。MatchExpression不允许引用多于一个本地文档字段路径因此这部分无法被抽取出来。与普通比较运算符不同$_internalExpr系列运算符采用非类型括号non-type bracketed语义以匹配$expr内部非类型括号的比较运算符。由于改写后的MatchExpression与 src/mongo/db/matcher/expression_expr.h 中的ExprMatchExpression之间存在语义差异它会匹配相同文档集合或超集。附注Type Bracketing类型括号语义Type bracketing确保比较只在同类型值之间进行避免意外结果。对于查询{field: {$gt: 5}}类型括号语义保证只考虑数值类型参与比较。例如{field: 10}与{field: 100.01}会匹配。这是MatchExpression的默认行为。反之没有类型括号时所有类型都参与比较。按照 BSON 排序顺序字符串高于数值所以文档{field: string}也会匹配上述查询。这是$expr的默认比较模式。例如MatchExpression中的$_internalExprEq会钻入数组而ExprMatchExpression中的$eq不会。因此原始$expr仍被保留作为第二层过滤确保返回结果符合预期的$expr语义。InternalExprMatchExpression语义的完整描述见 src/mongo/db/matcher/expression_internal_expr_comparison.h。附注Array Traversal Semantics数组遍历语义数组遍历语义定义了沿MatchExpression树遍历时如何处理数组。不同类型的MatchExpression可以为叶数组如路径a.b中b是数组和非叶数组如a是数组分别提供遍历要求。一般来说遍历数组意味着数组元素与整个数组对象都被考虑。在文档{f: [1, 2]}中沿路径f遍历时路径迭代器会依次返回 1、2 和 [1, 2]。如果行为是不遍历数组则只返回整个数组对象[1, 2]。还存在一种只返回数组元素、省略数组本身的模式。数组遍历模式的完整定义见 src/mongo/db/matcher/path.h 中的LeafArrayBehavior与NonLeafArrayBehavior。对MatchExpression默认模式是遍历数组对$expr默认模式是不遍历数组。例如{$expr: {$eq: [$f, [1, 2]]}}只会匹配f值恰为整个数组[1, 2]的文档。四、布尔简化Boolean Simplification在调用各子类的优化器之后得到的MatchExpression可能仍是可进一步简化的复杂布尔表达式。只要它落在ExpressionSimplifierSettings设定的限制之内就会进入布尔表达式简化器Boolean expression simplifier目标是降低计算开销并促成更好的计划生成。ExpressionSimplifierSettings 的完整定义源 README 列举了三个关键开关而 src/mongo/db/query/compiler/rewrites/matcher/expression_simplifier.h L39-L100 给出了完整结构设置项作用maximumNumberOfUniquePredicates表达式中唯一谓词数超过该值时认为表达式过大、放弃简化maximumNumberOfMinterms布尔变换过程中允许的最大最小项minterm数量maxNumPrimeImplicantsPetrick 方法是指数复杂度质蕴函子prime implicants数超过上限时跳过 Petrick 方法maxSizeFactor若简化后的表达式大小超过原表达式大小 ×maxSizeFactor则拒绝简化结果doNotOpenContainedOrs原表达式含 AND 时仍会简化但简化后合取项中的公共谓词不会被提出括号applyQuineMcCluskey为 false 时只做 DNF 转换不应用 Quine–McCluskey 算法这些限制存在的意义是有些查询复杂到不值得简化即使尝试简化若结果比原查询更复杂也会丢弃简化结果。从源码结构看生产环境下的取值由服务端参数装配expression_optimizer.cpp L787-L798 显示布尔简化受internalQueryEnableBooleanExpressionsSimplifier门控且maximumNumberOfUniquePredicates、maximumNumberOfMinterms、maxNumPrimeImplicants、maxSizeFactor、doNotOpenContainedOrs分别来自对应的internalQuery*服务端参数。简化器还带有isTriviallySimple()短路平凡简单的表达式不会进入简化器只累加trivialCount指标。布尔简化的入口是 src/mongo/db/query/compiler/rewrites/matcher/expression_simplifier.cpp 中的simplifyMatchExpression()声明见 expression_simplifier.h L106-L107。整体分六步第 1 步把MatchExpression转换为 bitset 树。附注Bitsetbitset是集合的紧凑表示序列中的每一位代表一个元素是否存在1 表示存在0 表示不存在。例如0001表示包含第 1 个元素的集合1010表示包含第 2 和第 4 个元素的集合。相比操作复杂的 AST 结构bitset 运算通常更快、更直接。查询过滤器被转换为 bitset 树谓词以 bitset 形式存放在叶子节点内部节点表示树结构内部节点可以是其子节点的合取AND或析取ORMQL 逻辑运算符表示为BitsetTreeNode{ type: 合取或析取, isNegated: 子节点是否被取反 }。各逻辑运算符的具体表示见 src/mongo/db/query/compiler/rewrites/boolean_simplification/bitset_tree.h。第 2 步把 bitset 树简化为 DNF。附注DNFDisjunctive Normal Form析取范式DNF 是逻辑表达式的一种标准范式合取项的析取即AND 的 OR。例如形如A ∧ (B ∨ C)的查询可以分配律展开为 DNF(A ∧ B) ∨ (A ∧ C)。DNF 表达式也可以理解为 minterms 的 maxterm其中maxterm指 DNF 表达式顶层的析取minterm指表达式的合取项。bitset 树进入 DNF 后可进一步缩减为最小项集合sum of products。第 3 步对 DNF 项应用 Quine-McCluskey 化简(x ∧ y) ∨ (x ∧ ~y) x。第 4 步应用吸收律Absorptions Lawx ∨ (x ∧ y) x。第 5 步使用 Petrick 方法进一步化简用于寻找最小覆盖minimal coverage即让谓词求值为真的最小 minterm 集合。例如输入 minterm 列表[[0, 1, 2], [2, 3], [0, 3]]可推出两个最小覆盖[0, 1]和[0, 2]。结果是所需 minterm 的下标向量——可以用原列表中任意一对 minterm 覆盖谓词 0、1、2、3。第 6 步还原出原始MatchExpression最后从 bitset 树与表示 bitset 中各位的表达式列表出发还原restoreMatchExpression树实现见 expression_simplifier.cpp。简化器在运行过程中会向serverStatus上报指标expression_simplifier.h L14-L34 定义了四个计数器query.expressionSimplifier.trivial因过滤器平凡而跳过、abortedTooLarge结果过大中止、notSimplified完成但无简化、simplified成功简化可用于观测简化器在线上查询中的实际收益。完整示例从四分支$or到两分支$or调用各类优化器之后的输入查询{ $or: [ { $and: [ { field0: A }, { field1: B } ] }, { $and: [ { field0: A }, { field1: B }, { field3: D } ] }, { $and: [ { field0: A }, { field2: C } ] }, { $and: [ { field1: B }, { field2: C } ] } ] }第 1 步转换为 bitset 树。设 bit 映射为field0 ABit 0field1 BBit 1field2 CBit 2field3 DBit 4注原文此处编号为 Bit 4而下方 bitset 图中实际按 Bit 3 使用BitsetTreeNode{ type: OR, children: [ BitsetTreeNode{ type: AND, bitset: 0011 // Bit 0 (field0 A) AND Bit 1 (field1 B) }, BitsetTreeNode{ type: AND, bitset: 1011 // Bit 0 (field0 A) AND Bit 1 (field1 B) AND Bit 3 (field3 D) }, BitsetTreeNode{ type: AND, bitset: 0101 // Bit 0 (field0 A) AND Bit 2 (field2 C) }, BitsetTreeNode{ type: AND, bitset: 0110 // Bit 1 (field1 B) AND Bit 2 (field2 C) } ] }第 2 步化简为 DNF。该树已经处于 DNF 形式此步无需再做功(0 AND 1) OR (0 AND 2 AND 3) OR (0 AND 2) OR (1 AND 2)第 3 步应用吸收律。(0 AND 2)吸收(0 AND 2 AND 3)因为后者是前者的子集。化简后的查询变为(0 AND 1) OR (0 AND 2) OR (1 AND 2)第 4 步寻找 minterm 最小覆盖。映射到 bit 0、1、2 的谓词用[0, 1]或[1, 2]中的任一即可仍求值为真。选前者得到(0 AND 1) OR (0 AND 2)最后还原MatchExpression。布尔简化结束时还原出MatchExpression大致映射为如下 MQL 查询保留原文档示例内容{ $or: [ { $and: [ { field1: A }, { field2: B } ] }, { $and: [ { field1: A }, { field3: C } ] } ] }五、在仓库中继续阅读与验证的路径围绕本文主题以下仓库路径可用于交叉验证与深入阅读主题路径优化器入口、按类型注册、failpoint 短路src/mongo/db/query/compiler/rewrites/matcher/expression_optimizer.cpp布尔简化设置、simplifyMatchExpression()与指标src/mongo/db/query/compiler/rewrites/matcher/expression_simplifier.h / .cppbitset 树、位运算代数、Petrick、Quine-McCluskeysrc/mongo/db/query/compiler/rewrites/boolean_simplification/bitset_tree.h、bitset_algebra.h、petrick.h、quine_mccluskey.h逻辑表达式树ListOfMatchExpression等src/mongo/db/matcher/expression_tree.h叶子表达式InMatchExpression等src/mongo/db/matcher/expression_leaf.h$expr与内部表达式比较src/mongo/db/matcher/expression_expr.h / expression_internal_expr_comparison.h数组遍历模式src/mongo/db/matcher/path.hfailpoint 在规划器与测试中的使用src/mongo/db/query/plan_enumerator/plan_enumerator.h、src/mongo/db/query/query_planner_tree_test.cpp需要注意的一个版本差异源 README 中引用的部分文件如matcher/expression.h、matcher/expression_simplifier.h、query/boolean_simplification/对应当前仓库已迁移到src/mongo/db/query/compiler/rewrites/matcher/与src/mongo/db/query/compiler/rewrites/boolean_simplification/下的同名文件函数名也从类成员optimize()演进为自由函数optimizeMatchExpression()机制与语义保持一致。六、小结MatchExpression的启发式改写是 MongoDB 查询规范化阶段的核心环节先由按matchType分派的特化优化器完成自底向上的表达式级变换$or合并为$in、单元素$in退化为等值、$expr抽取可索引子句等再在ExpressionSimplifierSettings的规模限制下把复杂布尔结构转成 bitset 树经 DNF 归一、Quine-McCluskey、吸收律与 Petrick 最小覆盖逐步缩减最后还原为更精简的MatchExpression。整个流程可用disableMatchExpressionOptimizationfailpoint 一键关闭为优化前后结果对比式的语义正确性验证提供了标准手段。理解这条流水线是后续阅读计划枚举plan enumeration与运行时规划器runtime planner源码的前置基础。【免费下载链接】mongoThe MongoDB Database项目地址: https://gitcode.com/GitHub_Trending/mo/mongo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考