SERVER-25023 Allow multiple indexes on the same fields with different partial index filters

4 files changed, 111 insertions, 3 deletions

diff --git a/src/mongo/db/matcher/expression.cpp b/src/mongo/db/matcher/expression.cpp
index c035e417848..680b75a8001 100644
--- a/src/mongo/db/matcher/expression.cpp
+++ b/src/mongo/db/matcher/expression.cpp
@@ -40,12 +40,77 @@ namespace mongo {
  */
 MONGO_FAIL_POINT_DEFINE(disableMatchExpressionOptimization);
 
+namespace {
+/**
+ * Comparator for MatchExpression nodes.  Returns an integer less than, equal to, or greater
+ * than zero if 'lhs' is less than, equal to, or greater than 'rhs', respectively.
+ *
+ * Sorts by:
+ * 1) operator type (MatchExpression::MatchType)
+ * 2) path name (MatchExpression::path())
+ * 3) sort order of children
+ * 4) number of children (MatchExpression::numChildren())
+ *
+ * The third item is needed to ensure that match expression trees which should have the same
+ * cache key always sort the same way. If you're wondering when the tuple (operator type, path
+ * name) could ever be equal, consider this query:
+ *
+ * {$and:[{$or:[{a:1},{a:2}]},{$or:[{a:1},{b:2}]}]}
+ *
+ * The two OR nodes would compare as equal in this case were it not for tuple item #3 (sort
+ * order of children).
+ */
+int matchExpressionComparator(const MatchExpression* lhs, const MatchExpression* rhs) {
+    MatchExpression::MatchType lhsMatchType = lhs->matchType();
+    MatchExpression::MatchType rhsMatchType = rhs->matchType();
+    if (lhsMatchType != rhsMatchType) {
+        return lhsMatchType < rhsMatchType ? -1 : 1;
+    }
+
+    StringData lhsPath = lhs->path();
+    StringData rhsPath = rhs->path();
+    int pathsCompare = lhsPath.compare(rhsPath);
+    if (pathsCompare != 0) {
+        return pathsCompare;
+    }
+
+    const size_t numChildren = std::min(lhs->numChildren(), rhs->numChildren());
+    for (size_t childIdx = 0; childIdx < numChildren; ++childIdx) {
+        int childCompare =
+            matchExpressionComparator(lhs->getChild(childIdx), rhs->getChild(childIdx));
+        if (childCompare != 0) {
+            return childCompare;
+        }
+    }
+
+    if (lhs->numChildren() != rhs->numChildren()) {
+        return lhs->numChildren() < rhs->numChildren() ? -1 : 1;
+    }
+
+    // They're equal!
+    return 0;
+}
+
+bool matchExpressionLessThan(const MatchExpression* lhs, const MatchExpression* rhs) {
+    return matchExpressionComparator(lhs, rhs) < 0;
+}
+
+}  // namespace
+
 MatchExpression::MatchExpression(MatchType type) : _matchType(type) {}
 
+// static
+void MatchExpression::sortTree(MatchExpression* tree) {
+    for (size_t i = 0; i < tree->numChildren(); ++i) {
+        sortTree(tree->getChild(i));
+    }
+    if (auto&& children = tree->getChildVector()) {
+        std::stable_sort(children->begin(), children->end(), matchExpressionLessThan);
+    }
+}
+
 std::string MatchExpression::toString() const {
-    BSONObjBuilder bob;
-    serialize(&bob, true);
-    return bob.obj().toString();
+    return serialize().toString();
 }
 
 std::string MatchExpression::debugString() const {
diff --git a/src/mongo/db/matcher/expression.h b/src/mongo/db/matcher/expression.h
index f870dbcbcda..052ab19c7ea 100644
--- a/src/mongo/db/matcher/expression.h
+++ b/src/mongo/db/matcher/expression.h
@@ -158,6 +158,21 @@ public:
         }
     }
 
+    /**
+     * Traverses expression tree post-order. Sorts children at each non-leaf node by (MatchType,
+     * path(), children, number of children).
+     */
+    static void sortTree(MatchExpression* tree);
+
+    /**
+     * Convenience method which normalizes a MatchExpression tree by optimizing and then sorting it.
+     */
+    static std::unique_ptr<MatchExpression> normalize(std::unique_ptr<MatchExpression> tree) {
+        tree = optimize(std::move(tree));
+        sortTree(tree.get());
+        return tree;
+    }
+
     MatchExpression(MatchType type);
     virtual ~MatchExpression() {}
 
@@ -299,6 +314,15 @@ public:
     virtual void serialize(BSONObjBuilder* out, bool includePath = true) const = 0;
 
     /**
+     * Convenience method which serializes this MatchExpression to a BSONObj.
+     */
+    BSONObj serialize(bool includePath = true) const {
+        BSONObjBuilder bob;
+        serialize(&bob, includePath);
+        return bob.obj();
+    }
+
+    /**
      * Returns true if this expression will always evaluate to false, such as an $or with no
      * children.
      */
diff --git a/src/mongo/db/matcher/expression_parser.cpp b/src/mongo/db/matcher/expression_parser.cpp
index a06e07b82d7..91caf31241c 100644
--- a/src/mongo/db/matcher/expression_parser.cpp
+++ b/src/mongo/db/matcher/expression_parser.cpp
@@ -1741,6 +1741,15 @@ StatusWithMatchExpression MatchExpressionParser::parse(
     }
 }
 
+std::unique_ptr<MatchExpression> MatchExpressionParser::parseAndNormalize(
+    const BSONObj& obj,
+    const boost::intrusive_ptr<ExpressionContext>& expCtx,
+    const ExtensionsCallback& extensionsCallback,
+    AllowedFeatureSet allowedFeatures) {
+    auto parsedTree = uassertStatusOK(parse(obj, expCtx, extensionsCallback, allowedFeatures));
+    return MatchExpression::normalize(std::move(parsedTree));
+}
+
 namespace {
 // Maps from query operator string name to function.
 std::unique_ptr<StringMap<
diff --git a/src/mongo/db/matcher/expression_parser.h b/src/mongo/db/matcher/expression_parser.h
index b4048949055..c0b7691d108 100644
--- a/src/mongo/db/matcher/expression_parser.h
+++ b/src/mongo/db/matcher/expression_parser.h
@@ -124,5 +124,15 @@ public:
         const boost::intrusive_ptr<ExpressionContext>& expCtx,
         const ExtensionsCallback& extensionsCallback = ExtensionsCallbackNoop(),
         AllowedFeatureSet allowedFeatures = kDefaultSpecialFeatures);
+
+    /**
+     * Parse the given MatchExpression and normalize the resulting tree by optimizing and then
+     * sorting it. Throws if the given BSONObj fails to parse.
+     */
+    static std::unique_ptr<MatchExpression> parseAndNormalize(
+        const BSONObj& obj,
+        const boost::intrusive_ptr<ExpressionContext>& expCtx,
+        const ExtensionsCallback& extensionsCallback = ExtensionsCallbackNoop(),
+        AllowedFeatureSet allowedFeatures = kDefaultSpecialFeatures);
 };
 }  // namespace mongo